Re: Why does Newton method converge?
From: Martin Brown (|||newspam|||_at_nezumi.demon.co.uk)
Date: 10/27/04
- Previous message: Hiu Chung Law: "Approximation of the ratio of Meijer G function"
- In reply to: Peter Spellucci: "Re: Why does Newton method converge?"
- Messages sorted by: [ date ] [ thread ]
Date: Wed, 27 Oct 2004 17:07:24 +0100
In message <clobtm$vf$1@fb04373.mathematik.tu-darmstadt.de>, Peter
Spellucci <spellucci@fb04373.mathematik.tu-darmstadt.de> writes
>
>In article <1098729246.821792@athnrd02>,
> Ioannis <morpheus@olympus.mons> writes:
> >Given y and f(z)=z*exp{c*exp(z)}, the following algorithm calculates a
> >All the references i've consulted, say that Newton's algorithm may not
> >work, when f'(r)=0.
> >
> > My question is not why Newton's Method fails when this happens, rather
> >why IT WORKS in the above case, when I try it at a branch point, where I
> >know that f'(bp)=0.
> >So the algorithm found a root, although f'(bp)=0. How can this be explained?
> >
> >Thanks much in advance,
> >--
> >I. N. Galidakis --- http://users.forthnet.gr/ath/jgal/
You get linear convergence provided that certain conditions are met.
Newton's method should normally give quadratic convergence.
>in one dimension Newtons method converges also for multiple roots, but linearly
>only. since also numerically the function decays much faster than the
>derivative
>to zero, even under roundoff you may obtain reasonable accuracy
>you can see this easily if you consider the iteration function
>
> phi(x)=x-f(x)/f'(x)
>and its derivative at the zero x*.
>if x* is k-fold, then
> f(x)=(x-x*)^k*f^{(k)}(x*)/k!*(1+O(x-x*))
> f'(x)=(x-x*)^(k-1)*f^{(k)}(x*)/(k-1)!*(1+O(x-x*))
>hence
> phi'(x*)=1-1/k
>and you have linear convergence.
>there is no analogy in higher dimensions
Also it is still quite possible to have unfortunate choices of starting
guess where the gradient becomes very small when the error in the
function is still quite large. The resulting step then bounces way past
the solution and in some awkward cases grows exponentially.
One classic that exhibits bad behaviour is Keplers equation;
f(E) = M + e.sin(E) - E
f'(E) = e.cos(E) - 1
When e ~ 1 and M ~ 0 this gives Newton's method a hard time for some
fairly reasonable initial guesses for E. ISTR Halley (of comet fame)
devised his refinement using the second derivative to ameliorate this
problem. ( e = 0.9999, M = 0.3, initial guess E = M should
demonstrate)..
Regards,
-- Martin Brown
- Previous message: Hiu Chung Law: "Approximation of the ratio of Meijer G function"
- In reply to: Peter Spellucci: "Re: Why does Newton method converge?"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
|
