Newton's Method Fractals

This article introduces a type of fractal that can be generated by using a version of Newton's method for finding roots of an equation with complex arithmetic. The article outlines the root finding method.

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.


Directions

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.

f(z)=(z-w1)*(z-w2)*...*(z-wk).

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    
End for

For the pictures in this article the cosine coloring method was used but anything, including flat colors, looks pretty interesting.

Back to Blog