Algorithm

**Sampras** · June 22nd 2009, 01:08 AM

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?

**running-gag** · June 22nd 2009, 11:32 AM

Originally Posted by Sampras

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$

**Sampras** · June 22nd 2009, 01:58 PM

Originally Posted by running-gag

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?

**running-gag** · June 23rd 2009, 10:43 AM

Originally Posted by Sampras

And that limit would be $\frac{\sqrt{y_{0}^{2}-x_{0}^{2}}}{\arccos(x_0/y_0)}$ right?

Yes

Thread: Algorithm

LinkBack

Thread Tools

Display

Algorithm

Similar Math Help Forum Discussions

algorithm

Algorithm

algorithm

Algorithm

gcd algorithm

Search Tags