1. Introductive definitions and theorems

A dynamical system consists of two components; one describes the state of the system and the other is a function f: that determines its future. The state is a n-dimensional vectorand it is written X_t, where t stands for a time index. If the time index is allowed to run continuously over time, then X_t is a continuous system. In this course we study discrete dynamical systems, for which the time index belongs to the set of natural numbers, .

The starting point (start-state) is denoted by X₀. Later states of the system are calculated by iterations of f(X₀). The composition f(f(x)) is denoted by f ²(x), f(f(f(x))) by f ³(x), i.e. the n:th iteration of x is denoted by f ⁿ(x). Assumed that the starting point is known, the state of the system at the time t+1 may be calculated by t+1 iterations of X₀ :

The state at time t+1 of a discrete dynamical system is according to [May76]:

Equation (1.1) may for example describe the size of a population [May76]. The interesting thing with discrete dynamical systems is to study the asymptotic behavior of the iterative process (1.1).

The forward orbit of a point x is a set O⁺ that consits of the points: x, f(x), f ²(x), . . .. The backward orbit of x, written O ^- , consists of the following points: x, f ^-1(x), f ^-2(x), . . ., assumed that the function f is invertible.

A point is a fixed point if:

The point x is a periodical point with the period , if:

The set of periodical points of period n of the function f is written Per_n(f).

The set of fixed points may be written as Per₁(f). The point x is a periodical point with the prime period n, if n is the least natural number that satisfies (1.3).

The local stable set of a periodical point is denoted by . If the map is invertible, the local unstable set is:

Definition 1.1. Assume that f: V-->V. The set of periodical points {Per_n(f), } is dense in V if the closure of = V

The closure of is the union of all periodical points.

Example 1.1. The function g()=sin(3) has periodical points that are dense in S¹. For an integer k the following holds: g(+k2)=g(). The periodical points may be calculated from (1.3) as the following:

1.1. A classification of periodical points

It’s interesting to study the qualitative changes in the periodical points as the function f changes. The periodical points may be stable or unstable. The classification of these are described in the next chapter.

1.1.1. One-dimensional systems

The classification of fixed and periodical points in one-dimensional systems may be done by the derivative [Dev89]. Assume that , the point p is said to be:

• hyperbolic if |(f ⁿ)’(p)| # 1
• attracting if |(f ⁿ)’(p)| < 1
• repelling if |(f ⁿ)’(p)| > 1

When choosing a start point x₀ from an open interval around a periodical point the behavior of the forward orbit depends on the map. If the periodical point p is hyperbolic, the forward orbit will strongly depend on the place of the starting point versus p. For attractive periodical points the following theorem can be proved:

Theorem Assume that and |(f ⁿ)’(p)| < 1. Then there is an open interval , such that for every :

Proof

According to the theorem above, there is an attractor of period n that is surrounded by an open interval I that is mapped inside itself by fⁿ. This neighborhood is contained in the stable set. For repelling periodical points an analogous theorem exists:

Theorem Assume that and |(f ⁿ)’(p)| > 1. Then there is an open interval , such that for every xÎU\{p} there exists kÎN such that:

Proof

The interval U in the theorem above is contained in the local unstable set of p.

Example 1.2. The function has the fixed points: { -1, 0, 1}. Their stability can be determined with the derivative: , and . The points -1 and 1 are repelling fixed points and the point 0 is attractive. The forward orbits for the following startpoints: { -1.1, -0.8, 0.8, 1.1} are shown in the figure below.

Figure 1. The forward orbit O⁺(x₀), where x₀ is in {-1.1, -0.8, 0.8, 1.1}.

In figure 1, the local stable and unstable sets are shown: , and . Alternatively the forward orbit O⁺ can be drawn as a function of , see figure 2.

Figure 2. The first points of the forward orbits of .

If the function f is linear, (1.1) may then be written as a difference equation of the first order:

(1.5)

The behavior of the sequence X_t depends on the values of a, b and X₀, as it is shown in (1.5). A thorough description can be found in [Gol58].

1.1.2. Higher dimensional systems

The classification of periodical points in multidimensional systems is done by the eigenvalues of the Jacobian matrix. The set of eigenvalues of the matrix A is denoted by . Assume that , where , (k>1). The Jacobian matrix of the map f is denoted by Df and defined as the following:

The eigenvalues of Df can be calculated from the equation: , where I is a -identitymatrix. Analogous to the one-dimensional case, the point p is said to be:

• hyperbolic if for every
• attracting if for every
• repelling if for every
• a saddle point if for some it holds that and some are such that

1.1.2.1. Linear systems

A linear system of the form (1.1) can also be written as (a system of first order difference equations):

where A is a n-dimensional square matrix and X and b are vectors with n elements. The Jacobianmatrix to the system (1.6) is simply the matrix A, from which the stability of the periodical points can be determined. For linear multidimensional systems the following theorem has been proved:

Theorem Assume that X_t+1=L(X_t), where L is a linear map, . Then if and only if for every , i=1, . . . , n.

Proof The theorem is proved for n=3 in pp. 175-176 of [Dev89].

Iteration of (1.6) gives:

If I-A is invertible, i.e. 1 isn't an eigenvalue of A, we get:

(1.7) can thus be written as:

The behavior of discrete multidimensional systems with the eigenvalues of A may be summarized as the following [Sch96]:

Table 1. Possible behavior of a linear system X_t+1 =A X_t +b.

In the above table it is assumed that the startpoint isn't a fixed or a periodical point. The system might behave in different ways if the fixed point is a saddle or nonhyperbolic, depending on the startpoint.

If A is diagonalizable and one of its eigenvalues is 1, A^k can be expressed with the matrices S and D, where S is a matrix with the eigenvectors (of A) as columns and D is a diagonal matrix, which diagonal entries are l _i , i=1, . . . , n, as the following:

(1.7) can thus be written as:

X_k= A^kX₀+(A^k-1+ A^k-2 + . . . +A+I)b

A is assumed to be diagonalizable, i.e. its eigenvectors are linearly independent. This means that the startpoint X₀ can be written as a linear combination of the eigenvectors s_i, (i=1, . . . , n). We may then write X₀ = c₁s₁+ c₂s₂+ . . .+ c_ns_n, and the following can be done:

The system X_k depends strongly on the starting point. If some l_i is such that |l_i|>1 , i.e. the fixed point is a saddle, the system might diverge depending on the c_i (this can be seen above).

If the matrix A is nondiagonalizable it can be written as: A=SJS ^-1 , where J is in Jordan form [Sch97]. In this case (1.7) can be written as:

A thorough analysis of (1.11) is found in [Sch97]. Generally, the behavior of linear systems doesn't, however, depend on the diagonalizability of A.

1.1.2.2. Nonlinear systems

Nonlinear systems can, if |l _i|#1 for every i, be approximated by linear functions in a neighborhood of the fixedpoints. Assume that the n-dimensional function f is nonlinear and that x* is a fixed point. f can then be approximated as:

The stability of periodical points of nonlinear systems can be determined by calculating the eigenvalues of Df and applying the theory of linear systems.

Example 1.3. The 2-dimensional map

has the following fixed points:

The eigenvalues of the Jacobianmatrix

can be found by solving the equation det(l I-Df(x_i*))=0, i=1,2,3. The eigenvalues of the Jacobian of the different fixed points and their behavior are shown in table 2.

Table 2. The behavior of the fixed points of f(x).

The linearisation may fail if the real parts of the eigenvalues are 0. In such cases other methods can be used to determine the stability of the fixed points [Sch96].

1.1.2.3. Substitution of difference equations

Dynamical systems or time series that are described by linear difference equations may be rewritten to the general form (1.1) of a dynamical system, whereafter the theory can be applied. Consider a linear difference-equation of order k+1:

Make the following substitution: u_t=( u_t⁰, u_t¹, . . . , u_t^k)^T =( X_t, X_t-1, . . . , X_t-k )^T, into (1.13).

(1.14)

The theory from previous chapters can then be used to analyze the behavior of (1.14). Consider the following linear difference equation of the second degree:

Put as above:

The eigenvalues of A can be calculated from:

(1.16)

The stability of the fixed point 0 can now be determined with the values of the parameters a and b.

1.2. Graphical analysis

The graphical analysis is very useful in creation of intuition and understanding of mathematical phenomena. Mathematical programs [Eme97], for example Matlab, Mathematica, Mathcad, Maple etc., are very easy to use for this purpose.

Fixed and periodical points can be calculated from the equations (1.2) and (1.3). They can also be determined by graphical analysis as the following: by drawing the function f(x) and the identity function id(x)=x, the fixed points are the points where f(x) and id(x) intersect. Analogously the periodical points can be found by drawing f ⁿ(x) and id(x).

Example 1.4. The fixed points: {0, 2/3} of the function f(x)=3x(1-x) can be solved from: 3x(1-x)=x.

The function doesn’t have any periodical points, which can be verified graphically:

The behavior of different points may easily be visualized by drawing the first points of the forward orbit. X_t is put on the vertical axis and the time t on the horisontal axis. Alternatively the behavior can be analysed by first drawing the function f(x) and id(x) followed by a choice of startpoint X₀. A horisontal line is then drawn from f(X₀) to id(f(X₀)). The point id(f(X₀)) is now X₁ , from which a line is drawn to f(X₁). From f(X₁) there is a line drawn to id(f(X₁)), which is now X₂. The procedure is repeated until some of the following events occur: an attracting fixed point is found, a periodical orbit is found or the system seems to diverge. The methods described above are used in figures 1 and 2, see examples. The forward orbit may also be drawn in two or three dimensions.

1.3. Bifurcation theory

Changes in parameters may lead to changes in the number of or the behavior of, the fixed and the periodical points. Different kinds of bifurcations (bifurcation="split apart") may occur, for example attracting fixed points may become repelling or become periodical. The tangent bifurcation or saddle-node bifurcation means that two new fixed points are born from a fixed point, of which one is stable and the other is unstable. This can be verified with the following theorem [Dev89]:

Theorem Suppose that:

1. fl0(x*)=x*,	2. fl0'(x*)=1,
3. fl0''(x*)#0,	4.

Then there exists an interval I about x* and a smooth function p:I->R satisfying p(x*)=l₀, such that f_p(x)(x)=x.

Proof: [Dev89] pp. 88-89.

In a period-doubling bifurcation the periods are doubled and stable periodical points becomes unstable. This is the content in the following theorem [Dev89]:

Theorem Suppose that

1. fl0(x*)=x*, for all l in an interval about l0.

2. fl0'(x*)=-1,

3.

Then there is an interval I about x* and a function such that but .

Proof: [Dev89] pp. 90-91.

In a transcritical bifurcation two fixed points are joined and then splitted apart. The different bifurcations can be seen from the following example.

Example 1.5. Consider the function f_a(x)=x²+a. Its fixed points are . The different bifurcations that occur can be seen in table 3.

Table 3. Fixed points of f_a(x).

Note that if a=1/4, both a saddle and a transcritical bifurcation occur, x₁*=x₂*=1/2. For a>1/4 the fixed points are complex [Dev89]. The absolute values of the derivatives in the fixed points are then: .

Graphical analysis visualizes the behavior of the real fixed points, see figure 5.

Figure 5. The graph of f_a(x)=x²+a, for aÎ {-3/2, -3/4, 0, ¼, 1}.

For a<1/4 the function has two real fixed points (of which the larger is repelling) and for a=1/4 these coincide. This can be seen in figure 5.

Bifurcations also occur in two- and higher-dimensional systems. In two dimensions a unique type of bifurcation may occur, i.e. the Hopf-bifurcation. In a Hopf-bifurcation attractive fixed points become reppelling and an attracting closed invariant curve is born. This occurs when the eigenvalues cross the unitcircle [Dev89].

1.3.1. Bifurcation diagrams

The different types of bifurcations can be visualised by so-called bifurcation diagrams. In such a diagram the stable fixed and periodical points are drawn as functions of the parameter [Dev89]. The bifurcation diagram for f_a(x) in example 1.5 is shown in figure 6. The diagram is made by iterating f_a(x) 1000 times for a-values between –2 and ¼. The last 100 points of each iteration is finally plotted at each a-value.

Figure 6. Bifurcationdiagram for f_a(x)=x²+a, aÎ [-2,1/4].

Figure 6 above shows that f_a has an attracting fixed point when a is within [-1/2-e,1/4] and the first perioddoubling occurs at the point a=-1/2-e , (e >0). The perioddoublings occur more often the smaller the a is and they seem to converge to a limit point, a_c. For a< a_c the function is chaotic, which can be seen from the figure as a black region [Dev89]. By zooming in the figure for a-values within [-1.8,-1.7] (see figure 7) an attracting 3-period cycle can be detected for a» -1.76. Figure 7 shows that for a<-1.76 a periodoubling occurs followed by a 6-periodic cycle that is followed by a 12-periodic cycle.

Figure 7. Enlargements of figure 6.

Approximations of parameter values when bifurcations occur can be done by zooming in the diagrams as it is done above.

Feigenbaum [Fei78] did the notation that for the logistic map (f_m (x) = m x(1-x), m Î [0,4], xÎ [0,1]) the parameter values (when the bifurcations occur) can be calculated from:

(1.17)

1.4. Chaos

The word chaos is used in many contexts in daily life, i.e. a desk may look chaotic, someones life may seem to be chaotic. Here the mathematical meaning of chaos is used, which doesn’t refer to any "disorder" or any "mess". Despite the popularity of chaos in recent years, there has not been any universally accepted mathematical definition of chaos [Ban92]. According to [Dev89] a chaotic system has the following three components: topological transitivity, sensitive dependence on initial conditions and dense periodical points. The first ones are defined as:

Definition f:V®V is topologically transitive if there exists a natural number k for all non-empty subsets I and J of V, such that f ^k(I)Ç J#Æ.

Definition f:V® V is sensitive dependent on initial conditions if there is a real number d >0, such that for every xÎ V and for every e >0 there exist y and nÎN such that: | x-y | < e and | f ⁿ(x)- f ⁿ(y) | > d .

With the definitions above and the definition 1.1 (density of periodical points) chaos can , according to [Dev89], be defined on metric spaces as the following:

Definition 1.2. Let V be a metric space. A continuous map f:V® V is said to be chaotic on V if:

1. f is transitive
2. the periodical points of f are dense in V
3. f has sensitive dependency on initial conditions

According to the first criteria (i) in the definition above, a chaotic system isn’t reducible. Because of the density of periodical points, some regularity exists. The third criteria is considered as the main criteria for chaotic systems (also known as the "Butterfly"-effect). According to this criteria, minute differences can lead to large scale divergency. A redundancy has been found in definition 1.2. because [Ban92] has proved the following theorem:

Theorem 1.1. If f:V® V is transitive and has dense periodical points then f has sensitive dependency on initial conditions.

If I is an interval on the real axis, it is (for chaos) enough to show that the map is topologically transitive, because of the following theorem that has been proved by [Vel94]:

Theorem 1.2. Let I be a, not necessarily finite, interval and f:I® I a continuous and topologically transitive map. Then

1. the periodical points of f are dense in I and
2. f has sensitive dependency on initial conditions.

Sometimes it is easier to investigate another similar map g to determine if a map f is chaotic or not. This is possible if the maps are topologically conjugate.

Definition The maps are said to be topologically conjugate if there exists a homeomorphism ,(i.e. h is injective, surjective, continuous and h ^-1 is also continuous), such that, h(f(x))=g(h(x)).

1.4.1. Some chaotic maps

The sensitive dependency may be examplified with a pinball machine [Lor93]. In figure 8 three different paths of a ball are drawn. The paths from the first pin are dependent of the following factors (parameters): the speed and angle of the ball as it arrives at the pin, friction and other disturbances. Small deviations in these factors give totally different paths because the paths are sensitively dependent on the initial conditions. The model fails to provide a perfect example of chaos since the chaotic behavior ceases after the last pin is struck.

Figure 8. Sensitive dependency on initial conditions in a pinball machine.

Some examples of chaotic maps:

• The logistic map f_m (x) = 4x(1-x) is chaotic on [0,1], which is proved and demonstrated in [Dev89].
• The map f _a(x)=x ²+a is chaotic when a=-1.95, the proof is found in [Sch96].
• The tent map T(x) is chaotic on the interval [0,1].

Proof.

• The baker map B(x) is chaotic on [0,1].

Proof.

Figures of the tent and baker maps are found in the function_plot applet.

1.5. About the roundoff errors

The errors that occur when functions are being iterated with computers might in many cases lead to results that are totally wrong. A system migth behave totally different depending on the precision of the chosen program (the program that does the iterations). Consider an iteration of the baker map B(x).Choose the following starting points: the rational number 4/7 and 0.6, which are periodical with the periods 3 and 4. Note that 4/7 is 0.57142857142857... in decimal form, i.e. the decimal comma is followed by an infinite sequence of the numbers 571428. Such numbers will be truncated in computers, i.e. 0.57142857142857... will be truncated to an finite sequence. In a program that calculates with 16 decimals the number 0.6 will be rounded to 0.6000000000000000. The forward orbit of the baker map, calculated exact and numerically with Matlab, is shown in table 4.

Table 4. Iteration of B(x), exactly and numerically with Matlab.

The exact values of B ^k(4/7) and B ^k(3/5) can be calculated with Mathematica, roundoff.nb. Iteration with decimal numbers like 0.6 also leads to wrong results within Mathematica. Table 4 shows that the iterations made by Matlab gives totally wrong results. The example proves that one shouldn't only rely on calculations done by computer programs. You may try this with the roundoff-applet.