Which of the following fixed point iterations will converge, and why? Also if possible please give the rate of convergence.
(a) $x_{n+1}=\cos(x_n)$
(b) $x_{n+1}=\sin(x_n)$
(c) $x_{n+1}=\tan(x_n)$
Thank you!
Asked
Active
Viewed 649 times
1
-
Have you tried it? – Mark McClure Feb 26 '14 at 04:06
-
I'm using mathlab at the moment (Octave to be more precise) and after enough iterations it seems like x = cos(x) is the only one that converges. My code is as follows: x=1; x=cos(x) which eventually converges to .73909 however I'm not sure how to go about explaining why this is happening, and also how to go about finding the rate of convergence. Sorry for not providing enough information. – BuddyD Feb 26 '14 at 04:15
-
@user3353400 Thanks for the details. I've provided some insight to your problem in an answer. It's still hard to tell the level that you're working at from just the description of your Octave experiment. For example, are you looking for proofs involving $\varepsilon$s, $\delta$s, and the mean value theorem? Or is an intuitive explanation sufficient. – Mark McClure Feb 26 '14 at 04:59
-
This was a more than sufficient response, and very helpful thankyou Mark – BuddyD Feb 26 '14 at 05:09
1 Answers
1
As explained in this answer (as well as in many sources on functional iteration), a fixed point $x_0$ is attractive if $\left|f'(x_0)\right|<1$ and repulsive if $\left|f'(x_0)\right|>1$. This explains your observation on the cosine and provides the rate of convergence, namely $\left|f'(x_0)\right|$. The tangent clearly has a lot of fixed points where the slope is larger than one that are all repulsive.
The tricky questions involve the behavior of the sine and the tangent at the $x_0=0$, which is a neutral fixed point for both. By neutral, I mean that $\left|f'(x_0)\right|=1$, which implies that the dynamics near this point are very slow. Thus, numerical experimentation might be unreliable.
If I iterate the sine function $100,000$ times starting from $x_0=1.0$, I find that the last few terms are
\begin{align} x_{99997}&=0.00547705\\ x_{99998}&=0.00547702\\ x_{99999}&=0.00547700\\ x_{100000}&=0.00547697 \end{align}
Note that the terms are decreasing. This must happen since $0<\sin(x)<x$, whenever $x>0$. As a result, this sequence is decreasing and bounded below, so it mush have a limit.
Experimentation suggested these results, but does not provide proof. If we iterate the tangent function $100,000$ starting from $1.0$, we get something like the following:
\begin{align} x_{99997}&=-0.00233827\\ x_{99998}&=-0.00233828\\\ x_{99999}&=-0.00233828\\ x_{100000}&=-0.00233829 \end{align}
Staying close to zero, so maybe convergent? Well, no - they're getting larger in absolute value. After $200,000$ iterates, we're only at about $-0.0029332$ but moving away. Can you see why?
I should also probably mention that the exact value of $100,000$ iterates are highly suspect, particularly in the presence of repulsive orbits. Nonetheless, the basic types of behavior can be gleaned from this type of experimentation.
Mark McClure
- 30,510