Newton's method and Newton basin fractals

Martin Pergler, 99.11.25. Handout for Calculus 151/30, fall 99.

    Newton's method is a method for iteratively approximating the roots of a function f(x) using the derivative. In other words, you want to find a value x such that f(x)=0, and you do it by guessing and then refining your guess over and over again.
    If the function is quite simple, you may be able to do some algebra to find a root x exactly. For instance, if f(x) is a quadratic polynomial, you can use the quadratic formula. If f(x) is a degree 3 or 4 polynomial, there are messier formulas which work as well. But if f(x) is a higher degree polynomial or a more complicated function, there is no analog to the quadratic formula, i.e. there is no systematic process to algebraically determine the roots exactly. You have to approximate, and Newton's method is one way of doing this.
    We'll start with considering Newton's method over the real numbers, i.e. when x is always real and so is f(x). However, we'll see that the situation becomes much more interesting when we let x and f(x) be complex numbers. For simplicity, we'll use  f(x)=x3-1 in this write-up. Of course, we all know that x=1 is the only real root, and there are two other complex roots
x = -1/2 + (31/2/2) i = -0.5 + 0.866 i  and  x = -1/2 - (31/2/2) i = -0.5 - 0.866 i.        (1)
[Exercise: verify this], and so we don't really need Newton's method in this example. However, even in this simple case we already get pictures which are quite complicated enough!

The Newton's method formula

    The idea behind Newton's method is simple. Let f(x) be a differentiable function. Take a starting "guess" for a root and call it x0. Draw the tangent line to f(x) at x0, and figure out where this tangent line crosses the x-axis. This is the next guess x1 for a root. If f(x) were equal to its tangent line, x1 would actually be a root of f(x), of course. In general, this is not the case. However, the tangent line approximates f(x) for x near x0, and so we hope that x1 is not "too far off" from a root of f(x), in particular hopefully closer than x0. Repeat the process with x1 instead of x0 to get the next approximation x2, and so on. Thus each xn is determined by f(xn-1) and the slope of the tangent line at xn, which is  f '(xn-1). The appropriate formula [Exercise: do this or look up in the textbook] is
xn = xn-1 - f(xn-1) / f '(xn-1)                    (2)

Examples for f(x)=x3-1 over the real numbers

 
   In this case, formula (2) becomes 
xn = xn-1 - (xn-13-1) / 3xn-12.                (3)
Let's start with the guess x0=0.5. Iterating formula (3) gives the sequence shown at right. We are getting closer and closer to the root x=1, so things are working well. In fact, you can see from the picture that any guess x0>1 will quickly converge to the root x=1. In fact, if you randomly pick almost any x0, chances are xn will converge to x=1. Notice, however, that if x0 is close to 0, then the tangent line there is almost flat and x1 will be blasted way out to the right on the x axis. This is not much of a problem, though, since x2 will be pushed rapidly back, as the graph shows for x1=1.7 (approx.). 
    If we choose x0=0, we are in trouble, since the tangent is horizontal, f '(x0)=0 and formula (*) crashes. Furthermore, if we choose a different x0 which eventually "lands" on xn=0, we have the same problem. The graph at right shows this in red for x0=-1.434, which crashes in 2 steps in this manner. There is an infinite sequence of "bad" negative points like this. Note that if we choose an initial guess very close to such a bad point, xn will eventually become close-but-not-equal-to 0, and then xn+1 will get blasted way out to the right and from there eventually converge to x=1. The closer we began to a bad point, the more steps it will take to get "reasonably close" to x=1. [The previous statements all require some work to prove. Skipped.]   An example of this is shown in blue. 

Using complex numbers

    What happens if we now allow x (and f(x)) to be complex numbers rather than just real numbers? Can we get the other complex roots? Though it is beyond the scope of a first-year calculus course, it is possible to define the derivative over complex numbers just as for real numbers, so formula (2) makes sense. It turns out that polynomials are all complex-differentiable, and the complex-derivative is (surprise!) the same as the real-derivative. So formula (3) still holds, even though the geometry is much more complicated. (In part since x is now in some sense 2-dimensional and likewise f(x), so we need to think in 4 dimensions!)
    We change notation and call the variable z instead of x, and write x and y for its real and imaginary parts, so that z = x + i y. Starting with some (complex) guess z0, we can apply the formula and get a sequence zn, which hopefully converges to a (complex) root. Here is what happens for three values of z0 close to 0.5 + 0.5 i.
    The picture shows that one choice (blue) converges to the real root, but another (green) converges to one of the other complex roots. But if we choose precisely z0 = 0.539 + 0.417 i (determined with some effort!), then z1= 0 .539 - 0.417 i, and z2=z0! So we get into an infinite cycle back and forth between these two values and do not converge to any root. This is a different sort of "bad point" than the ones we found on the negative real axis, when f '(x)=0.
    Incidentally, the grey shading in the graph represents |f(z)|. The dark squares are near the roots, when |f(z)| is 0, and the squares are progressively lighter as |f(z)| gets bigger, and hence f(z) gets "further from 0".

The basin of attraction picture

    A natural question to ask is as follows: as z0 varies, which root does zn converge to and when does it not converge? This is shown by coloring in the diagrams below:
>>  >> 
    The first is for x and y ranging from -2 to +2, and the remaining two are successive magnifications of the part of the image in the white square. The three roots have been arbitrarily assigned the colours blue, green, and purple.
    Where are the "bad" points? We already saw there are points of no convergence, shown by red trajectories in previous sections. These are isolated points however, and not easy to hit without trying, and so don't show up in a "random" calculation. It can be proven (check this. ref?) that precisely at any "corner" between blue, green, and purple, there is actually an isolated red (bad) point. In fact, it so happens that on the straight line between any two points of different colours lie points of any other colour! (and hence infinitely many points of all colours).
    The above pictures are called Newton basin of attraction images for f(z)=z3-1.

Fractals

    Fractals are images which generally exhibit the following related 2 properties: [details beyond the scope of the course] 
  1. They exhibit small-scale self-similarity, i.e. little sections appear to be "almost" copies of a larger section of the image, one which contains the little section in question.
  2. They are in some sense "infinitely complicated" on a small scale. 
    The discussion in the previous section shows that Newton basins of attraction are fractals. You may have seen another mathematical fractals such as the Mandelbrot set (at right), which also arises from an iterative system somewhat similar to equation (2). Fractals of various sorts occur in many ways in nature, for instance in modelling the earth's surface or in living objects such as trees and ferns. In recent years, they have also been used to create super-realistic computer graphics in movies!

Some other related pictures...

    Here is the Newton basin of attraction picture for f(z)=z5+6z+1, which cannot be algebraically factored. However, f(z) is "almost" the same as g(z)=z(z4+6), which would have roots z=0 and 4 symmetrical roots around the origin for the quartic factor. Hence we are not surprised the roots and the basin of attraction picture is "almost" symmetrical.
>> 
    Finally, instead of colouring our picture by which root z0 converges to, we can instead measure how many iterations of formula (2) it takes to get zn "really close" to the root it converges to ("really close" means to some fixed small distance). Then we get pictures like the one at right (for our cubic example). The closer the colour is to white, the more iterations are required. It clearly shows how complicated the situation is near to the rays dividing the plane into 3 sections. 
 

Playing around more...

(Pictures drawn using Maple, Fractint, and a bit of tweaking. This page and the first 3 pictures are copyright (c) 1999, Martin Pergler)