Drawing Fractals with Interval Arithmetic - Part 2

Dr Rupert Rawnsley. June 2005.

Acknowledgments

I would like to thank Dr John Hedley for reading and commenting on this work throughout its evolution, Dr Luiz de Figueiredo for taking time to comment on the previous paper, and Dr Bill Walster for his encouragement and enthusiasm.

Introduction

The application of interval arithmetic to the task of drawing the Mandelbrot set was introduced in a previous paper. The motivation for this work was not principally the production of fractal images (although it's always nice to have some eye-candy), but to explore the application of interval arithmetic to the simulation of a simple chaotic systems.

It was concluded that a moderate amount of further work could round off some of the rough-edges in the initial approach. The algorithm used by Joãn Batista Oliveira and Luiz Henrique de Figueiredo (described in their presentation "Images of Julia sets that you can trust") to produce images from the, very similar, Julia set was adapted to the Mandelbrot set. Their approach was innovative because it allowed the fractal to be characterized by strict, mathematically guaranteed, set membership. This scheme has been reproduced and more thoroughly described in this paper and extended to the Mandelbrot set.

Dr de Figueiredo and Dr Walster have been very generous with their comments about the previous paper, and it has not been possible to do justice to the wide range of issues raised. The relevant correspondence is available on request, but a publishable version would be a whole paper in itself, and one that I do not feel qualified to edit.

Implementation

A simple application was developed for this paper that builds on the one from the original paper, again in Microsoft C#.NET. The new application supports Mandelbrot and Julia fractals using either single-point or interval arithmetic. The binary files (for Windows 2000 and above) are available here, and the source code is also available for reference purposes. This tool requires that you have the .NET framework installed on your machine (see http://support.microsoft.com/?kbid=316091).

Mandelbrot Algorithm

The single point version of the algorithm is standard and does not warrant explanation.

For the interval algorithm, the Mandelbrot equation is applied iteratively to the region of the complex plane, C, under investigation:

Z_n+1 = Z_n² + C

Where Z₀ is the interval [0, 0] + [0, 0]i.

The initial value for C is the box describing the whole region of the complex plane as follows:

C = [x_min, x_max] + [y_min, y_max]i

Where x is the real component, and y the imaginary component, as shown in the following figure:

The horizontal and vertical midpoints (x_mid and y_mid) are bisected such that the midpoint falls on the nearest pixel boundary:

The four quarters are then tested for membership, and subdivided in the same way if still indeterminate. This continues until the size of the region is exactly one pixel, if this pixels membership still cannot be determined then it is marked as "Indeterminate" (grey).

The algorithm used to determine Mandelbrot set membership for every region, C, is as follows:

1. Seed Z with [0, 0] + [0, 0]i.

2. Seed set P as empty.

3. Apply Z = Z² + C.

4. If Z is inside any of the complex intervals in P then label C as "definitely in" and terminate.

5. If Z is completely outside the magnitude-2 circle then label C as "definitely out" and terminate.

6. If Z completely contains the magnitude-2 circle then label C as "indeterminate" and terminate.

7. Add Z to P.

8. Goto 3.

The following diagrams illustrate the three termination conditions of the algorithm, corresponding to the three possible states of set membership:

One interesting difference between the interval algorithm and the single-point algorithm is that there is no need for an iteration limit "bail-out". The time complexity of the algorithm has not been derived, but in practice it seems to terminate in several thousand iterations. This upper limit tends to increase as the zoom level increases, which correlates with experience of the single-point algorithm, where greater iteration limits are required to resolve “deeper” features.

Julia Algorithm

The algorithm used for the Julia set was identical to that for the Mandelbrot except that C is a constant and Z is seeded with the complex interval bounding the region under investigation.

The constant C characterizes the particular Julia set under investigation (as in the single point algorithm), but the interval components of C are artificially widened by the smallest possible increment to eliminate the possibility of introducing the sort of sampling noise intrinsic in the single-point approach. In limited experiments, this modification made no discernable difference to the output.

Results

A small number of results are presented here, but the reader is encouraged to download the tool and explore the fractals for themselves.

Mandelbrot

The following two figures are the single point Mandelbrot set (left) and the interval Mandelbrot set (right). Clearly the two images differ significantly, and the same features as were seen in the first paper are present, but the new “definitely out” boundary (white/grey interface) is clearly present.

Pseudo-detail can be seen if the traditional approach of coloring by termination iteration is applied. In the following figures the termination iteration controls the saturation of the color and the white and grey are replace with blue and red respectively:

Julia

Here is the single and interval versions of the San Marco Julia set (-1 + 0i)

The following is a Julia (0.293333333333333 + -0.28i) that exhibits an interesting Moiré pattern:

Conclusion

Clearly the conclusions of the previous paper still stand: that single point and interval arithmetic approaches to fractal generation produce considerably different results. Furthermore, the interval algorithm described in this paper offers guarantees about set membership not offered by the previous implementation or the single point approach.

It is quite likely that a the size of the indeterminate regions can be reduced by more sophisticated algorithms or greater precision, and any researcher looking to apply interval arithmetic to chaotic systems may find this a useful starting point or sounding board for new ideas.

We must also entertain the possibility that no significant reduction can be made in the areas of indeterminacy, and it might be that chaotic systems and interval arithmetic are not comfortable bedfellows (even for such a simple system as the Mandelbrot and Julia equations). However, this pessimism must be tempered by two considerations:

1. This is a toy problem, and it is not possible to say if a high level of indeterminacy would actually be a disadvantage in a real world application. Perhaps the “interesting” solutions always fall into definitive categories, or enough latitude exists to discard indeterminate solutions in favor of determinate ones.

2. The single point approach intrinsically has these problems, they are just not explicit. This is a common caveat when criticizing many interval approaches.