[Math] Relating convergence theorem for Newton-Raphson method to Newton fractal

complex numbersfractalsnumerical methods

I have created a Newton fractal (below) using the Newton-Raphson method to find the five solutions of

f = (z^5-1)

The convergence theorem of Newtons method say "Suppose that f is smooth and that
f(x) = 0 and f'(x) =/= 0. Then, there exists epsilon > 0 so that Newton’s method converges to the root x of f if the initial guess x 0 ∈ [x − epsilon, x + epsilon]."

However, I am struggling to see how the epsilon relates to the plot I have made. How could I determine an epsilon value for this? And is it possible to have epsilon as a complex number? Would this still create a circle surrounding x0?

Thanks,

enter image description here

Best Answer

The relation is this:

For each root there is a small disk around the root whose points have all the same color.

You can find a suitable radius $\varepsilon$ by inspection from the picture.

Joel Friedman in On the Convergence of Newton's Method (Theorem 2.2) gives an explicit radius for such a disk for a polynomial $f$: $$ r=\frac{\eta}{2d} $$ where $\eta$ is the minimum distance between two roots of $f$ and $d$ is the degree of $f$.

Other explicit bounds are given by Anthony Manning in How to be sure of finding a root of a complex polynomial using Newton's method (Theorem 1.2).

See also How to find all roots of complex polynomials by Newton's method by Hubbard et al.
Invent. Math. 146 (2001), no. 1, 1–33. pdf

Related Question