Newton fractal

Newton’s method looks for a root of a polynomial $p$ by repeating one step from a starting point $z_0$:

Every pixel of the picture is a starting point in the complex plane. It takes the colour of the root whose disc it enters first. Each disc is proven: by Smale’s γ theorem, Newton’s method from any start inside it converges to that root, so a colour is never a guess made from “which root is nearest”. Around a simple root $\zeta$ the disc has radius $(3-\sqrt7)/(2\gamma)$, where $\gamma = \max_{k\ge2}\bigl|p^{(k)}(\zeta)/(k!\,p'(\zeta))\bigr|^{1/(k-1)}$.

Shading represents how many steps a start needs to reach a disc; the light and dark treatment varies with the chosen look. The thin lines mark the edges of “the starts that reach a disc within k steps” — the levels the red key shows one by one. Black means only that a start has entered no disc within the steps tried. The smooth shading, the glow along the boundary and the gold wire of the gilt look are display only; which root a pixel goes to, and in how many steps, are numerical results of 32-bit computation.

The whole basin of a root is every start that eventually reaches it, including the small pieces far from the root. All these basins have one and the same boundary: the Julia set of the map $N$. So arbitrarily close to any boundary point there are starts going to every root. That is why the colours alternate at every scale, and why “only one root’s basin” shows it in every bead along the boundary.

Near this boundary, a few steps of Newton’s method can pull neighbouring starts far apart. In the highlight “A hair apart”, two starts 0.02 apart on $z^3-1$ are 0.047 apart after one step and 0.268 after two; they enter the discs of different roots at steps 6 and 7.

With only two roots the picture is simple: the boundary is the perpendicular bisector of the two roots. In the coordinate $w = (z-1)/(z+1)$ (roots at ±1), Newton’s step becomes $w \mapsto w^2$. With a third root the boundary becomes a fractal.

For $p(z) = z^3 - 2z + 2$ the start 0 goes to 1 and back to 0 for ever: a cycle whose multiplier $N'(0)\,N'(1)$ is 0, so every start close enough to it falls into it too. Those starts form the black islands; they never reach a root.

Where can such cycles appear? $N' = p\,p''/p'^2$ vanishes at every root, so each root is a critical point of $N$ and sits in its own basin. The other critical points — the free critical points — are the zeros of $p''$ that are not roots; where $p'$ vanishes too, $N$ has a multiple pole there, still a critical point, sent to ∞. By a theorem of Fatou every attracting cycle attracts at least one critical point. A cycle that is not a root cannot attract a root, which stays in its own basin, so it must attract a free critical point. Following the free critical points can therefore reveal these failures. The list uses numerical approximations; if zeros cannot be separated reliably, it reports them as unresolved rather than declaring a multiple point or a pole. The converse does not hold: for $z^3-1$ the free critical point 0 is also a zero of $p'$; it is sent to ∞, a repelling fixed point of $N$, and there are no black islands.

With three roots, $p''$ has one zero, the centroid of the roots; unless it is a root itself (as for $z^3-z$), it is the one free critical point. The inset is a map of positions for the selected root, the other two fixed: each point takes the colour of the root whose proven disc the centroid’s orbit enters when the selected root is put there, and black if it enters none within 300 steps. In this family of cubic polynomials the black blocks show small copies of Mandelbrot-set structure, first seen in computer experiments by Curry, Garnett and Sullivan (1983). Drag the selected root through one and the black islands in the picture appear and disappear. Moving root 1 of $z^3-2z+2$ left along the real axis through its block (the highlight “Through the black block”), the cycle’s period doubles, 2 → 4 → 8, at about −1.8045 and −1.832 (numerically) — as along the real axis of the Mandelbrot set.

Arthur Cayley asked in 1879 which root Newton’s method finds from a given complex start; he settled two roots and found three hard. Pierre Fatou and Gaston Julia built the theory of iterating rational maps around 1918–1920, long before computer pictures. Pictures of Newton’s basins, and the Mandelbrot-like structure in their parameter space, appeared in the early 1980s; Steve Smale’s estimates (1986) give the proven discs used here.