# Thread: Numerical analysis, Newton's iteration

1. ## Numerical analysis, Newton's iteration

We're interested in solving $f(x)=x^2-a=0$ to get a value for $\sqrt a$, using Newton's iteration $x_{n+1}=\frac{1}{2} \left ( x_n+ \frac{a}{x_n} \right )$.
I must show that for any $x_0>0$, $x_n \geq \sqrt a$ holds.

I've tried algebraically to show the inequality but I failed in every attempts.
For instance if I can show that $x_{n-1} \left ( \frac{x_{n-1}}{2} -\sqrt a \right ) + a \geq 0$ then I'd be done.
Or equivalently if $\frac{1}{4} \left ( x_{n-1}^2 +\frac{2a}{x_{n-1}} + \frac{a^2}{x_{n-1}^2} \right ) \geq a$.
I have a strong feeling that I should use a well known inequality to show this straightforwardly, but I don't know which one.
I'd like some help. Thanks in advance.

2. You can try working backwards along with an induction.

For a base case, suppose that we have chosen $x_1> \sqrt{a}$. Now suppose that $x_n>\sqrt{a}$. We want to show that $x_{n+1}>\sqrt{a}$. But this is equivalent to showing

$\displaystyle \frac{1}{2}\left(x_n+\frac{a}{x_n}\right)> \sqrt{a}$, or
$\displaystyle \frac{1}{2}\left(x_n+\frac{a}{x_n}\right)- \sqrt{a}>0$, or
$\displaystyle \frac{a-2 \sqrt{a} x_n+x_n^2}{2 x_n}>0$, or
$\displaystyle a-2 \sqrt{a} x_n+x_n^2>0$

But it is easy to show the last inequality, because from the inductive hypothesis,

$\displaystyle a-2 \sqrt{a} x_n+x_n^2>a-2\sqrt{a}\sqrt{a}+\sqrt{a}^2=a-2a+a=0$

so this proves it.

3. Thank you for your help, however I have one question:
Originally Posted by roninpro
For a base case, suppose that we have chosen $x_1> \sqrt{a}$.
I do not choose $x_1$, I choose $x_0$. And it's not necessarily greater or equal than $\sqrt a$. What happens in that case?
I think your proof is valid when you choose $x_0$ such that $x_1$ happens to be $\geq \sqrt a$ while they ask a valid proof for any $x_0>0$.
What do you think?

4. Originally Posted by arbolis
Thank you for your help, however I have one question:

I do not choose $x_1$, I choose $x_0$. And it's not necessarily greater or equal than $\sqrt a$. What happens in that case?
I think your proof is valid when you choose $x_0$ such that $x_1$ happens to be $\geq \sqrt a$ while they ask a valid proof for any $x_0>0$.
What do you think?
You don't need to assume that $x_1>\sqrt a$. As roninpro showed, you need to prove that $\dfrac{a-2\sqrt ax_n+x_n^2}{2x_n}>0$. But the numerator is equal to $(\sqrt a-x_n)^2$, which is obviously positive. So you just need to check that the denominator $2x_n$ is positive, and that is very easily checked by induction.

5. Thanks for the clarification. I could solve it.

6. Originally Posted by arbolis
Thank you for your help, however I have one question:

I do not choose $x_1$, I choose $x_0$. And it's not necessarily greater or equal than $\sqrt a$. What happens in that case?
I think your proof is valid when you choose $x_0$ such that $x_1$ happens to be $\geq \sqrt a$ while they ask a valid proof for any $x_0>0$.
What do you think?
It would be all right to choose $x_0$ or $x_1$ - it is just a matter of indexing. For your other question, I glossed over this detail in my post, but it turns out that if you choose your initial term $0, you will have $x_1>\sqrt{a}$. So you could say that the initial term is larger than $\sqrt{a}$ without loss of generality.

7. Thanks roninpro, you're absolutely right.
I've shown the iteration is decreasing. Or maybe I should use the word "sequence" if I talk about $\{ x_n \}$. I also know that $\{x_n \} \geq \sqrt a$ for $n\geq 1$.
I must show that the iterations converge to $\sqrt a$. I'd like an idea.

8. Originally Posted by arbolis
Thanks roninpro, you're absolutely right.
I've shown the iteration is decreasing. Or maybe I should use the word "sequence" if I talk about $\{ x_n \}$. I also know that $\{x_n \} \geq \sqrt a$ for $n\geq 1$.
I must show that the iterations converge to $\sqrt a$. I'd like an idea.
If a decreasing sequence is bounded below then it converges. So you know that $x_n\to x$ as $n\to\infty$, for some value of $x$. To find $x$, let $n\to\infty$ in the equation $x_{n+1} = \frac12\bigl(x_n + \frac a{x_n}\bigr).$

9. Thank you Opalg, problem solved.