# Newton's method for square roots - digit precision (exercise from Cheney's Numerical Analysis)

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}<e_n^2$. 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.

-

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} <x_n< \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.

-