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
    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
    @joriki: Yes, the problem was phrased somewhat awkwardly.2012-08-06