# Derivative Extrapolation

Robert P. Munafo, 2023 Jul 8.

"Derivative extrapolation", also "differential approximation", is a perturbation method using the iterates of a single reference point, along with the iterated derivative, a linear model for extrapolating nearly points, and a "rebasing" method to remove roundoff error when the iteration comes near the origin.

It is effectively a degree 1 approximation of the recurrence relation, rather than degree 3 as in cubic deltas. The method is called "derivative extrapolation" because it extrapolates iterate values based on a derivative of the reference point's iterates; alternatively it is called "differential estimation" because the differential (difference between a point's iterate and a nearby point's iterate) is being estimated (approximated).

Given the actual iterate values of a "reference point" (whose c value must be near the c of the iteration to be approximated), the iterates of any "nearby" point of interest can be approximated by calculating successive values of the difference between its iterates and the reference point's iterates. The definition of "nearby" is expressed in terms of a view area (typically a rectangle) and the use of a period-finding technique to locate the lowest-period nucleus within that view area (even if its mu-atom is much smaller than a pixel). Period-finding methods are described in: the period article, section "Finding the Period of a mu-Atom", and the articles Jordan curve method and Synchronous-Orbit Algorithm both which have illustrations.

In comparison to cubic deltas, the use of fewer terms means that iteration cannot proceed through any step that puts the reference point very close to the origin; however this is not a problem if that condition is checked on every iteration. When needed a rebasing calculation is performed, in which a new high precision key point value is created based on the previous (good) values; then iteration continues as usual.

In turn, using a linear model makes it easier to perform the condition test with accurate results (no "false negatives"). Such a test was introduced by "Zhuoran" on Fractal Forums in 2021 Dec.

The practical benefit is far fewer "glitches", making it no longer necessary to use higher-degree extrapolation models to get good images. For this reason DE has mostly supplanted cubic deltas. It is used in the more recent versions of Kalles Fraktaler and contemporaneous deep zooming programs.

### The Model

Given a reference point C that is known to be periodic (a nucleus
or Misiurewicz point) and relatively close to the pixels we want to
draw, its iterates (preperiod plus limit cycle) are calculated
at full precision, then each iterate is rounded to a lower-precision
Z_{n} that can be at lower precision (typically single or
double precision).

For every other pixel, define its parameter in terms of C and an offset: c=C+Δc. Its iterates are defined similarly:

z_{n}=Z_{n}+Δz_{n} for all n (1)

We wish to calculate the Δz_{n}, which can be done at lower
precision because c is close to C and the iterates won't diverge
much until the point is close to escape.

The initial value for any iteration is z=0, and so z_{0} =
Z_{0}+Δz_{0} = 0 amd Δz_{0} = 0. Iteration proceeds using the
standard recurrence relation:

z_{n+1} = z_{n}^{2} + c (2)

Use (1) to substitute z_{n} on the right, expand and regroup:

z_{n+1} = (Z_{n}+Δz_{n})^{2} + C+Δc

= Z_{n}^{2} + 2 Z_{n} Δz_{n} + Δz_{n}^{2} + C + Δc

= Z_{n}^{2} + C + 2 Z_{n} Δz_{n} + Δz_{n}^{2} + Δc

Now we use (2) to replace Z_{n}^{2}+C with Z_{n+1}:

z_{n+1} = Z_{n+1} + 2 Z_{n} Δz_{n} + Δz_{n}^{2} + Δc

and use (1) to replace z_{n+1} with Z_{n+1}+Δz_{n+1} on the left:

Z_{n+1}+Δz_{n+1}
= Z_{n+1} + 2 Z_{n} Δz_{n} + Δz_{n}^{2} + Δc

So we can subtract Z_{n+1} from both sides to get:

Δz_{n+1} = 2 Z_{n} Δz_{n} + Δz_{n}^{2} + Δc (3)

Therefore the code for the main iteration step is simply:

/* Calculate new dz */ dz := 2 * Z[n] * dz + dz * dz + c;This matches the two published implementations (computer code). Zhuoran's code has:

dz = 2 * dz * Reference[RefIteration] + dz * dz + dc;Claude Heiland-Allen's code is refactored slightly to save one multiplication (here with my comments added):

Z = Z_ptr[m]; // Z_ptr is the precomputed array of reference iterates z = (2 * Z + z) * z + c; // "z" is their name for Δz### Relation to Derivative Iteration

Now consider the derivative calculation for constant c, as when
making an image of a Julia set. The derivative (with respect to
z_{n} of the recurrence relation is:

d/dz_{n} (z_{n}^{2}+c) = 2 z_{n}

d (z_{n}^{2}+c) = 2 z_{n} dz_{n}

d (z_{n+1}) = 2 z_{n} dz_{n}

This is the first part of (3); the rest of (3) is just the right side
of (2). Thus we are augmenting the ordinary iteration formula by also
performing the derivative iteration, allowing us to calculate
estimates of the differences Δz_{n} between our desired iterates
z_{n} and the reference iterates Z_{n}.

revisions: 20230620 first version; 20230622 add model equations and derivations of iteration; 20230703 move the BLA text to its own heading; 20230708 rewrite mose of the text

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

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 09. s.27