Results 1 to 9 of 9

Thread: 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
    10
    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
    10
    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: Oct 23rd 2011, 07:28 PM
  2. Numerical Analysis - Fixed Point Iteration
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: Oct 10th 2011, 01:19 PM
  3. Replies: 6
    Last Post: Dec 27th 2010, 11:17 PM
  4. Numerical Analysis: Newton's Method Problem
    Posted in the Calculus Forum
    Replies: 1
    Last Post: Jan 31st 2009, 04:39 PM
  5. Newton's Method: Numerical Analysis
    Posted in the Advanced Applied Math Forum
    Replies: 3
    Last Post: Jun 12th 2008, 02:33 PM

/mathhelpforum @mathhelpforum