Perturbation theory

From Fractal Wiki
Jump to navigation Jump to search

Observing that for most of the time, nearby orbits in escape-time fractals remain nearby, one can largely avoid the need to iterate all orbits in high precision. Instead a reference orbit can be iterated at high precision, with low precision deltas to the individual orbits of each pixel. In general one uses symbolic algebra to rearrange [math]F(Z + z, C + c) - F(Z, C)[/math] to get an iteration formula for [math]z[/math] that avoids loss of precision though addition of values of greatly differing scales.

Examples

Mandelbrot set

The escape time formula for the Mandelbrot set involves iterating [math]z \to z^2 + c[/math] starting from [math]z = 0[/math] with [math]c[/math] being the coordinates of the pixel. Perturbation works by replacing each variable with an unevaluated sum of a high precision reference (upper case) and a low precision delta (lower case). Thus:

[math]Z + z \to (Z + z)^2 + (C + c)[/math]

which can be re-arranged (using [math]Z \to Z^2 + C[/math]) to give:

[math]z \to 2 Z z + z^2 + c[/math]

in which most of the high precision [math]Z, C[/math] have cancelled out, and [math]z[/math] can be iterated with low precision numerics.

Burning Ship

The escape time formula for the Burning Ship involves iterations with the absolute value function [math]|\cdot|[/math]. Applying perturbation means one wants to calculate

[math]|X + x| - |X|[/math]

in low precision, without the tiny [math]x[/math] being lost to catastrophic cancellation with the much larger [math]X[/math]. laser blaster derived a case analysis for the diffabs function:

// evaluate |X + x| - |X| without catastrophic cancellation
float diffabs(float X, float x) {
  if (X >= 0) {
    if (X + x >= 0) { return x; }
    else { return -(2 * X + x); }
  } else {
    if (X + x > 0) { return 2 * X + x; }
    else { return -x; }
  }
}

Problems

Reference escape

If the reference escapes before all pixels have escaped, another reference is needed.

Glitches

Glitches can occur, usually around features in embedded Julia sets where the dynamics of the pixel are significantly different to the dynamics of the reference orbit. Typically the surroundings of the glitch start to get fuzzy, with a flat interior. Distance estimation can give impossible results when comparing nearby pixels. Glitches can be corrected by using another reference (one more appropriate to the dynamics of the glitch).

Pauldelbrot's glitch test

Pauldelbrot derived a glitch test that can tell when a pixel is likely to be glitched. It is quite conservative, so there may be pixels reported as glitches which would look visually fine.

If [math]|Z + z| \lt {10}^{-3} |Z|[/math] at any iteration, then the pixel may be glitched.

Extensions

For well-behaved functions, the iterations of the low-precision deltas can be expressed as a power series in [math]c[/math]. This technique is known as Series approximation.

History

Perturbation theory for the Mandelbrot set was popularized by K. I. Martin's SuperFractalThing, first version in the Internet Archive is around 2013. Sergey Khashin used a similar technique, which a web page claims in 2011, but the first version in the Internet Archive (and the date of the paper) is 2016.

See Also


Original Page by Claude