Newton Basins

Newton's method

David E. Joyce

Clark University
August, 1994



Although you can enjoy the Newton Basin images without knowing the technical basis for them, it helps to understand it.

Newton's method for finding roots of functions.

Newton's method began as a method to approximate roots of functions, equivalently, solutions to equations of the form f(x)=0. Not only is the method easy to comprehend, it is a very efficient way to find the solution to the equation.
Suppose you start with a value x0 that you think might be close to a root. The line tangent to the curve y=f(x) through the point (x0, f(x0)) is pretty close to the curve, so wherever that line crosses the x-axis should be very close to the root. Since the slope of the curve is the derivative f'(x0), that point of intersection is easy to compute; the point's x-value is

x1 = x0 f(x0)
f'(x0)
.

So, a better approximation than x0 ought to be x1. Now, if that's not close enough for you, use the method again on x1 to get a better approximation x2:

x2 = x1 f(x1)
f'(x1)
.

Iterate the method until you're satisfied.
For a lot of functions, this iterative method works very well. But not for all functions. For instance, it doesn't work for any function that doesn't have a root. How could it? And it doesn't always work for some functions that do have roots, for instance, the cube root function. If you look for the root of the function f(x) = x1/3 with any initial value, your estimates won't converge. The graph shows how with in initial estimate x0 near 0, the subsequent estimates x1, x2, and so forth, run off to infinity!

Even for those functions it does work for, you might choose a bad initial point x0. For instance, f'(x0) might be zero. Still, it's pretty good, and there are various criteria to tell when it's going to work at all.

Newton's method and complex numbers: Newton basins

The method works for complex functions, too. For more information on complex numbers, see Dave's Short Course on Complex Numbers. For a complex-valued function f(z) whose argument z is complex, you can get better approximations to the root by replacing an initial approximation z0 by the next approximation using the same formula as before:

z1 = z0 f(z0)
f'(z0)
.

Exceptions occur for complex functions as they do for initial functions.
Now, a function can have several roots. A polynomial of degree n has n roots. That's the "fundamental theorem of algebra." Of course, you have to count multiplicities of roots, and you have to allow complex roots as well as real roots. The question is: which root do you approach when you start with an initial value? If you start close to a root, then Newton's method brings you closer to the root faster and faster. But if you start far from a root, then Newton's method may take you to some root other than the closest one. Suppose you paint the complex plane in colors so that all the points that approach a particular root are painted one color. We'll say those points lie in one Newton basin for the function. An interesting pattern emerges. (A few points won't approach any root. Don't color them any color.)


Up to the Introduction
On to some Examples


copyright © 1994, 1997.

The address of this file is http://aleph0.clarku.edu/~djoyce/newton/newton.html