Visualizing the Mandelbrot set with JavaScript

Fractals and the Mandelbrot set

Even though mathematical structures that are now called fractals were first analysed in the 19th century, the study of self-similar structures got a significant boost when computers able to visualize them started to appear in the 1970s. In fact, the term fractal was coined in 1975 by the late Benoit Mandelbrot to describe structures whose parts are similar to the whole.

The Mandelbrot set is a particular fractal set defined as:

\displaystyle M = \{ c \in \mathbb{C}: \lim_{n\to\infty} P_c^n(0) \neq \infty \},

where P_c^n(z) describes the polynomial resulting of iterating n times the parameterized quadratic polynomial P_c(z):

\displaystyle P_c(z) = z^2 + c.

More about the Mandelbrot set

It is said that the limit of a complex sequence z_n is infinite if for any positive number M there is an element of the sequence z_N such that its module and the modules of all succeeding sequence elements are greater than M. In formal notation:

\displaystyle \lim_{n\to\infty} z_n = \infty \iff \forall M > 0\,\exists N > 0\,\forall n \geq N: |z_n| \geq N.

All the points of the complex plane that have a modulus greater than 2 are outside the set. To show that, let’s take a point c_0 whose module is strictly greater than 2:

\displaystyle |c_0| > 2.

To avoid cluttering the inequalities, let’s make two definitions:

\displaystyle a_n = |P_{c_0}^n(0)| and

\displaystyle k = |c_0|.

Then the statement that all points with modulus greater than two are outside the Mandelbrot set is equivalent to

\displaystyle \lim_{n \to \infty} a_n = \infty.

It’s clear from the definition that a_n is non-negative. Let’s analyse carefully the relationship between a term and the previous one:

\displaystyle a_{n+2} = |P_{c_0}^{n+2}(0)| = \left|\left(P_{c_0}^{n+1}(0)\right)^2+c_0\right|

\displaystyle a_{n+2} \geq \left|\left|\left(P_{c_0}^{n+1}(0)\right)^2\right|-|c_0|\right|

\displaystyle a_{n+2} \geq \left|\left|P_{c_0}^{n+1}(0)\right|^2-k\right|

\displaystyle a_{n+2} \geq \left|a_{n+1}^2-k\right|.

We can now inductively explore the hypothesis a_{n+2} \geq (1 + \epsilon) a_{n+1}, with \epsilon = k - 2.

Checking the base case:

\displaystyle a_2 \geq |a_1^2 - k| = |k^2 - k| = |(k-1)k| = (k-1)k = (1+\epsilon)k = (1+\epsilon)a_1

Applying the strong inductive hypothesis to a_{n+1} we get:

\displaystyle a_{n+1} \geq (1 + \epsilon)a_n \geq \ldots \geq (1 + \epsilon)^n a_1 = (1 + \epsilon)^n k

Using this result in the previous inequality:

\displaystyle a_{n+2} \geq a_{n+1}^2-k \quad (a_{n+1}^2 > a_{n+1} > k)

\displaystyle a_{n+2} > a_{n+1}^2-a_{n+1} \quad (a_{n+1} > k)

\displaystyle a_{n+2} > a_{n+1}(a_{n+1} - 1)

\displaystyle a_{n+2} > a_{n+1}(k - 1) \quad (a_{n+1} > k)

\displaystyle a_{n+2} > (1 + \epsilon) a_{n+1} \quad (1 + \epsilon = k - 1)

This implies that a_n will diverge at least geometrically, with ratio 1+ \epsilon. Then any point c whose modulus is greater than 2 will be outside the set.

It can be seen by a slight extension of this argument that, if there is some n such that |P_c^n(0)| is greater than 2, c will be outside the Mandelbrot set too.

Plotting the Mandelbrot set

The simplest way to plot a Mandelbrot set is to iterate the quadratic polynomial P_c(z) over the points c that are associated with an image in the normal way (via some choice of origin and scale factor). If the iterated point reaches a modulus greater than 2 we know that its module will diverge and that it is outside the set. There isn’t any simple test to know if a point is inside the set, but we can choose a fixed number of iterations or to stop the process when no new point outside the set is detected.

Any point known to be outside the set (reached a modulus greater than 2 when iterated) can be colored white, using black to color the points of the set:

A Mandelbrot set plotted using black for the points inside the set and white for those outside the set. (Click to see a live version.)

We can make prettier visualizations if we use some measure of the “difficulty of divergence” for each point. One natural measure for this quantity is the number of iterations required to reach a given modulus. Combining this number of iterations with a function translating the potentially unbounded number of iterations to a color in the range black – white, we get:

Mandelbrot set in gray scale. The gray level of the points outside the set are related to the number of iterations required to reach a given modulus. (Click to see a live version.)

This visualization is nicer, and shows more clearly the existence of filament-like structures (in fact, the set is connected, but I don’t know how to prove that… 😀 ). But we can do better by interpolating the iteration number in a continuous way, giving us a less discrete measure of the “difficulty of divergence”. If we use the algorithm described by Linas Vepstas,

\mu = n + 1 - \frac{1}{\log 2}\log \log P_c^n(0),

being \mu the “continuous” iteration count, the we get this picture:

A representation of the Mandelbrot set using the "continuous iteration count" to colorize the exterior. (Click to see a live version.)

The source code of the visualization software can be seen in the SVN repository of this blog and it can be used to check the self similarity of the fractal (left click zooms in, right click zooms out):

A "copy" of the Mandelbrot set in a filament. Zoom out in the live version to see its location.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s