4
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ Wow, that's pretty! $\endgroup$ – terrace Nov 26 '14 at 15:06
  • $\begingroup$ I once made an effort to visually compare the easily programmable methods in mathematik.hu-berlin.de/~llehmann/topics/newton-fractal . As can be seen, Newton's method produces by far the most "interesting" fractals, i.e., the most clutter at the borders of the basins of attraction. $\endgroup$ – Lutz Lehmann Sep 16 '15 at 22:30
  • 1
    $\begingroup$ Rather than go pick flowers for my girlfriend, I think I should just generate them from now on. $\endgroup$ – Simply Beautiful Art Nov 28 '16 at 23:29
4
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ See also math.stackexchange.com/q/34581. $\endgroup$ – lhf Nov 25 '14 at 18:16
  • $\begingroup$ Thanks for this answer - I was unaware of such a simple bound. I wonder if there is a similar result for rational functions as well? In practice, I typically try to find a positive $\varepsilon$ such that $|N'(x)|<1$ for all $x$ within $\varepsilon$ of the root. This not too hard to code, but certainly must take much longer than using a simple bound like the one that you state here. $\endgroup$ – Mark McClure Nov 26 '14 at 14:09
  • $\begingroup$ @MarkMcClure, I'm not aware of a similar result for rational functions. I'd love to know one. $\endgroup$ – lhf Nov 26 '14 at 15:20

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.