Newton Fractals and Where an Approximation Will Land

Definition A Newton fractal is the pattern that appears in the complex plane when Newton’s method for a polynomial equation is started from every point and each start is colored by the root its guesses approach. Complex numbers $a + bi$, with $a$ and $b$ real and $i^2 = -1$, are drawn as the points $(a, b)$ of this plane, and $\lvert z - w \rvert$ is the distance between the points $z$ and $w$. The standard example is the equation $z^3 - 1 = 0$, whose roots are the three cube roots of unity $1$, $\omega$ and $\omega^2$ described below. Its Newton step is

which is defined for every $z \ne 0$. The rules are as follows. Choose a start $z_0$, compute $z_1 = N(z_0)$, then $z_2 = N(z_1)$, and so on, and give $z_0$ the color of a root when the guesses converge to that root. A start for which some guess equals $0$, where the step is undefined, or whose guesses converge to no root, gets no root color. The regions of the three colors are the basins of attraction of the three roots. Each basin is open and contains the disk of radius $1/3$ around its root, so a start that does reach a root can be moved a little without changing its color. The surprise is how the basins meet. The three basins have exactly the same boundary, so every point on the edge of one color is also on the edge of the other two, and every disk around such a point, however small, contains starts of all three colors. Every start off this common boundary converges to one of the roots, and no start on it does. The boundary contains $0$ and every start whose guesses land on $0$, these starts come arbitrarily close to every point of the boundary, and near each of them the picture around $0$ appears again, turned and rescaled, with a better match the closer one looks. The fractal in the picture is this common boundary, which in the theory of iteration is called the Julia set of the map $N$. Pictures show the pattern, but they do not by themselves prove these facts or give the boundary’s fractal dimension.

Definition Newton’s method is a procedure for approximating a solution, or root, of an equation $f(x) = 0$, where $f$ is a differentiable function. Start from a guess $x_0$ and compute

for $n = 0, 1, 2, \dots$, which is possible only as long as $f'(x_n) \ne 0$. If some guess has $f'(x_n) = 0$, the next guess is undefined and the method stops. In the graph, $x_{n+1}$ is the point where the tangent line to $y = f(x)$ at the point $(x_n, f(x_n))$ crosses the $x$-axis. For a polynomial $p$ in a complex variable $z$ the same formula is used with complex arithmetic, and the derivative $p'$ comes from the usual power rule. The method comes with a guarantee near a simple root, which is a root $r$ with $f'(r) \ne 0$. Suppose $r$ is a simple root and $f$ has a continuous second derivative near $r$, as every polynomial does. Then there is a distance $\delta > 0$ such that every start within $\delta$ of $r$ gives guesses that are all defined and converge to $r$, and there is a constant $C$ with $\lvert x_{n+1} - r \rvert \le C \lvert x_n - r \rvert^2$ for every $n$. The same holds for a simple root of a polynomial in a complex variable, with a disk around the root in place of an interval. Once the guesses are close, the number of correct digits roughly doubles with each step. Farther from a root there is no such promise. The guesses can land where the derivative is zero, jump back and forth forever, or wander.

Definition The cube roots of unity are the three complex numbers $z$ with $z^3 = 1$. Factoring $z^3 - 1 = (z - 1)(z^2 + z + 1)$ and solving the quadratic equation $z^2 + z + 1 = 0$ with the quadratic formula gives

where $\omega$ is the Greek letter omega. All three lie on the unit circle, the circle of radius $1$ around $0$, at the angles $0^\circ$, $120^\circ$ and $240^\circ$ measured counterclockwise from the positive real axis. They are the corners of an equilateral triangle with side $\sqrt{3}$, only $1$ is real, and they add up to $1 + \omega + \omega^2 = 0$. Each is a simple root of $z^3 - 1$, because the derivative $3z^2$ is not $0$ at any of them, so the guarantee of Newton’s method applies near each one. Multiplying by $\omega$ turns the plane by $120^\circ$ about $0$ and sends $1$ to $\omega$, $\omega$ to $\omega^2$ and $\omega^2$ back to $1$. The page Complex Numbers and the Plane Behind the Pictures covers complex multiplication and its effect on angles.

Definition Let $p$ be a polynomial and $r$ a root of $p$ with $p'(r) \ne 0$. The basin of attraction of $r$ under Newton’s method is the set of all starts $z_0$ for which every Newton step is defined, meaning $p'(z_n) \ne 0$ for every $n$, and the guesses $z_n$ converge to $r$. Basins of different roots never overlap, because a sequence cannot converge to two different numbers. Each basin contains a disk around its root, by the guarantee of Newton’s method, and it is an open set, which means that every start in it has a small disk around it that also lies in the basin. The starts that belong to no basin include the zeros of $p'$ that are not roots, every start whose guesses land on one of them, and every start whose guesses cycle or wander without converging to a root.