Math Insight

More details on solving linear discrete dynamical systems

The linear discrete dynamical system

When discussing discrete dynamical systems as function iteration, we described the simplest type of discrete dynamical system, where the state space was one-dimensional and the evolution rule at each time point depended just on the values of the state variables at that time. If we let $x_t$ be the snapshot of the state variable at time $t$, then then the trajectory of a given initial state $x_0$ is determined by iterating some function $f(x)$. The result is a dynamical system in written function iteration form, i.e., equation (1) from that page, which we rewrite here as: \begin{gather} x_{t+1}=f(x_t) \quad \text{for $t=0,1,2,3, \ldots.$ } \label{recursion} \end{gather}

What is the simplest form for the function $f(x)$? The boring simplest case would be $f(x)=c$ for some constant $c$. But in those cases, nothing much happens, as all $x_t=c$.

In the next simplest case $f(x)$ is a linear function of the form $$f(x) = Rx$$ where $R$ is some fixed positive constant. In this case, the state variable $x_{t+1}$ at time $t+1$ is proportional to the state variable $x_t$ at the previous time. We have a linear discrete dynamical system.

The behavior of the trajectory $x_1,x_2,x_3, \ldots$ depends on whether $R$ is larger or small than one. The case $R=1$ is a special case since then $x_{t+1}=x_t$. Since in this case, the state variable doesn't change from one snapshot in time to the next, we immediately know that $x_t=x_0$ for all $t$ and we never move from the initial condition value $x_0$.

The more interesting cases are when $R \ne 1$ so that the state variables change over time. If $R \gt 1$, then the state variable becomes larger in magnitude after each time step. But if $0 \lt R \lt 1$, then the state variable decreases in magnitude after each time step. As we will show, these cases correspond to exponential growth and exponential decay, respectively, of the state variable as time increases.

Solving the dynamical system

If $f(x)=Rx$, we can write the discrete dynamical system as \begin{align} x_{t+1} &= Rx_t \quad \text{for $t=0,1,2,3,\ldots.$}\notag\\ x_0 &= \text{a known value}. \label{linear_dynamical_system}\tag{2} \end{align} A solution to the dynamical system \eqref{linear_dynamical_system} is a formula for computing $x_t$ solely in terms of the time $t$ and initial conditions $x_0$. The given system \eqref{linear_dynamical_system} is a recipe for computing all $x_t$, but it is not considered a solution since it is not a formula that lets us directly compute $x_t$ for any $t$.

As described when discussing discrete dynamical systems as function iteration, we can compute the value of $x_t$ for any $t$ by starting with the initial condition $x_0$ and iterating the function many times. In the general case, the expression for the iteration got pretty messy. But, for our special case of $f(x)=Rx$, we can write the result with a nice formula.

Starting with $x_0$, we see that \begin{align*} x_{1}=Rx_0, \end{align*} which is just equation \eqref{linear_dynamical_system} for case when $t=0$. Since equation \eqref{linear_dynamical_system} for case when $t=1$ is $x_2=Rx_1$, we just need to multiply by $R$ twice to go from $x_0$ to $x_2$: \begin{align*} x_{2}=Rx_1 = R(Rx_0)= R^2x_0. \end{align*} We can continue this procedure to calculate $x_t$ for later times $t$: \begin{align*} x_{3}&=Rx_2 = R(Rx_1) = R(R(Rx_0))= R^3x_0\\ x_{4}&=Rx_3 = R(Rx_2) = R(R(Rx_1))= R(R(R(Rx_0)))=R^4x_0. \end{align*}

There's no need to stop at $t=4$ or any particular value of $t$, as we can continue this process as long as we want. For any positive integer $n$, if we want to know $x_n$, the state variable for $t=n$, we would just start with $x_0$ and continuing multiplying by $R$ until we've done it $n$ times. We have the simple formula \begin{align*} x_n = R^n x_0. \end{align*} Or, if we prefer, we can write it in terms of the integer time $t$ \begin{align} x_t = R^t x_0. \label{solution}\tag{3} \end{align} Equation \eqref{solution} is the solution to the dynamical system \eqref{linear_dynamical_system}. It is a simple formula that allows us to immediately compute $x_t$ from the initial condition $x_0$.

Sometimes, it is more natural to think of the dynamical system \eqref{linear_dynamical_system} in terms of the change of the state variable in time $t$: $x_{t+1}-x_t$. In that case, we can rewrite \eqref{linear_dynamical_system} in difference form by subtracting $x_t$ from both sides of the equation. The result is \begin{align} x_{t+1} -x_t &= rx_t \quad \text{for $t=0,1,2,3,\ldots.$}\notag\\ x_0 &= \text{a known value}. \label{linear_dynamical_system_change}\tag{4} \end{align} where $r=R-1$. We can rewrite the solution \eqref{solution} in terms of $r$ as \begin{align} x_t = (r+1)^t x_0. \label{solution2}\tag{5} \end{align}

The case $r \gt 0$ corresponds $R \gt 1$, and the solution exhibits exponential growth. The state variable $x_t$ will blow up to very large magnitude numbers as the time $t$ increases. The case $-1 \lt r \lt 0$ corresponds to $0 \lt R \le 1$, and the solution exhibits exponential decay. The state variable $x_t$ will decay toward zero as the time $t$ increases.