When does the Newton Raphson method fail?

Question

Can someone please tell me the conditions under which the Newton Raphson method will not converge?

I looked around online, and couldn't find a general way to determine convergence.

For example, for the Fixed Point iteration method, there is a simple way of determining: if we have $g(x_{n})=x_{n+1}$, then $|g'(x)|<1$ implies that the series $g$ will converge to its fixed point, but in the Newton Raphson method, It seems like it is totally depends on "luck", meaning if you were lucky enough to pick a "good" initial guess or not.

Answer 1

Since the NR method can be written as follows: $$ x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}, $$ it means that it cannot converge as soon as:

• $x_n$ is a local minimum/maximum of $f(\cdot)$;

Hope it helps.

Answer 2

Think geometrically about how the method works. We draw a tangent line to a curve. We follow that tangent down (or up) to the $x$-axis. Then, we jump up to the function at that point and repeat.

Now, what happens if the tangent line overshoots the root and sends us to a point on the function where the tangent line has the opposite slope? Can you visualize the ping-pong behavior?

What happens if the slope is very small (i.e. a flat tangent line)? What happens if the slope is very steep (i.e. a nearly vertical tangent line)?

Answer 3

To visualize geometrically what's going on, I will code an interactive diagram with GNU Dr. Geo (free software of mine) from where I can drag the initial value (the red dot) and see how the method converge or not.

For example $x \rightarrow cos x + x$, comes with some mines, but not $x \rightarrow cos x +1.1x$.

When you get close to a flat area, the tangent sends you far away, even further than your initial value.

Your best option is to get close to the root in an area without nul value of the derivative. I guess it is the tough part as it depends on the function. Visualizing can help.

This article explains how to code with Pharo+DrGeo this interactive diagram and the link with the Hero method from the classical period.