8
$\begingroup$

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!

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for your answer. If my computation as well as their induction are correct then why am I getting different Delta2 than the author started with? Also, do you know what technique is used to obtain the A, B, and C equations? Taylor? $\endgroup$ – NightElfik Dec 19 '14 at 6:22
  • $\begingroup$ The author's computation for $\Delta_2$ is incorrect, as you showed. The equations for $A_n$, $B_n$, and $C_n$ come from plugging $\Delta_n = A_n \delta + B_n \delta^2 + C_n \delta^3 + o(\delta^4)$ into $\Delta_{n+1} = 2 X_n \Delta_n + \Delta_n^2 + \Delta_0$. $\endgroup$ – Neal Lawton Dec 19 '14 at 12:10
  • $\begingroup$ How do you know what to initialize the variables to? $\endgroup$ – Byte11 Nov 27 '17 at 23:24
  • $\begingroup$ Can this be used for the Julia fractal too (I don't see any reason why not)? Julia replaces $X2n+X0$ by $X2n+c$. $\endgroup$ – Bim Nov 15 '18 at 19:40
  • $\begingroup$ @Byte11 because $\Delta_0 = \delta = 1 \delta + 0 \delta^2 + 0 \delta^3 + \ldots$ $\endgroup$ – Claude Nov 18 '18 at 15:51

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.