Generator

The basins of Newton's method on z³ = 1

A generator in the dynamics library, called 40 times across 9 essays. Below: what it draws with nothing chosen and at each mode an essay asks for, what it checks while drawing, and everywhere it is used.

basins is one function. Everything below came out of it during this build, at parameters taken from the essays rather than invented for this page — so a figure here is the same figure a reader meets in an essay, and if the generator changes, this page changes with it.

With nothing chosen

The basins of Newton's method on z³ = 1. The complex plane coloured by which cube root of one Newton's method converges to from each starting point.

Newton's and Halley's basins for z³ − 1

How many steps Halley's method needs on z³ − 1

How fast the error falls, root by root and method by method

An area of starting points from which z³ − 2z + 2 is never solved

Newton's method for z² − 1: two half-planes and the line between

What it checks while it draws

Collected by running the family and recording what it asserted, not written here. The count is how many separate times the claim was put to the test while these drawings were made.

root 1 is reached from at least one of the starting points ×5
a point beside root 1 runs to root 1 ×3
the iteration cap is a whole number between 8 and 200 ×3
the sample count is a whole number between 60 and 700 ×3
at a root of multiplicity 2 each step multiplies the error by (m − 1)/m ×2
the 5 roots are all distinct and all found ×2
the span is between 0.02 and 6 ×2
a grid of 80 to 240 starting pairs a side ×1
a parameter just outside the copy sends 0 to a root ×1
a region of starting points never reaches a root ×1
a secant step of 0.01 nearly always lands where Newton does, and a step of 1 much less often ×1
along the line, the copy's period is twice the Mandelbrot set's ×1
and the cycle attracts, because the product of the map's derivative round it is under one ×1
and the disc was sampled at 144 points ×1
at least one root was found ×1
at the centre, 0 goes to a second point and straight back ×1
cap is read only by the speed and compare views ×1
chords go flat at the first, second and third steps somewhere in the square ×1
doubling the step at a double root restores the doubling of digits ×1
each cotangent returns after n steps ×1
each error divided by the product of the two before tends to f″/2f′ at the root ×1
each marked parameter traps the critical point in an attracting cycle ×1
each root cubes to one ×1
each step of the orbit, seen through the change of variable, is a squaring ×1
every point called a root really is one ×1
every point of a small disc round the cycle reaches no root ×1
every root marked is a root ×1
every start off the dividing line runs to the root on its side ×1
Halley at a simple root roughly triples them ×1
Halley's step is Newton's step for p/√p′ ×1
just inside, 0 falls into a cycle of period 2 ×1
method is read only by the speed view ×1
Newton at a simple root roughly doubles the digits each step ×1
outside the copy, 0 lingers near the ghost of the cycle before reaching a root ×1
poly is read by the cycle, universal, speed and compare views ×1
so the failing set has area rather than being a boundary ×1
the centre found returns 0 to 0 in the stated number of steps ×1
the digits gained grow by the golden ratio at each step ×1
the histogram follows the Cauchy density ×1
the method is Newton's, Halley's or the relaxed Newton ×1
the orbit's angle doubles at each step ×1
the parametrised curve lies on x₀² + x₀x₁ + x₁² = 1 ×1
the period of the cycle at the centre of the copy's largest bulb ×1
the polynomial is one the family knows ×1
the roots found are counted ×1
the set has as many points as the construction asks for ×1
the two points really do map to each other ×1
the view is one the family draws ×1
with no imaginary part left over ×1

Where it is called

Every figure on this list is drawn by the same rule, so a change to the rule changes all of them at once. That is why the list is published.

Dynamics

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.

Dynamics

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.

Analysis

A map that shrinks everything

One extra hypothesis — that every distance is shortened by at least a fixed factor — turns the existence of a fixed point into its uniqueness, an algorithm for finding it, and a bound on the error after any number of steps.

Dynamics

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.

Dynamics

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.

Dynamics

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.

Dynamics

Newton's method without a derivative

Replace Newton's tangent by the chord through the last two guesses and the method no longer needs a derivative — but it needs two starting values, so its basins live in a plane of pairs instead of on a line. The errors multiply instead of squaring, their logarithms add like Fibonacci numbers, and the digits gained grow by the golden ratio: 1, 3, 5, 9, 15, 25, 41, 67, 109.

Dynamics

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.

Dynamics

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.

The whole library · What the figures prove