From boring to puzzling in 30 iterative steps

The function {f(x)=2\cos x } may be nice and important as a part of trigonometric basis, but there is nothing exciting in its graph:

f(x) = 2 cos x
f(x) = 2 cos x

Let’s look at its iterations {f^n=f\circ f\circ \dots \circ f} where {n } is the number of iterations, not an exponent. Here is the graph of {f^{14}}:

14th iteration
14th iteration

A rectangular pattern is already visible above; further iterations only make it stronger. For example, {f^{30} }:

30 iterations
30 iterations

It may be impossible to see on the graph, but the rectangles are slightly apart from one another (though of course they are connected by the graph of continuous function). This is easier to see on the histogram of the values {f^{n}(0) } for {n=0,\dots, 10000 }, which contains two small gaps in addition to a large one:

Histogram of an orbit of f
Histogram of an orbit of f

What goes on here? The range of {f} on {[-2,2]}, as well as the range of any of its iterates, is of course connected: it is the closed interval {[f^{2}(0),f(0)] = [2 \cos 2, 2]}. But the second iterate {f^2=f\circ f} also has two invariant subintervals, marked here by horizontal lines:

Second iterate
Second iterate

Namely, they are {I_1=[f^{2}(0), f^{4}(0)]} and {I_2=[f^{3}(0),2]}. It is easy to see that {f(I_1)=I_2} and {f(I_2)=I_1}. The gap between {I_1} and {I_2} contains the repelling fixed point of {f}, approximately {x=1.03}. Every orbit except for the fixed point itself is pushed away from this point and is eventually trapped in the cycle between {I_1} and {I_2}.

But there is more. A closer look at the fourth iterate reveals smaller invariant subintervals of {f^4}. Here is what it does on {I_2}:

Fourth iterate
Fourth iterate

Here the gap contains a repelling fixed point of {f^2}, approximately {1.8}. The invariant subintervals of {I_2} are {I_{21}=[f^{3}(0), f^{7}(0)]} and {I_{22}=[f^9(0), 2]}. Also, {I_1} contains invariant subintervals {I_{11}=[f^{2}(0), f^{6}(0)]} and {I_{12}=[f^8(0), f^4(0)]}. These are the projections of the rectangles in the graph of {f^{30}} onto the vertical axes.

No more such splitting occurs. The histogram of the values of iterates of {f} indeed consists of four disjoint intervals. Can one get a Cantor-type set in this way, starting from some boring function?

Fun with TI-83: billions upon billions of cosines

Okay, maybe not billions. But by taking cosines repeatedly, one can find the solution of the equation {\cos x = x} with high precision in under a minute.

Step 1: Enter any number, for example 0, and press Enter.
Step 2: Enter cos(Ans) and press Enter

Step 2
Step 2

Step 3: Keep pushing Enter. (Unfortunately, press-and-hold-to-repeat does not work on TI-83). This will repeatedly execute the command cos(Ans).

Step 3
Step 3

After a few iterations, the numbers begin to settle down:

Convergence
Convergence

and eventually stabilize at 0.7390851332

Limit
Limit

Explanation: the graph of cosine meets the line {y = x} at one point: this is a unique fixed point of the function {f(x)=\cos x}.

Fixed point of f(x)=cos x
Fixed point of f(x)=cos x

Since the derivative {f'(x)=-\sin x} at the fixed point is less than 1 in absolute value, the fixed point is attracting.

Now try the same with the equation {10 \cos x =x}.

Beginning
Beginning

This time, the numbers flat out refuse to converge:

Chaos!
Chaos!

Explanation: the graph of {f(x)=10\cos x} meets the line {y = x} at seven point: thus, this function has seven fixed points.

Seven fixed points
Seven fixed points

And it so happens that {|f'(x)|>1} at each of those fixed points. This makes them repelling. The sequence has nowhere to converge, because every candidate for the limit pushes it away. All that’s left to it is to jump chaotically around the interval {[-10,10]}. Here are the first 1024 terms, plotted with OpenOffice:

There is some system in this chaos
There is a pattern in this chaos…

Clearly, the distribution of the sequence is not uniform. I divided the interval {[-10,10]} into subintervals of length {0.05} and counted the number of terms falling into each.

Distribution of terms
Distribution of terms

What is going on here? Stay tuned.