Newton's Method Fractals
Newton's method is a way to find roots of an equation. Recall that
the roots of an equation are the x-values that make the function zero.
The idea is pretty simple. Finding the root of a line y=ax+b is easy.
You set y=0 and solve getting x=-b/a. If you have some other
equation, then first you find the tangent line at a point close to a
root. You then find the root of the tangent line instead of
finding the root of the equation. This doesn't do the whole job but
(usually) the root of the tangent line is much closer to the root than
your original guess. This means that finding the root of the tangent
line to a curve as a guess at a root improves the guess. Since it can
improve any guess, you just keep going. Guess, improved guess,
improved improved guess, etc. In the picture below X0 is our original
guess and X1 is the improved guess.
Finding tangent lines requires calculus. If you don't know any
calculus yet, then don't worry, just remember that we have this method
of improving guesses at a root. This is the key to creating Newton's
method fractals. If you've read the article on complex arithmetic you know we
can identify the the Cartesian plane with the set of complex numbers.
To get a Newton's method fractal we (i) pick a complex polynomial
f(z), (ii) find the roots, those z for which f(z)=0, (iii) for every
(x,y) in our view window set w=x+iy and apply Newton's method
with w as the initial guess. We color the point at (x,y) according to
which root Newton's method converged to.
The fractal at the top of the page is derived from the complex
polynomial f(z)=z^5-1. This polynomial has five roots with values 1,
0.309+0.951i, -0.809+0.588i, 0.309-0.951i, and
-0.809-0.588i. These are the five fifth roots of one. The
view window for the fractal is a square with corners -1.6-1.6i
and 1.6+1.6i and so the roots, all of which are distance 1 from
(0,0), are visible in the picture. They are in the center of small
monochrome disks at the center of the ripples in each of the five
largest colored regions.
Think of all points that converge to the red root as the red
``country.'' Likewise for other colors. Then, in a Newton's method
fractal, crossing from one country to another requires you to cross
all of the other countries on the way. This is true for any pair of
countries (colors). This would be impossible on a real map, but for a
fractal it can happen. Look at the picture at the top of the article.
To go from blue to green you must cross red. But to get from blue to
red you must cross green. But to get from blue to green you must
cross red, gold, and violet. This continues indefinitely, at all
scales. At the border between countries normal geometric rules break
down and you get fractal behavior. Remember that even though you can
see places where two colors touch in the picture, that's just because
the area in between with the other color is smaller than one pixel.
Instead of specifying a polynomial and then finding its roots, it
is much easier when creating pictures of Newton's method fractals,
to just specify a list of roots. The applet triggered by the button above
does exactly this. The guess improver for Newton's method is:
the new guess is the old guess minus the ratio of the function at the
old guess and the slope of the tangent line at the old guess. In
terms of calculus: new = old - f (old) / f '(old). Keeping that in mind, here
is the Newton's method algorithm.
Newton's method fractal algorithm
Choose a list of complex numbers w1, w2, ... wk.
Pick a tolerance epsilon.
Pick an iteration cutoff limit.
For every point (x,y) in your view rectangle
Use Newton's method starting at x+iy
If within limit iterations you are within
epsilon of one of the Wi, then color (x,y)
with color i
Else color with the non-covergent color
For the pictures in this article the cosine
coloring method was used but anything, including flat colors,
looks pretty interesting.
Back to Blog