4
$\begingroup$

I came up with an algorithm that seems to work well in practice for (interior and exterior) distance estimate rendering of the Mandelbrot set, for each starting point $c$:

  • $d := 0$
  • $z := 0$
  • $m := \infty$
  • for $p$ in $1, 2, 3, ...$
    • $d := 2zd+1$ (the running derivative w.r.t. $c$)
    • $z := z^2 + c = f_c(z)$
    • if $|z| \le m$
      • $m := |z|$
      • use Newton's method to solve $f_c^p(z_0) = z_0$ using $z$ as initial guess
      • if $\left|\frac{\partial}{\partial z}f_c^p(z_0)\right| \le 1$
        • the point $c$ is interior to a hyperbolic component of period $p$
        • the interior distance estimate can be computed using $z_0$ and $p$
        • STOP
    • if $|z| \gt R \ge 2$
      • the point $c$ is exterior to the Mandelbrot set
      • the exterior distance estimate can be computed using $z$ and $d$
      • STOP

The question is to prove the correctness of the algorithm, perhaps via proving these conjectured properties:

  1. if $c$ is in a hyperbolic component of period $p$, then $|z|$ reaches a new minimum at iteration $p$
  2. if $c$ is in a hyperbolic component of period $p$, then Newton's method starting from $f_c^p(0)$ will always converge
  3. if Newton's method converges, then $z_0$ is in the limit cycle reachable by repeated iterations of $f_c$ starting from $0$
  4. if the computed distance estimate is larger than a small constant factor of the unit of least precision of the numeric type used for iteration, then the classification into "exterior" or "interior to period $p$ component" is guaranteed to be accurate despite rounding errors occurring throughout iteration (I think this might be related to "backward stability").

There remains the problem of points in the boundary of the Mandelbrot set (that are neither interior to a hyperbolic component nor exterior the set), to which end I already asked about dyadic rational boundary points.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.