0
$\begingroup$

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!

2 Answers 2

4

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

  • 0
    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!2012-08-05
  • 0
    See the additions above...2012-08-05
  • 0
    Thank you very much! This was really helpful! :)2012-08-05
1

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

  • 0
    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!2012-08-05
  • 0
    Hm, even when I try to solve this equation, I still get $n = 33$ steps in my first calculation :(2012-08-05
  • 0
    @Kristian: Sorry, there was a sign error; I've corrected it.2012-08-05
  • 0
    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. . .2012-08-05
  • 0
    @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.2012-08-05
  • 0
    Joriki: What I mean is that I start the iterations with $x_0$ again - only this time I choose to look at the error magnitude. When combined with copper.hat's approach below, we get the correct answer of 40 iterations in total.2012-08-05
  • 0
    @Kristian: I see. By the way, you don't have to ping me under my own answer since I get notified of any comments under it anyway; but if you do want to ping someone (under a post that isn't theirs), you need to put an @ in front of the user name.2012-08-05
  • 0
    Thanks a lot for the tip! I wasn't aware of the use of @. I will remember this from now on :)2012-08-05
  • 0
    @Kristian: You're welcome. And you were right to switch the accepted answer.2012-08-05
  • 0
    @Jorki: Yeah, I felt a bit guilty after having already marked your answer as the correct one, but I guess it is the right thing to do. But I really appreciate your efforts too. Thank you very much!2012-08-05
  • 0
    Sorry, didn't mean to edge in. The 'restart' is presumably to switch the analysis from the so-called linear convergence to the so-called quadratic convergence.2012-08-05
  • 0
    @copper.hat: Yes, I also assumed so.2012-08-05
  • 0
    @Kristian: What threw me off was that the hint said to "restart Newton's algorithm", not to restart its analysis. If I understand correctly now, the idea is to apply Newton's algorithm in the usual way for $40$ steps and apply two different kinds of analysis to these steps.2012-08-06
  • 0
    @joriki: Yes, the problem was phrased somewhat awkwardly.2012-08-06