Results 1 to 4 of 4

Math Help - Algorithm

  1. #1
    Senior Member Sampras's Avatar
    Joined
    May 2009
    Posts
    301

    Algorithm

    Suppose we have

    start:  (x_0, y_0) with  x_0 < y_0 .

    step:  x_{n+1} = \frac{x_n+y_n}{2} ,  y_{n+1} = \sqrt{x_{n+1}y_n} . Find  \lim x_n and  \lim y_n .

    So consider  \frac{x_{n+1}}{y_{n+1}} = \sqrt{\frac{1+ x_n/y_n}{2}} . We know that  \cos \frac{\alpha}{2} = \sqrt{\frac{1- \cos \alpha}{2}} . Put  \alpha_n = \frac{x_n}{y_n} . Then  \cos \alpha_{n+1} = \cos \frac{\alpha_n}{2} . Now how would we get  \alpha_n ? Because taking inverse cosines, we get  \alpha_{n+1} = \frac{\alpha_n}{2} . So then  \alpha_{n} = \frac{\alpha_0}{2^n} . Thus  2^n \arccos \frac{x^n}{y^n} = \arccos \frac{x_0}{y_0} . From here, can we get the limit?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2008
    From
    France
    Posts
    1,458
    Quote Originally Posted by Sampras View Post
    Suppose we have

    start:  (x_0, y_0) with  x_0 < y_0 .

    step:  x_{n+1} = \frac{x_n+y_n}{2} ,  y_{n+1} = \sqrt{x_{n+1}y_n} . Find  \lim x_n and  \lim y_n .

    So consider  \frac{x_{n+1}}{y_{n+1}} = \sqrt{\frac{1+ x_n/y_n}{2}} . We know that  \cos \frac{\alpha}{2} = \sqrt{\frac{1- \cos \alpha}{2}} . Put  \alpha_n = \frac{x_n}{y_n} . Then  \cos \alpha_{n+1} = \cos \frac{\alpha_n}{2} . Now how would we get  \alpha_n ? Because taking inverse cosines, we get  \alpha_{n+1} = \frac{\alpha_n}{2} . So then  \alpha_{n} = \frac{\alpha_0}{2^n} . Thus  2^n \arccos \frac{x^n}{y^n} = \arccos \frac{x_0}{y_0} . From here, can we get the limit?
    No

    You can show by induction that (x_n)_n is increasing, (y_n)_n is decreasing and \forall n~x_n \leq y_n

    Starting from this you can show that (x_n)_n has a limit since it is increasing and majored by y_0. The same for (y_n)_n.

    Then you can show that (x_n)_n and (y_n)_n are adjacent since x_{n+1}- y_{n+1} = \frac{x_n-y_n}{2\:\left(1+\sqrt{\frac{2y_n}{x_n+y_n}}\right)  } \leq \frac{x_n-y_n}{4}

    Then you can show that (x_n)_n and (y_n)_n have the same limit l.

    You can see that 2^n \arccos \frac{x_n}{y_n} = \arccos \frac{x_0}{y_0} may be true but 2^n has infinite limit whereas \arccos \frac{x_n}{y_n} converges towards \arccos 1 = 0
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member Sampras's Avatar
    Joined
    May 2009
    Posts
    301
    Quote Originally Posted by running-gag View Post
    No

    You can show by induction that (x_n)_n is increasing, (y_n)_n is decreasing and \forall n~x_n \leq y_n

    Starting from this you can show that (x_n)_n has a limit since it is increasing and majored by y_0. The same for (y_n)_n.

    Then you can show that (x_n)_n and (y_n)_n are adjacent since x_{n+1}- y_{n+1} = \frac{x_n-y_n}{2\:\left(1+\sqrt{\frac{2y_n}{x_n+y_n}}\right)  } \leq \frac{x_n-y_n}{4}

    Then you can show that (x_n)_n and (y_n)_n have the same limit l.

    You can see that 2^n \arccos \frac{x_n}{y_n} = \arccos \frac{x_0}{y_0} may be true but 2^n has infinite limit whereas \arccos \frac{x_n}{y_n} converges towards \arccos 1 = 0
    And that limit would be  \frac{\sqrt{y_{0}^{2}-x_{0}^{2}}}{\arccos(x_0/y_0)} right?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2008
    From
    France
    Posts
    1,458
    Quote Originally Posted by Sampras View Post
    And that limit would be  \frac{\sqrt{y_{0}^{2}-x_{0}^{2}}}{\arccos(x_0/y_0)} right?
    Yes
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. algorithm
    Posted in the Advanced Applied Math Forum
    Replies: 3
    Last Post: January 19th 2010, 03:46 AM
  2. Algorithm
    Posted in the Advanced Math Topics Forum
    Replies: 7
    Last Post: November 22nd 2009, 08:11 AM
  3. algorithm
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: July 16th 2008, 02:29 PM
  4. Algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 27th 2008, 02:02 PM
  5. gcd algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 5th 2007, 12:47 AM

Search Tags


/mathhelpforum @mathhelpforum