Matpic
mathematics, in pictures
Series

Newton basins — the series

5 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 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.

    part 1 · dynamics
  2. 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.

    part 2 · dynamics
  3. 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.

    part 3 · dynamics
  4. 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.

    part 4 · dynamics
  5. 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.

    part 5 · dynamics

All series