Newtons method
Named by 12 essays across 3 fields — each of them below, with the objects they name alongside it.
Where Newton's method goes instead
An algorithm designed to find roots, run from every starting point at once. Three roots, three basins, and a boundary at which all three are arbitrarily close — so a rule with no randomness in it has starting points whose answer cannot be predicted.
How fast the staircase arrives
The slope at a crossing decides whether an orbit reaches it. The same number decides how fast — and when the slope is zero the arithmetic changes kind, from a fixed factor per step to a doubling of the correct digits.
An area that never finishes
Newton's method's famous failure is a boundary, and a boundary has no area — a random start misses it with probability one. The real failure is different in kind: a polynomial with small whole-number coefficients whose method has a region of starting points, with area, from which it provably never terminates.
Covering rather than avoiding
Two arguments say no starting guess is safe: the boundary is fractal and some regions are permanently trapped. The repair is not a better guess. It is a fixed list of starting points, computed from the degree alone, from which every root of every polynomial of that degree is found.
A double root halves the error instead of squaring it
Near an ordinary root, Newton's method squares its error at every step and a handful of steps reach full precision. Near a double root it only halves the error — twenty steps where five would do, and a ceiling of about eight correct digits that no number of steps can break through. Doubling the step repairs the double root and ruins the simple one.
A cubic method that is Newton's in disguise
Halley's method, from 1694, uses the second derivative as well as the first and cubes the error at every step where Newton's squares it. It is also, exactly, Newton's method applied to a different function — p divided by the square root of p′ — and that single fact explains why its basins are calmer, why it walks out of the trap that holds Newton for ever, and why its boundaries are still fractal.
A root lifted one digit at a time
On a dial of seven, 3 × 3 is 2. On a dial of forty-nine the square root of 2 must reduce to 3, so there are only seven candidates, and exactly one of them works: 10. On a dial of 343 exactly one lift of 10 works: 108. Each step adds one digit on the left, found by solving a linear equation, and the digits go on for ever — a number …21216213 whose square is 2, in a world where closeness means divisibility by seven.
How smooth the disguise is
An unlocked circle map is a rigid rotation in different coordinates, and whether those coordinates are smooth is decided by arithmetic. Solving for the change of coordinates means dividing, harmonic by harmonic, by numbers that come arbitrarily close to nought — and the golden rotation number keeps them far enough away that the result is not merely smooth but analytic, while a number lying close to a fraction makes it buckle.
Three circles that touch and are not the largest
In 1803 Gian Francesco Malfatti asked how to cut three round columns from a triangular block of marble with as little waste as possible, and answered with three circles each touching the other two and two sides. The circles exist in every triangle and are found by solving three equations. They are never the answer to his question: the plain greedy rule — the inscribed circle first, then the largest circle that still fits, twice — always does better, by 1.4 per cent on the equilateral triangle and by almost double on a thin one.
Chaos on the line between two roots
Newton's method for a quadratic is the one case solved completely: every starting point goes to the nearer root, and the plane splits into two half-planes. Cayley did it in 1879. What his solution also contains is a line on which the method never settles — and a change of variable shows that on that line Newton's method is exactly the doubling map, the simplest chaos there is. Run on the real line for x² + 1, which has no real root to find, it becomes a source of Cauchy-distributed randomness.
Small Mandelbrot sets among the cubics
For most cubics Newton's method finds a root from almost every start. For some it does not: a whole region of starting points falls into a cycle and never finishes. Which cubics are the bad ones is decided by a single starting point — the one critical point that is not a root — and when the cubics are laid out in a plane and coloured by where that point goes, the bad ones form small, exact copies of the Mandelbrot set.
Stable cycles a hair from Hénon's chaos
Nobody knows whether the Hénon map at a = 1.4 is chaotic, because a stable cycle in a window too thin to see would look exactly the same. So hunt the windows: a stable orbit of period 19 at a = 1.4001616, proved to exist and to attract by interval arithmetic, in a window 15 hundred-millionths wide and 0.00016 from the classical value — and nothing nearer, down to a spacing of a ten-billionth.
Named alongside it
The objects these essays reach for when they reach for this one.
Basin of attractionIterationPeriodic orbitRoot-findingDerivativeConvergenceConvergence rateComplex numbersConjugacyError analysisFractalQuadratic convergence