An area that never finishes

The three basins are a striking picture of a failure that hardly matters. The boundary between them is fractal, every point of it has all three basins arbitrarily close, and the root the method returns from a starting point near it is not determined by anything a program can measure.

And the boundary has measure zero. A starting point chosen at random lands in the interior of a basin with probability one, converges quadratically, and none of the structure is ever met. The pathology is real, ubiquitous, and of no practical consequence — which is the standard shape of a numerical hazard and is why the method remains the default.

There is a second failure that is not like that at all.

That uncoloured region has area. It is not a boundary, it does not shrink as the iteration cap rises, and a starting point chosen at random inside the square falls into it with probability around one in a hundred.

The cycle, exactly #

The polynomial is $z^3 - 2z + 2$, whose coefficients are $1, 0, -2, 2$ — as small as a cubic’s get. The Newton map is

$$N(z) \;=\; z - \frac{z^3 - 2z + 2}{3z^2 - 2}.$$

At $z = 0$: the numerator is $2$ and the denominator is $-2$, so $N(0) = 0 - (-1) = 1$. At $z = 1$: the numerator is $1 - 2 + 2 = 1$ and the denominator is $3 - 2 = 1$, so $N(1) = 1 - 1 = 0$.

So $0 \mapsto 1 \mapsto 0$, exactly, in whole numbers. No approximation and no search — two evaluations settle it.

That a cycle exists is not by itself enough; a repelling cycle would be met by no starting point but the cycle itself. The multiplier decides, and for Newton’s method it has a short form:

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

At $z = 0$, $f''(0) = 0$ — the second derivative of a cubic with no quadratic term vanishes at the origin — so $N'(0) = 0$. The cycle’s multiplier is the product round it, which is therefore zero: the cycle is superattracting, in exactly the sense an attracting fixed point of a map on an interval is, and convergence into it is as fast as convergence to a root.

Why it is an area and not a curve #

The distinction the essay turns on is worth stating carefully, because measure zero is easy to say and easy to mishandle.

A superattracting cycle has a neighbourhood that is carried into itself and contracted. Every point of that neighbourhood converges to the cycle, so the set of starting points that fail contains an open disc, which has positive area. The figure checks exactly that: it samples a small disc round one of the two cycle points at a hundred and forty-four positions and requires every one of them to reach no root.

The fractal boundary of the three basins contains no disc at all — every point of it has points of all three basins arbitrarily close, so it has empty interior. Those are the two possible shapes of a bad set and they differ completely in what they mean for an algorithm.

A measure-zero failure is a hazard nobody meets. An open failure is a hazard with a probability attached, and here that probability is about one per cent of a reasonably chosen square.

One per cent sounds small and is not, in the setting where it matters. A root-finder called a million times from starting points a caller chose without thinking about this — from data, from a previous iteration, from a grid — meets the trap ten thousand times, and each meeting is a hang or a spurious failure rather than a small error. A probability of one in a hundred is a certainty at scale, which is the difference between this failure and one that lives on a set of measure zero.

How to know in advance #

A program cannot sample the plane before solving a cubic, so the practical question is whether a given polynomial has such a trap — and there is a complete answer, from a theorem about iteration in general.

Every attracting cycle of a rational map attracts a critical point. That is Fatou’s, and it is the reason the Mandelbrot set is drawn by following one orbit: a map of degree $d$ has at most $2d - 2$ critical points, so it has at most that many attracting cycles, and following each critical point’s orbit finds all of them.

For a Newton map the critical points are easy to name. $N' = f f'' / (f')^2$ vanishes where $f = 0$ — the roots, which are the superattracting fixed points the method is designed for — and where $f'' = 0$. So the free critical points are the roots of the second derivative, and there are only $d - 2$ of them.

For a cubic that is one point. $f'' = 6z$ for $z^3 - 2z + 2$, so the one free critical point is $z = 0$ — and $0$ is in the cycle.

So deciding whether a cubic’s Newton method has a trap is: compute $f''$, find its root, iterate a few hundred times, see whether it settles on a root or on something else. That is a finite test, it is cheap, and it is complete. The figure runs it.

What a cap actually measures #

The last figure raises a question the three-basin picture settles for its own case and this one has to settle again: what is the uncoloured region a picture of?

Three different things can leave a point uncoloured. It may be heading for a root and not yet within tolerance — a cap problem, cured by more steps. It may be on the boundary between basins, where it will never decide at any cap because it is heading nowhere. Or it may be in the basin of a cycle, where it decides immediately and decides against every root.

The three are distinguishable and the figures do not distinguish them, which is why the disc check exists. Sampling a disc round the cycle and finding every point of it uncoloured at a large cap separates the third case from the other two, because a cap problem shrinks with the cap and a boundary contains no disc.

That is the whole methodological content of the page. A picture of an escape-time computation shows the answer after $N$ steps, always, and the claim being made about it has to be established by something other than looking — which for a boundary means a theorem and for an area means a sample.

Where this was found, and how recently #

The cubic $z^3 - 2z + 2$ is the standard example and it appears in Smale’s 1981 paper on the efficiency of the Newton algorithm, where he raised the general question of how often the method fails. Barna had shown in the 1950s that for real polynomials with all roots real, the set of failing real starting points is measure zero — so the trap needs either complex starts or a polynomial with complex roots, and $z^3 - 2z + 2$ has one real root and two complex ones. Its real root is about $-1.7693$, and starting anywhere real between roughly $-0.25$ and $0.25$ falls into the cycle — which means the failure is reachable from an ordinary real starting guess, with no complex arithmetic anywhere.

The example is nearly as old as the question and the general picture is not settled. What is known: the failing set for a given polynomial is either measure zero or contains an open set, decided by the critical orbits; a polynomial chosen at random from a reasonable distribution has a trap with probability zero for degree three; and for higher degrees the parameter regions where traps occur are the analogue of the Mandelbrot set’s hyperbolic components, and are as complicated.

Which cubics have one, as a picture in the coefficients #

Since the test is follow the one free critical point, the natural next question is which cubics fail it — and the answer has the shape the whole subject has.

Every cubic can be shifted so that its quadratic term vanishes, giving $z^3 + pz + q$; the free critical point is then $0$ and the test is whether the orbit of $0$ under the Newton map settles on a root. Scaling reduces the two parameters to one, so the family of cubics is effectively one-dimensional up to the moves that do not change the dynamics, and the set of bad parameters is a subset of a plane.

That subset is not simple. It is a union of regions, each one a parameter range where the critical orbit falls into a cycle of some fixed period, and its structure is that of the Mandelbrot set’s components — including small copies of the whole arrangement at every scale. $z^3 - 2z + 2$ sits in the period-two region, which is the largest of them and the one anybody finds first.

So does this cubic trap? is a decidable question with a computable answer and an undrawable boundary. Deciding one polynomial is cheap; describing which polynomials in closed form is the same kind of problem as describing the Mandelbrot set, which is to say nobody expects one.

That is worth holding beside the practical statement of the last section. The test is easy and the classification is hopeless, and an implementation only ever needs the test.

What it costs an implementation #

The practical reading is short and is not the one the picture suggests.

Any loop that iterates until convergence, with no cap, hangs on this polynomial. Not slowly — for ever, from an open set of starts. That is a real defect and every serious implementation guards against it with an iteration cap, which converts a hang into a wrong answer reported as a failure.

The guard is the same one that handles the derivative vanishing, which is the other way a Newton step goes wrong: $f'$ near zero throws the next guess arbitrarily far, and a horizontal tangent crosses zero nowhere near the root. That second hazard is a difference too small to measure amplified by division, and it is the more common of the two in practice because roots close together produce it without any exotic dynamics at all.

And neither guard is a repair. A capped loop that gives up has not solved the problem; it has noticed it — and noticing is worth something, since the alternative is a program that appears to be working. A root-finder that returns no root found from this start has told the caller something true, and a root-finder that hangs has not. What solves it is not starting anywhere in particular, which is covering rather than avoiding.

What the method was proved to do, and under what hypothesis #

It is worth setting the failure against the guarantee, because both are true and the guarantee is the one usually quoted.

Newton–Kantorovich. There is a condition, checkable at the starting guess from $f$, $f'$ and $f''$ there, under which the method converges quadratically to a root and the root is inside an explicitly given ball. A guess satisfying it lands inside a basin’s interior and everything on this page is irrelevant to what happens next.

So the algorithm splits in two. A local phase where the guarantee applies and Newton’s method is unbeatable, and a global phase whose only job is to get inside the region where the guarantee applies. Every serious implementation is built that way: bisection or a line search until the condition holds, then Newton.

This essay is entirely about the global phase, and so is the three-basin picture. The trapped region and the fractal boundary are both statements about starting points that do not satisfy the condition — which is to say about the part of the problem the guarantee explicitly does not cover.

That division is worth carrying beyond root-finding. A convergence theorem with a hypothesis at the starting point is a theorem about a region, and the algorithm’s real difficulty is usually finding the region rather than what happens inside it. The same is true of gradient methods, of iterative solvers, and of every scheme whose proof begins sufficiently close to.

The same phenomenon elsewhere in iteration #

An attracting cycle stealing an open set of starting points is not special to root-finding, and two neighbours are worth naming because they make the general shape clear.

The logistic map. Beyond the first doubling, an attracting two-cycle takes every starting point in the interval except a measure-zero set, and the fixed point that used to attract has become a repeller. There the cycle is the answer; here it is the failure, and the mathematics is identical.

The Mandelbrot set’s interior. Every interior component of that set is a parameter region where the critical orbit falls into an attracting cycle of some period. The uncoloured region in this essay’s hero is the same object read in the dynamical plane rather than the parameter plane, and the reason both are drawn by following a critical point is the theorem of the section above.

The common structure: an attracting cycle owns an open set, the set is found by following a critical orbit, and there are finitely many cycles because there are finitely many critical points. That is Fatou and Julia’s theory in one sentence, and it arrived here in a question about an algorithm.

An uncoloured region means three different things #

The uncoloured region is what the cap could not decide, and that is two things at once. Points falling into the cycle never decide at any cap; points very near a basin boundary have not decided at this cap and would at a larger one. The figure cannot separate them, and the caption’s percentage is an upper bound on the genuinely trapped area rather than a measurement of it.

The disc check is the part that carries the claim, and it is not visible. A hundred and forty-four points round the cycle are tested and every one fails; that is what establishes interior, and the figure shows the conclusion rather than the test.

And the cycle’s superattraction is computed and not drawn. That $N'(0) = 0$ is two lines of arithmetic; the picture shows two marked points and a dashed line between them, which conveys that they map to each other and nothing about how strongly.

Still open: covering instead of avoiding #

The interleaved basins say no single starting point is safe, and this page says some starting regions are permanently unsafe. Both are arguments against choosing a guess.

The repair is to stop choosing. There is a finite set of starting points, computable from the degree alone, from which every root of every polynomial of that degree is found — and its size grows almost linearly in the degree. The fractal is not avoided; it is covered. That is covering rather than avoiding.

Measure zero, and the other kind #

The habit is to ask, of any set of bad inputs, whether it has interior.

A bad set of measure zero is a mathematical curiosity: it is met with probability nought, no random start hits it, and the only way to land on it is to construct it. A bad set with interior is an engineering fact: it has a probability, the probability is not small, and an algorithm meets it in the ordinary course of being used.

That test applies well beyond this subject. A floating-point operation that is catastrophic on a measure-zero set of inputs is fine; one that is catastrophic on an interval is a bug. Both are usually described as the method can fail, and the two statements are worth completely different amounts. The picture that made Newton’s method famous for failing is the harmless one. The failure that matters has a much duller picture and a positive probability, and telling them apart is a question about interior rather than about how complicated the boundary looks.