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.
 A: 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.
