Fractals from Newton's Method

Isaac Newton discovered what we now call Newton's method around 1670. Although Newton's method is an old application of calculus, it was discovered relatively recently that extending it to the complex plane leads to a very interesting fractal pattern. Suppose we have a function f[x] and we would like to estimate its roots to a high degree of accuracy. Perhaps we can make an initial guess based on numerical or graphical evidence. Newton's method says that if the initial estimate was close enough to the actual root, then we can improve on the initial estimate by applying the function:
Newt[x] = x - f[x]/f'[x]
We can then use this output as a new initial guess for an even better estimate and so on. This leads to an iterative procedure which should converge to the actual root. For example, suppose
f[x] = x^3 - 2
Looking at the graph we see that there is one root a little less than 1.5.

We can evaluate Newt[1.5] to get the improved estimate 1.2963. We can have Mathematica perform this iteration until a fixed point is found. Here is the result:

{1.5, 1.2963, 1.26093, 1.25992, 1.25992}

Thus 1.25992 is a very good approximation to the cube root of 2.

The analysis above need not be restricted to real numbers. The initial guess could just as easily be a complex number. We usually use the variable z to indicate that the function accepts complex input. When viewed as a function of a complex variable, f[z] has not just one but three roots. Here they are with there positions in the complex plane:

{{z -> 1.25992}, {z -> -0.629961 - 1.09112 I}, 
 
  {z -> -0.629961 + 1.09112 I}}

In 1879, Cayley asked the following question: given an initial input z0, to which root will Newton's method converge. The answer was only fully understood recently and leads to a beautiful fractal pattern. We can have a computer draw this pattern as follow:

Divide the square [-2,2]x[-2,2] into a large number of smaller subsquares. Each subsquare corresponds to a complex number.
Perform Newton's method on the complex number for each subsquare to determine to which of the three roots this initial choice converges.
Color the subsquare red, yellow, or blue depending on the answer in the above step.

Here is the result:

The above function actually corresponds to the function f[z] = z^3 - 1 so the three roots will be the cube roots of 1 rather than 2. We can modify the above to generate related images. Suppose we're interested not in to which root the iteration converges but, rather, how long the iteration takes to get reasonably close to the root. Then we'll generate a shaded image which highlights the roots.

Finally, here's a picture which takes into account both the root converged to and the number of iterations required to get close.

Here is the Mathematica code to generate these images.

[UNCA | Math Dept. | Mark's Home]