# Perturbation

# 1 The Idea

The shape of the Mandelbrot set is exceedingly intricate, with variety increasing the further we zoom in. Zooming in requires more precise numerical methods: we need at least enough information to distinguish nearby points in the region we want to visualize. Using this much information for each point is certainly good enough, but as the precision increases it gets slower.

The idea of perturbation (seeminly rediscovered independently by K. I. Martin “SuperFractalThing Maths” (2013) and Sergey Khashin “Fast calculation of the Mandelbrot set with infinite resolution” (2016)) is simple: take a high precision orbit for one point as a reference, and assuming a well-behaved function, the orbits for points near to the reference will for the most part be near to the reference orbit. Instead of computing nearby orbits at high precision, save time and effort by computing only the difference from the reference orbit.

This works out because if you have two high precision numbers close together, their difference has less meaningful precision. For example A=123456798B=123456789A−B=9\begin{aligned} A &= 123456798 \\ B &= 123456789 \\ A - B &= 9 \end{aligned} even with AA and BB known to 99 significant figures, we can only determine their difference to 11 significant figure.

# 2 Applying The Technique

Choose a reference cc and iterate zz (and its derivatives if needed) with high precision:

z0=zzn+1=zn2+cddzz0=1ddzzn+1=2znddzznddcz0=0ddczn+1=2znddczn+1ddzddzz0=0ddzddzzn+1=2znddzddzzn+2ddzzn2ddcddzz0=0ddcddzzn+1=2znddcddzzn+2ddcznddzzn\begin{aligned} z_0 &= z & z_{n+1} &= z_{n}^2 + c \\ \frac{\mathrm{d}}{\mathrm{d}z}z_0 &= 1 & \frac{\mathrm{d}}{\mathrm{d}z}z_{n+1} &= 2 z_{n} \frac{\mathrm{d}}{\mathrm{d}z}z_{n} \\ \frac{\mathrm{d}}{\mathrm{d}c}z_0 &= 0 & \frac{\mathrm{d}}{\mathrm{d}c}z_{n+1} &= 2 z_{n} \frac{\mathrm{d}}{\mathrm{d}c}z_{n} + 1 \\ \frac{\mathrm{d}}{\mathrm{d}z}\frac{\mathrm{d}}{\mathrm{d}z}z_0 &= 0 & \frac{\mathrm{d}}{\mathrm{d}z}\frac{\mathrm{d}}{\mathrm{d}z}z_{n+1} &= 2 z_{n} \frac{\mathrm{d}}{\mathrm{d}z}\frac{\mathrm{d}}{\mathrm{d}z}z_{n} + 2 {\frac{\mathrm{d}}{\mathrm{d}z}z_{n}}^2 \\ \frac{\mathrm{d}}{\mathrm{d}c}\frac{\mathrm{d}}{\mathrm{d}z}z_0 &= 0 & \frac{\mathrm{d}}{\mathrm{d}c}\frac{\mathrm{d}}{\mathrm{d}z}z_{n+1} &= 2 z_{n} \frac{\mathrm{d}}{\mathrm{d}c}\frac{\mathrm{d}}{\mathrm{d}z}z_{n} + 2 \frac{\mathrm{d}}{\mathrm{d}c}z_{n} \frac{\mathrm{d}}{\mathrm{d}z}z_{n} \end{aligned}

Define the deltas ⟨⟨c⟩⟩,⟨⟨z⟩⟩,…\left\langle\left\langle{c}\right\rangle\right\rangle,\left\langle\left\langle{z}\right\rangle\right\rangle,\ldots for a nearby orbit C,Z,…C,Z,\ldots which can be computed with lower precision:

C=c+⟨⟨c⟩⟩Zn=zn+⟨⟨zn⟩⟩ddzZn=ddzzn+⟨⟨ddzzn⟩⟩ddcZn=ddczn+⟨⟨ddczn⟩⟩ddzddzZn=ddzddzzn+⟨⟨ddzddzzn⟩⟩ddcddzZn=ddcddzzn+⟨⟨ddcddzzn⟩⟩\begin{aligned} C &= c + \left\langle\left\langle{c}\right\rangle\right\rangle \\ Z_{n} &= z_{n} + \left\langle\left\langle{z_{n}}\right\rangle\right\rangle \\ \frac{\mathrm{d}}{\mathrm{d}z}Z_{n} &= \frac{\mathrm{d}}{\mathrm{d}z}z_{n} + \left\langle\left\langle{\frac{\mathrm{d}}{\mathrm{d}z}z_{n}}\right\rangle\right\rangle \\ \frac{\mathrm{d}}{\mathrm{d}c}Z_{n} &= \frac{\mathrm{d}}{\mathrm{d}c}z_{n} + \left\langle\left\langle{\frac{\mathrm{d}}{\mathrm{d}c}z_{n}}\right\rangle\right\rangle \\ \frac{\mathrm{d}}{\mathrm{d}z}\frac{\mathrm{d}}{\mathrm{d}z}Z_{n} &= \frac{\mathrm{d}}{\mathrm{d}z}\frac{\mathrm{d}}{\mathrm{d}z}z_{n} + \left\langle\left\langle{\frac{\mathrm{d}}{\mathrm{d}z}\frac{\mathrm{d}}{\mathrm{d}z}z_{n}}\right\rangle\right\rangle \\ \frac{\mathrm{d}}{\mathrm{d}c}\frac{\mathrm{d}}{\mathrm{d}z}Z_{n} &= \frac{\mathrm{d}}{\mathrm{d}c}\frac{\mathrm{d}}{\mathrm{d}z}z_{n} + \left\langle\left\langle{\frac{\mathrm{d}}{\mathrm{d}c}\frac{\mathrm{d}}{\mathrm{d}z}z_{n}}\right\rangle\right\rangle \end{aligned}

Some boring algebraic manipulation gives the iterations for the deltas:

⟨⟨zn+1⟩⟩=2zn⟨⟨zn⟩⟩+⟨⟨zn⟩⟩2+⟨⟨c⟩⟩⟨⟨ddzzn+1⟩⟩=2(ddzzn⟨⟨zn⟩⟩+zn⟨⟨ddzzn⟩⟩+⟨⟨zn⟩⟩⟨⟨ddzzn⟩⟩)⟨⟨ddczn+1⟩⟩=2(ddczn⟨⟨zn⟩⟩+zn⟨⟨ddczn⟩⟩+⟨⟨zn⟩⟩⟨⟨ddczn⟩⟩)⟨⟨ddzddzzn+1⟩⟩=2(ddzddzzn⟨⟨zn⟩⟩+zn⟨⟨ddzddzzn⟩⟩+2zn⟨⟨ddzzn⟩⟩+⟨⟨zn⟩⟩⟨⟨ddzddzzn⟩⟩+⟨⟨ddzzn⟩⟩2)⟨⟨ddcddzzn+1⟩⟩=2(ddcddzzn⟨⟨zn⟩⟩+zn⟨⟨ddcddzzn⟩⟩+⟨⟨zn⟩⟩⟨⟨ddcddzzn⟩⟩+ddczn⟨⟨ddzzn⟩⟩+⟨⟨ddczn⟩⟩ddzzn+⟨⟨ddczn⟩⟩⟨⟨ddzzn⟩⟩)\begin{aligned} \left\langle\left\langle{z_{n+1}}\right\rangle\right\rangle &= 2 z_{n} \left\langle\left\langle{z_{n}}\right\rangle\right\rangle + \left\langle\left\langle{z_{n}}\right\rangle\right\rangle^2 + \left\langle\left\langle{c}\right\rangle\right\rangle \\ \left\langle\left\langle{\frac{\mathrm{d}}{\mathrm{d}z}z_{n+1}}\right\rangle\right\rangle &= 2 \left( \frac{\mathrm{d}}{\mathrm{d}z}z_{n} \left\langle\left\langle{z_{n}}\right\rangle\right\rangle + z_{n} \left\langle\left\langle{\frac{\mathrm{d}}{\mathrm{d}z}z_{n}}\right\rangle\right\rangle + \left\langle\left\langle{z_{n}}\right\rangle\right\rangle \left\langle\left\langle{\frac{\mathrm{d}}{\mathrm{d}z}z_{n}}\right\rangle\right\rangle \right) \\ \left\langle\left\langle{\frac{\mathrm{d}}{\mathrm{d}c}z_{n+1}}\right\rangle\right\rangle &= 2 \left( \frac{\mathrm{d}}{\mathrm{d}c}z_{n} \left\langle\left\langle{z_{n}}\right\rangle\right\rangle + z_{n} \left\langle\left\langle{\frac{\mathrm{d}}{\mathrm{d}c}z_{n}}\right\rangle\right\rangle + \left\langle\left\langle{z_{n}}\right\rangle\right\rangle \left\langle\left\langle{\frac{\mathrm{d}}{\mathrm{d}c}z_{n}}\right\rangle\right\rangle \right) \\ \left\langle\left\langle{\frac{\mathrm{d}}{\mathrm{d}z}\frac{\mathrm{d}}{\mathrm{d}z}z_{n+1}}\right\rangle\right\rangle &= 2 \left( \frac{\mathrm{d}}{\mathrm{d}z}\frac{\mathrm{d}}{\mathrm{d}z}z_{n} \left\langle\left\langle{z_{n}}\right\rangle\right\rangle + z_{n} \left\langle\left\langle{\frac{\mathrm{d}}{\mathrm{d}z}\frac{\mathrm{d}}{\mathrm{d}z}z_{n}}\right\rangle\right\rangle + 2 z_{n} \left\langle\left\langle{\frac{\mathrm{d}}{\mathrm{d}z}z_{n}}\right\rangle\right\rangle \right. \\ & \quad + \left. \left\langle\left\langle{z_{n}}\right\rangle\right\rangle \left\langle\left\langle{\frac{\mathrm{d}}{\mathrm{d}z}\frac{\mathrm{d}}{\mathrm{d}z}z_{n}}\right\rangle\right\rangle + \left\langle\left\langle{\frac{\mathrm{d}}{\mathrm{d}z}z_{n}}\right\rangle\right\rangle^2 \right) \\ \left\langle\left\langle{\frac{\mathrm{d}}{\mathrm{d}c}\frac{\mathrm{d}}{\mathrm{d}z}z_{n+1}}\right\rangle\right\rangle &= 2 \left( \frac{\mathrm{d}}{\mathrm{d}c}\frac{\mathrm{d}}{\mathrm{d}z}z_{n} \left\langle\left\langle{z_{n}}\right\rangle\right\rangle + z_{n} \left\langle\left\langle{\frac{\mathrm{d}}{\mathrm{d}c}\frac{\mathrm{d}}{\mathrm{d}z}z_{n}}\right\rangle\right\rangle + \left\langle\left\langle{z_{n}}\right\rangle\right\rangle \left\langle\left\langle{\frac{\mathrm{d}}{\mathrm{d}c}\frac{\mathrm{d}}{\mathrm{d}z}z_{n}}\right\rangle\right\rangle \right. \\ & \quad + \left. \frac{\mathrm{d}}{\mathrm{d}c}z_{n} \left\langle\left\langle{\frac{\mathrm{d}}{\mathrm{d}z}z_{n}}\right\rangle\right\rangle + \left\langle\left\langle{\frac{\mathrm{d}}{\mathrm{d}c}z_{n}}\right\rangle\right\rangle \frac{\mathrm{d}}{\mathrm{d}z}z_{n} + \left\langle\left\langle{\frac{\mathrm{d}}{\mathrm{d}c}z_{n}}\right\rangle\right\rangle \left\langle\left\langle{\frac{\mathrm{d}}{\mathrm{d}z}z_{n}}\right\rangle\right\rangle \right) \end{aligned}

For interior coordinates and interior distance estimation, we need to solve Zp=Z0Z_p = Z_0, but when zp=z0z_p = z_0 we can apply the perturbation technique to Newton’s method for root finding:

Z0(m+1)=Z0(m)−Zp(m)−Z0(m)ddzZp(m)−1⟨⟨z0⟩⟩(m+1)=⟨⟨z0⟩⟩(m)−⟨⟨zp⟩⟩(m)−⟨⟨z0⟩⟩(m)ddzzp+⟨⟨ddzzp⟩⟩(m)−1\begin{aligned} Z_0^{(m+1)} &= Z_0^{(m)} - \frac{Z_p^{(m)} - Z_0^{(m)}}{\frac{\mathrm{d}}{\mathrm{d}z}Z_p^{(m)} - 1} \\ \left\langle\left\langle{z_0}\right\rangle\right\rangle^{(m+1)} &= \left\langle\left\langle{z_0}\right\rangle\right\rangle^{(m)} - \frac{\left\langle\left\langle{z_p}\right\rangle\right\rangle^{(m)} - \left\langle\left\langle{z_0}\right\rangle\right\rangle^{(m)}}{\frac{\mathrm{d}}{\mathrm{d}z}{z_p} + \left\langle\left\langle{\frac{\mathrm{d}}{\mathrm{d}z}{z_p}}\right\rangle\right\rangle^{(m)} - 1} \end{aligned}

The precondition isn’t too onerous, as it’s often sensible to choose a periodic point as a reference, and it’s enough if pp is a multiple of the period of the reference.