Mandelbrot set

From Example Problems
Jump to navigation Jump to search
File:Mandelset hires.png
A rendering of the Mandelbrot set: black points represent the stable points under the iterative map

In mathematics, the Mandelbrot set is a fractal that is defined as the set of points c in the complex plane for which the iteratively defined sequence

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z_0 = 0\,}
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z_{n+1} = {z_n}^2 + c}

does not tend to infinity.

The sequence is thus expanded mathematically as follows for each point c in the complex plane:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c=x+iy \,}
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z_0=0 \,}
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{matrix}z_1&=&z_0^2+c \\ \ &=& x+iy\end{matrix} \,}
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{matrix}z_2&=&z_1^2+c \\ \ &=&(x + iy)^2+x+iy \\ \ &=&x^2+2ixy-y^2+x+iy \\ \ &=&x^2-y^2+x+(2xy+y)i\end{matrix} \,}
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z_3=z_2^2+c=\dots \,}

and so on.

If we reformulate this in terms of the real and imaginary parts (x and y coordinates of the complex plane), looking at each iteration n, replacing:

  • zn with the point xn plus yn times i. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (z_n:=x_n+y_ni)}
  • c with the point a plus b times i. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (c:=a+bi)}

then we get

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{n+1} = {x_n}^2 - {y_n}^2 + a \,}

and

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_{n+1} = 2{x_n} {y_n} + b \,}

The Mandelbrot set can be divided into an infinite set of black figures: the largest figure in the center is a cardioid. There is a (countable) infinity of near-circles (the only one to be actually an exact circle being the largest, immediately on the left of the cardioid) which are in direct (tangential) contact with the cardioid, but they vary in size, tending asymptotically to zero diameter. Then each of these circles has in turn its own (countable) infinite set of smaller circles which branch out from it, and this set of surrounding circles also tends asymptotically in size to zero. The branching out process can be repeated indefinitely, producing a fractal. Note that these branching processes do not exhaust the Mandelbrot set: further upwards in the tendrils, some new cardioids appear, not glued to lower level "circles". The largest of these, and the most easily visible from a view of the entire set, is along the "spike" which follows the negative real axis out, roughly from real values of -1.78 to -1.75.

History

The Mandelbrot set was first defined in 1905 by Pierre Fatou, a French mathematician working in the field of complex analytic dynamics. Fatou studied recursive processes like

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z \mapsto z^2 + c\,}

Starting with some point Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z_0} on the complex plane, successive points may be generated by repeatedly applying this formula. The sequence of points thus obtained is called the orbit of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z_0} under the transformation

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z \mapsto z^2 + c\,}

Fatou realised that the orbit of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z_0 = 0} under this transformation would provide some insight into the behaviour of such systems. There are an infinite number of such functions - one for each value of c. Fatou did not have access to a computer capable of plotting the orbits of all these functions, but attempted to do so by hand. He proved that once a point moved to a distance greater than 2 from the origin, then the orbit would escape to infinity.

Fatou never saw the image of what we now call the Mandelbrot set as we do because the number of calculations required to generate this is far more than could be calculated by hand. Professor Benoît Mandelbrot was the first person to use a computer to plot the set.

Fractals were popularised by Mandelbrot in 1975 in his book Les Objets Fractals: Forme, Hasard et Dimension. In this book, Mandelbrot used the term fractal to describe a number of mathematical phenomena that seemed to exhibit chaotic or surprising behaviour. All of these phenomena involved the definition of some curve or set through the use of some recursive functions or algorithms. The Mandelbrot set is one such phenomenon that is named after its discoverer.

Relationship with Julia sets

File:Embedded-julia.jpg
An "embedded Julia set"

The Mandelbrot set was created by Benoît Mandelbrot as an index to the Julia sets: each point in the complex plane corresponds to a different Julia set. The points within the Mandelbrot set correspond precisely to the connected Julia sets, and the points outside correspond to disconnected ones.

Intuitively, the "interesting" Julia sets correspond to points near the boundary of the Mandelbrot set; those far inside tend to be simple geometric shapes, while those well outside look like dust surrounded by blobs of color. Some programs, such as Fractint, let the user choose a point, and jump to the corresponding Julia set, making it easy to find Julia sets that the user is likely to enjoy.

The Mandelbrot set also contains structures that strongly resemble Julia sets; indeed, for any value c, the region of the Mandelbrot set near c resembles the center of the Julia set with parameter c.

Mathematics

Douady and Hubbard have shown that the Mandelbrot set is connected, and even simply connected. It is conjectured but unproven to be path connected. The Hausdorff dimension of its boundary equals 2 by a result of Shishikura, therefore it qualifies as a fractal under Mandelbrot's definition. The Mandelbrot set is compact, and thus measurable; its area was estimated as 1.5065918 by Hill [1]. In the Blum-Shub-Smale model of real computation, the Mandelbrot set is undecidable, while its complement is computably enumerable.

Plotting the set

File:Mandelbrotset.png
Sample generated image with colouring given by the rate of divergence to infinity, the brighter the points the slower the divergence
File:Fractal-zoom-1-03-Mandelbrot Buzzsaw.png
Still image of a movie of increasing magnification on 0.001643721971153 + 0.822467633298876i

It can be shown that once the absolute value of zn is larger than 2 (in cartesian form, when xn2 + yn2 > 22) the sequence will tend to infinity, and c is therefore outside the Mandelbrot set. This value, known as the bail-out value, allows the calculation to be terminated for points outside the Mandelbrot set. For points inside the Mandelbrot set, i.e. values of c for which zn doesn't tend to infinity, the calculation never comes to such an end, so it must be terminated after some number of iterations determined by the program. This results in the displayed image being only an approximation to the true set. Mandelbrot hobbyists quickly learn to recognize the "blobby" images caused by a program mistakenly placing points in the set, and will then up the iteration count (at the expense of slowing down the calculation of every point actually in the set).

Adding color

Mathematically speaking, the pictures of the Mandelbrot set and Julia sets are "black and white". Either a point is in the set or it is not. Most computer-generated graphs are drawn in color. Under the most common rendering method, for the points that diverge to infinity, and are therefore not in the set, the color reflects the number of iterations it takes to reach a certain distance from the origin. This creates concentric shapes, each a better approximation to the Mandelbrot set than the last. One possible scheme is that points that diverge quickly are drawn in black; then you have brighter colors for the middle; then you have white for the points in the set, and near-white for the points that diverge very slowly.

In order to determine if the point, c, is going to be in the Mandelbrot set (traditionally coloured black) or outside the set (coloured according to the escape speed), the distance of the zn must be calculated at each iteration in the sequence:

If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z_n = x + iy \ } , then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \|z_n\| = \sqrt{x^2 + y^2}} . Note that one of the many possible optimisations for calculating mandelbrots can be applied here. Rather than testing to see if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sqrt{x^2 + y^2} > 2} , we can simply test to see if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^2 + y^2 > 4 \ } —thus saving the square root operation.

So, if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \|z_n\|^2 < 4} then colour the point black, otherwise colour it according to the value of n. Using the number of iterations required to determine that the point has escaped is the easiest and most common way of recording the "speed" of escape. This number can be directly mapped to a colour via a lookup table or palette, or by use of some suitable algorithm.

So far, we have worked out how to tell if the point is outside the set—it moves more than a distance of 2 away from the origin. How do we tell it is inside the set? There are lots of strategies for this—this is not so simple. If it were, there would not be so many different algorithms out there for calculating mandelbrots. This is the essence of the problem. Clearly most points will not actually get to zero in a reasonable number of iterations. The simplest algorithm is to simply limit the number of iterations and if you have not gone outside the boundary by the time you have done your last iteration, then you assume the point is in the set.

Indeed, points nearer the set take longer to escape. This is why plotting slows down near the dark region—because more terms in the expansion are having to be calculated to determine the escape speed. When not near the set, one can "get away with" a lower maximum iteration count. The images below, of the same location, are created with iteration limits of 32, 64, 128, 256, 512, 1024, 2048 and 1000000, respectively. Note that there are diminishing returns in upping the iteration count past a point; these are also good examples of the "blobby" images one gets with a too-low iteration count. These images are centered at -1.7490110509, -0.0004525. The image is roughly 0.000417 of a unit wide, and located about halfway down the "valley" at the +x end of the largest mini-set.

Optimization

One way to improve calculations is to find out beforehand whether the given point lies within the cardioid or in the large circle to the left of it. The cardioid is characterized by periodicity = 1; this allows its shape to be determined. The large circle, which has periodicity = 2, can also be determined by elementary methods.

The cardioid's polar equation turns out to be

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho_c = {1 \over 2} - {1 \over 2} \cos \theta }

but with the center of polar coordinates located at (1/4,0)—the cardioid's cusp—instead of at the origin. Given point (x,y), calculate

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho = \sqrt{\left( x - {1 \over 4} \right)^2 + y^2} }

If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \le \rho -2 \rho ^2 + {1 \over 4} } then point (x,y) is in the cardioid (color it black), and the usual calculations can be skipped; this can be easily proved from the formula for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho_c } . It is also easy to check if a point is in the large circle to the left of the cardioid; its center is at Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x = -1 } and its radius is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {1 \over 4} } .

To prevent having to do huge numbers of iterations for other points in the set, one can do "periodicity checking"—which means check if a point reached in iterating a pixel has been reached before. If so, the pixel cannot diverge, and must be in the set.

Error creating thumbnail: Unable to save thumbnail to destination
A portion of the Mandelbrot set centred at (0.282, -0.01)

Art and the Mandelbrot set

Some people have a hobby of searching the Mandelbrot set for interesting pictures. They have a collection of pictures, along with the coordinates for generating that picture. For example, the image to the right is a closeup centred at coordinates (0.282, -0.01). Below are more examples of Mandelbrot set regions:

Cool Mandelbrot Hot Mandelbrot

There are many free fractal-generating programs available, such as those by Stephen Ferguson (Sterling Fractal and the Tierazon series) and many people write such programs themselves for the highest level of control over their pictures. Below is a min-cardioid, connected by filaments (too thin to be seen) to the main set (and other cardioids, some of which are actually in this image but too small to be seen).

File:RufusCont.jpg
Contemplating the Mandelbrot set

Mini-set with filaments leading elsewhere

Generalizations

When people speak of the Mandelbrot set, they usually are referring to the set described above. Any function that maps to and from the complex number plane has a Mandelbrot set, which characterizes whether or not the Julia set corresponding to that function is connected.

Example:

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_c(z) = z^3 + c} .

For each value of c, we draw the Julia set Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle J_c} of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_c(z)} , and determine if it is connected or not. If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle J_c} is connected, then c is in the Mandelbrot set of {Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_c} }, otherwise c is not in the Mandelbrot set.

This can also be generalized to Julia sets parameterized by more than two real numbers. For example, a collection of Julia sets parametrized by three real numbers will have a three dimensional Mandelbrot set. Of course, only the 2-dimensional case will have an easily viewed picture.

Mandelbrot set in song

The Australian band GangGajang has a song Time (and the Mandelbrot set) where the term Mandelbrot set is used liberally in the lyrics.

The American singer Jonathan Coulton has a song titled Mandelbrot Set about the history of the Mandelbrot set, and of Benoit Mandelbrot himself.

The Blue Man Group's first album Audio features tracks titled "Mandelgroove", "Opening Mandelbrot", and "Klein Mandelbrot". The album was nominated for a Grammy in 2000.

External links

Template:Wikisource

cs:Mandelbrotova množina de:Mandelbrot-Menge es:Conjunto de Mandelbrot fr:Ensemble de Mandelbrot is:Mandelbrot mengið it:Insieme di Mandelbrot ja:マンデルブロ集合 ko:만델브로트 집합 pl:Zbiór Mandelbrota pt:Conjunto de Mandelbrot ru:Множество Мандельброта sv:Mandelbrotmängden