© 2009 Mitch Richling
 |
 |
While the Mandelbrot set may be the most famous fractal image, the so called "Newton's Fractal" is not too far behind in recognizably. First a bit of background. Newton's method, is an iterative algorithm used to find the roots of a function given an initial guess. In mathematical terms, Newton's method takes a function and an initial guess, 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 what initial guesses will lead to a root, and to which root the might converge when the function has multiple roots. 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.
If we fix a function, 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:
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.
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:
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:
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.