2
$\begingroup$

Are the intriguing and lovely Mandelbrot Set hoops and curls the result of floating point computation inaccuracy?

I have written various Mandelbot Set computer implementations, such as a dynamic zoom and playback. Some use fixed point arithmetic, others use the FPU.

I have seen this question which suggests that every bud is a mathematically smooth shape, with smaller buds around.

Are the parades of sea-horse shapes and so on, a side effect of the limitations of computer floating point arithmetic, and not the actual Mandelbrot Set?

$\endgroup$
2
  • $\begingroup$ Weather Vane. I've had exactly the same question. Have you found any more resources since asking this question? (Side note: I came to this question from an information theory angle. Most mathematicians seem to take for granted that all floating point data structures, although always commutative, are not always associative. For floats f1, f2, f3. (f1+f2)+f3 is not always equal to f1 + (f2 + f3). There are other emergent properties that are inherent to the concept of floating point. People using the phrase "rounding error" are usually unaware of the much more serious and unexpected intermediate $\endgroup$
    – BitPass
    Jun 6, 2019 at 16:04
  • $\begingroup$ @BitPass no, I have not explored this any further. In this same question I mentioned that I plan to use some lossless fixed-point arithmetic (on a small area!) but not yet got round to it. Thank you for alluding to what I wanted to ask: does the arithmetic have emergent properties that cause artifacts which are not actually a feature of the M-Set? Particularly when they are observed in the apparently chaotic area where minor effects of the arithmetic may tip the orbit one way or the other. $\endgroup$ Jun 6, 2019 at 18:09

3 Answers 3

4
$\begingroup$

No. The Mandelbrot set is an example of a complex dynamical system which has chaotic behaviour, i.e. the long-term behaviour of the orbit of a point can be very sensitive to the initial conditions. This sensitivity to initial conditions means that two points that are close together in the complex plane may follow radically different trajectories under iteration. This ultimately leads to the fractal nature of the (boundary of) the Mandelbrot set. This is not the result of numerical error, but a real mathematical phenomenon.

However, I don't think that the Mandelbrot set is a very good first example of this phenomenon, as there are several layers of complexity that we might want to discuss before getting there. Instead, let me try to convince you by considering Newton's method for finding the roots of a particular polynomial.

Newton in a Nutshell: Let $f$ be a polynomial in $\mathbb{C}$. Fix some $x_0\in\mathbb{C}$, and define $$z_{n+1} := f'(z_n)(z-z_n) + f(z_n). $$ For most values of $z_0$, the limit $z_{\infty} := \lim_{n\to\infty} z_n$ exists. Moreover, when $z_{\infty}$ exists, we have $f(z_{\infty}) = 0$.

Newton's method is a way of numerically approximating the roots of sufficiently smooth functions (though I'm restricting our attention to only polynomials here). For an example of how the method works, I've put together a little Desmos demonstration for finding a root of the polynomial $f(z) = z(z+1)(z-1)$. By dragging the "Initial Guess" around, you can see how the first couple of iterations begin to approximate roots.

enter image description here

However, note that there are a couple of caveats to this:

  1. For most values of $z_0$, the limit exists. However, there are circumstances under which the limit does not exist (for example, if $f'(z_n) = 0$ for some $n$). So one reasonable first question is "For which values of $z_0$ does the limit exist?" In playing with the Desmos demo, you might think about what happens when you choose initial guesses that are near $\pm0.5$.
  2. While $z_{\infty}$ is a zero of $f$, it is not always possible to tell which zero it will be. In our example of $z \mapsto z(z+1)(z-1)$, we know that there are three zeros ($z \in \{0, \pm 1\}$) but, given an initial guess we don't know which zero will be the limit point (assuming that the limit exists). Hence it is also reasonable to ask "Given an initial point $z_0$, what is the limit point $z_{\infty}$?"

One way to get at this is to attempt to graph the iterations. To do this, start with the complex plane:

enter image description here

Here, points in the complex plane are assigned a color. Black points are near zero, red points are along the positive real axis, cyan points are along the negative real axis, and so on. To "graph" a function on the complex plane, pick a point, figure out where the function sends that point, and color the original point with the corresponding color from the limit point. For example, if we apply one iteration of Newton's method to the complex plane (for the function $f(z) = z(z+1)(z-1)$), we obtain

enter image description here

Note that points near zero remain near zero, and that numbers of large magnitude don't seem to move very far, but that something interesting is happening near the origin. After 100 more iterations, we get this picture:

enter image description here

There are basically three colors in this picture: black (corresponding to the point $0$), red (corresponding to the point $1$), and cyan (corresponding to the point $-1$). This picture shows us where a given initial value $z_0$ is sent by Newton's method. Nearly every point in the complex plane is sent to one of the three roots, but observe that there is some chaotic behaviour near the boundary of each basin of attraction (the red region is the basin of attraction for the root $z=1$, as every point in the red region is "attracted to" this root by Newton't method)---there a little blobs of different colors running along these boundaries.

If you played with the Desmos demo, you might have noticed that if you pick an initial guess near $\pm0.5$, the subsequent guesses "bounce around" a lot before they start to settle in towards one of the roots. This is exactly the chaotic behaviour that leads to the little bulbs in the last image above. This detail is the result of a real phenomenon (which you can readily see for yourself by fiddling with the demonstration), and is not due to numerical errors introduced by the computer.

$\endgroup$
2
  • $\begingroup$ Thank you for the thought provoking answer. I understand that the discs arranged around discs in the Mandelbrot set (and the infinitely thin thread connections) are real, not a side effect of computation. The more accurate the computations, and the greater the iteratioon depth, the more the image tends to be arrays of smooth discs. I still wonder if there are two effects at work though. The interest isn't the boundary of the M-set itself, but close to it, where the function has escaped. $\endgroup$ Apr 12, 2018 at 4:26
  • $\begingroup$ You probably meant to define that $z_{n+1}$ is the root of $z\mapsto f(z_n)+f'(z_n)(z-z_n)$. $\endgroup$ May 13, 2022 at 12:56
3
$\begingroup$

I'm not absolutely sure, but I think the shadowing lemma applies to the Mandelbrot set, meaning that near any rounded-off floating point trajectory there is a true trajectory that started nearby, i.e. the backward error is small:

The main causes of error are round-off error and truncation error. The forward error of the algorithm is the difference between the result and the solution; in this case, Δy = y* − y. The backward error is the smallest Δx such that f(x + Δx) = y*; in other words, the backward error tells us what problem the algorithm actually solved.

(quote from https://en.wikipedia.org/wiki/Numerical_stability )

If this is the case, it should be possible to find the floating point precision required to make the backward error as small as desired (e.g. a fraction of pixel spacing), or at least check whether your given precision was enough to meet your backward error target, using derivatives. Checking the rounding errors of the derivatives themselves adds some complication, but perhaps not insurmountable.

See also:

$\endgroup$
2
  • $\begingroup$ Thank you for this answer. I understand that neighbouring points may follow a similar trajectory, but as one zooms in (to the chaotic region) points in between can follow an entirely different path. I don't think my idea can be proved empirically. Even if a scale is chosen such that each pixel's coordinates can be exactly represented in floating point arithmetic, the precision required at each iteration doubles and becomes impossible in practical terms. $\endgroup$ Apr 12, 2018 at 4:26
  • $\begingroup$ Sure, to obtain a proper image one would need a low pass filter to bandlimit before sampling. $\endgroup$
    – Claude
    Apr 12, 2018 at 15:21
1
$\begingroup$

No, a properly written program will make sure the display is not driven by floating point errors. As the size of the numbers in the set never exceeds $2$ you can do all the computations in fixed point if you want. It is usual not to be limited to the word size of your computer but to use some extended precision arithmetic implementation.

One simple way to verify this is to look at the figures from many different programs. If you take the coordinates of a a particular figure and type it into different programs you get the same picture, despite the fact that the calculation techniques are different. I have seen programs that did run out of precision. The pictures do not look like what you are used to in Mandelbrots at all.

$\endgroup$
3
  • $\begingroup$ You have not understood my question. The typical computer implementation is not perfect maths. Every error in a floating point implementation is carried forward to the next iteration - maybe thousands of iterations. Is that imperfection shown in the cascading whorles etc? $\endgroup$ Apr 10, 2018 at 22:25
  • $\begingroup$ I did understand it. The point is that by using enough precision you can prevent this being a problem. The good programs do this. You are not limited to the default 32 or 64 bits of precision. The fact that the spirals are nice logarithmic spirals also argues for the precision being good enough. Logarithmic spirals is what one would expect. $\endgroup$ Apr 10, 2018 at 22:28
  • $\begingroup$ Nope, there is never enough precision in iterative computer algorithims. I need a better answer, but thank you. I tried to convey in my question that I am not a novice in implementing the M-Set. $\endgroup$ Apr 10, 2018 at 22:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .