Stories about Fractal Plotting
The Divergence Scheme
The Convergence Scheme
Fatou Patterns
Julia Patterns
Newton Patterns
Basic 3D Plotting
Links
Speaking loosely without technical terms such as the HausdorffBesicovitch dimension and topological dimension of a set of points, a fractal, coined by Benoit Mandelbrot, is a geometric shape that is selfsimilar, i.e., a large part of it contains a great many smaller parts that resemble the large part in some way; see Figure 1 below.
Nature is filled with fractals as seen in such objects as mountains, shorelines, trees (branches, barks and roots), ferns, fluid flow patterns, cloud formations (with or without lightning), blood vessels and mycelium strands. The idea of fractal was already conceived by some mathematicians like Cantor in the 19th century, and about a hundred years ago, a group of mathematicians represented by Fatou and Julia studied certain fractals generated by the socalled “dynamical systems.” So, the fractals are an old subject which did not particularly excite mathematicians for about fifty years until Mandelbrot showed the Mandelbrot set plotted by a computer using some of the theories developed earlier by Fatou and Julia. Stimulated by the novelty, beauty and complexity of the Mandelbrot set, some of the mathematicians reinvigorated the subject and developed deeper and more extensive theories that contributed to fractal geometry.
On the other hand, “chaos,” often associated with fractals, was basically born as a brand new subject in 1974 from biologist Robert May’s computer simulations of population dynamics through the dynamical system called “logistic equation,” although some chaosrelated phenomena such as the sensitivity to a small change in the initial situation that might cause a hugely unexpected outcome or the “butterfly effect” had been observed earlier by some mathematicians and physicists. “Chaos” was then welcomed with great sensations after American Mathematical Monthly published “Period Three Implies Chaos” by T.Y. Li and James Yorke in 1975. Younger mathematicians were especially excited to see the fact that there appeared very little difference between chaotic and random outcomes even though the former resulted from the deterministic process through the logistic equation.
Now, fractals provide not only mathematical insights for natural objects and phenomena that are beyond the reach of Euclidean geometry but also numerous applications in surprisingly many areas in sciences, mathematics and art especially when it is tied with chaos.
Through
Google or
Yahoo!, we can find thousands of Internet fractal galleries, many of which display stunningly beautiful computergenerated fractal art images. This indicates that a very large population not only appreciates the digital art form but also participates in the eyeopening creative activity. Written below is a guide on how to program a computer and plot popular types of fractals that are closely tied to chaos. Because of the close association to chaos, a slight change in input values (intentional or accidental) may greatly affect the pattern of the output fractal and this unpredictability provides an added excitement while running the computer program. The subject is kept less formal and mathematical with light topics added here and there in an attempt to avoid it to become cutanddried. The audience, who may be merely intrigued by the general idea behind fractal plotting, is encouraged to try it. Although the basic process is not based on higher mathematics, it certain takes intelligence and patience to be successful in the outcomes. Therefore, the experience may at some point start to stir your deep imaginations in the part of mathematics that is quite profound and involved. Best of all, though, it is plain fun and worth the effort.
Each of the fractals we discuss is generated by a single equation and may be classified into one of the three categories, which I call Fatou, Julia, and Newton patterns, using the names of the giants in history of mathematics contributed to the fractal plotting in hand. I should warn the audience at this stage, however, that the terms such as “Fatou pattern” are used rather loosely for the sake of convenience in this site and they are not universally adopted in the field. The prerequisite for our project is to know (1) fundamental algebra and geometry of complex numbers, (2) entrylevel calculus up to the idea of derivative, and (3) basic computer programming in such language as Java in a graphics mode. I use a modernized "objectoriented" version of Pascal called Delphi marketed by Borland. (1) includes the practice of writing a complex number z as a point (x, y) in the xyplane, called the complex plane, as well as the standard algebraic expression z = x + yi.
At the outset of each plotting process, we choose three objects: (a) a rectangular canvas, part or whole of which will appear in the computer's display screen and which will be filled with a (visual) fractal pattern at the end; (b) A generating equation such as z_{n+1}= z_{n}^{2} + p, which is essential in determining the fractal pattern and which involves two indexed variables and the third variable p called a parameter; (c) A rectangular region R in the complex plane consisting of points, er complex numbers z = (x, y), which will be filled with the digital (version of the) fractal pattern comprising a bunch of integers that later gets visual when transferred to the canvas with various colors determined by the integers.
The canvas comprises finitely many small rectangular picture elements, a.k.a. pixels, and it can be larger than the computer screen like having the dimensions of 4000x3000 pixels. But for an early trial, it is smarter to choose a small canvas with say 400x300 pixels because the program runs so much faster this way and the resulting output picture is likely to be thrown into the trash bin. If you have done computer graphics, then you are also aware that at the outset of each program you have to construct a natural onetoone mapping from the canvas into R, while the rectangles belong to different planes with different coordinate systems, namely the screen coordinates and the familiar Cartesian coordinates. We can find the process in a programming manual or through Googling, which involves a simple change of coordinates that also allows us to choose the same (finite) number of points (complex numbers) (x, y) in R using the onetoone mapping. As in a graphics calculator, it is convenient to call the four real numbers bounding R xmin, xmax, ymin, and ymax.
For the sake of simplicity in our argument, we will henceforth assume that R has the finite number of points (so computers can handle it) and identify the canvas and R through the onetoone correspondence. Thus, a pixel will always mean a complex number. This way, we can avoid getting caught up with the technical details each time we discuss the fractal plotting and losing our focus on the essence of the subject. While we run our computer program, there is an interaction between the generating equation and each pixel (complex number) in the canvas, which determines the pixel color and eventually fills the canvas with a fractal pattern. Here comes an example:
(A) The Divergence Scheme
We begin our discussion with the square canvas R consisting of say 300x300 = 90,000 pixels and bounded by say xmin = 2.1, xmax = 2.1, ymin = 2.1, and ymax = 2.1, and the generating equation
(*)
z_{n+1} = z_{n}^{2} + p ,
where the parameter p is a pixel in the canvas R. (*) is called the Mandelbrot equation or sometimes the Fatou equation as Pierre Fatou studied the dynamics of the equation nearly a century ago.
The bestknown figure in fractal geometry is given by iterating the Fatou equation using the initial value z_{0}= (0, 0) for n = 0, 1, 2, ... , M, and for "every" one of the 90,000 pixels p in R. Here M is a prescribed maximum number of iterations that rescues the computer from getting trapped in an infinite loop, and M = 500 is used in this example. In my program, M is almost always a number between 50 and 500,000 but it occasionally gets as large as 2,000,000.
Assuming that our object is to plot a picture in black and red with a background or canvas color say white, our painting scheme is basically given by the IF statement:
If
z_{1} > 2 then color the pixel p black,
else if z_{2} > 2 then color the pixel p red,
else if z_{3} > 2 then color the pixel p black,
else if z_{4} > 2 then color the pixel p red,
etc.,
where z_{n} stands for the modulus or absolute value of z_{n}. It can be shown that z_{n} > 2
for some n if and only if the sequence z_{n} tends
to infinity as n increases; this implies that the above scheme assigns a color to each pixel p according to how quickly the complex number z_{n} escapes from the circle of radius 2 before taking a long journey toward infinity. This basic scheme can be streamlined in the actual program by using:
just two variables zold and znew instead of the large array z_{0} , z_{1} , z_{2} , ...;
z_{n}^{2 }> 4 in place of z_{n}
> 2 to avoid the hidden square root operation; and
MOD operation to simplify the awkward and repetitive blackred coloring scheme.
Also, the use of any radius greater than 2 (say 100) in place of 2 in the above scheme works just as well and in some cases even better. Computer programming has two faces, art and science, and requires artful wits as well as rigidly logical thinking. Writing, streamlining and debugging computer programs, therefore, provide us with an ideal way of exercising our brain and maintaining normal connections among the neurons. I would recommend it highly to people with computers to take up computer programming. (It’s in a way funny to say it because people used to get near a computer only to run their computer programs.)
Observe that for each pixel value p, we have a sequence of complex numbers z_{n} , n = 0, 1, 2, …, which moves about the complex plane, and for this reason, a generating equation like (*) is called a dynamic mathematical system or dynamical system. We may view a dynamical system as the collection of the sequences z_{n }, one sequence for each choice of p in the canvas where the initial value z_{0 } is fixed at a single value (like 0 in the current example) for all of the sequences. (Later we will consider a dynamical system consisting of the sequences where the initial value z_{0 } varies in the canvas while the parameter value p is fixed at single value for all of the sequences.)
As we noted, the color of a pixel is determined according to the "escape speed" of the corresponding sequence z_{n} , n = 0, 1, 2, …, from a prescribed circle about the origin. Since all of the escaping sequences diverge to infinity, I call the coloring scheme (without limiting a number of colors) the divergence scheme. Figure 2 is given by the above basic redblack divergence scheme, and the area that retains the white canvas color depicts the famous Mandelbrot set or M set, for short. The set consists of the pixels p attached to the sequences z_{n }that stay within the circle forever regardless of the value of n. If we alter the values of xmin, etc. and run the same program to zoom in on a small area of the plot near the boundary of the Mandelbrot set, we will discover the selfsimilarity property of fractals along with a hairy characteristic of the "snowman". Many microscopic shapes resembling the snowman are connected by an extremely intricate network, which we can find by zooming intently and patiently; for example, see the Mandelbrot Set or Logistic M Set in the gallery. Not surprisingly, it has been verified that the Mandelbrot set is one of the most complex figures ever plotted on a piece of paper.
Here is the very essence of our fractal plotting:
The closer the zoomed area is to the boundary, the finer the fractal pattern.
The reason, which leads us to the idea of chaos, is that parameters p near the boundary often belong to the sequences
z_{n }with diverse properties interlaced in a complex fashion. Thus, a very slight change in the value of p in this area may result in an utterly different "future behavior" of the corresponding sequence z_{n }which dictates its escape speed and the pixel color. Yes, these sequences z_{n } are just like people, most of whom would behave unpredictably when they are placed near an infernal border between life and death and cause chaos for the whole population in the area. What is interesting in mathematics is that chaos near the border between life (staying within the circle) and death (diverging to infinity) stems from an innocentlooking equation such as (*) and instead of ugly consequences it often produces beautiful fractal patterns. You might remember that Steven Spielberg's Jurassic Park premiered in 1993 includes a mathematician who introduced himself as a "chaotician." A chaotician obviously deals with chaotic behaviors of various dynamical systems including the Fatou equation (*).
It was in fact around the 1970s and the early 80s when several significant events coincidentally took place in mathematics: (a) People saw the computergenerated epochmaking Mandelbrot set for the first time invigorating fractals to a great extent. (b) The new field called "chaos" was born from a computer experiment and generated a great sensation among younger mathematicians for the reason mentioned earlier. (c) Powerful computers found their way to become main tools among theoretical mathematicians who used to pride themselves on using only pencil and paper to discover recondite theories; like in chemistry and physics, experimental investigations became important part of mathematics; (d) Apple Inc., established in a garage, produced and marketed desktop computers for the first time in the world and soon IBM followed suit with then budding Microsoft. Also a small company, Nintendo’s “Pacman” that ran on Apple computers, invaded mathematicians’ offices munching out their office hours. The rest is history.
(B) The Convergence Scheme
The divergence scheme leaves the Mandelbrot set stuck with the canvas color since none of the parameters in the set are attached to escaping sequences. Among those sequences that stay within a finite range, many converge to a point in the set with varying speeds. We can therefore colorcode each of the pixels in the Mandelbrot set according to the speed of convergence of the corresponding sequence. This convergence scheme is based on socalled Cauchy's criterion and given by replacing z_{n} > 2 of the divergence scheme by
z_{n+1}  z_{n} < e
where e is a small number like 10^{10} x (minimum of {xmaxxmin, ymaxymin}). Incorporating the convergence scheme and a greater number of colors into the earlier program may result in a picture like Figure 3. The gold area consists of the pixels attached to the convergent sequences while the green disks are associated with the sequences that eventually become almost periodic of period greater than one. These virtually periodic sequences neither converge to a point nor diverge to infinity, but one can still colorcode the accompanying pixels in a similar fashion and add more colors to the image provided that their period is known.
(C) Fatou Patterns
Since it was published in 1980, the Mandelbrot set became so popular that zillions of digital artists, mathematicians, and computer programmers and hackers have explored around it and shown their fractal images on a variety of objects including web pages, posters, book covers, Tshirts, and coffee mugs. Although the complexity of the M set is boundless and the hidden beauty inexhaustible, it has become quite a challenge to unearth new patterns from the Mandelbrot equation (*) using available computers and software with certain limitations. Consequently, creative work calls for modification of this formula, and there are infinitely many formulas available for this purpose. I call a fractal given by the divergence/convergence schemes applied on a dynamical system of the form
(**)
z_{n+1 }= f_{p}(z_{n})
a Fatou Pattern, where f_{p} is a function of complex numbers that contains a parameter or pixel p. For example, we may find
Fatou Patterns using the logistic equation
z_{n+1 }= f_{p}(z_{n}) = p(1  z_{n}) z_{n }.
An initial value z_{0} is usually chosen from the socalled critical points of the function f_{p} , at which the derivative vanishes, because it provides us with a better chance for a good output, but it is not mandatory from an artistic viewpoint. Just do a lot of experiments because our computers are really good at it. As you can see in the picture Logistic Equation, a noncritical initial point like z_{0} = (0.1,0) gives us certain deforming effect. The picture also shows a substantial difference between the logistic and Mandelbrot equations even though the two equations are known to be very close relatives and conceal similar fractal patterns. From the logistic equation restricted to just real numbers and its frequently unpredictable behavior discovered through computer simulations, the term chaos was born in 1974. The primary application of the logistic equation lies in population dynamics, which explains why the chaotician got into Jurassic Park always looking worried.
(D) Julia Patterns
A fractal, which I call a Julia pattern, is given by fixing the parameter value p in the dynamical system (**) and
iterating it for every choice of the initial value z_{0} (instead of p in plotting Fatou Patterns) in the rectangular region R (which is our canvas). Thus, z_{0} plays the role of a pixel in the canvas. As in the earlier case, a Julia pattern appears more interesting when the parameter value p is chosen from the area of the corresponding Fatou Pattern showing the sign of chaos. A Julia pattern with an appropriate p value contains what appears to be the boundary between two sets, one consisting of every z_{0} which keeps the sequence z_{n} within a fixed circle and the second set consisting of every other z_{0}. The boundary is called a Julia set, which is also related to the idea of chaos and can have a complex topological structure. Gaston Julia, Pierre Fatou, and several other mathematicians, amazingly envisioned fairly good fractal images generated by certain dynamical systems about a hundred years ago using their diligence, intelligence and keen imaginations but not computers, of course, that were not available then.
Gatekeepers in Figure 1 above, for example, is a Julia pattern given by
z_{n+1}= z_{n}^{3} + z_{n} + p,
p = (0.185, 0.00007666),
on the rectangular region with xmin = 1.1, xmax = 1.1, ymin = 0.7, and ymax = 0.7. The gatekeepers are painted by the convergence scheme with various shades of gold and the red background by the divergence scheme; thus, the Julia set in this pattern is the outline (or the boundary) of the gatekeepers. Once you find a value of p yielding a nice Julia pattern, change the value slightly to see if you can improve the picture while retaining the same motif. The corresponding change in the picture sometimes appears gradual and sometimes quite dramatic as you can see in
Julia Dragons in the main gallery.
(E) Newton Patterns
A fractal, which I call a Newton Pattern, is a Julia pattern given by a dynamical system of the form
z_{n+1 }= z_{n} g(z_{n})/g'(z_{n})
where p = (0, 0) is invisible and g is an elementary function with its derivative g'. Although g is a function of a complex variable, the familiar rules of differentiation in the beginning calculus hold for g. In my program, g is almost always a polynomial which allows me to take advantage of the timesaving scheme called Horner's method to efficiently and repeatedly evaluate both g and g' that appear in the dynamical system. Horner’s method is nothing but the “synthetic division” taught in high school algebra, and it should be interesting for you to see how (differently) it is applied in computer programming. Furthermore, as you may have recognized, the dynamical system is, in practice, Newton's RootFinding Algorithm, and as such, each sequence converges to a root of the polynomial equation g(z) = 0 quickly more often than it converges slowly or diverges. For this reason, I usually use the convergence scheme alone and a relatively small M, the maximum number of iterations, such as 500 to process a Newton pattern instead of between 500 and 2,000,000 for Fatou and other Julia patterns. As in a general Julia pattern, an interesting Newton pattern is a fractal that contains at least a part of a Julia set, which ironically causes the unpredictable behavior due to chaos of the otherwise extremely useful rootfinding algorithm.
After you get accustomed to using a polynomial, you may extend it to a rational function. In this event, you just have to include the divergence scheme in the process as well as the convergence scheme because a root of the denominator likely causes the Newton’s method to diverge toward infinity. However, the quotient rule for its derivative still shows that the plotting process is essentially the same as in the case of a polynomial except that it relies a lot more heavily upon Horner’s method.
To appreciate the true beauty of the Newton patterns, you need to know an idea belonging to college math higher than calculus, however. It is callled “Müller's algorithm” which finds all the roots of a polynomial (hence, of a rational function whose numerator is a polynomial) efficiently and automatically unlike occasionally unpredictable Newton’s method. Its purpose is to make the fractals much more colorful; see Newton's Basins of Attraction in the Main Gallery for the application of roots in coloring.
Figure 4 above is a Newton pattern over the unit disk of the complex plane given by the polynomial
g(z) = z^{3}  1
and the “advanced” convergence scheme, which utilizes the three roots to make the number of colors increase threefold. Arthur Cayley, one of the great mathematicians of the 19^{th} century, understood the complex nature of Newton’s algorithm but apparently not to the extent of the hidden Julia set and chaos involved and was frustrated by a geometric problem that turned out to be equivalent to sketching the threecolor Newton Pattern (without shading) by hand on a paper.
(F) Basic 3D Plotting
As we know by now, each pixel color is determined by the number of iterations the corresponding sequence undertakes before escaping from a circle of a prescribed radius or before getting sufficiently near a fixed point in the complex plane. This number, say w, of iterations adds one more dimension to the complex number underlying the pixel that already has two dimensions (x, y). Following elementary threedimensional analytic geometry, therefore, we may plot every point of the form (x  dy, w  dy) in the xwplane using a pixel color determined by w, where d is a nonnegative real number between 0 and 1. If the "depth" number d is nonzero, the above scheme creates an illusion of having an object in the threedimensional space with x and w axes that are horizontal and vertical and yaxis that is perpendicular to the xwplane. Note that the expression dy has nothing to do with calculus. If d happens to be zero, the picture will lose the depth and show the projection (or the sideview) of the object on the xwplane.
Here is a caution about the 3D plotting: When a dynamical system becomes highly chaotic (which is desirable in the earlier 2D plotting), it tends to give too many variations on the altitudes w causing the fractal pattern to look like a reedy swamp. To remedy this problem, we may plot the points of the form (x  cy, h(w)  dy) instead, where c and d are real numbers (that may be negative) and h is a "height" function. For example, if h is the natural logarithm, it may deemphasize the excessive variations of w. Figure 5 shown above is basically given by c = 0, d = 0.7, and the piecewise defined height function
h(w)= w, if w is the number of iterations in the divergence scheme;
h(w)= 2M  w, if w is the number of iterations in the convergence scheme
where M = 500. More examples are shown in the
Fractal Art Main Gallery.
You can extend the basic techniques described above and draw more artistic and/or realistic 3D images by learning various ideas in Multivariable Calculus, Linear Algebra, Numerical Analysis and Topology. The Fractal Art Gallery Annex shows some of the advanced examples.
