Generator

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

A generator in the dynamics library, called 25 times across 6 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

67 starting points that find all 5 roots

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
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
cap is read only by the speed and compare views ×1
doubling the step at a double root restores the doubling of digits ×1
each root cubes to one ×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
Halley at a simple root roughly triples them ×1
Halley's step is Newton's step for p/√p′ ×1
method is read only by the speed view ×1
Newton at a simple root roughly doubles the digits each step ×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 method is Newton's, Halley's or the relaxed Newton ×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

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

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