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 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!

share|improve this question
add comment

2 Answers 2

up vote 3 down vote accepted

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$.

share|improve this answer
    
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
add comment

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\;.$$

share|improve this answer
    
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
show 9 more comments

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.