Proceed to Safety

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 xn. The variable naming is different, so first we will restate the Mandelbrot calculation (as seen in the iteration article):

x0 = complex number to be iterated
xn+1 = xn2+x0                                     (eq.1)

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

n = yn - xn                   (and the same for n+1)
yn = xn + ∂n                   (and the same for n+1)

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

yn+1 = yn2+y0

Replace the yn with xn+∂n, and replace y0 with x0+∂:

yn+1 = (xn+∂n)2+x0+∂

Expand the binomial:

yn+1 = xn2 + 2xnn + ∂n2 + x0 + ∂

Because xn+1 is xn2+x0, we can combine those two:

yn+1 = xn+1 + 2xnn + ∂n2 + ∂

Move the xn+1 to the other side:

yn+1 - xn+1 = 2xnn + ∂n2 + ∂

Because ∂n+1=yn+1-xn+1, we now have an expression for ∂n+1:

n+1 = 2xnn + ∂n2 + ∂                            (eq.2)

The Cubic Model

To approximate the ∂n values without calculating both xn and yn, we use a model that extrapolates what will happen as ∂n is iterated, based on the iterations of xn. 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 = An∂ + Bn2 + Cn3 + o(∂4)                   (eq.3)

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

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

A0 = 1 B0 = 0 C0 = 0

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

n+1 = 2xnn + ∂n2 + ∂
       = 2xn(An∂ + Bn2 + Cn3) + (An∂ + Bn2 + Cn3)2 + ∂
       = 2xnAn∂ + 2xnBn2 + 2xnCn3 + (An∂)2 + (Bn2)2 + (Cn3)2 + 2AnBn2 + 2AnCn3 + 2Bn2Cn3 + ∂
       = (2xnAn + 1)∂ + (2xnBn + An2)∂2 + (2xnCn + 2AnBn)∂3 + o(∂4) + o(∂5) + o(∂6)

Now we see that:

An+1 = 2xnAn + 1
Bn+1 = 2xnBn + An2
Cn+1 = 2xnCn + 2AnBn

Notice that we need to multiply the high-precision values xn by the lower-precision values An etc. but this multiplication can be done at the lower precision by truncating the iterates xn (which need only be done once and the values reused for every yn 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.

From the Mandelbrot Set Glossary and Encyclopedia, by Robert Munafo, (c) 1987-2024.

Mu-ency main pageindexrecent changesDEMZ

Robert Munafo's home pages on AWS    © 1996-2024 Robert P. Munafo.    about    contact
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. Details here.

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