1

If root is very near to the max/min, what happens with Newton Raphson method? Does it diverge? Or converges slowly? I know if some iteration involves a stationery point then we can not go further. But is there a possiblity that even in such a case we can avoid the stationery point?

Jacob
  • 500
  • Since your question almost addresses the problem of root multiplicty, I suggest you have a look at https://mat.iitm.ac.in/home/sryedida/public_html/caimna/transcendental/iteration%20methods/accelerating%20the%20convergence/mrac.html – Claude Leibovici Mar 18 '15 at 09:36

2 Answers2

1

It's difficult to answer generally. Firs of all, the Newton-Raphson method convergence depends on the interval in which you look for the solution. If a root is of first degree, and close to a min/max point, then convergence depends on the starting point you consider, i.e. if the starting point is or not between the root and the stationary point.

When the root is double i.e. $f'(x_0) = 0 $, in general, this method converges as the bisection one. However when the derivative varies a lot around the root the convergence is not garanteed, and could be better to use other algorithms, like this.

Oscar
  • 381
1

To add to the description of Oscar: The typical scenario is captured by the equation $f(x)=x^2+a$ where $a$ can be $-ε,0,ε$.

From far away these three functions look the same, also for the Newton method, so that the steps will differ only insignificantly. Using the case $a=0$ one gets $x_+=x-f(x)/f'(x)=x/2$.

Only very close to $x=0$ will the method see a difference. In the case of $f(x)=x^2-ε$, it will switch to quadratic convergence to one of the roots. The switching point might be so small that it does not appear in floating point computations. For $f(x)=x^2+ε$ the tangent close to the minimum will be close to horizontal and thus throw the iteration nearly randomly far away from $x=0$. For the case of a double root, both cases may happen.

In the case of higher degrees, the other roots of course also influence the non-local behavior. Some time ago I saw a counter example of the form $$ f(x)=((x+3)^2+ε^2)(x-3) $$ or similar with additional factors for complex roots that shows convincing convergence to $-3$ as in a double root and then in the last moment jumps to $+3$.

Lutz Lehmann
  • 126,666