I have almost managed to solve a problem (I think), but I am a bit unsure if my procedure is correct, and my answer is not quite the correct one. Would appreciate any input! The problem is as follows:
If Newton's method is used with $f(x) = x^2 - 1$ and $x_0 = 10^{10}$, how many steps are required to obtain the root with accuracy $10^{-8}$. Solve analytically, not experimentally. (Hint: restart Newton's algorithm when you know that $e_n < 1$).
OK. My solution is as follows:
If we have $x_0 = 10^{10}$, and we find, by using Newton's algorithm, that $x_1 = \frac{x_0}{2}$, and $x_2 = \frac{x_1}{2}$ (I tried this for the first few terms). Thus, we have that:
$x_{n+1} = \frac{x_0}{2^n}$
Using the hint, and knowing that the closest root is $x = 1$, and $e_n = x_n - r$, we want to find the first value value $x_n$ such that $|x_n - 1| < 1$. So we have $-2 < x_n < 2$. My next step is therefore:
$\frac{10^{10}}{2^n} < 2$.
$10^{10} < 2^{n+1}$
Solving this for $n$ yields:
$n > 32,2$.
So we must take $33$ steps to get to this point.
OK, now - again using the hint - we restart Newton's algorithm again. Set $n = 0$ again, and we now know that $e_0 < 1$. We have that:
$e_{n+1} = \frac{e_{n}^2}{2(e_{n} + 1)} < \frac{e_{n}^2}{2}$
Then:
$e_1 < \frac{e_{0}^2}{2} \leq \frac{1}{2}, e_2 < \frac{e_{1}^2}{2} \leq \frac{1}{2^3}, e_3 < \frac{e_{2}^2}{2} \leq \frac{1}{2^7}, etc$.
In general:
$e_{n} < \frac{1}{2^{2^{n} -1}}$
We want $e_n < 10^{-8}$, and this is found when $n = 6$. Thus we need to use a total of $33 + 6 = 39$ steps in total.
According to my book, however, the total number of steps should be $40$. So am I making a mistake here somwhere? If someone can see if my procedure is correct, and perhaps spot my mistake, I would be very, very grateful!