Rounding errors in images of Julia sets

Question

One typically computes Julia sets by iterating a complex function, such as a polynomial or rational function.

How do rounding errors affect the results?

I'm looking for references on this issue, especially but not exclusively for the escape time method.

The only ones I have found so far are:

• "The [inverse iteration] method is very insensitive to round-off errors, since $f$ tends to be expanding on its Julia set, so that $f^{-1}$ tends to be contracting.'' [Milnor, Dynamics in one complex variable, page 49]
• "Theorem 1 makes it plausible that in almost all cases rounding errors do not affect the computer graphics of Julia sets.'' [Steinmetz, Rational iteration, page 175]

Answer 1

Computer generated images of Julia sets tend to agree strongly with theory so we expect there must be some reason. I believe there are two main forces at work that generally mitigate the problem of round off error in this context.

First, the predominate behavior under the iteration of a polynomial (or even generally a rational function) is stability. That is, the Julia set (where the chaos happens) is a compact, nowhere dense subset of the Riemann sphere. The generic point lies in the Fatou set which is intrinsically stable. Thus, the escape time algorithm is essentially a test for membership of the Fatou set, which works well. As the Julia set is the complement of the Fatou set, it works well there as well.

Second, even near the Julia set, the Shadowing lemma guarantees that our computer generates actual orbits, though perhaps not exactly the orbit we intended. I don't have any specific references but a google search for Julia set shadowing turns up a number of scholarly hits that might be relevant.

Note that the claims above assume hyperbolic behavior and, in fact, there are definitely Julia sets that cannot be computed. The book by Braverman and Yampolsky cited in Alan's answer contains a theorem showing that certain quadratic functions of the form $e^{2\pi i t}z+z^2$ have uncomputable Julia sets. And, of course, the Julia set of a rational function may very well be the whole Riemann sphere.

Answer 2

Perhaps this book by Braverman and Yampolsky may be of interest to you? http://www.springer.com/gp/book/9783540685463

Answer 3

When calculating Julia Sets and performing iterative operations with real numbers, round-off errors manifest themselves at the boundary of the Julia set. (They may or may not manifest themselves elsewhere, but my efforts were principally at the boundary.)

The boundary is referred to as the Julia set by Kenneth Falconer in Fractals: A Short Introduction (NY: Oxford University Press, 2013). Falconer demonstrates z= z*z+c where c=(0,0) as a nice starting place. It is a nice starting place and the most elementary means of generating a Julia set. Points inside the Julia set converge to (0,0); points outside diverge to infinity; points on the Julia set stay at the unit circle.

However, when performing computer calculations, most the points that should remain on the unit circle do not behave well due to round-off errors. They either run off to infinity (with the postman) or converge to (0,0). The problem is exactly with round-off error.

To convince yourself, open a spreadsheet, and set up a couple of columns for unit circle points, and do the tedious iterative calculations:

x²-y², 2.0*x*y

Computationally, nothing behaves well on the unit circle.

You can switch to polar coordinates when the starting point c=(0,0). This approach is nice because it shows that points on the unit circle converge piecewise to the unit circle.

Now plot the points for everything I've mentioned above - not the iterations, but the points themselves. It will give you a clear visual perception of the gap between mathematics as it is and what really happens with your computer calculations.

Lynn Wienck

Answer 4

Here are a few examples of numerical problems : https://en.wikibooks.org/wiki/Fractals/Mathematics/Numerical

If you want to make numerical aproximation of Julia set ( not filled-in Julia set) then then points of Julia set are repellers of forward iteration ( = hard to find) . Using inverse iteration makes "easy" to find them.

Rounding (and other) errors will be always in numerical computations, but they can be smaller by :

• choosing bigger resolution ( subpixel accuracy )
• dynamically adjusting precision ( and other parameters) when going near Julia set ( zoom in or point close to Julia set ) . One can use for example mpc library. Distance between dwell bands is decreasing when getting toward Julia set so it can be used as a measure of desired precision

One can also use interval arithmethic, it will not change the numerical errors caused by computations but the images will be more accurate because of errors caused by scanning the plane

There are :

• many types of Julia sets ( like parabolic = hard to compute or Cremer = impossible to compute ( up to now) )
• there are many algorithms ( each has it's own numerical problems)

but notice that :

"... a single algorithm for computing all quadratic Julia sets does not exist." Computability of Julia sets by Mark Braverman, Michael Yampolsky

HTH