Newton's method for Misiurewicz points
Misiurewicz points in the Mandelbrot set are strictly preperiodic. Defining the quadratic polynomial \(F_c(z) = z^2 + c\), then a Misiurewicz point with preperiod \(q > 0\) and period \(p > 0\) satisfies:
\[\begin{aligned} {F_c}^{q + p}(c) &= {F_c}^{q}(c) \\ {F_c}^{q' + p}(c) &\ne {F_c}^{q'}(c)\text{ for all } 0 \le q' < q \\ {F_c}^{q + p'}(c) &\ne {F_c}^{q}(c)\text{ for all } 1 \le p' < p \end{aligned}\]
where the first line says it is preperiodic, the second line says that the preperiod is exactly \(q\), and the third line says that the period is exactly \(p\). A naive solution of the first equation would be to use Newton's method for finding a root of \(f_1(c) = 0\) where \(f_1(c) = {F_c}^{q + p}(c) - {F_c}^{q}(c)\), and it does work: but the root found might have lower preperiod or lower period, so it requires checking to see if it's really the Misiurewicz point we want.
This need for checking felt unsatisfactory, so I tried to figure out a way to reject wrong solutions during the Newton's method iterations. The second line equation for exact preperiod gives \({F_c}^{q' + p}(c) - {F_c}^{q'}(c) \ne 0\), so I tried dividing \(f_1(c)\) by all those non-zero values to give an \(f_2(c)\) and applying Newton's method for finding a root of \(f_2(c) = 0\). So:
\[\begin{aligned} f_2(c) &= \frac{g_2(c)}{h_2(c)} \\ g_2(c) &= {F_c}^{q + p}(c) - {F_c}^{q}(c) \\ h_2(c) &= \prod_{q'=0}^{q-1}\left( {F_c}^{q' + p}(c) - {F_c}^{q'}(c) \right) \\ f_2'(c) &= \frac{g_2'(c) h_2(c) - g_2(c) h_2'(c)}{h_2(c)^2} \\ g_2'(c) &= ({F_c}^{q + p})'(c) - ({F_c}^{q})'(c) \\ h_2'(c) &= h_2(c) \sum_{q'=0}^{q-1} \frac{({F_c}^{q' + p})'(c) - ({F_c}^{q'})'(c)}{{F_c}^{q' + p}(c) - {F_c}^{q'}(c)} \end{aligned}\]
with the Newton step \(c_{n+1} = c_{n} - \frac{f_2(c_n)}{f_2'(c_n)}\) where \(c_0\) is an initial guess. Here are some image comparisons, where each pixel is coloured according the the root found (grey for wrong (pre)period, saturated circles surround each root within the basin of attraction, edges between basins coloured black, with the Mandelbrot set overlayed in white). The top half of each image uses the naive method, the bottom half the method detailed in this post (which seems better, because the saturated circles are larger):
The images are labelled with preperiod and period, but there might be an off-by-one error with respect to standard terminology: here I iterate \(F_c\) starting from \(c\), while some iterate \(F_c\) starting from \(0\). So my preperiods are one less than they would be if I'd started from \(0\). I tried extending the method to reject lower periods as well as lower preperiods, but it didn't work very well.
The C99 source code for this post is available: newton-misiurewicz.c, using code from my new (work-in-progress) mandelbrot-numerics library mandelbrot-numerics library (git HEAD at 7fe3b89465390a712c7427093b8fc5377d2e65b6 when this post was written). Compiled using OpenMP for parallelism, it takes a little over 25mins to run on my quad-core machine.
References: