6
$\begingroup$

I would greatly appreciate some help for this exercise in Kincaid and Cheney's Numerical Analysis: "apply Newton's method to $f(x)=x^2-r$ (where r>0). Prove that if $x_n$ has $k$ correct digits after the decimal point, then $x_{n+1}$ has at least $2k-1$ correct digits, as long as $r>0.006$ and $k\geq 1$".

In general, if f'' is continuous and $r$ is a simple root of $f$ it holds that e_{n+1}=x_{n+1}-\sqrt{r}=\frac{1}{2}\frac{f''(\xi_n)}{f'(x_n)}e_n^2, where $\xi_n$ is some number between $x_n$ and $\sqrt{r}$.

I suppose that the condition they're asking for is achieved (but I'm not sure) when $e_{n+1}. Applying the formula above gives $e_{n+1}=\frac{1}{2x_n}e_n^2<\frac{1}{2r}e_n^2$; this seems enough to find $r$. I don't know where the $0.006$ comes from.

On the other hand, the textbook suggests to use $x_{n+1}=\frac{1}{2}(x_n+\frac{r}{x_n}).$ This expression can be transformed into one involving $e_{n+1}$ and $e_n$ but I don't know how to do it so that it would be more useful than the former bound.

Thanks in advance for any help given.

1 Answers 1

10

Please don't be deterred by the length of the answer. I did not have the time to make it shorter!

I take it that you are supposed to assume and use the general result you quote, beginning with "In general."

One really have said what one means by $e_k$. From the expression you quote, $e_n$ must be $x_n-\sqrt{r}$.

So let's start to work with the estimate. In our case, we have $f(x)=x^2-r$. So f'(x)=2x and f''(x)=2. Thus for square roots the general error estimate simplifies to $e_{n+1}=\frac{1}{2}\frac{2}{2x_n}e_n^2=\frac{1}{2x_n}e_n^2$

Finally, you want to obtain some control over the term $1/(2x_n)$. We want to show that this is not big.

Suppose now that $x_n$ has $k$ correct digits after the decimal point. So $|e_n| <0.5\times 10^{-k}$. That means that $\sqrt{r}-0.5\times 10^{-k} We want to show that $1/(2x_n)$ is not too large. If we are pessimistic, we assume that $x_n$ is even smaller than the estimate above allows. So if in our error formula we take $x_n=\sqrt{r}-0.5\times 10^{-k}$, we will get an estimate of the error that is as pessimistic as possible.
We conclude that $|e_{n+1}|<\frac{1}{|2\sqrt{r}-10^{-k}|}(0.5)^2(10^{-2k})$

Now we ask: what is the smallest that $|2\sqrt{r}-10^{-k}|$ could possibly be? That would happen if $\sqrt{r}$ were as small as possible, and $10^{-k}$ were as big as possible. Recall that $r >.006$, so $\sqrt{r}>0.077$. Recall also that $k\ge 1$, so $10^{-k}\le 1/10$. It follows (calculator) that $\frac{1}{|2\sqrt{r}-10^{-k}|} <\frac{1}{0.154-0.1} <18.52$ We conclude that $|e_{n+1}|<(18.52)(0.5)^2(10^{-2k}) <0.464 \times 10^{-(2k-1)}$ This estimate says that the estimate $x_{n+1}$ is correct to at least $2k-1$ decimal places.

We were as pessimistic as possible, given the information about $r$. You can see on closer analysis that the error behaves a little better if we start above $\sqrt{r}$ than if we start below. the reason we had to insist that $r$ not be too close to $0$ is that in that case, $1/(|2\sqrt{r}-10^{-k}|)$ could be large.