Newton's method and Newton basin fractals
Martin Pergler, 99.11.25. Handout for Calculus 151/30,
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.
[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]
xn = xn-1 - f(xn-1) / f '(xn-1)
Examples for f(x)=x3-1 over the real numbers
| In this case, formula (2) becomes
xn = xn-1 - (xn-13-1)
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 are images which generally exhibit
the following related 2 properties: [details beyond the scope of the course]
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
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.
They are in some sense "infinitely complicated" on a small scale.
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...
You can interactively draw Newton basin of attraction pictures for any
polynomial you want (by specifying its complex roots) by visiting David
E. Joyce's Newton Basins site at Clark University.
You can also draw all sorts of fractals on a DOS/Windows computer
They also have lots of fascinating pictures at another page on the same site.
If f(x) has several real roots, you can still draw
interesting pictures using only real numbers by coloring the
points on the x (real) axis according to which root they iterate to. There
is a Java applet that does this at
(Pictures drawn using Maple, Fractint, and a bit of tweaking.
This page and the first 3 pictures are copyright (c) 1999,