Numerical analysis, Newton's iteration

Printable View

March 25th 2011, 09:23 PM
arbolis

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.
March 25th 2011, 10:08 PM
roninpro

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.
March 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 $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?
March 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 $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.
March 26th 2011, 01:06 PM
arbolis

Thanks for the clarification. I could solve it.
March 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 $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<x_0<\sqrt{a}$ , you will have $x_1>\sqrt{a}$ . So you could say that the initial term is larger than $\sqrt{a}$ without loss of generality.
March 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 $\{ 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.
March 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 $\{ 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).$
March 27th 2011, 07:46 AM
arbolis

Thank you Opalg, problem solved.