Results 1 to 9 of 9

Math Help - Numerical analysis, Newton's iteration

  1. #1
    MHF Contributor arbolis's Avatar
    Joined
    Apr 2008
    From
    Teyateyaneng
    Posts
    1,000
    Awards
    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor arbolis's Avatar
    Joined
    Apr 2008
    From
    Teyateyaneng
    Posts
    1,000
    Awards
    1
    Thank you for your help, however I have one question:
    Quote Originally Posted by roninpro View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by arbolis View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor arbolis's Avatar
    Joined
    Apr 2008
    From
    Teyateyaneng
    Posts
    1,000
    Awards
    1
    Thanks for the clarification. I could solve it.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    Quote Originally Posted by arbolis View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor arbolis's Avatar
    Joined
    Apr 2008
    From
    Teyateyaneng
    Posts
    1,000
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by arbolis View Post
    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).
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor arbolis's Avatar
    Joined
    Apr 2008
    From
    Teyateyaneng
    Posts
    1,000
    Awards
    1
    Thank you Opalg, problem solved.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Numerical Analysis - Newton's Forward Difference
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: October 23rd 2011, 07:28 PM
  2. Numerical Analysis - Fixed Point Iteration
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: October 10th 2011, 01:19 PM
  3. Replies: 6
    Last Post: December 27th 2010, 11:17 PM
  4. Numerical Analysis: Newton's Method Problem
    Posted in the Calculus Forum
    Replies: 1
    Last Post: January 31st 2009, 04:39 PM
  5. Newton's Method: Numerical Analysis
    Posted in the Advanced Applied Math Forum
    Replies: 3
    Last Post: June 12th 2008, 02:33 PM

/mathhelpforum @mathhelpforum