Discrete Dynamical Systems

Section 3.1 Discrete Dynamical Systems

A dynamical system is a pair \((X,R)\) where \(X\) is the set of states a system can be in and \(R\) is a rule for how the system evolves or changes. This can feel like a really abstract and general statement, so let’s look at some real life examples and some simple math examples that we can easily work with.

Example 3.1.1.

Let our state space be the set of all possible collections of position, velocities, and times of the sun and nine planets (Pluto is still a planet to me...). You might store each planet’s position, velocity, and time as a vector then we would say that the ten vectors are the current state of the system and the rule for evolution would be the the force of gravity. In this way, each state leads to the next by following the dynamical rule.

The field of dynamical systems would study questions like 1)if this system always has a solution, 2)what properties solutions typically have, or 3) what is the long term behavior of solution? Another important part of the system above would be an initial condition, or the state of the system at beginning.

You often label this as time zero and state the values for the different planets’ position and velocity at time zero. This leads to even more questions like "If the initial configuration of planets was a bit different, would the long term behavior still be the same?" This example is a continuous dynamical system since we look how the states of the system evolve in terms of a continuous variable (time in this case). This particular system is quite complicated and has been a focus of science, philosophy, and religion for quite some time.

Example 3.1.2.

Let us look at a much simplier example and do some calculations. Let our dynamical system be \((\mathbb{R},f(x)=x^2)\text{.}\) This means that our state space is the set of real numbers and our current state evolves according to the rule \(x \rightarrow x^2\text{.}\)

Notice here that we can only apply our rule (apply the function\(f\)) in discrete amounts. So if we start with the initial value \(x_0=a\text{,}\) then our next state will be \(x_1=f(x_0=a)=a^2\text{.}\) Our study really becomes about the sequence \(x_0,x_1=f(x_0),x_2=f(x_1)=f(f(x_0)), x_3=f(x_2)=f(f(f(x_0))), \ldots\text{.}\) This is called a discrete dynamical system because we can measure the state of the system (and it’s evolution) only at discrete values.

Take a few minutes to find the solution sequence for \(x_0=2\text{.}\) Try to write out what the long term behavior of this solution sequence is. Will all initial values have this same long term behavior? How many different long term behaviors can you find?

Example 3.1.3.

You may think a game like chess is also a dynamical system but that is not the case. You could consider all the different ways that pieces could be configured on the board as a state space for the game, there is no rule for how the configuration must change. This is what makes chess an interesting game.

Subsection 3.1.1 Predator-Prey Systems

In this section we will look at a basic type of two dimensional discrete dynamical system that models the populations of a predator and a prey, which we will call foxes (\(F\)) and rabbits, \(R\text{.}\) We will construct a discrete dynamcial system that describe the amount of foxes and rabbits in the next year based on the amount of foxes and rabbits in the current year. In other words,

\begin{equation*} F_{n+1}=g(F_n,R_n) \end{equation*}

\begin{equation*} R_{n+1}=h(F_n,R_n) \end{equation*}

Let’s figure out reasonable functions for \(g\) and \(h\) under the following ideas:

If there are no rabbits, then some of the foxes will die in the next year (starvation)
If there are rabbits, then the fox populations grows in the next year based on the interaction of the species (predation)
If there are no foxes, the rabbit population will grow by some proportion in the next year
If there are foxes, then the rabbit population will decrease based on the interaction of the species (being eaten)

Functions that fit these simple rules might be of the form

\begin{equation*} F_{n+1}=g(F_n,R_n)= -a F_n + b R_n \end{equation*}

\begin{equation*} R_{n+1}=h(F_n,R_n)= c R_n - d F_n \end{equation*}

So choosing coefficients would give the relative weight of each of these rules on the change in each population. For instance,

\begin{equation*} F_{n+1} = -0.2 F_n + 0.13 R_n \end{equation*}

\begin{equation*} R_{n+1} = 1.05 R_n - 2.1 F_n \end{equation*}

Note here that we can use linear algebra to analyse this type of problem because our sequence now looks like

\begin{equation*} \vec{x}_0=\colvec{F_0 \\R_0}, \vec{x}_1=A \vec{x}_0, \vec{x}_2=A \vec{x}_1 = A(A \vec{x}_0), \ldots \end{equation*}

where \(A=\begin{bmatrix} a\amp b \\c \amp d \end{bmatrix} \text{.}\) In other words, the solution to this two dimensional, discrete dynamical system is of the form \(\vec{x}_n = A^n \vec{x}_0\text{.}\)

Subsection 3.1.2 Difference Equations and Linear Algebra

A dynamical system with an n-dimensional vector for the state and dynamical rule given by \(\vec{x}_{n+1} = A \vec{x}_n\) is called a linear difference equation.

Let examine how eigenvalues and eigenvectors could help us easily understand the long term behavior of a linear difference equation. In particular, we will assume that we have a difference equation given by a \(n\) by \(n\) matrix \(A\) and that we can find a set of \(n\) linearly independent eigenvectors, \(\{\vec{v}_1,\vec{v}_2, \ldots, \vec{v}_n\}\text{,}\) with eigenvalues \(\{\lambda_1,\lambda_2, \ldots, \lambda_n\}\text{.}\) This is actually a really big assumption and is NOT true in general, so the discussion below will not be enough to analyze the general case. Because we have a set of \(n\) linearly independent vectors from \(\mathbb{R}^n\text{,}\) we can put them as columns of a matrix and apply the Invertible Matrix Theorem to demonstrate that this set will also span all of \(\mathbb{R}^n\text{.}\) This means that no matter what initial values we take for our system, we can write that initial value as a linear combination of the set \(\{\vec{v}_1,\vec{v}_2, \ldots, \vec{v}_n\}\text{.}\) In other words, there is a solution to the vector equation

\begin{equation*} \vec{x}_0 = c_1 \vec{v}_1 + c_2 \vec{v}_2 + \ldots+ c_n \vec{v}_n \end{equation*}

for every \(\vec{x}_0 \in \mathbb{R}^n\text{.}\) Because these vectors in our spanning set are not just some vectors, but rather are eigenvectors of \(A\text{,}\) we will be able to write out the rest of the sequence and understand the long term behavior regardless of initial values of our system.

Looking at \(\vec{x}_1\) we get the following:

\begin{equation*} \vec{x}_1 = A \vec{x}_0 = A (c_1 \vec{v}_1 + c_2 \vec{v}_2 + \ldots+ c_n \vec{v}_n) \end{equation*}

\begin{equation*} = c_1 (A \vec{v}_1) + c_2 (A \vec{v}_2) + \ldots+ c_n (A \vec{v}_n) \end{equation*}

Since each of the \(\vec{x}_i\) are eigenvectors, \(A \vec{v}_i = \lambda_i \vec{v}_i\text{.}\) Thus,

\begin{equation*} \vec{x}_1 = c_1 \lambda_1 \vec{v}_1 + c_2 \lambda_2 \vec{v}_2 + \ldots+ c_n \lambda_n \vec{v}_n \end{equation*}

In this same way, we can look at the \(k\)-th iteration of our system and get

\begin{equation*} \vec{x}_k = A^k \vec{x}_0 = A^k (c_1 \vec{v}_1 + c_2 \vec{v}_2 + \ldots+ c_n \vec{v}_n) \end{equation*}

\begin{equation*} = c_1 \lambda_1^k \vec{v}_1 + c_2 \lambda_2^k \vec{v}_2 + \ldots+ c_n \lambda_n^k \vec{v}_n \end{equation*}

Notice that the only thing changing under iteration is the power of the eigenvalue. Once we figure out how much of our inital value vector is in the direction of each of our eigenvectors, then that amount does NOT change during the evolution of our system! The only thing changing is that each eigenvector direction is getting stretched or shrunk by the eigenvalue at each step. So when will these different parts grow or shrink?

Activity 3.1.1.

In this activity, we want to go through all of the parts of the argument above and its geometric meaning for the difference equation described by \(A=\begin{bmatrix} 2 \amp 0 \\ 0 \amp \frac{1}{2} \end{bmatrix}\text{.}\)

(a)

What are the eigenvalues and eigenvectors of \(A\text{?}\)

(b)

How can we write the vector \(\colvec{2 \\ -3}\) as a linear combination of the eigenvectors of \(A\text{?}\)

(c)

How can we write the vector \(\colvec{\alpha \\ \beta}\) as a linear combination of the eigenvectors of \(A\text{?}\)

(d)

Show that if \(\vec{w}=c_1 \vec{v}_1 +c_2 \vec{v}_2\text{,}\) then \(A \vec{w} = c_1 \lambda_1 \vec{v}_1 +c_2 \lambda_2 \vec{v}_2\text{.}\)

(e)

What is the long term behavior of the solution with initial value \(\colvec{2 \\ -3}\text{?}\)

Activity 3.1.2.

In this activity, we want to go through all of the parts of the argument above and its geometric meaning for the difference equation described by \(A=\begin{bmatrix} 1 \amp 3 \\ 3 \amp 1 \end{bmatrix}\text{.}\)

(a)

What are the eigenvalues and eigenvectors of \(A\text{?}\)

(b)

How can we write the vector \(\colvec{2 \\ -3}\) as a linear combination of the eigenvectors of \(A\text{?}\)

(c)

Show that if \(\vec{w}=c_1 \vec{v}_1 +c_2 \vec{v}_2\text{,}\) then \(A \vec{w} = c_1 \lambda_1 \vec{v}_1 +c_2 \lambda_2 \vec{v}_2\text{.}\)

(d)

What is the long term behavior of the solution with initial value \(\colvec{2 \\ -3}\text{?}\)

Subsection 3.1.3 Types of Solutions to Two Dimensional Linear Difference Equations

Question 3.1.4.

What are the fixed points of the difference equation \(\vec{x}_{k+1}=A \vec{x}_k\) where \(A=\begin{bmatrix} 1 \amp 2 \\ 3 \amp 4 \end{bmatrix}\text{.}\)

Question 3.1.5.

What are the fixed points of the difference equation \(\vec{x}_{k+1}=A \vec{x}_k\) where \(A=\begin{bmatrix} 2 \amp -1 \\ 1 \amp 0 \end{bmatrix}\text{.}\)

Since the long term behavior of these type of systems depends on the eigenvalues, we wil try to talk about all of the possible cases of eigenvalues and the corresponding behaviors. Remember that we need to pay attention to how \(\lambda^k\) changes as \(k\) increases.

\(|\lambda_1| \lt 1\) and \(|\lambda_2| \lt 1\)
\(|\lambda_1| \gt 1\) and \(|\lambda_2| \gt 1\)
\(|\lambda_1| \lt 1\) and \(|\lambda_2| \gt 1\)
\(|\lambda_1|=1\) and \(|\lambda_2| \lt 1\)
\(|\lambda_1|=1\) and \(|\lambda_2| \gt 1\)
\(|\lambda_1|=0\) and \(|\lambda_2| \lt 1\)
\(|\lambda_1|=0\) and \(|\lambda_2| \gt 1\)
What other possibilities are there?

Activity 3.1.3.

Use your new found appreaciation of eigenvalues and eigenvectors to describe the general solution and behavior of solutions to the difference equation \(\vec{x}_{k+1}=A \vec{x}_k\) with each of the following \(A\text{.}\)

(a)

\(A=\begin{bmatrix} 2 \amp 0 \\ 0 \amp 1/2 \end{bmatrix}\)

(b)

\(A=\begin{bmatrix} 0.75 \amp 0 \\ 0 \amp 0.999 \end{bmatrix}\)

(c)

\(A=\begin{bmatrix} -2 \amp 0 \\ 0 \amp 3 \end{bmatrix}\)

(d)

\(A=\begin{bmatrix} 1.25 \amp -0.75 \\ -0.75 \amp 1.25 \end{bmatrix}\)

(e)

\(A=\begin{bmatrix} 2 \amp 1 \\ 1 \amp 2 \end{bmatrix}\)

(f)

\(A=\begin{bmatrix} 2 \amp -1 \\ 1 \amp 0 \end{bmatrix}\)

(g)

\(A=\begin{bmatrix} 1 \amp -1 \\ 1 \amp 1 \end{bmatrix}\)

(h)

\(A=\begin{bmatrix} -0.2 \amp 0.13 \\ -2.1 \amp 1.05 \end{bmatrix}\)

Definition 3.1.6.

An attractor or attracting fixed point is a fixed point of a dynamical system where all nearby points converge to the fixed point. These are also called sinks.

A repeller or repelling fixed point is a fixed point of a dynamical system where all nearby points move away from the fixed point. These are also called sources.

A saddle fixed point is a fixed point of a dynamical system where some nearby points converge to the fixed point and other nearby points move away from the fixed point.

Question 3.1.7.

If we consider the dynamical system given by \((\mathbb{R},f(x)=-x^2)\text{,}\) what are the fixed points of this system and what behaviors do they exhibit?

Activity 3.1.4.

Use your work from the earlier activity to describe the fixed points and thier behavior for the difference equation \(\vec{x}_{k+1}=A \vec{x}_k\) with each of the following \(A\text{.}\)

(a)