How to draw a fractal from $z \mapsto z^2 + c$ explained for a mere mortal?

Question

I am interested in:

1) Understanding in detail how fractals are draw.

2) Coding a computer program to draw a simple fractal.

Can someone with good explaining skills take care of 1) for me? I don't think this link does a good job. I step-by-step example would be fantastic or a link/video with a good step-by-step explanation. THX!

---

I know complex numbers and the complex plane. My understanding is that you choose a complex number to begin with and keep feeding back the result into the equation (i.e. iterating). Now my question: how from the results do you draw something? You just put a black dot for each result in the complex plane?

Answer 1

The answer is yes, you just put a little black point if the result says it is in the Mandelbrot set, and no point if it doesn't.

But the fact is, you would have to iterate through an infinite amount of points to do that! Instead, something like the following is usually done. Some psuedo-code:

$$ \color{blue}{\text{for }x_{\text{min}} \to x, x \neq x_{\text{max}}, x+\Delta \to x}: $$ $$ \color{green}{\text{for }y_{\text{min}} \to y, y \neq y_{\text{max}}, y+\Delta \to y}: $$ $$ \color{red}{\text{If Number In Set}(x+yi)}:$$ $$ \color{red}{\text{Color}(x+yi)} $$ $$ \color{green}{\text{Repeat}}$$ $$ \color{blue}{\text{Repeat}}$$

Where $\Delta$ is a small number, but not too small. Depending on the size of your picture, usually somewhere around $\Delta = 0.05$ is good.

Answer 2

chrisapotek wrote, "... I am interested in the mathematical rationale behind the image..."

The Julia image for c=0 is pretty simple, and forms the mathematical basis for understanding other Julia sets. Iterating $z\gets z^2+0$, all the points inside the unit circle go to zero, and all the points outside the unit circle go to infinity. On the unit circle itself, each iteration doubles the angle $\theta\gets 2\theta$ since $(\exp(2\pi i \theta))^2=\exp(2\times 2\pi i \theta)$. The unit circle is the boundary, separating the points that go to infinity, the Fatou set, from the points that go to zero, the Julia set.

There is a Fatou set of points that go to infinity for the Julia/Fatou set for iterating $z\gets z^2+c$ with other values of c as well. For almost all of these cases, the boundary is a fractal, unless the z=0 point goes to infinity, in which case it is a cantor dust. It turns out that for other values of "c", the Bottcher equation can put the Fatou set into 1 to 1 correspondence with the Fatou set for z^2, and the fractal boundary corresponds to the boundary of the analytic Bottcher function. The set of points for which the Bottcher equation is defined is mathematically equivalent to the set of points go to infinity when you iterate z=z^2+c. So this is the mathematical basis for just iterating and seeing which points go to infinity, for coloring Julia sets. Similar much more complicated arguments apply to the Mandelbrot set.

Milnor's book, Dynamics in One Complex Variable, is probably the best reference.

Answer 3

Generally speaking it depends on the fractal. Not all fractals use complex numbers. There's a lot of different kinds of fractals, and even for the same fractal there can be completely different kinds of algorithms. Example: Sierpinski Triangle via L-systems and Sierpinski Triangle via chaos game.

---

The criterion for a point to be in the Mandelbrot set is that it doesn't diverge off into infinity after an infinite number of iterations. That's of course impossible (strictly speaking) to do on a computer, but for a practical algorithm if you run at least a couple dozen iterations you can make a very good guess about whether the point is or isn't inside the set.

Given a complex number $z$, if the distance from the origin (which you could call the absolute value of $z$) is $<$ 2, then that number may or may not go off into infinity. But if the distance from the origin is $\ge$ 2, then that number will definitely go off into infinity (because after this the distance only increases).

So basically what you do is, for a given point, iterate some number of times, say 20, and if at any iteration the distance of the complex number from the origin is $\ge$ 2, then just stop there and go to the next point. But if you make it through those 20 iterations and the point is still within a radius of 2, then go ahead and draw that point.

---

Remember that to calculate the distance from the origin, you can use the Pythagorean theorem. If $z = x + i y$, then a point is, for the time being, safe if:

$$\sqrt {x^2 + y^2} < 2$$

For the purposes of writing the algorithm, notice that the following is equivalent:

$$x^2 + y^2 < 4$$

Which is why the Wikipedia algorithm @RahulNarain linked to has this:

x*x + y*y < 2*2

---

You can get fancier if, instead of just drawing a point or not drawing a point, you vary the color of all points (even ones that you wouldn't normally draw as part of the set) depending on how fast they diverge past a radius of 2. So if a point is in the set, good, but if it's not in the set, then make the color redder or darker or whatever depending on how many iterations it takes to go past a radius of 2. This is what the Wikipedia algorithm does and it's one of the schemes used to color the various Mandelbrot set pictures you've seen.

Answer 4

The fractal you're talking about is the Julia set for the polynomial $z \mapsto z^2 +c$. If $f:\Bbb{C} \rightarrow \Bbb{C}$ is this polynomial, the set $K(f) \subset \Bbb{C}$ is definied as follows: $$K(F) = \{x |\lim_{n\to\infty} |f^n(x)| < \infty \}$$

where $f^n$ denotes the $n$th composition of $f$, that is $f \circ f \circ \dots \circ f(x)\,\, n $ times.

The Julia set, $J(f)$ which has far more exciting properties and is a little easier to calculate is simply $\partial K(f)$ the boundary of $K(x)$. The 'why' of this set forming a fractal for $c \neq 0$ is quite challenging and I can't go into that here. I will however refer you to a number of excellent resources that will help you. The book that requires pretty light prerequisites and is spectacular in regards to the geometry of fractals is this one by Kenneth Falconer. The best monograph on the subject of complex dynamics is that of Milnor, here.

But I digress now back to the subject of how to draw the Julia set for $z \mapsto z^2 +c$. The first method I will describe is the most straightforward. Idiomatically it goes like: for each pixel iterate $f$ and if it goes outise of the circle with radius 2, then color it some color depending on the number of iterations it takes to escape this circle, otherwise color it black. Here is my mathematica code for this:

f[z_] := z^2 - 0.53 - 0.53*I;
bailOut = 50;
test[z_] := Abs[z] <= 2;
JuliaCount[z0_] := Length[NestWhileList[f, N[z0], test, 1, bailOut]];
DensityPlot[JuliaCount[x + I*y], {x, -1.6, 1.6}, {y, -1.2, 1.2}, 
 AspectRatio -> Automatic, Mesh -> None, PlotPoints -> 1000, 
 ColorFunction -> (If[# == 1, RGBColor[0, 0, 0], Hue[#]] &)]

which produces the following image, albeit very slowly:

If we want to make this faster, there are some interesting properties of Julia sets for polynomials that we can use in order to draw them with more reasonable computation. I'm going to list some watered down versions of the facts we'll need here and reference you to the Falconer book if you want more details and information.

$$1.\quad J(f^n) = J(f) \text{ and } J(f) \text{ is a repelling fixed set for } f\\ 2.\quad \text{Periodic orbits of } f \text{ are dense in} J(f)\\ 3.\quad J(f) = \partial E(f), \text{ the points that escape to infinity}\\ 4. \quad J(f) \text{ is an attracting stable set for } f^{-1} $$

Using these facts and basic properties of $f$, it should be easy to see that if we apply $f^{-1} : z \mapsto \sqrt{z-c} $ to some point outside of the circle of radius 2, we will eventually get a point arbitrarily close to $J(f)$ and successive iteration will 'likely' produce many points far within one pixel of the of the set. So if we pick 10 points at random outside of the circle with radius 2, and perform the following idiomatic algorithm on them, we should get a nice drawing of the Julia set:

Perform $f^{-100}$ on $s_0$, the first starting point. Call this point $a_0$.

Color this point, as well as $f^{-1}(a_0) = a_1$, $f^{-1}(a_1) = a_2$ and so on for some number of iterations.

Repeat for other $s_i$ on the same drawing to get a picture of $J(f)$.

This should produce a very similar picture, with the major difference that it won't be colored and therefore probably won't be as pretty.