The Newton fractal | Aseem Raj Baranwal

Newton’s method is a standard recipe for finding a root of a smooth function $f$ . From a starting point $z_0$ , iterate

z_{k+1} \;=\; z_k - \frac{f(z_k)}{f'(z_k)}.

If $f$ is a polynomial with $n$ distinct roots, the iteration is well-defined on the complex plane (except at the critical points where $f'$ vanishes), and from almost every starting point it converges to one of the $n$ roots. The set of starting points converging to a particular root is called that root’s basin of attraction.

For polynomials of degree $\ge 3$ , the basins are not the simple regions one might expect from the algebra. Their boundaries are fractal.

The simplest non-trivial case

Take $f(z) = z^n - 1$ , whose roots are the $n$ -th roots of unity, evenly spaced on the unit circle:

\zeta_k \;=\; e^{2\pi i k / n}, \quad k = 0, 1, \ldots, n - 1.

The Newton iteration simplifies to

z_{k+1} \;=\; z_k - \frac{z_k^n - 1}{n\, z_k^{n-1}} \;=\; \frac{(n-1) z_k^n + 1}{n\, z_k^{n-1}}.

Color each starting point in a region of the plane by which root it ends up at, with darker shades for points that take more iterations to converge. The result is the Newton fractal.

Slide $n$ to change the polynomial. Click anywhere on the picture to launch a Newton iteration from that point and watch the iterates converge.

For $n = 2$ , the basins are exactly the left and right half-planes, separated by the imaginary axis. No fractal. For $n \ge 3$ , every basin shares its boundary with every other basin: any small disk that contains a boundary point also contains points from all $n$ basins. This is the Wada property of the Newton fractal.

Where the boundary is fractal

The set of starting points that do not converge to any root is the Julia set of the Newton iteration map $N(z) = z - f(z)/f'(z)$ . For $f(z) = z^n - 1$ with $n \ge 2$ , this Julia set is non-empty and self-similar at every scale. It has Hausdorff dimension strictly between $1$ and $2$ .

The Newton iteration is a holomorphic dynamical system: the map $z \mapsto N(z)$ is meromorphic on the complex plane. The local theory of holomorphic dynamics says that the boundary of any attracting basin is automatically a fractal except in degenerate cases. The fractal boundary is not a quirk of $z^n - 1$ ; it is generic.

What is interesting beyond the picture

Sensitivity to initial conditions is not the same as randomness. Even though arbitrarily close starting points may converge to different roots, the iteration is fully deterministic. The fractal is exactly the place where this determinism is most dramatic.
Numerical robustness. When you run Newton’s method to find a root of a polynomial, you implicitly assume your starting point is “obviously” in the right basin. The fractal shows that for some initial guesses, this assumption is delicate — a tiny perturbation flips you to a different root.
Algorithms that need all roots of a polynomial cannot rely on naive Newton from a single starting point; they need to navigate the basin geometry. Hubbard, Schleicher, and Sutherland (2001) gave an explicit small set of starting points that is guaranteed to find all roots of any degree- $n$ polynomial via Newton’s method, by understanding the basin structure carefully.

References

John Hubbard, Dierk Schleicher, Scott Sutherland. How to find all roots of complex polynomials by Newton’s method. Inventiones Mathematicae, 146(1):1-33, 2001.
John Milnor. Dynamics in One Complex Variable. Princeton University Press, 2006.
Robert L. Devaney. An Introduction to Chaotic Dynamical Systems. Westview Press, 2003.