Newton's method in the complex plane

To find a root of a function f(z), Newton's method iterates z ← z − f(z)/f′(z). When z is a complex number this same rule traces a path through the plane. For most starting points the path spirals into one of the polynomial's roots.

Basins of attraction

The basin of a root is the set of all starting points that eventually converge to it. We give every root a distinct color and paint each pixel by the basin it belongs to, shading it brighter when convergence is fast (few iterations) and darker when it is slow.

The fractal boundary

Where basins meet, the picture never settles down: arbitrarily close to a point heading for root A there are points heading for root B and root C. This boundary is a fractal with the striking property that every boundary point touches all the basins at once.

Cayley's problem

In 1879 Arthur Cayley solved the case z² − 1 (the basin boundary is just the imaginary axis) but found z³ − 1 "presents considerable difficulty." That difficulty is the fractal — a structure that could not be seen until computers could color millions of pixels.

Relaxation & chaos

Over- or under-relaxed Newton uses z ← z − a·f(z)/f′(z). With a = 1 you get classic Newton; pushing a away from 1 (or choosing a polynomial like z³ − 2z + 2 with attracting cycles) breaks convergence and reveals chaotic, never-converging regions.