Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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 at 16:54
1  
Some examples are given by lhf in answering this question –  Ross Millikan Mar 25 at 16:55

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
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 at 17:14
1  
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 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)?

share|improve this answer
    
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 at 17:07
    
In fact, some several trips around the sun ago, I recall this exact example being on my numerical analysis final exam. –  Arkamis Mar 25 at 17:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.