# 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 \[\begin{aligned} A &= 123456798 \\ B &= 123456789 \\ A - B &= 9 \end{aligned}\] even with \(A\) and \(B\) known to \(9\) significant figures, we can only determine their difference to \(1\) significant figure.

# 2 Applying The Technique

\( \newcommand{\dd}[1]{\frac{\partial}{\partial{#1}}} \newcommand{\DD}[1]{\left\langle\!\!\!\left\langle#1\right\rangle\!\!\!\right\rangle} \newcommand{\SA}[1]{\left[\!\left[{#1}\right]\!\right]} \) Choose a reference \(c\) and iterate \(z\) (and its derivatives if needed) with high precision: \[\begin{aligned} z_0 &= z & z_{n+1} &= z_{n}^2 + c \\ \dd{z}z_0 &= 1 & \dd{z}z_{n+1} &= 2 z_{n} \dd{z}z_{n} \\ \dd{c}z_0 &= 0 & \dd{c}z_{n+1} &= 2 z_{n} \dd{c}z_{n} + 1 \\ \dd{z}\dd{z}z_0 &= 0 & \dd{z}\dd{z}z_{n+1} &= 2 z_{n} \dd{z}\dd{z}z_{n} + 2 {\dd{z}z_{n}}^2 \\ \dd{c}\dd{z}z_0 &= 0 & \dd{c}\dd{z}z_{n+1} &= 2 z_{n} \dd{c}\dd{z}z_{n} + 2 \dd{c}z_{n} \dd{z}z_{n} \end{aligned}\]

Define the deltas \(\DD{c},\DD{z},\ldots\) for a nearby orbit \(C,Z,\ldots\) which can be computed with lower precision: \[\begin{aligned} C &= c + \DD{c} \\ Z_{n} &= z_{n} + \DD{z_{n}} \\ \dd{z}Z_{n} &= \dd{z}z_{n} + \DD{\dd{z}z_{n}} \\ \dd{c}Z_{n} &= \dd{c}z_{n} + \DD{\dd{c}z_{n}} \\ \dd{z}\dd{z}Z_{n} &= \dd{z}\dd{z}z_{n} + \DD{\dd{z}\dd{z}z_{n}} \\ \dd{c}\dd{z}Z_{n} &= \dd{c}\dd{z}z_{n} + \DD{\dd{c}\dd{z}z_{n}} \end{aligned}\] Some boring algebraic manipulation gives the iterations for the deltas: \[\begin{aligned} \DD{z_{n+1}} &= 2 z_{n} \DD{z_{n}} + \DD{z_{n}}^2 + \DD{c} \\ \DD{\dd{z}z_{n+1}} &= 2 \left( \dd{z}z_{n} \DD{z_{n}} + z_{n} \DD{\dd{z}z_{n}} + \DD{z_{n}} \DD{\dd{z}z_{n}} \right) \\ \DD{\dd{c}z_{n+1}} &= 2 \left( \dd{c}z_{n} \DD{z_{n}} + z_{n} \DD{\dd{c}z_{n}} + \DD{z_{n}} \DD{\dd{c}z_{n}} \right) \\ \DD{\dd{z}\dd{z}z_{n+1}} &= 2 \left( \dd{z}\dd{z}z_{n} \DD{z_{n}} + z_{n} \DD{\dd{z}\dd{z}z_{n}} + 2 z_{n} \DD{\dd{z}z_{n}} \right. \\ & \quad + \left. \DD{z_{n}} \DD{\dd{z}\dd{z}z_{n}} + \DD{\dd{z}z_{n}}^2 \right) \\ \DD{\dd{c}\dd{z}z_{n+1}} &= 2 \left( \dd{c}\dd{z}z_{n} \DD{z_{n}} + z_{n} \DD{\dd{c}\dd{z}z_{n}} + \DD{z_{n}} \DD{\dd{c}\dd{z}z_{n}} \right. \\ & \quad + \left. \dd{c}z_{n} \DD{\dd{z}z_{n}} + \DD{\dd{c}z_{n}} \dd{z}z_{n} + \DD{\dd{c}z_{n}} \DD{\dd{z}z_{n}} \right) \end{aligned}\] For interior coordinates and interior distance estimation, we need to solve \(Z_p = Z_0\), but when \(z_p = z_0\) we can apply the perturbation technique to Newton’s method for root finding: \[\begin{aligned} Z_0^{(m+1)} &= Z_0^{(m)} - \frac{Z_p^{(m)} - Z_0^{(m)}}{\dd{z}Z_p^{(m)} - 1} \\ \DD{z_0}^{(m+1)} &= \DD{z_0}^{(m)} - \frac{\DD{z_p}^{(m)} - \DD{z_0}^{(m)}}{\dd{z}{z_p} + \DD{\dd{z}{z_p}}^{(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 \(p\) is a multiple of the period of the reference.