# Newton's method - determine accuracy in calculation

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!

-

Since $f$ is convex, you can show that if $x_0>1$ then $x_n \geq 1$ for all $n$. So we can bound the term $\frac{1}{x_n} \leq 1$. The Newton update for $f$ is $x_{n+1} = \frac{1}{2} (x_n + \frac{1}{x_n})$. So we have the bound $x_{n+1} \leq \frac{1}{2} x_n + \frac{1}{2}$. Working through the details gives $x_n \leq \frac{1}{2^n} x_0 + \frac{1}{2^n} + \cdots + \frac{1}{2} = \frac{1}{2^n} (x_0-1) + 1$. To estimate the number of iterations to get an error of less than 1. we want to find the smallest $n$ such that $2>\frac{1}{2^n} (x_0-1) + 1$, or equivalently, $n > \log_2 (x_0-1) \approx 33.2$. Hence, using this estimate, it will take (assuming I have made no mistakes) 34 iterations to get within an error of 1.

This is an elaboration on the bound above: Since $x_{n+1} \leq \frac{1}{2} x_n + \frac{1}{2}$, we have $x_{1} \leq \frac{1}{2} x_0 + \frac{1}{2}$. For the induction step, suppose $x_n \leq \frac{1}{2^n} x_0 + \frac{1}{2^n} + \cdots + \frac{1}{2}$. Then we have $x_{n+1} \leq \frac{1}{2} x_n + \frac{1}{2} \leq \frac{1}{2} (\frac{1}{2^n} x_0 + \frac{1}{2^n} + \cdots + \frac{1}{2}) + \frac{1}{2} = \frac{1}{2^{n+1}} x_0 + \frac{1}{2^{n+1}} + \cdots + \frac{1}{2}$, hence the formula is true for all $n$.

Summing the geometric series, we have $\frac{1}{2^n} + \cdots + \frac{1}{2} = \frac{1}{2}(\frac{1-\frac{1}{2^n}}{1-\frac{1}{2}}) = 1-\frac{1}{2^n}$, which gives $x_n \leq \frac{1}{2^n} x_0 + \frac{1}{2^n} + \cdots + \frac{1}{2} = \frac{1}{2^n} x_0 + 1-\frac{1}{2^n} = \frac{1}{2^n} (x_0-1) + 1$.

-
Thanks a lot! This is most likely a correct approach here. Can I just ask one question? I don't quite see how you get that $\frac{1}{2^n}x_0 + \frac{1}{2^n} + \cdot \cdot \cdot + \frac{1}{2} = \frac{1}{2^n}(x_0 - 1) + 1$. I would be very grateful if you could show how you get this. Other than that, I understand everything in your reasoning. Thanks again! – Kristian Aug 5 '12 at 21:40
See the additions above... – copper.hat Aug 5 '12 at 22:08
Thank you very much! This was really helpful! :) – Kristian Aug 5 '12 at 22:13

Your equations $x_1=x_0/2$ and $x_2=x_1/2$ are incorrect. Applying Newton's method to $f(x)=x^2-1$ yields

$$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}=x_n-\frac{x_n^2-1}{2x_n}=x_n-\frac{x_n}2+\frac1{2x_n}=\frac{x_n}2+\frac1{2x_n}\ne\frac{x_n}2\;.$$

-
Ah. Thanks a lot. Yeah, I only solved it on my calculator, and since the answers appeared to be halved every time, I assumed this would be correct. I should have definitely been more careful here! – Kristian Aug 5 '12 at 20:14
Hm, even when I try to solve this equation, I still get $n = 33$ steps in my first calculation :( – Kristian Aug 5 '12 at 20:20
@Kristian: Sorry, there was a sign error; I've corrected it. – joriki Aug 5 '12 at 20:33
Thanks. I have trouble finding a general term involving only $x_n$ and $x_0$ here though. I suppose I could just run this through my Newton algorithm in MatLab, but I kinda feel like I'm cheating if I do it. . . – Kristian Aug 5 '12 at 20:40
@Kristian: I'm afraid I don't understand what you mean by "restarting" the algorithm. If I just apply it to $10^{10}$, I get within $10^{-8}$ of $1$ after $37$ steps. – joriki Aug 5 '12 at 21:33