5
$\begingroup$

In our calculus class, we were introduced to the numerical approximation of root by Newton Raphson method. The question was to calculate the root of a function up to nth decimal places.

Assuming that the function is nice and our initial value does lead to convergence. Our teacher terminated the algorithm when the two successive iterations had the same first n digits and told us that the the approximation was correct up to the nth digit!

I feel that the termination step is valid if $f(x_n)$ and $f(x_{n+1})$ has different signs but my teacher disagrees. How do I sort this out??

Futhermore how do I find the error in the nth iteration without knowing the exact root?

$\endgroup$
5
$\begingroup$

Your teacher's example cannot work in general as I present a counter example below. Nonetheless, I think that your teacher's approach is a reasonable way to explain the intuition behind what happens in a typical case, provided that the proper caveats are given.

I think a more reasonable stopping condition, for programming purposes, is to iterate until the value of $f$ is very small. If the first derivative is relatively large in a neighborhood of the last iterate, this might be enough to prove that there is definitively a root nearby. Of course, Christian Blatter has already provided sufficient conditions.

For a counter example, let's suppose that $$f(x) = x(x-\pi)^2 + 10^{-12}.$$ Then, the Newton's method iteration function is $$N(x) = x-f(x)/f'(x) = x-\frac{x (x-\pi)^2+10^{-10}}{3 x^2-4\pi x+\pi ^2}$$ and if we iterate $N$ 20 times starting from $x_0=3.0$, we get $$ 3., 3.07251, 3.10744, 3.12461, 3.13313, 3.13736, 3.13948, 3.14054, \ 3.14106, 3.14133, 3.14146, 3.14153, 3.14156, 3.14158, 3.14158, \ 3.14159, 3.14159, 3.14159, 3.14159, 3.14159, 3.14159 $$ Thus, your teacher's method implies there is a root at $x=3.14159$ when, of course, there is no root near here. There is, however, a root near zero to which the process eventually converges after several thousand iterates.

To place this in a broader context, let's examine the basins of attraction for this polynomial in the complex plane. There are three complex roots, one just to the left of zero and two at $\pi\pm\varepsilon i$ where $\varepsilon$ is a small positive number. In the picture below, we shade each complex initial seed depending on which of these roots Newton's method ultimately converges.

enter image description here

Now, it is a theorem in complex dynamics that, whenever two of these basins meet, there are points of the third basin arbitrarily near by. As a result, there is definitely a number whose decimal expansion starts with $3.14159$ that eventually converges to the root near zero under iteration of Newton's method.

$\endgroup$
  • $\begingroup$ I think that what the teacher is saying is that when two iterations have the same numbers of digits equal then they have the same digits equal to the root. In this case, suppose we are looking for $4$ digits. Then at step 16 we can stop, and in fact we are getting 3.1415... To prove the teacher wrong we would need an iteration that starts getting close together at some point, but that eventually makes a jump and converges somewhere else. $\endgroup$ – Pp.. Jan 27 '15 at 13:33
  • $\begingroup$ I would try with a cubic so that there is an inflexion point between the initial approximation and the actual root. $\endgroup$ – Pp.. Jan 27 '15 at 13:35
  • $\begingroup$ @Pp.. Thanks for the suggestion, though I disagree. Why does the sequence need to move on? The teacher erroneously concludes that there is a root when there is none. That's not to say that your desire to find an example where the sequence moves on is uninteresting and it is certainly sufficient - it's just not necessary. I've modified my example to include a situation where there is another root. $\endgroup$ – Mark McClure Jan 27 '15 at 13:45
  • 1
    $\begingroup$ I didn't notice that you put $+10^{-12}$ instead of $-10^{-12}$. It is true that in a sense, this could be considered a counterexample. But, although some people do it, one shouldn't start Newton's with an interval in which there is no root. I think the more essential problem with the teacher stopping condition is that it assumes that is some iterations are close together they are getting close to the root. $\endgroup$ – Pp.. Jan 27 '15 at 13:51
  • 1
    $\begingroup$ There is something interesting, though. You see, the teacher could replay: "But when the iterations cluster near 3.1415, this is a good approximation of the complex roots. So, this doesn't prove me wrong." Do you know if it is possible to make the iterations converge to one root after clustering in some other place that is not near a root (complex or real)? I don't know the answer to that question. $\endgroup$ – Pp.. Jan 27 '15 at 15:28
3
$\begingroup$

To properly start Newton's method we begin by first localizing the root, finding a compact interval $I$ that contains it, ideally that contains only that root. Then we take the first approximation in that interval. We can say that the initial error $e_0$ is smaller than the length of the interval.

Now we can use the estimation of the $n$-th error

$$e_{n+1}\leq Me_n^2$$ where $M=\frac{1}{2}\sup_I\frac{f''(x)}{f'(x)}$. If you begin by putting $e_0=|I|$ (instead of the actual unknown initial error $\epsilon_0$) you can stop for sure when this recurrence gives you $e_{n+1}$ smaller than the precision you want.

The stopping condition that your teacher used is not correct in general.

$\endgroup$
  • $\begingroup$ How can I find $e_0$ without knowing the root?? $\endgroup$ – curious33 Jan 27 '15 at 13:06
  • $\begingroup$ @curious33 You don't use the actual $e_0$ for the recurrence, we use the length of the interval $I$ where we localized the root, and where we proved the algorithm converges. $\endgroup$ – Pp.. Jan 27 '15 at 13:08
  • 1
    $\begingroup$ However it would be great if I am able to find a counter example to convince my teacher/ $\endgroup$ – curious33 Jan 27 '15 at 13:11
  • $\begingroup$ +1 for the recursive formula on the error bound. In the real case, Newton's method is often combined with a bracketing technique like this. It's not quite clear how to extend that to the complex case, however. $\endgroup$ – Mark McClure Jan 27 '15 at 13:26
  • $\begingroup$ @curious33 If you like this response, which you seem to indicate, you should upvote it. I think you can do that, now that your reputation exceeds 15. $\endgroup$ – Mark McClure Jan 27 '15 at 13:28
3
$\begingroup$

This is a complement to Pp.'s answer.

Newton's method converges, and with the rate given in Pp.'s answer, only if certain assumptions are met. In simple numerical examples these assumptions are usually not tested in advance. Instead, one chooses a reasonable starting point $x_0$ and will then soon find out whether the process converges to the intended root.

Simple sufficient conditions are the following: You have made out an interval $I:=[a,b]$ such that $f(a)f(b)<0$, and that $f'(x)\ne0$, $f''(x)\ne0$ for all $x\in I$. Depending on the signs of $f$, $f'$, $f''$ at the endpoints of $I$ you should chose either $x_0:=a$ or $x_0:=b$ and then can be sure that the $x_n$ converge to the unique root $\xi\in I$. E.g., if $f(b)>0$, $f'(x)>0$ and $f''(x)>0$ $\>(x\in I)$ you should choose $x_0:=b$. Note that in this case $x_n>\xi$ for all $n$ (draw a figure!), so that the lower estimate $a$ of the root is never improved.

$\endgroup$
-3
$\begingroup$

By the quadratic convergence of the algorithm, the corrections decrease very quickly, so that the error is much smaller than the last correction. Usually, you can stop iterations when the latter falls below your tolerance.

$\endgroup$
  • $\begingroup$ Why this downvote ? $\endgroup$ – Yves Daoust Jan 27 '15 at 16:45

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.