Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 7 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.