Newton's Method Fractals
If you've taken Calculus I then you probably know about Newton's method, which is an iterative method for solving an equation of the form f(x)=0. Starting with an initial guess, x0, that approximates the solution, the idea is to get a better approximation by computing x1 = x0 - f(x0)/f'(x0). Even better approximations are obtained by computing x2 = x1 - f(x1)/f'(x1), etc. If the sequence of approximations converges then they converge to a solution of the equation.
Many students have asked, "If the equation f(x)=0 has multiple solutions, how do we know which one Newton's method will converge to?" In turns out the answer can be extremely difficult to predict, as the images below illustrate.
Newton's method also works for complex numbers (ie. having real and imaginary parts). In this case both the initial guess and the solution itself can be represented as points in the complex plane. If you associate a color with each solution of f(x)=0, and you paint each point in the complex plane in the color corresponding to the solution Newton's method converges to if you use that point as the initial guess, then you get a map of the "basins of attraction" for the equation. This map can be used to predict which solution Newton's method will converge to: if your initial guess is at a point colored red, then Newton's method will coverge to the solution associated with the color red.
The images below show the basins of attraction that show up for different choices of the function f(x) (all polynomials; recall that if f(x) is polynomial of degree n, then f(x) can have at most n distinct complex roots, so the corresponding basins of attraction will involve at most n colors). All these images have a remarkable self-similar (ie. fractal) character: they contain patterns that repeat themselves on arbitrarily small scales.
Image gallery
Click on an image to view the larger version.
Zoom sequences
Click on an image to view a sequence of enlargements (up to a magnification factor of 10 million) illustrating fine detail at all scales.
Back to my home page