Jump to my Home Page Send me a message Check out stuff on GitHub Check out my photography on Instagram Check out my profile on LinkedIn Check me out on Facebook

Newton Fractal


Table Of Contents

Introduction

While the Mandelbrot set may be the most famous fractal image, the so called "Newton's Fractal" is not too far behind in recognizably. The fractal is a byproduct of an algorithm known as "Newton's method". In mathematical terms, Newton's method takes a function with an initial guess for a root, and specifies a method of constructing an infinite sequence that frequently converges to some root of the function. The fine print for Newton's algorithm surrounds the words "frequently" and "some" in the previous sentence! It can be very difficult to tell if an initial guesses will lead to a root, and to which root it might converge! Knowing that Newton's method converges for a given initial guess tells us almost nothing about the convergence properties for other initial guesses - even ones infinitely close.

For any function we might choose, we may use Newton's method to construct a sequence for any point in the complex plane by using that point as the initial guess for Newton's method. We may then use the convergence properties for each point in the complex plane to draw a picture. This is very similar to the way a sequence convergence pattern is used to draw the Mandelbrot set. The classical Newton's fractal is obtained by drawing the convergence pattern of Newton's method applied to the following function:

f(x)=z^3

If a sequence generated by applying Newton's method to this function converges, then it will be to one of the three cube roots of -1. Because of this, the shading method for Newton's Fractal is a bit more complex than it is for the Mandelbrot set (who's sequences have but one interesting limit point). For the classic Newton's fractal, we color each point according to which limit point the sequence converges.

The Traditional Newton's Fractal

One can generate Newton's Fractal as normally presented with just a little bit of code. We color a point red if it converges to the real cube root of -1, green if it converges to the complex root in the right half-plane, blue if it converges to the complex root in the left half-plane, and we leave the point black if it doesn't converge at all. The shade of red, blue, or green is determined by how fast the sequence appeared to converge to the appropriate root - brighter colors mean faster convergence.

        #include "ramCanvas.h"
        #include <math.h>
        #include <complex>
        #include <iostream>
                  
        #define pi 3.14159265359
                  
        using namespace mjr;
                  
        int main(void) {
          int   MaxCount = 255;
          int   MultCol  = 15;
          float Tol      = .0001;
          std::complex<double> r1(1,               0);
          std::complex<double> r2(-0.5,  sin(2*pi/3));
          std::complex<double> r3(-0.5, -sin(2*pi/3));
          ramCanvas4c8b theRamCanvas = ramCanvas4c8b(4096, 4096, -2.0, 2, -2, 2); 
                  
          for(int y=0;y<theRamCanvas.get_numYpix();y++) {
            for(int x=0;x<theRamCanvas.get_numXpix();x++) {
              std::complex<double> z(theRamCanvas.int2realX(x), theRamCanvas.int2realY(y));
              int  count = 0;
              while((count < MaxCount) && (abs(z-r1) >= Tol) && (abs(z-r2) >= Tol) && (abs(z-r3) >= Tol)) {
                if(abs(z) > 0)
                  z = z-(z*z*z-1.0)/(z*z*3.0);
                count++;
              }
                  
              if(abs(z-r1) < Tol)
                theRamCanvas.drawPoint(x, y, color4c8b(255-count*MultCol, 0, 0));
              if(abs(z-r2) <= Tol)
                theRamCanvas.drawPoint(x, y, color4c8b(0, 255-count*MultCol, 0));
              if(abs(z-r3) <= Tol)
                theRamCanvas.drawPoint(x, y, color4c8b(0, 0, 255-count*MultCol));
            }
          }
          theRamCanvas.writeTGAfile("-");
        }
        

The above program will generate this picture:

LISP-ers might be interested in a LISP version of the above program.

Another Way To Color Newton's Fractal

Nothing wrong with the traditional way of drawing Newton's fractal; however, some insight into just how strange the convergence is for Newton's method may be obtained from a different coloring algorithm. In the funny regions between roots, it is clear that very tiny disks exist that contain distinct points which converge to each of the three roots. One can see this at the center of the image for example where we see red, blue, and green very near each other. In fact, each place where the "fish" come together to "kiss" contains such a disk. Even knowing such little disks have this behavior doesn't necessarily prepare one for the fact that newton's method doesn't converge very well in such disks -- i.e. the sequence doesn't simply start in the disk and make a bee-line for the appropriate root. Instead, the sequence can "blow up" and reach VERY large complex numbers (in modulus) before it begins to behave itself and converges nicely to a root. One can see this strange behavior by coloring the pixels according to the maximum modulus achieved by a sequence on the way to convergence.

This new image may be generated by making a slight modification to the previous program:

        #include "ramCanvas.h"
        #include <math.h>
        #include <complex>
        #include <iostream>

        #define pi 3.14159265359

        using namespace mjr;

        int main(void) {
          int   MaxCount = 255;
          int   MultCol  = 400; // 1, 400, 3000
          float Tol      = .0001;
          std::complex<double> r1(1,               0);
          std::complex<double> r2(-0.5,  sin(2*pi/3));
          std::complex<double> r3(-0.5, -sin(2*pi/3));
          ramCanvas4c8b theRamCanvas = ramCanvas4c8b(4096, 4096, -2.15, 1.85, -2, 2);

          for(int y=0;y<theRamCanvas.get_numYpix();y++) {
            for(int x=0;x<theRamCanvas.get_numXpix();x++) {
              std::complex<double> z(theRamCanvas.int2realX(x), theRamCanvas.int2realY(y));
              int  count = 0;
              double maxMod = 0.0;
              while((count < MaxCount) && (abs(z-r1) >= Tol) && (abs(z-r2) >= Tol) && (abs(z-r3) >= Tol)) {
                if(abs(z) > 0)
                  z = z-(z*z*z-1.0)/(z*z*3.0);
                if(abs(z)>maxMod)
                  maxMod=abs(z);
                count++;
              }

              if(abs(z-r1) <= Tol)
                theRamCanvas.drawPoint(x, y, color4c8b(255-maxMod*MultCol, 0, 0));
              if(abs(z-r2) <= Tol)
                theRamCanvas.drawPoint(x, y, color4c8b(0, 255-maxMod*MultCol, 0));
              if(abs(z-r3) <= Tol)
                theRamCanvas.drawPoint(x, y, color4c8b(0, 0, 255-maxMod*MultCol));
            }
          }
          theRamCanvas.writeTGAfile("-");
        }
        

The above program will generate this picture:

LISP-ers might be interested in a LISP version of the above program.

Modified Newton's Fractals

A very slight change to Newton's method is frequently used to generate different fractals. The normal Newton iteration is defined by the following equation:

\$z_{n+1}=z_n-\frac{f(z_n)}{f'(z_n)}\$

We simply add a factor to the equation thus modifying the delta at each step like so:

\$z_{n+1}=z_n-\alpha\frac{f(z_n)}{f'(z_n)}\$

By varying the value for alpha, very different fractals are generated:

alpha=1.0 alpha=-0.5 alpha=2.0 alpha=-0.5+2i

The images above were all generated by a small LISP program which may be downloaded by clicking on the image and following the code link.

References

I have never seen the second coloring algorithm discussed above; however, it seems unlikely to me that I'm the first person to dream it up. Unfortunately I am unable provide any references for this particular technique. I would appreciate any references to the literature making use of similar coloring algorithms. That said, the works below are a good source for information regarding the traditional form of Newton's fractal.

I strongly recommend the book "The Science of Fractal Images" (ISBN: 0-387-96608-0) to anyone who actually wants to use a computer to generate pictures. This book has an all star group of contributing authors.

For a very interesting introduction to the history of Chaos I would suggest James Glick's book: "CHAOS: Making a New Science" (ISBN: 0-14-009250-1). This book has almost no mathematics or formal material regarding Fractals or dynamical systems, but is well worth the read for the historical perspective.

If you are looking for a good introduction to dynamical systems, I would suggest Steven Storgatz's book: "Nonlinear Dynamics and Chaos" (ISBN 0-7382-0453-6).

For a good, encyclopedic, introduction to the field in general, I strongly suggest "Chaos and Fractals: New Frontiers of Science" (ISBN: 0-387-97903-4) by Peitgen, Jurgens, and Saupe. This book is notable because of it's clear presentation and breadth of coverage. It's a great book to have around for the casual reader because it is broken up into semi self-contained sections that one can just pick up and read.

© 2009 Mitch Richling