next up previous
Next: Symbolic Dynamics and Analysis Up: Symbolic Dynamics in Mathematics Previous: Introduction

Unimodal Maps and Kneading Theory

The prototypical example of a unimodal map is the quadratic map:
Figure 1 shows tex2html_wrap_inline482, and includes a few iterations of the point tex2html_wrap_inline570. In general, a unimodal map maps an interval I into intself, has a single critical point C in I, and is monotone increasing on the left of C and decreasing on the right. For the quadratic map, I = [0,1] and C=1/2. The key topological property of a unimodal map is that it stretches and folds the interval I into itself.

Figure 1: The quadratic map, with tex2html_wrap_inline568. The vertical and horizontal lines show five iterates of the point tex2html_wrap_inline570.

One of the motivating reasons for studying the quadratic map is to understand the diagram shown in Figure 2. A closer view of part of this plot is shown in Figure 3. In each of these plots, a large sequence of increasing values of tex2html_wrap_inline524 are generated. For each value of tex2html_wrap_inline524, we set tex2html_wrap_inline508, and iterate the quadratic map 1000 times. We then plot the next 32 values in the iteration versus tex2html_wrap_inline524. These plots provide a rough picture of the asymptotic behavior of the quadratic map. For example, Figure 2 shows that for tex2html_wrap_inline512, there is a stable equilibrium. (Indeed, it is easy to prove that for tex2html_wrap_inline514, tex2html_wrap_inline516 is an equilibrium, and it is stable for tex2html_wrap_inline518.) At tex2html_wrap_inline520, the equilibrium becomes unstable, and a stable period 2 orbit is born. As tex2html_wrap_inline524 is increased, the period 2 orbit eventually becomes unstable, and a period 4 orbit is born. This sequence of period doubling bifurcations appears to continue as tex2html_wrap_inline524 is increased, but there is not sufficient resolution in the figures to see what happens. We can see a stable period 6 orbit at tex2html_wrap_inline526, and a stable period 3 orbit at tex2html_wrap_inline528.

In principle, we could determine all the periodic orbits (and determine their stability) by solving the appropriate formula. For example, period 3 orbits satisfy x = f(f(f(x))). However, these equations quickly become intractable as the period increases. It has also been observed that very similar bifurcation diagrams can be found with other unimodal maps, suggesting that the qualitative structure of the bifurcation diagram is not unique to the quadratic map. It turns out that the phenonema illustrated in the bifurcation diagrams can be elucidated with symbolic dynamics and kneading theory.

Figure 2: Bifurcation diagram for the quadratic map, tex2html_wrap_inline536.

Figure 3: A closer look at the bifurcation diagram for the quadratic map, tex2html_wrap_inline542.

To set up the symbolic dynamics of this system, we must first define a partition. In general, a partition is the separation of phase space into disjoint regions. For the quadratic map with tex2html_wrap_inline544, I=[0,1]. We define tex2html_wrap_inline548, C=1/2, and tex2html_wrap_inline552. Given tex2html_wrap_inline564, we define tex2html_wrap_inline556 by (1). We now define
The symbol sequence or itinerary of the point tex2html_wrap_inline564 is the sequence tex2html_wrap_inline566. For example, if tex2html_wrap_inline568 and tex2html_wrap_inline570 (see Figure 1), then tex2html_wrap_inline572. The quadratic map acts on the sequence as a shift:
where tex2html_wrap_inline574 operates on sequences by discarding the left-most symbol, and shifting the rest of the sequence to the left.

We present a brief discussion of kneading theory [6, 7]. (A nice introduction to the theory is given by Devaney [8].) First, we define an ordering tex2html_wrap_inline576 on the itineraries which preserves the ordering on the interval. More precisely, if tex2html_wrap_inline578, then x < y, and if x < y, then tex2html_wrap_inline584. Note that for a unimodal map, f is increasing on tex2html_wrap_inline592 and decreasing on tex2html_wrap_inline594. After one iteration, the order of points in tex2html_wrap_inline592 is maintained, while the order of points in tex2html_wrap_inline594 is reversed. That is, if tex2html_wrap_inline596 and tex2html_wrap_inline598, and x < y, then f(x) > f(y).

Define the order of the symbols to be 0 < C < 1. Let's compare the symbol sequences tex2html_wrap_inline606 and tex2html_wrap_inline608. Clearly, if tex2html_wrap_inline610, then x < y, and if tex2html_wrap_inline614 then x > y. If tex2html_wrap_inline618, we compare tex2html_wrap_inline620 and tex2html_wrap_inline622. However, we have to take into account that if tex2html_wrap_inline626, then the order of the points has been reversed by the first iteration of the mapping. Therefore, if tex2html_wrap_inline626 and tex2html_wrap_inline628, then it must be that x > y (and x < y if tex2html_wrap_inline634). Now suppose that the first two symbols agree, but, say, tex2html_wrap_inline636. If the first two symbols are 00, then there have been no reversals, so x < y. If the first two symbols are 01 or 10, then there has been one reversal, so x > y. Finally, if the first two symbols are 11, then there have been two reversals, so x < y.

In general, the order is determined by the order of the first pair of symbols that differ in the two sequences. In order to know the correct direction of the inequalities, we must keep track of how many times the order has been reversed. But this is just the number of 1s that appear in the segment of the sequences that agree, because a 1 means that the points are to the right of C, and their order will be reversed by the next iteration. If there are an even number of 1s, then we use the natural order of the first symbols that differ. If there are an odd number of ones, then the order of x and y is the reverse of the order of the first pair of different symbols.

These simple observations on the ordering of symbol sequences lead to some remarkable consequences. An illustration of the power of the kneading theory are the following theorems, which hold for a large class of unimodal maps. We define the kneading sequence K(f) of the unimodal map f to be the itinerary of x=f(C), i.e. K(f) = S(f(C)).

Theorem. Let tex2html_wrap_inline688 be a symbol sequence. If K(f) is not periodic, and tex2html_wrap_inline676 for all tex2html_wrap_inline678, then there is a point tex2html_wrap_inline680 such that tex2html_wrap_inline682.

This means we can construct an arbitrary symbol sequence tex2html_wrap_inline688, and if this sequence precedes the kneading sequence of the map, then there is a point in the interval with symbol sequence tex2html_wrap_inline688. A generalization is the following.

Theorem. Suppose we are given two symbol sequences tex2html_wrap_inline688 and tex2html_wrap_inline690, and there is a tex2html_wrap_inline692 such that tex2html_wrap_inline694. If there is an tex2html_wrap_inline696 such that tex2html_wrap_inline698 for all tex2html_wrap_inline700, then there is tex2html_wrap_inline680 such that tex2html_wrap_inline682.

These results prove especially useful when we consider periodic orbits. (See, for example, Chapter 1.19 of Devaney [8] for a more detailed introduction.) As we vary tex2html_wrap_inline524, the kneading sequence K(f) changes, and the above results shows that the kneading sequence ``determines'' which periodic orbits exist. It turns out that for the quadratic map, the kneading sequence increases (in the sense of the order defined above) as tex2html_wrap_inline524 increases. By combining the kneading theory with an additional property of the quadratic map (namely that is has a negative Schwarzian derivative), we obtain a detailed description of how periodic orbits arise as tex2html_wrap_inline524 (and hence the kneading sequence) increases. This theory explains the qualitative features of the bifurcation diagram in Figure 2.

next up previous
Next: Symbolic Dynamics and Analysis Up: Symbolic Dynamics in Mathematics Previous: Introduction