I recently discovered very clever technique how co compute deep zooms of the Mandelbrot set using Perturbation and I understand the idea very well but when I try to do the math by myself I never got the right answer.
I am referring to original PDF by K.I. Martin but I will put the necessary equations below.
Theory
Mandelbrot set is defined as $X_{n+1} = X_n^2 + X_0$.
Where the complex number $X_0$ is in the Mandelbrot set if $|X_n| \leq 2$ for all n. Otherwise we assign a color based on $n$ where $|X_n| > 2$.
Now consider another point $Y_0$ that gives us $Y_{n+1} = Y_n^2 + Y_0$.
Let $\Delta_n = Y_n – X_n$, Then
$\Delta_{n+1} = Y_{n+1} – X_{n+1} = 2X_n \Delta_n + \Delta_n^2 + \Delta_0$
So far this is crystal clear to me. But now we want to compute $\Delta_n$ directly from $\Delta_0$ using pre-computed coefficients of the recursive equation.
The author continues:
Let $\delta = \Delta_0$
$\Delta_1 = 2X_0\delta + \delta^2+\delta = (2X_0+1)\delta + \delta^2\\
\Delta_2 = (4X_1X_0 – 2X_1-1)\delta + ((X_0-1)^2+2X_1)\delta^2 + (4X_0-2)\delta^3 + o(\delta^4)$
Let $\Delta_n=A_n\delta+B_n\delta^2+C_n\delta^3+o(\delta^4)$
Then
$A_{n+1} = 2 X_n A_n + 1\\
B_{n+1} = 2 X_n B_n + A_n^2\\
C_{n+1} = 2 X_n C_n + 2 A_n B_n$
Knowing all $X_n$ we can pre-compute $A_n$, $B_n$, and $C_n$ and given new point $Z_0$ we can compute $\delta_z$ and searching for $|Z_n| > 2$ is just binary search that is O(log n).
Question
My question is how to compute the equations for $A_n$, $B_n$, and $C_n$? I tried to "check" the equations by applying the $\Delta$ recurrence but I obtained:
$\Delta_2 = 2 X_n \Delta_1 + \Delta_1^2+\Delta_0 =\\
=(4X_1 X_0 + 2 X_1 + 1) \delta + (2X_1 + (2X_0 + 1)^2)\delta^2 + (4X_0+2)\delta^3+\delta^4$
Which does not match author's $\Delta_2$.
I have also tried to apply given formulas for $A_n$, $B_n$, and $C_n$ to compute forst few $\Delta$'s but they matched my $\Delta_2$, not authors (for example $C_2 = 4 X_0 + 2).$
What am I doing wrong? Is it something with complex numbers?
Bonus
There is probably a general formula for $\Delta_n$, can you help me to find it? Something like $\Delta_n=\sum_{i=0}^\infty C_n^{(i)} \delta^i$.
Edit
Anybody? The "Tumbleweed" badge for this question is cool but I thought this should be rather "simple" problem. The solution should probably involve Taylor series, I just need to point out to the right direction. Thanks!
Best Answer
Your computation is correct:
$\Delta_2 = (4X_1 X_0 + 2 X_1 + 1) \delta + (2X_1 + (2X_0 + 1)^2)\delta^2 + (4X_0+2)\delta^3+\delta^4$
Their computation for the induction is correct:
$ A_{n+1} = 2 X_n A_n + 1 \\ B_{n+1} = 2 X_n B_n + A_n^2 \\ C_{n+1} = 2 X_n C_n + 2 A_n B_n $
Initialise $A_0 = 1, B_0 = 0, C_0 = 0$ and use their computation for the induction.