Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Convergence of the sequence from Heron's method.

  1. May 25, 2015 #1
    ##a_1=1##

    ##a_{n+1}=\frac{1}{2} ( a_{n} + \frac{b}{a_n} )##

    This should converge to ##\sqrt{b}## but I seem not to be able to prove this. Could someone give me a hint.
     
  2. jcsd
  3. May 25, 2015 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    First prove that a limit exists. Show this by proving (by induction) that the sequence (starting from ##a_2##) is nonincreasing and bounded below.
     
  4. May 26, 2015 #3
    One can define a new sequence [itex]\delta_1,\delta_2,\delta_3,\ldots[/itex] by setting [itex]\delta_n=a_n-\sqrt{b}[/itex], and then solve an equivalent recursion formula for [itex]\delta_{n+1}[/itex]. Proving [itex]\delta_n\to 0[/itex] can turn out more natural than proving the original claim directly.
     
  5. May 27, 2015 #4
    First we prove that any term that is given by the recursion formula is either larger or equal to ##\sqrt{b}##.

    ##\frac{1}{2}(a_n + \frac{b}{a_n}) \ge \sqrt{b}##
    This can be rewritten as :

    ##(a_n-\sqrt{b})^{2} \ge 0 ##

    Which is obviously always the case. To conclude, any term starting from ##a_2## is larger or equal to ##\sqrt{b}##

    Next we will look at when the succeeding term is non increasing:

    ##a_{n+1}=\frac{1}{2}(a_n + \frac{b}{a_n}) \le a_n ## ?

    ## a_n + \frac{b}{a_n} \le 2 a_n ##

    ##b \le a_n^{2} ##

    This means that as long as the previous term was above ##\sqrt{b}## the next one will be smaller. However I proved that from ##a_2## all the terms are above ##\sqrt{b}## which means that from ##a_2## on it is non decreasing and bounded from below by ##\sqrt{b}##.
     
  6. May 27, 2015 #5

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    That is correct. So now you've shown that ##(a_n)_n## is decreasing and bounded below, which means that it converges. Now we use a dirty trick to find the actual limit of ##(a_n)_n##. We have

    [tex]\lim_{n\rightarrow +\infty} a_n = \lim_{n\rightarrow +\infty} a_{n+1} = \lim_{n\rightarrow +\infty} \frac{1}{2}\left(a_n + \frac{b}{a_n}\right)[/tex]

    I'll let you do the rest.
     
    Last edited: May 27, 2015
  7. May 27, 2015 #6
    Wow that is indeed a dirty trick! However it clearly does follow from it, thanks a lot.
     
  8. May 28, 2015 #7
    It seems my advice wasn't useful for the precise requested task, but I insist that it can be useful for other purposes. For example here the sequence converges towards [itex]\sqrt{b}[/itex] at a rate that is faster than exponential, and that can be relevant for numerical purposes, but it wasn't yet proven by the used tricks.
     
    Last edited: May 28, 2015
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Convergence of the sequence from Heron's method.
  1. Sequence Convergence (Replies: 4)

Loading...