Results 1 to 4 of 4

Thread: Algorithm

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

    Algorithm

    Suppose we have

    start: $\displaystyle (x_0, y_0) $ with $\displaystyle x_0 < y_0 $.

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

    So consider $\displaystyle \frac{x_{n+1}}{y_{n+1}} = \sqrt{\frac{1+ x_n/y_n}{2}} $. We know that $\displaystyle \cos \frac{\alpha}{2} = \sqrt{\frac{1- \cos \alpha}{2}} $. Put $\displaystyle \alpha_n = \frac{x_n}{y_n} $. Then $\displaystyle \cos \alpha_{n+1} = \cos \frac{\alpha_n}{2} $. Now how would we get $\displaystyle \alpha_n $? Because taking inverse cosines, we get $\displaystyle \alpha_{n+1} = \frac{\alpha_n}{2} $. So then $\displaystyle \alpha_{n} = \frac{\alpha_0}{2^n} $. Thus $\displaystyle 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: $\displaystyle (x_0, y_0) $ with $\displaystyle x_0 < y_0 $.

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

    So consider $\displaystyle \frac{x_{n+1}}{y_{n+1}} = \sqrt{\frac{1+ x_n/y_n}{2}} $. We know that $\displaystyle \cos \frac{\alpha}{2} = \sqrt{\frac{1- \cos \alpha}{2}} $. Put $\displaystyle \alpha_n = \frac{x_n}{y_n} $. Then $\displaystyle \cos \alpha_{n+1} = \cos \frac{\alpha_n}{2} $. Now how would we get $\displaystyle \alpha_n $? Because taking inverse cosines, we get $\displaystyle \alpha_{n+1} = \frac{\alpha_n}{2} $. So then $\displaystyle \alpha_{n} = \frac{\alpha_0}{2^n} $. Thus $\displaystyle 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 $\displaystyle (x_n)_n$ is increasing, $\displaystyle (y_n)_n$ is decreasing and $\displaystyle \forall n~x_n \leq y_n$

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

    Then you can show that $\displaystyle (x_n)_n$ and $\displaystyle (y_n)_n$ are adjacent since $\displaystyle 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 $\displaystyle (x_n)_n$ and $\displaystyle (y_n)_n$ have the same limit l.

    You can see that $\displaystyle 2^n \arccos \frac{x_n}{y_n} = \arccos \frac{x_0}{y_0}$ may be true but $\displaystyle 2^n$ has infinite limit whereas $\displaystyle \arccos \frac{x_n}{y_n}$ converges towards $\displaystyle \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 $\displaystyle (x_n)_n$ is increasing, $\displaystyle (y_n)_n$ is decreasing and $\displaystyle \forall n~x_n \leq y_n$

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

    Then you can show that $\displaystyle (x_n)_n$ and $\displaystyle (y_n)_n$ are adjacent since $\displaystyle 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 $\displaystyle (x_n)_n$ and $\displaystyle (y_n)_n$ have the same limit l.

    You can see that $\displaystyle 2^n \arccos \frac{x_n}{y_n} = \arccos \frac{x_0}{y_0}$ may be true but $\displaystyle 2^n$ has infinite limit whereas $\displaystyle \arccos \frac{x_n}{y_n}$ converges towards $\displaystyle \arccos 1 = 0$
    And that limit would be $\displaystyle \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 $\displaystyle \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: Jan 19th 2010, 02:46 AM
  2. Algorithm
    Posted in the Advanced Math Topics Forum
    Replies: 7
    Last Post: Nov 22nd 2009, 07:11 AM
  3. algorithm
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: Jul 16th 2008, 01:29 PM
  4. Algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Feb 27th 2008, 01:02 PM
  5. gcd algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Dec 4th 2007, 11:47 PM

Search Tags


/mathhelpforum @mathhelpforum