Limitations of newton rapson's method
Answers
The Newton-Raphon method is an iterative approach to finding the roots of some differentiable function f(x). That is, it’s a method for approximating x∗ such that f(x∗)=0. The method is advantageous, because it is simple to implement, and when it works, it approaches x∗ quadratically (that is, if the approximation xn has k correct digits, the next approximation will have roughly 2k correct digits), and is relatively efficient. It can be formulated for differentiable functions that map from Rn→R, and some other cases as well. The moral of the method is that it follows the local gradient of the function towards a root.
The method for f:R→R goes as follows:
Choose x0 near x∗. You can do this by some bounding method, such as checking that sgn(f(x+ϵ))=−sgn(f(x−ϵ)), for some sufficiently small positive ϵ.
Given xn, compute xn+1=xn−f(xn)f′(xn).
Terminate when |f(xn)| is sufficiently small for your purposes.
The method can fail in a few ways.
You might choose x0 outside the basin of attraction for the root x∗ you wish to approximate, and you’ll converge to another root instead.
You might choose x0 such that for some iteration xn, |f′(xn)|≪1, which will result in problem 1, or f′(xn)=0, in which case the method fails entirely.
You might choose x0 in the basin of attraction of a fixed point of Fk(x), where F(x)=x−f(x)f′(x), and Fk(x) indicates that the map F is applied k>1 times to x.
An example of the third failure can occur with functions such as f(x)=x(x2−a2), where a≠0. Some choices of x0 can result in xn converging to one value for n even, and to a different value for n odd, because the gradient at xn “overshoots” the root in the middle and results (for this function) in a point xn+1≈−xn, which also overshoots so that xn+2≈xn. More complicated functions can result in longer periods of the map F.