Newton Fractal Explorer

Guess a solution to an equation. Draw the tangent to the curve at your guess, follow it down to the axis, and take the place where it lands as your next guess. That is the whole of Newton’s method, and for three centuries it has been the first thing anyone reaches for when an equation will not solve by algebra.

It earns that place by speed. Close to a root the error does not shrink by a steady fraction. It is squared. A guess good to two digits becomes good to four, then eight, then sixteen, and a calculation that looked endless is finished in a handful of steps.

Yet the rule hides a question its inventors never asked. An equation of degree three has three roots. If the method arrives somewhere, which starting guesses lead to which root?

A rule that doubles its own accuracy

The method is older than its name suggests. Newton wrote it down in manuscripts of 1669 and 1671 that waited decades for print, and in the second he used it on the equation x^3 - 2x - 5 = 0, hunting the root that lies between 2 and 3. Joseph Raphson published a simpler account in 1690 in a book on the general solution of equations. The Royal Society’s minutes for 17 December of that year record Edmond Halley producing the book, and describe its rule as one that doubles the known figures of a root at each operation.

In symbols the step is short: replace z by z - p(z)/p’(z), where p’ is the slope. Computing both p and its slope takes little work when the polynomial is written in nested form, a scheme named after William George Horner though it is much older. A polynomial of degree n costs n multiplications and n additions, and one more pass of the same kind gives the slope.

Mathematicians grade this sort of speed by an order. If each error is about a fixed fraction of the one before, the convergence is linear. If each error is about a constant times the square of the one before, it is quadratic. At an ordinary root, one where the slope is not zero, Newton’s method is at least quadratic, which is where the doubling of digits comes from.

A worked case shows it. Take p(z) = z^3 - 1, whose roots are 1 and two complex numbers at one third and two thirds of a turn around the unit circle. Start at 1.03 + 0.04i, one twentieth of a unit from the root at 1. The distances to the root on the next three steps are about 0.0024, then 0.0000058, then 0.000000000033. The count of correct digits runs roughly 1, 3, 5, 10.

Cayley’s question

In March 1879 Arthur Cayley, then the Sadleirian professor of pure mathematics at Cambridge after fourteen years earning his living as a lawyer, sent a note of barely a page to the American Journal of Mathematics. Drop the restriction to real numbers, he proposed. Let the coefficients and the first guess be complex, mark the roots as points A, B, C on a plane, and take the first guess P anywhere at all.

His problem was to find the regions of the plane such that a start anywhere inside one region ends at A, anywhere inside another at B, and so on. Today such a region is called a basin of attraction: the set of all starting conditions that are drawn, step after step, to the same resting place.

For a quadratic he had the answer, and called the solution easy and elegant. In a longer paper the same year he worked it through for the equation whose two roots are n and -n. A start nearer to n than to -n converges to n. The plane splits along the line of points equally far from both, and each root takes the half on its own side. The picture is two flat colors and one straight border.

Then came the sentence that kept the note alive. The next case, the cubic, appeared to him to present considerable difficulty. No solution of the kind he wanted exists.

Why three roots cannot share a simple border

The set of start points that fail to settle on any root is, in modern terms, the Julia set of the Newton step, and the basins are the open regions it leaves behind. A theorem about such sets says the basins share one common border: every point of the Julia set is approached, as closely as you like, by points of every basin.

With two basins that is no hardship, since a line has two sides. With three it is strange. A point on an ordinary border between two countries has two neighbors, and only a rare corner has three. Here every border point must be a three way corner. No simple curve can do that, so the border has to be an endlessly crinkled thing.

Topologists met this possibility in an older construction called the Lakes of Wada, three regions of a square that all share the same boundary. The basins of z^3 - 1 have the same property. Zoom into any stretch of border between two colors and beads of the third color appear along it, and between those beads and their neighbors, beads again, at every scale the arithmetic can reach.

This is what a picture of the basins shows. Color each start point by the root it reaches, and the calm interiors record the famous fast convergence, while the borders record sensitivity. In the tool above, type the start point 0.3 + 0.2i for z^3 - 1. It begins closest to the root at 1, but the first step throws it far below the real axis, a later one throws it out to the upper left, and it settles, within one millionth, on the root above and to the left after 12 steps.

Where the method fails outright

Slow borders are not the only trouble. The step divides by the slope, so a guess where the slope is exactly zero has no successor. For z^3 - 1 the origin is such a spot.

Worse, whole patches of the plane can be lost. The cubic z^3 - 2z + 2 has a real root near -1.76929, but start at 0 and the first step lands on 1, the next on 0, and the sequence 0, 1, 0, 1 repeats forever. The loop attracts. A start at 0.99 goes to about -0.063, then 1.006, then 0.037, pulled ever closer to the cycle and never to a root. Around the cycle sits an open region of doomed starts, and smaller copies of it are scattered along the borders, so an honest picture needs a color that means no root at all.

A repeated root fails more quietly. Where two roots coincide the slope vanishes at the root itself, and the squaring is lost. Each step then removes only a fixed share of the error, one half for a double root, so ten digits take dozens of steps where five would have done. If the multiplicity m is known, multiplying the correction by m restores the fast rate, a change that is easy to try and to watch.

Even a start that will succeed can dawdle. For x^20 - 1 started at 0.5, the first step flings the guess out past 26,000, and the method then creeps back, losing about one twentieth of the distance each time. Around the two hundredth step it comes within reach of the root at 1, and only then do the digits begin to double.

What the pictures do and do not say

A basin picture is an experiment, and it has the limits of one. Each pixel stands for a single start point, followed for a stated number of steps and awarded to a root only when it comes within a stated distance. Raise the step limit and a few dark pixels gain a color. None of them proves anything about the points between.

The numbers have a floor as well. Ordinary double precision spaces its values about 2^-52 apart near 1, a little over two parts in ten to the sixteenth. Zoom far enough and neighboring pixels stand for start points the machine cannot tell apart, so the picture stops describing the polynomial and starts describing rounding. A careful explorer states that depth and refuses to go past it.

Nor do the tangled borders mean the method is unreliable in practice. The thin border set is exactly where one would not choose to start, and work in this century has made the choice systematic. There is an explicit set of starting points, depending only on the degree, that is guaranteed to reach every root of a suitably scaled polynomial, and Newton’s method run from such points has found all the roots of polynomials of degree above one million.

Practical solvers also use relatives of the method that avoid the question of basins altogether. One, found by Weierstrass in 1891 and again by Durand in 1960 and Kerner in 1966, moves approximations to all the roots at the same time, correcting each one by its distances from the others. Its answers can be checked without trusting it, since the sum and the product of the roots must match two of the coefficients.

What the pictures say, then, is narrower and stranger than a verdict on usefulness. They say that a rule can be excellent near every answer and still give no short description of which answer it chooses. Cayley saw as much when he gave up on the cubic. It took a century, and machines that could try a million starting guesses, before anyone saw what he had been looking at.