Newtons's Method Fractals (Back) (Root)


A Newton's Method Fractals

Newton's method is usually thought of as a way to find roots of an equation. 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 close number. This means that finding the root of the tangent line to a curve at 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 building 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) fin the roots, those z for which f(z)=0, (iii) for every (x,y) in our view window set w=x+iy and fun 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 five roots with values 1, 0.309+0.951i, -0.809+0.588i, 0.309-0.951i, and -0.809-0.588i. There are the five fifth roots of one. The view window for the fractal is a circle of radius two about the origin 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 colored region. The fractal below is a zoom on part of the Newton's method fractal for f(z)=z^3-1 with three roots.

You can click on the above image to enlarge it 16-fold (4-fold in each dimension). This fractal is a good one to look at to understand one of the odder properties of a newton's method fractal. The function f(z)=z^3-1 has three roots that we will call the red, green, and blue root. Think of all points that converge to the red root as the red ``country''. Likewise for green and blue. Then in a Newton's method fractal crossing from one country to another requires you to cross all of the others on the way. This is true for any pair of countries. This would be impossible on a real map, but for a fractal it can happen. Look at the picture above. 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. This continues indefinitely, at every shrinking 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 polynomials and then finding their roots it was much easier, when writing software for Newton's method fractals, to give a list of roots. The guess improver for Newton's method is that the new guess is the old guess minus 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 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. For examples see the gallery of Newton's method fractals.