# How to estimate distance from root to nearest immediate basin boundary for Newton's method in one complex variable?

Context: I want to check that the atom domain size estimate is smaller than the inradius of the Newton immediate basin, for centers of hyperbolic components in the Mandelbrot set, and thus justify using Newton's method to find the center given an initial guess inside an atom domain.

Initial approach: I am using Newton's method for finding roots of polynomial (and sometimes rational) functions in one complex variable: $$z_{n+1} = z_{n} - \frac{f(z_n)}{f'(z_n)}$$ Once I have found each root, I wish to estimate each distance to the nearest (fractal) boundary of the immediate basin of attraction/convergence, like the radii of the white circles shown on the image (background coloured by root, shaded by number of iterations to converge), so that I can check that the atom domain size estimate is smaller:

(Image originally from https://commons.wikimedia.org/wiki/File:Newtroot_1_0_m3i_m5m2i_3_1.png modified to add white circles, under CC BY-SA license)

How do I estimate the circle radius given the root? I can evaluate the function and all derivatives as necessary.

One approach I tried is based loosely on formulas from Wikipedia: for a root $$\alpha$$, first find the distance $$r_0$$ from $$\alpha$$ to the nearest root of $$f'(z) = 0$$ (this is because of condition 1 from the page; this step may be tricky for the high degree polynomials I will be using in practice...). Then use condition 3c to get $$r_C = \frac{1}{C}\left|\frac{f'(\alpha)}{f''(\alpha)}\right|$$ Then the desired $$r = \frac{1}{2} \min(r_0, r_C)$$ where the $$\frac{1}{2}$$ is empirically chosen. I also used $$C = \frac{1}{2}$$ for want of better ideas. Here is the result for one cubic polynomial:

It has the problem of the middle radius of three roots in a row getting very small, and for my actual functions finding the nearest root of the derivative is problematic: using Newton's method gives a root, but not necessarily the nearest, at least I think that is why my code calculates a too-large radius for the 3rd root from the left in this picture:

Can this approach be cleaned up and justified formally?

Alternatively, I am considering tracing a path along the steepest ascent gradient of a smoothed iteration count, would this work? I suppose I would stop tracing when the Newton method step size starts to go down again (as it approaches the boundary).

I derived a smooth iteration count (number of iterations required to get from $$z_0$$ to within $$\epsilon$$ of a root) as $$\mu_n = n + \log_2 \frac{\log\epsilon - \log|z_{n+1}-z_n|}{\log|z_{n+2}-z_{n+1}| - \log|z_{n+1}-z_n|}$$ which I think is valid for $$z_n$$ in the immediate basin region of quadratic convergence and $$\epsilon \to 0$$, and for the spatial derivative to find the steepest slope I got as far as $$(\mu_n)_x = \frac{1}{\log 2}\left( \frac{-\frac{|z_{n+1}-z_n|_x}{|z_{n+1}-z_n|}}{\log\epsilon - \log|z_{n+1}-z_n|} - \frac{\frac{|z_{n+2}-z_{n+1}|_x}{|z_{n+2}-z_{n+1}|}-\frac{|z_{n+1}-z_n|_x}{|z_{n+1}-z_n|}}{\log|z_{n+2}-z_{n+1}| - \log|z_{n+1}-z_n|}\right)$$ and similarly for $$\cdot_y$$, which may be computable numerically using dual numbers with two dual dimensions.

But there is also a problem of where to start tracing from: from the root itself wouldn't work as $$z_{n+2}=z_{n+1}=z_n$$ there, so I suppose to pick an $$r>\epsilon$$ (not too small, not too big...) and try probe points on the boundary of the circle radius $$r$$...

Another idea: perhaps I don't need to compute the Newton basin inradius at all: if I could show that the Newton step of $$B(\alpha, R_a(\alpha))$$ (the ball centered on the root with atom domain size estimate as radius) is contained entirely within that self-same ball, then would it be guaranteed to be entirely inside the immediate basin of the root $$\alpha$$? Could the Kantorovich theorem help here?

For example some period 6 components in the Mandelbrot set: radius as described above with second derivatives in red, atom domain radius in green, Mandelbrot set boundary in blue, Newton basins in black: The radii computed are not totally ordered (sometimes red is outside green, sometimes the opposite), what I really want to show is that the green circles are inside the immediate Newton basins.

• – lhf
Commented May 5, 2023 at 12:33
• @lhf thanks. unfortunately, for Mandelbrot polynomials of period $p$, this global radius becomes the extremely tiny $r = 3\pi^2 8^{-p}$ using section 13.5.1 of Corless, R.M., Lawrence, P.W. (2013). The Largest Roots of the Mandelbrot Polynomials. In: , et al. Computational and Analytical Mathematics. Springer Proceedings in Mathematics & Statistics, vol 50. Springer, New York, NY. doi.org/10.1007/978-1-4614-7621-4_13 Commented May 6, 2023 at 10:26

• The conjecture in my comment of Jan 26 2021 is false, see mathr.co.uk/blog/2021-11-12_atom_domains_and_newton_basins.html for details, the counter-example has angled internal address $1 \to_{1/2} 2 \to_{1/8} 16 \to_{1/2} 18$. Commented Nov 12, 2021 at 12:27