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 10 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 Newton's method for z² − 1: two half-planes and the line between. The complex plane split down the imaginary axis into two shaded halves, the roots ±1 marked, and five orbits of Newton's method each converging to the root on its own side.

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 · Newton basins Where the free critical point goes, for every cubic in a family. The parameter plane of the cubics (z − 1)(z² + z + a) from −2 to 3 across and −2.5i to 2.5i up, coloured by the root Newton's method takes 0 to, with small dark regions where 0 is trapped in a cycle.

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 · Newton basins A ring of identical clocks locked into a twist. Ring of 40, nearest-neighbour coupling, settled into a 2-twisted state; largest deviation 2.6e-11; order parameter 2.5e-16.

A ring of clocks settles into a twist

Put identical oscillators round a ring, each pulled only by its neighbours, and start them at random. They always lock — every one ends at the same frequency — but most of the time not in step: the angles wind round the ring a whole number of times and stay wound. The winding number a random start chooses is spread like a bell whose width grows like the square root of the ring, and only coupling to about a third of the ring makes full synchrony certain.

dynamics · Sensitive dependence Where the secant method goes, from every starting pair. x^3−x, 180×180 on [−2,2]²: to −1 10164, to 0 11954, to 1 10164, none 118.

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

Named alongside it

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

Newtons methodIterationRoot-findingPeriodic orbitComplex numbersConvergenceConvergence rateFractalDerivativeMandelbrot setSensitive dependenceConjugacy

All concepts