7
$\begingroup$

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:

Newton fractal with immediate basin circles in white

(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:

Newton fractal in white with roots circled in red

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:

red circles drawn around roots in a Newton fractal based on period 5 components in the Mandelbrot set

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: Newton basins and the Mandelbrot set 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.

$\endgroup$
2
  • 1
    $\begingroup$ See also math.stackexchange.com/a/1038487/589 $\endgroup$
    – lhf
    Commented May 5, 2023 at 12:33
  • $\begingroup$ @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 $\endgroup$
    – Claude
    Commented May 6, 2023 at 10:26

1 Answer 1

0
$\begingroup$

Not really an answer, just contributing some relevant pictures from a modification of the code for the first Newton-fractal image.

The last image looks quite optimal. Doing directly what you proposed, determine the atom period and apply Newton to try to find the next hyperbolic center for this period gives the Newton-Fractal

X:-1.7578 Y:0.0138 R:5.0e-03

X:-1.7578 Y:0.0138 R:5.0e-03

with the full set having the coloration

enter image description here

As usual, color indicates the roots and shading the number of steps needed to reach a neighborhood of the root. The color is white if the root is already reached in the first step, black if no convergence was achieved.

$\endgroup$
2
  • $\begingroup$ These images seem to back up (but don't yet prove) a hypothesis that Newton's method from a point in an atom domain in the complement of the Mandelbrot set, using the atom period, will converge to the root at the center of the hyperbolic component at the center of the domain. $\endgroup$
    – Claude
    Commented Jan 26, 2021 at 12:20
  • $\begingroup$ 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$. $\endgroup$
    – Claude
    Commented Nov 12, 2021 at 12:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .