2

Find $x$ for which $x^2-2=0$ using the newton algorithm and $x_0 = 1.4$.

Then you get $x_{k+1} = x_k + \frac{1}{x_k} - \frac{x_k}{2}$.

How to show that you need 100 steps for 100 digits precision?

So I need to show for which $N$ it is $|x_N-\sqrt{2}| \leq 10^{-100}$ and therefore I am asked to show $$|x_k - \sqrt{2}|\leq\delta<0.1 \implies |x_{k+1}-\sqrt{2}|\leq \frac{\delta^2}{2}$$

Then it obviously follows that you need 100 steps, but I don't manage to show this..

fritz
  • 65
  • Why do you think you need $100$ steps? – Chris Eagle Feb 02 '13 at 16:45
  • If the lemma is shown it follows that the error falls quadratically and for the given $x_0$ it is $|x_0 - \sqrt{2}|<\frac{1}{10}$. If you go 100 steps then, using the Lemma you get $|x_{100}-\sqrt{2}|\leq \frac{10^{-100}}{2^{100}}$ – fritz Feb 02 '13 at 16:51
  • The behaviour of an error falling quadratically is $\delta^{2^N}$, not $\delta^N$. Here one needs about $6$ steps, not $100$. – Did Feb 02 '13 at 16:53
  • Hm.. okay.. so I got this wrong. But to show that it is 6 steps I still need to show the lemma? But isn't using it $20^{-6} > 10^{-100}$? – fritz Feb 02 '13 at 17:00

1 Answers1

2

Try to show that $|x_{k+1}-\sqrt2|\leqslant\frac12(x_k-\sqrt2)^2$ hence $|x_k-\sqrt2|\leqslant2\delta_k$ implies that $|x_{k+1}-\sqrt2|\leqslant2\delta_{k+1}$ with $\delta_{k+1}=\delta_k^2$.

Then note that $\delta_0\lt10^{-2}$ hence $\delta_k\leqslant10^{-2^{k+1}}$ for every $k$, in particular $2\delta_6\lt2\cdot10^{-128}$ ensures (slightly more than) $100$ accurate digits.

Did
  • 279,727