Where Newton's method goes instead

Newton’s method is the standard way to solve an equation numerically. Guess, follow the tangent to where it crosses zero, use that as the next guess:

$$z \mapsto z - \frac{f(z)}{f'(z)}.$$

It is fast, it is old, and it is the algorithm behind most root-finding in practice. Apply it to $z^3 = 1$, which has three roots, and ask the only question the formula does not answer: from a given start, which root does it find?

The three roots are $1$ and the two complex ones at $120°$ either side. If the answer were “the nearest root”, the picture would be the Voronoi diagram of the three roots — three sectors meeting at the origin, with straight boundaries. It is not.

What the picture shows that the formula does not #

The formula is a statement about one step. The picture is a statement about the limit, and there is no expression for it.

Near a root the method is excellent: the error squares each step, so three correct digits become six, then twelve. That is the local behaviour and it is what the textbook proves. The picture is about everything else — the starting points that are not near any root, where the tangent throws the guess somewhere unrelated and the process begins again from there.

That makes Newton’s method a dynamical system: one map, iterated, with the roots as attracting fixed points. Each root has a basin of attraction, the set of starting points that end up at it, and the question the picture answers is what the basins look like.

Three large lobes are visible, one around each root, and that much is expected. What is not expected is everything between them: chains of shrinking discs running along every boundary, each of them a whole basin, and between those, more of the same. The lobes account for most of the area and almost none of the structure.

All three, everywhere along the boundary #

Look at any point where two of the three basins meet. The third one is there too — not nearby, but arbitrarily close, at every scale.

This is the Wada property, and it is stranger than an ordinary fractal boundary. Two countries can share a border without a third being involved; here every boundary point is on the border of all three basins at once. There is no segment of boundary between exactly two of them.

The reason is a consequence of the map rather than a coincidence of this equation. The boundary is the Julia set of the Newton map, and the Julia set is where the iteration is unstable — every point of it has neighbours doing every possible thing. Since there are three possible things, every boundary point has all three arbitrarily close.

So the previous essay’s object has appeared without being invited. Nobody set out to iterate a rational function for its dynamics; the map came from an algorithm designed for something else entirely, and the geometry arrived with it. That is the strongest argument for studying the family for its own sake — it turns up in problems that were not about it, and the way it turned up in the parameter plane of a quadratic is the same way it turns up in a root-finder.

The one-dimensional version has none of this #

Newton’s method on the real line, which is where it is taught, shows almost none of what the picture above shows — and the difference is worth stating, because it explains why this was not noticed for two hundred years.

On the real line a cubic with three real roots does have interleaved basins, and a plot of them is a set of intervals in a complicated arrangement. But an interval has only two ends. A boundary point on the line separates exactly two sides, so nothing like the Wada property can happen; the three-way interleaving needs a second dimension to happen in.

More importantly, the real picture is a sampling of a much larger object. The real line is one line through the plane above, and reading the dynamics off it is like judging a landscape from a single transect. Everything interesting in the figure — the spirals, the chains of shrinking copies, the three-way boundary — is invisible from the line, and no amount of care with real arithmetic would find it.

Cayley noticed this in 1879. He solved the problem completely for a quadratic, where the two basins are the two half-planes on either side of the perpendicular bisector of the roots and the boundary is a straight line, then wrote that the cubic case “appears to present considerable difficulty” and did not return to it. He was right, and the difficulty is the figure at the top of this essay, which nobody saw for another century.

What this costs in practice #

The picture is a statement about an algorithm people actually run, and it has three practical readings.

The answer is unpredictable near the boundary. For a starting point within rounding error of the boundary, the root the method returns is not determined by anything a program can measure. Two runs with different floating-point rounding can return different roots. This is not a bug in the implementation.

Basin membership is not a local property. No amount of examining a starting point and its immediate neighbourhood determines which root it goes to, because the neighbourhood contains points of all three basins.

But it almost never matters. The boundary has measure zero. A starting point chosen at random lands in a basin’s interior with probability one, and converges quadratically as advertised. The pathology is real, ubiquitous, and of measure zero — which is the standard shape of a numerical hazard, and the reason Newton’s method remains the default despite the picture.

Where it fails completely #

Convergence to some root is not guaranteed at all, and the failure has a picture too.

Newton’s method has its own cycles. For some polynomials there are starting regions — with interior, not measure zero — from which the iteration falls into a periodic orbit and never approaches any root. The cubic $z^3 - 2z + 2$ is the standard example: the method run from near $0$ gives $1$, then $0$, then $1$ forever.

That is a genuinely open region of starting points from which the algorithm provably never terminates, and it exists for a polynomial with small integer coefficients. Any implementation that loops until convergence, with no iteration cap, will hang on it.

There is a second failure with no picture at all, and it is the one that bites in practice. Newton’s method needs $f'$, and a step where the derivative is near zero throws the guess arbitrarily far — a horizontal tangent crosses zero nowhere near the root. Polynomials with roots close together have exactly this problem between them, which is why the method that converges fastest of any in common use is also the one most often wrapped in guards.

The one saving grace is that these regions can be found: the same critical-orbit criterion as the last essay applies, since an attracting cycle must attract a critical point of the Newton map. Checking the finitely many critical points settles whether a given polynomial has such a trap.

Why the roots are attracting at all #

It is worth seeing why the roots are fixed points and why they attract, since both follow from the same derivative and neither is assumed.

At a root $r$, $f(r) = 0$, so the correction term vanishes and $r$ maps to itself: the roots are exactly the fixed points, provided $f'(r) \neq 0$.

For the multiplier, differentiate the Newton map:

$$N'(z) = \frac{f(z)f''(z)}{f'(z)^2}.$$

At a simple root the numerator has $f(r) = 0$ in it, so $N'(r) = 0$. That is the same multiplier test an attracting fixed point was decided by on the interval, and it gives the strongest possible answer here. The multiplier is not merely under one — it is zero, which is why convergence is quadratic rather than merely geometric, and why each root is superattracting in the sense the last two essays used.

That also explains a failure the picture does not show. At a repeated root, $f'(r) = 0$ too, the cancellation is incomplete, and the multiplier comes out at $1 - 1/m$ for a root of multiplicity $m$. That is under one, so the method still converges — but linearly, losing the quadratic behaviour entirely, and slowing further the higher the multiplicity.

The same picture in another guise #

Colour a chaotic map’s plane by which of several attractors each point reaches and this structure appears whenever there is more than one attractor. It is not special to Newton’s method or to polynomials.

A forced pendulum with two resting positions has interleaved basins of the same kind. So does a magnetic pendulum over three magnets — a physical system, buildable on a desk, in which releasing the bob from nearly the same place twice gives different magnets, for exactly the reason drawn above.

The magnetic pendulum is worth dwelling on because it removes the last defence against taking this seriously. There is no computer in it, no floating point, no iteration cap and no rounding — just a bob, three magnets and friction. Released twice from positions a hair apart, it lands on different magnets, and the reason is the geometry drawn above rather than any imprecision in the release. The measurement problem that made the weather unforecastable is doing the same work here on an object that fits on a desk.

What that means is that unpredictability does not require a chaotic attractor. The end state here is completely tame: the system settles onto one of three fixed points and stays. All the complication is in the transient, in the question of which one, and the transient is enough. Sensitive dependence is usually introduced with orbits that never settle; this is the version where everything settles and the answer is still not knowable in advance.

What a good starting guess is worth #

The practical response to all of this is not to abandon the method but to stop starting it anywhere in particular, and the figure says exactly how much that is worth.

The basins have interior, and near each root there is a disc inside which convergence is guaranteed and quadratic. Standard analysis gives such a disc explicitly in terms of $f$, $f'$ and $f''$ at the starting point — the Newton–Kantorovich condition — and it is checkable at the guess itself, before running anything. A guess that satisfies it lands in the interior of a basin, and the picture above is irrelevant to what happens next.

So the algorithm splits in two. A global phase whose job is to get inside such a disc, and where the geometry of the basins is the whole difficulty; and a local phase where Newton’s method is unbeatable and the geometry does not matter. Every serious implementation is built this way: bisection or a line search first, Newton once the guess is provably good enough, with a fallback if a step leaves the region.

Reading it that way turns the figure from a curiosity into a specification. It is a picture of what the global phase is for, drawn at the scale where the global phase is hardest, and the reason the hybrid design is not an excess of caution. The same division shows up wherever an iterative method is fast near its answer and unreliable far from it — the fast part is a statement about a slope at a single point, and a slope at a point knows nothing about anywhere else.

What the drawing had to decide #

There is a choice buried in the figure that the caption does not make and every picture of this kind has to make: when does the iteration stop, and what happens to points that have not converged?

The generator runs forty steps and then asks which root the point is nearest, with a tolerance. Points that are not within tolerance of any root count as undecided and get no colour. That is a defensible rule and it is not the only one, and the picture depends on which is chosen.

That figure is the honest statement of what the boundary is. It is not a curve the program finds; it is where the program runs out of time, and the true boundary is the limit of those regions as the cap goes to infinity. Since convergence is quadratic once a point is close, the thickness shrinks fast — but the set of points that never decide at all is exactly the Julia set, and no cap resolves it.

The same caveat applied to the Mandelbrot drawings, and it applies to every escape-time picture on this site. What is drawn is always “the answer after $N$ steps”, and saying so is the difference between a figure and an illustration.

What the figure is evidence of #

The generator makes three assertions, and they are chosen because each would fail under a different mistake.

The roots cube to one, checked in complex arithmetic — a test of the arithmetic itself, which would catch a sign error in the multiplication. A point beside each root converges to that root — a test of the iteration, which would catch a wrong derivative, the most likely error in a hand-written Newton step. And the sampled field separates into three regions rather than one or two, which would catch a convergence test so loose that everything counts as the same root.

None of them proves the Wada property; that is a theorem, and no finite sampling could establish it. What the assertions establish is that the picture is a picture of Newton’s method on $z^3 - 1$ and not of something else — which is the most a computed figure can be asked for, and more than most are asked for.