From: kovarik@mcmail.cis.McMaster.CA (Zdislav V. Kovarik)
Subject: Re: Newton-Raphson question.
Date: 22 Mar 1999 13:37:37 -0500
Newsgroups: sci.math
Keywords: Examples of failure of Newton's method
In article ,
Fredrik Conradson wrote:
>I'm implementing a solver for non-linear systems using the Newton-Raphson
>method and I have a question: Does this method always converge to a root
>regardless of the inital-values?
>
>thanks for any help!
>Fredrik
>conne@mindless.com
It's a potential disaster area, even in single variable. It helps if you
sketch the graphs and the effect of initial gusses.
Example 1. f(x) = x^3 - 5*x
Starting with x_0 = 1, you will get into a 2-cycle {1, -1 , -1, ...}
This cycle is unstable, and starting nearby may lead to hopping back and
forth before settling near one of the three roots. And you may not know
(because of round-off) where you land.
Example 2. f(x) = x^3 - 2*x + 2
Starting in the interval [-0.1, 0.1] , you will get into a stable
asymptotic 2-cycle, and very quickly so (used as an example by S. Smale).
Of course, there is a negative root to which Newton's method will
converge if started, say, to the left from the root.
Example 3 . f(z) = z^3 - 1 (z complex, equation f(z)=0 can be re-written
as a real system).
The regions of attraction have boundaries that puzzled Cayley because he
did not have the graphical or topological machinery. These boundaries,
placed symmetrically around the straight lines
theta=2*k*pi/3, k in {-1, 0, 1}
were later identified as fractals. If you start at some points of that
boundary set, the iterations will wander around without converging
anywhere.
Hope it helps, ZVK(Slavek).