Cubic Deltas

Robert P. Munafo, 2023 Jun 17.

The cubic delta approximation technique, pioneered by Kevin Martin (also called series approximation of degree 3), is a perturbation method using a single reference point and third-order polynomial (i.e. cubic) extrapolation.

A single reference point x is iterated at full precision, with its iterates called x_n. The variable naming is different, so first we will restate the Mandelbrot calculation (as seen in the iteration article):

x₀ = complex number to be iterated
x_n+1 = x_n²+x₀ (eq.1)

Any other desired point y₀ is iterated by first noting its difference from x₀, i.e. ∂=y₀-x₀ or equivalently y₀=x₀+∂. To iterate a different point y_n involves calculating the difference of each y_n from x_n. These two are equivalent:

∂_n = y_n - x_n (and the same for n+1)
y_n = x_n + ∂_n (and the same for n+1)

As for x, we iterate y by the same formula as (eq.1) above:

y_n+1 = y_n²+y₀

Replace the y_n with x_n+∂_n, and replace y₀ with x₀+∂:

y_n+1 = (x_n+∂_n)²+x₀+∂

Expand the binomial:

y_n+1 = x_n² + 2x_n∂_n + ∂_n² + x₀ + ∂

Because x_n+1 is x_n²+x₀, we can combine those two:

y_n+1 = x_n+1 + 2x_n∂_n + ∂_n² + ∂

Move the x_n+1 to the other side:

y_n+1 - x_n+1 = 2x_n∂_n + ∂_n² + ∂

Because ∂_n+1=y_n+1-x_n+1, we now have an expression for ∂_n+1:

∂_n+1 = 2x_n∂_n + ∂_n² + ∂ (eq.2)

The Cubic Model

To approximate the ∂_n values without calculating both x_n and y_n, we use a model that extrapolates what will happen as ∂_n is iterated, based on the iterations of x_n. The particular model we use is a cubic polynomial with coefficients A, B, and C. These coefficients also change with each iteration so they have subscripts:

∂_n = A_n∂ + B_n∂² + C_n∂³ + o(∂⁴) (eq.3)

The "o(∂⁴)" part means that there is an additional quantity that is assumed to be of a magnitude comparable to ∂⁴.

The initial ∂, which we can also think of as "∂₀", has the coefficients:

A₀ = 1 B₀ = 0 C₀ = 0

Now we can derive a way to iterate the values of these coefficients. Substitute (eq.3) into (eq.2) omitting the o(∂⁴) part, expand, and regroup terms according to the power of ∂:

∂_n+1 = 2x_n∂_n + ∂_n² + ∂
       = 2x_n(A_n∂ + B_n∂² + C_n∂³) + (A_n∂ + B_n∂² + C_n∂³)² + ∂
       = 2x_nA_n∂ + 2x_nB_n∂² + 2x_nC_n∂³ + (A_n∂)² + (B_n∂²)² + (C_n∂³)² + 2A_n∂B_n∂² + 2A_n∂C_n∂³ + 2B_n∂²C_n∂³ + ∂
       = (2x_nA_n + 1)∂ + (2x_nB_n + A_n²)∂² + (2x_nC_n + 2A_nB_n)∂³ + o(∂⁴) + o(∂⁵) + o(∂⁶)

Now we see that:

A_n+1 = 2x_nA_n + 1
B_n+1 = 2x_nB_n + A_n²
C_n+1 = 2x_nC_n + 2A_nB_n

Notice that we need to multiply the high-precision values x_n by the lower-precision values A_n etc. but this multiplication can be done at the lower precision by truncating the iterates x_n (which need only be done once and the values reused for every y_n pixel).

The above was developed and implemented in Java by Kevin Martin in the program "SuperFractalThing", announced to fractalforums in Apr 2013.

Later History

This method was reimplemented by Botond Kosa, later improved by Karl Runmo and implemented in his program Kalles Fraktaler. (That program also applies these methods to multibrot sets and many other recurrence relations.) The cubic model breaks down when iterating points near islands whose period is less than the number of iterations; yielding incorrect dwell values for pixels. This was clearly visible in images, and called "glitches" in the fractal community. For some time, glitches were fixed manually by designating additional reference points in the image to be iterated at full precision.

Eventually it because clear that automatic detection of some kind was needed; and in 2014 Pauldelbrot posted to fractalforums an automatic detection method. It was based on second-order perturbation theory (approximating the iterated ∂_n values as ∂ plus ε_n), which he developed in his program "Nanoscope". It effectively locates embedded Julia sets and related nodes within the image so that the pixels near them can be iterated separately based on their own reference point, chosen to be near the related island.

Sometime around this point the bilinear approximation technique was adopted in place of cubic deltas; see that article for more.

Mu-ency main page — index — recent changes — DEMZ

This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2023 Jul 03.

s.27