2
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – vonbrand Mar 25 '14 at 16:54
  • 2
    $\begingroup$ Some examples are given by lhf in answering this question $\endgroup$ – Ross Millikan Mar 25 '14 at 16:55
5
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – so.very.tired Mar 25 '14 at 17:14
  • 1
    $\begingroup$ 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. $\endgroup$ – 7raiden7 Mar 25 '14 at 17:18
  • 2
    $\begingroup$ -1: because the last sentence in the answer is not true as stated. For instance take $f(x)=x^2$, it has a root with multiplicity two at the origin, and the NR interation is $x_{n+1}=x_n/2$, which converges beautifully to the root, zero. $\endgroup$ – Martin Argerami Dec 2 '17 at 4:21
  • $\begingroup$ @MartinArgerami you're right, I've edited the answer, thanks for that! $\endgroup$ – 7raiden7 Dec 2 '17 at 10:39
10
$\begingroup$

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.

enter image description here

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.

enter image description here

|cite|improve this answer
$\endgroup$
  • $\begingroup$ +1: this gives rise to a new type of problem, i.e. find $x_0$ such that, say, $x_6 = x_0$. Having to actively hunt for examples that trigger a cycle will help students remember it far better than being presented with a standard case. Kind regards $\endgroup$ – Carl Christian May 22 '18 at 19:44
2
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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