Matpic
mathematics, in pictures
Concept

Basin of attraction

The set of starting points whose orbits all end up at the same place. Iterating a map divides the space into basins, one for each attractor, and the boundaries between them can be extremely intricate.

Named by 6 essays across one field — each of them below, with the objects they name alongside it.

A Julia set. Points of the complex plane shaded by how long the iteration takes to escape, with the set itself the innermost region.

One c, one picture

The same iteration, with the parameter held still and the starting point varied instead. Every complex number gets its own picture, and moving the parameter a hair can shatter it into dust.

dynamics · Complex numbers 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.

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.

dynamics · Newton basins An area of starting points from which z³ − 2z + 2 is never solved. The complex plane coloured by which root of z³ − 2z + 2 Newton's method reaches from each starting point, with the points that reach no root left uncoloured.

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 · Newton basins 67 starting points that find all 5 roots. The roots of z⁵ − 1 with a ring of starting points around them, each start marked by which root the method reaches from it, and every root reached by at least one.

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 basins How many steps Newton's method needs on (z − 1)²(z + 1). A square of the complex plane shaded in bands by the number of iterations a root-finding method needs from each starting point, darker meaning slower, with the roots marked.

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.

dynamics · Newton basins Newton's and Halley's basins for z³ − 1. Two squares of the complex plane side by side, each coloured by which root a starting point converges to, the left under Newton's method and the right under Halley's, with non-converging starts marked.

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 · Newton basins

Named alongside it

The objects these essays reach for when they reach for this one.

IterationNewtons methodRoot-findingComplex numbersConvergenceFractalConvergence rateDerivativePeriodic orbitConnectednessError analysisEscape-time

All concepts