# Numerical analysis, Newton's iteration

• Mar 25th 2011, 09:23 PM
arbolis
Numerical analysis, Newton's iteration
We're interested in solving $\displaystyle f(x)=x^2-a=0$ to get a value for $\displaystyle \sqrt a$, using Newton's iteration $\displaystyle x_{n+1}=\frac{1}{2} \left ( x_n+ \frac{a}{x_n} \right )$.
I must show that for any $\displaystyle x_0>0$, $\displaystyle 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 $\displaystyle x_{n-1} \left ( \frac{x_{n-1}}{2} -\sqrt a \right ) + a \geq 0$ then I'd be done.
Or equivalently if $\displaystyle \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.
• Mar 25th 2011, 10:08 PM
roninpro
You can try working backwards along with an induction.

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

$\displaystyle \displaystyle \frac{1}{2}\left(x_n+\frac{a}{x_n}\right)> \sqrt{a}$, or
$\displaystyle \displaystyle \frac{1}{2}\left(x_n+\frac{a}{x_n}\right)- \sqrt{a}>0$, or
$\displaystyle \displaystyle \frac{a-2 \sqrt{a} x_n+x_n^2}{2 x_n}>0$, or
$\displaystyle \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 \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.
• Mar 26th 2011, 10:51 AM
arbolis
Thank you for your help, however I have one question:
Quote:

Originally Posted by roninpro
For a base case, suppose that we have chosen $\displaystyle x_1> \sqrt{a}$.

I do not choose $\displaystyle x_1$, I choose $\displaystyle x_0$. And it's not necessarily greater or equal than $\displaystyle \sqrt a$. What happens in that case?
I think your proof is valid when you choose $\displaystyle x_0$ such that $\displaystyle x_1$ happens to be $\displaystyle \geq \sqrt a$ while they ask a valid proof for any $\displaystyle x_0>0$.
What do you think?
• Mar 26th 2011, 11:27 AM
Opalg
Quote:

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

I do not choose $\displaystyle x_1$, I choose $\displaystyle x_0$. And it's not necessarily greater or equal than $\displaystyle \sqrt a$. What happens in that case?
I think your proof is valid when you choose $\displaystyle x_0$ such that $\displaystyle x_1$ happens to be $\displaystyle \geq \sqrt a$ while they ask a valid proof for any $\displaystyle x_0>0$.
What do you think?

You don't need to assume that $\displaystyle x_1>\sqrt a$. As roninpro showed, you need to prove that $\displaystyle \dfrac{a-2\sqrt ax_n+x_n^2}{2x_n}>0$. But the numerator is equal to $\displaystyle (\sqrt a-x_n)^2$, which is obviously positive. So you just need to check that the denominator $\displaystyle 2x_n$ is positive, and that is very easily checked by induction.
• Mar 26th 2011, 01:06 PM
arbolis
Thanks for the clarification. I could solve it.
• Mar 26th 2011, 03:12 PM
roninpro
Quote:

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

I do not choose $\displaystyle x_1$, I choose $\displaystyle x_0$. And it's not necessarily greater or equal than $\displaystyle \sqrt a$. What happens in that case?
I think your proof is valid when you choose $\displaystyle x_0$ such that $\displaystyle x_1$ happens to be $\displaystyle \geq \sqrt a$ while they ask a valid proof for any $\displaystyle x_0>0$.
What do you think?

It would be all right to choose $\displaystyle x_0$ or $\displaystyle 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 $\displaystyle 0<x_0<\sqrt{a}$, you will have $\displaystyle x_1>\sqrt{a}$. So you could say that the initial term is larger than $\displaystyle \sqrt{a}$ without loss of generality.
• Mar 26th 2011, 05:35 PM
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 $\displaystyle \{ x_n \}$. I also know that $\displaystyle \{x_n \} \geq \sqrt a$ for $\displaystyle n\geq 1$.
I must show that the iterations converge to $\displaystyle \sqrt a$. I'd like an idea.
• Mar 26th 2011, 11:48 PM
Opalg
Quote:

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 $\displaystyle \{ x_n \}$. I also know that $\displaystyle \{x_n \} \geq \sqrt a$ for $\displaystyle n\geq 1$.
I must show that the iterations converge to $\displaystyle \sqrt a$. I'd like an idea.

If a decreasing sequence is bounded below then it converges. So you know that $\displaystyle x_n\to x$ as $\displaystyle n\to\infty$, for some value of $\displaystyle x$. To find $\displaystyle x$, let $\displaystyle n\to\infty$ in the equation $\displaystyle x_{n+1} = \frac12\bigl(x_n + \frac a{x_n}\bigr).$
• Mar 27th 2011, 07:46 AM
arbolis
Thank you Opalg, problem solved.