Proceed to Safety

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 Zn 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:

zn=Zn+Δzn    for all n        (1)

We wish to calculate the Δzn, 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 z0 = Z0+Δz0 = 0 amd Δz0 = 0. Iteration proceeds using the standard recurrence relation:

zn+1 = zn2 + c                  (2)

Use (1) to substitute zn on the right, expand and regroup:

zn+1 = (Zn+Δzn)2 + C+Δc
     = Zn2 + 2 Zn Δzn + Δzn2 + C + Δc
     = Zn2 + C + 2 Zn Δzn + Δzn2 + Δc

Now we use (2) to replace Zn2+C with Zn+1:

zn+1 = Zn+1 + 2 Zn Δzn + Δzn2 + Δc

and use (1) to replace zn+1 with Zn+1+Δzn+1 on the left:

Zn+1+Δzn+1 = Zn+1 + 2 Zn Δzn + Δzn2 + Δc

So we can subtract Zn+1 from both sides to get:

Δzn+1 = 2 Zn Δzn + Δzn2 + Δ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 zn of the recurrence relation is:

d/dzn (zn2+c) = 2 zn

d (zn2+c) = 2 zn dzn

d (zn+1) = 2 zn dzn

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 Δzn between our desired iterates zn and the reference iterates Zn.

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 pageindexrecent changesDEMZ

Robert Munafo's home pages on AWS    © 1996-2023 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 09. s.27