# When does the Newton Raphson method fail?

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.
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.

-
The condition for the fixed iteration method to converge is far from that"simple. And if you look closely, Newton-Raphson is fixed-point iteration, just of a different function. – vonbrand Mar 25 '14 at 16:54
Some examples are given by lhf in answering this question – Ross Millikan Mar 25 '14 at 16:55

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)$;

• $f(\cdot)$ has a multiple root, i.e. with multiplicity greater than 1.

Hope it helps.

-
Hi, @7raiden7, thanks for the help. Although these are good points, and helped a lot, this still will not help me figure out in advance which $x_0$'s will cause convergence. for example, according to your first point, I can find myself picking some $x_0$, and on sheer luck (or, more accurately, bad luck) "step on a mine" - meaning stepping on an $x_k$ which satisfies $f'(x_k)=0$. and that's exactly what I wand to avoid. (the second point can help me decide to avoid the NR method altogether). – so.very.tired Mar 25 '14 at 17:14
Therefore you may want to check some modified NR method. I've never gone through that, but I guess that for you should pose a tolerance for $f'(x_n)$, like a flux limiter. Unfortunately this is a very tough field, it is very far from being simple. I recommend you to read some paper about fixed point theory/numerical root finding. You should also consider reducing the accuracy in favour of more stability, i.e. going for the bisection method or affine ones. – 7raiden7 Mar 25 '14 at 17:18

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)?

-
yes, I understand the geometry implication. that alone made me wonder about the unexpected behavior of an initial $x_0$. – so.very.tired Mar 25 '14 at 17:07
In fact, some several trips around the sun ago, I recall this exact example being on my numerical analysis final exam. – Emily Mar 25 '14 at 17:21

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.

-