Author |
Topic: cos of cos of .... (Read 1506 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
cos of cos of ....
« on: Dec 11th, 2004, 5:22pm » |
 Quote  Modify
|
Start with an arbitrary real number. Repeatedly take the cosine (assume radians). Do we even converge to a number? Why does it converge/not converge?
(In other words, define the sequence xn+1 = cos(xn), x1 being arbitrary. Does xn converge to a limit?)
What if we repeatedly take the sine?
|
|
 IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: cos of cos of ....
« Reply #1 on: Dec 11th, 2004, 6:52pm » |
Quote Modify
|
:: An iteration xn+1 = f(xn) converges to the stationary point s that satisfies f(s) = s, if |f'(s)| < 1. (This follows from substituting xn = s + [epsilon]n in above iteration equation and Taylor expanding f(x) around x=s .)
The absolute value of the derivative of the cosine function is smaller than unity around x=s satisfying cos(s) = s, so the cos iteration converges.
This is not the case for the sin iteration: sin(s) = s has the solution s=0, and the derivative of the sine function around this stationary point equals unity. ::
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: cos of cos of ....
« Reply #2 on: Dec 11th, 2004, 7:03pm » |
Quote Modify
|
That the repeated cosine sequence converges is easily discovered with a calculator, but proving that it does (rather than this being an artifact of the finite mathematics of calculators) is a bit harder. In fact, it was situations like this that were the birth of chaos theory, and the concept of attractors.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: cos of cos of ....
« Reply #3 on: Dec 12th, 2004, 1:05am » |
Quote Modify
|
on Dec 11th, 2004, 6:52pm, JocK wrote:| :: This is not the case for the sin iteration: sin(s) = s has the solution s=0, and the derivative of the sine function around this stationary point equals unity. :: |
|
Isn't that a sufficient condition for convergence rather than a necessary one? In fact, the sequence xn+1 = sin(xn) is convergent to 0.
on Dec 11th, 2004, 7:03pm, Icarus wrote:
That the repeated cosine sequence converges is easily discovered with a calculator, but proving that it does (rather than this being an artifact of the finite mathematics of calculators) is a bit harder
|
|
True, it is convergent. The proof is not hard too. Observing the values with the calculator might help one arrive at a not-so-hard proof.
|
| « Last Edit: Dec 12th, 2004, 1:10am by Aryabhatta » |
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: cos of cos of ....
« Reply #4 on: Dec 12th, 2004, 4:38am » |
Quote Modify
|
on Dec 12th, 2004, 1:05am, Aryabhatta wrote:
Isn't that a sufficient condition for convergence rather than a necessary one?
In fact, the sequence xn+1 = sin(xn) is convergent to 0. |
|
You are right. A necessary condition is |f'(s)| [le] 1.
If |f'(s)| < 1 the iteration converges, and if |f'(s)| > 1 the iteration diverges. The case |f'(s)| = 1 is in-between and the convergence/divergence behaviour gets dictated by the next term in the Taylor expansion. Writing xn = s + [epsilon]n and using f(s) = s we get:
[epsilon]n+1 = [epsilon]nf'(s) + ([epsilon]n2/2)f''(s) + O([epsilon]n3)
In case of the sin iteration f'(s) = 1 and f''(s) = -1 so that:
[epsilon]n+1/[epsilon]n = 1 - [epsilon]n/2 + O([epsilon]n2)
Because the second term on the RHS is negative, a convergence (albeit a very slow one) sets in.
|
| « Last Edit: Dec 12th, 2004, 4:40am by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: cos of cos of ....
« Reply #5 on: Dec 12th, 2004, 4:55am » |
Quote Modify
|
Now that Jock has done the easy part, 
:The actual limit is the solution of cosx = cos-1x, about 0.739085
(Not that it was asked for, of course.)
|
| « Last Edit: Dec 12th, 2004, 5:01am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: cos of cos of ....
« Reply #6 on: Dec 12th, 2004, 5:12am » |
Quote Modify
|
on Dec 11th, 2004, 7:03pm, Icarus wrote:| .. it was situations like this that were the birth of chaos theory, and the concept of attractors. |
|
Indeed, if the derivative of the iterated function at the stationary point in absolute value exceeds unity (|f'(s)| > 1), chaotic behaviour (via so-called period doubling) may result from the iteration.
Instead of iterating cos(x), try iterating xn+1 = [lambda] cos(xn)
Start with [lambda] slightly larger than 1 and let lambda grow. Initially the derivatives are small, and a rather boring convergence is observed. However, for larger [lambda] values that is no longer true, and interesting behaviour sets in when [lambda] reaches values around 2 and beyond. To visualise this, plot the first so many iteration values that are obtained after - say - 1,000 iterations as function of [lambda].
|
| « Last Edit: Dec 12th, 2004, 5:17am by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: cos of cos of ....
« Reply #7 on: Dec 12th, 2004, 10:42am » |
Quote Modify
|
on Dec 12th, 2004, 4:55am, THUDandBLUNDER wrote:| The actual limit is the solution of cosx = cos-1x, about 0.739085 |
|
No, it's the solution of cos x = x. Of course, the same value does solve cos x = cos-1x, but that equation also has other solutions.
|
| « Last Edit: Dec 12th, 2004, 10:44am by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: cos of cos of ....
« Reply #8 on: Dec 12th, 2004, 11:07am » |
Quote Modify
|
Quote:| Of course, the same value does solve cos x = cos-1x, but that equation also has other solutions. ] |
|
Of course, cosx = x is simpler. 
But the domain of cos-1x is [-1,1]; so how can there be more (real) solutions?
|
| « Last Edit: Dec 12th, 2004, 11:23am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: cos of cos of ....
« Reply #9 on: Dec 12th, 2004, 11:09am » |
Quote Modify
|
Okay, so maybe the others are unreal. Nevermind.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: cos of cos of ....
« Reply #10 on: Dec 12th, 2004, 10:13pm » |
Quote Modify
|
on Dec 12th, 2004, 4:55am, THUDandBLUNDER wrote:The actual limit is the solution of cosx = cos-1x, about 0.739085
(Not that it was asked for, of course.)
|
|
Are you trying to hint at something?
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: cos of cos of ....
« Reply #11 on: Dec 12th, 2004, 11:10pm » |
Quote Modify
|
on Dec 12th, 2004, 10:13pm, Aryabhatta wrote:
Are you trying to hint at something? |
|
No. Obviously, you didn't ask because it was too simple, even for Easy.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: cos of cos of ....
« Reply #12 on: Dec 13th, 2004, 1:43am » |
Quote Modify
|
on Dec 12th, 2004, 11:10pm, THUDandBLUNDER wrote:
No. Obviously, you didn't ask because it was too simple, even for Easy.
|
|
I was referring to the way you stated the limit, as the root of cosx = cos-1x, instead of the simpler cosx = x. I thought you were subtly hinting at a 'more elementary' proof than Jock's by stating the limit this way. Anyway, let me state what I thought you were hinting at:
xn+1 = cos(xn).
Consider the two subsequences {x2n} and {x2n+1}.
:
Also, here is an 'elementary' proof that the sequence xn+1 = sin xn converges.
wlog we can assume x1 [in] (0,1].
i.e xn > 0 for all sufficiently large n.
Now, for positive x, sinx < x.
So the sequence is monotonically decreasing. It is bounded below by zero. Hence it is convergent to a number L which satisfies sinL = L which implies L = 0.
|
| « Last Edit: Dec 13th, 2004, 1:47am by Aryabhatta » |
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: cos of cos of ....
« Reply #13 on: Dec 13th, 2004, 4:17am » |
Quote Modify
|
Quote:| I thought you were subtly hinting at a 'more elementary' proof than Jock's by stating the limit this way. |
|
I think most people would agree that my hints are not usually that subtle.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: cos of cos of ....
« Reply #14 on: Dec 17th, 2004, 11:07am » |
Quote Modify
|
Ok. Here is a 'not-so-hard' proof that xn+1 = cosxn converges.
note that cos is decreasing in [0,[pi]/2] and in that interval, cosx = x has only one solution say L.
wlog we can assume 0 [le] x1 < L. This implies L < x2 [le] 1.
Now we can split the sequences into two subsequences x2n-1 and x2n say an and bn respectively.
an < L for all n.
bn > L for all n.
Also an+1 = cos(cos(an)) and bn+1 = cos(cos(bn)).
We can easily show that f(x) = cos(cos(x)) - x is decreasing. f(L) = 0.
Thus we see that an is bounded above an increasing, bn is bounded below and decreasing. Thus both converge and they can only converge to L. This implies xn converges to L.
|
| « Last Edit: Dec 17th, 2004, 11:09am by Aryabhatta » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print