The idea: run Newton's method from every start
Newton's method finds a root of f by following the tangent line down to zero, again and again:
z₁ = z₀ − f(z₀) / f′(z₀), z₂ = z₁ − f(z₁) / f′(z₁), …The same formula works for complex numbers z. Take f(z) = z³ − 1. It has three roots: 1 and −½ ± (√3/2)i. Start Newton at any point z₀ of the plane and it almost always ends on one of them. Give each root a colour and paint z₀ with the colour of the root it reaches. That picture is the Newton fractal.
Basins of attraction
The set of starts that go to one root is that root's basin of attraction. Near a root, Newton is very fast: the number of correct digits about doubles each step, so the basin is a calm patch of one colour around each root. The page also makes a pixel darker the more steps it needs (at most 120), so slow starts near the edges show up dark (Demo: z³ − 1, a start near a root: z₀ = 1 + 0.5i reaches 1 in 5 steps).
- Start at z₀ = the pixel.
- Repeat z → z − f(z)/f′(z) until z is within 0.001 of a root, at most 120 times.
- Colour = that root; shade = number of steps. No root, or f′(z) = 0 on the way: near-black.
Cayley's question: two roots are easy, three are not
In 1879 Arthur Cayley asked which root Newton finds from each start. For f(z) = z² − 1 he found a clean answer: starts with Re z > 0 go to 1, starts with Re z < 0 go to −1, and the boundary is the straight line Re z = 0 (Demo: z² − 1, no fractal: zoom ×64 and it is still a line). For z³ − 1 he could not find the answer, and now we can see why: the boundary is a fractal.
Every boundary point touches every basin
Look along the edge between red and blue: there is always a yellow bead in between, and between red and that yellow, a smaller blue one, and so on. The rule is that a point on the edge of one basin is on the edge of all of them. So a start near the edge can go anywhere: z₀ = −0.6 + 0.1i lies closest to the yellow root, jumps off the picture at step 4 because f′ is small there, and ends on root 1, the farthest root (Demo: a start near the boundary lands on the farthest root).
Zooming shows the same thing again. The page zooms ×2 six times about t = −2−1/3 ≈ −0.7937, the point that one Newton step sends to 0. At 0, f′(0) = 0 and the next step would be infinite, so all points that end up there form the skeleton of the boundary (Demo: zoom ×64 into the boundary of z³ − 1). The same beads come back at every zoom.
| f(z) | roots | basins |
|---|---|---|
| z² − 1 | ±1 | two half-planes, a straight line between them |
| z³ − 1 | 1, −½ ± (√3/2)i | three, with a fractal boundary |
| z⁴ − 1 | ±1, ±i | four, beads along the diagonals |
| z⁵ − 1 | the fifth roots of 1 | five, a five-armed star of beads |
| z³ − 2z + 2 | −1.7693, 0.8846 ± 0.5897i | three, plus black regions that find no root |
When Newton fails
Two things can stop Newton from finding a root:
- A flat tangent. Where f′(z) = 0 there is no next guess. For z³ − 1 that is z = 0 (choose orbit of: z₀ = 0).
- An attracting cycle. For f(z) = z³ − 2z + 2, N(0) = 0 − 2/(−2) = 1 and N(1) = 1 − 1/1 = 0. The orbit goes 0 → 1 → 0 → 1 … forever, and starts near 0 or 1 are pulled into the same cycle. They form black regions: about 1 % of the window, and in the zoom a black blob with its own fractal edge (Demo: z³ − 2z + 2).
The boundary is a Julia set
Newton's step N(z) = z − f(z)/f′(z) is itself a map of the plane, applied again and again, just like z → z² + c on the Julia set page. The roots are attracting fixed points of N, the basins are where orbits settle, and the boundary between them is the Julia set of N. The black regions of z³ − 2z + 2 even contain small copies of the Mandelbrot set.
What the page leaves out
Polynomials with complex coefficients or repeated roots (where Newton slows to linear speed), the damped and relaxed versions of Newton (z → z − a·f/f′), Newton in two or more real variables, the proofs (Fatou, Julia), and deep zooms past ×64. See root finding for Newton compared with bisection and the secant method on the real line, and complex numbers for multiplying and dividing them.