How do I find the error of nth iteration in Newton's Raphson's method without knowing the exact root

Question

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?

Answer 1

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.

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.

Answer 2

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.

Answer 3

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.