Video: Solving linear discrete dynamical systems
Video links
This video is found in the pages
Transcript of video
If we have a discrete dynamical system such as \begin{align*} x_{t+1} &= 1.2 x_t\\ x_0 &= 0.5 \end{align*} then it is simple to calculate $x_t$ for future times. To go from time step $t$ to time step $t+1$, we need to multiply by $1.2$. We can iterate this process to go from $x_0$ to $x_1$ to $x_2$, etc. \begin{align*} x_1 &= 1.2 x_0 = 1.2(0.5) = 0.6\\ x_2 &= 1.2 x_1 = 1.2(0.6) = 0.72 \end{align*} Continuing in this process, \begin{align*} x_3 &= 1.2 x_2 = 1.2(0.72) = 0.864 \end{align*}
We could do this indefinitely. We could calculate $x_{100}$ with this process, but it would take awhile.
For a system as simple as $x_{t+1} = 1.2 x_t$, though, there is another way to figure out what $x_t$ will be for any value of $t$. We can actually solve the system to give us a direct formula to calculate $x_t$ directly. By solving the system, we mean find a formula for $x_t$ in terms of the time step $t$ and the initial condition $x_0$. Unlike the system we are given, it cannot depend on the value of $x$ from the previous time step.
How do we come up with such a solution? We don't have a standard algorithm to solve discrete dynamical systems. In fact, for most such systems, we can't even find a solution formula. But, the above system is simple enough that we can find a solution.
For this dynamical sytsem, to advance one time step, we must multiply by $1.2$. To advance two time steps, we just have to do the same thing twice: multiply by $1.2$ twice, or multiply by $1.2^2$. For example, to go from $x_0$ to $x_2$, we start with $x_0$, multiply by $1.2$ to get to $x_1=1.2 x_0$, and multiply by $1.2$ again to get \begin{align*} x_2 = 1.2 x_1 = 1.2 (1.2 \cdot x_0) = 1.2^2 x_0. \end{align*} Similarly, $x_3$ is $1.2$ times $x_2$, so it is $1.2^3 x_0$.
If we want to go from $x_0$ all the way to $x_t$, we just have to multiply by $1.2$ $t$ times; in other words, we have to multiply by $1.2^t$. For any initial condition $x_0$, the solution to the dynamical system is $$x_t = 1.2^t x_0.$$ If we plug in our initial condition $x_0 = 0.5$, then the specific solution is $$x_t = 1.2^t 0.5.$$ We can immediately calculate that \begin{align*} x_3 &= 1.2^3 0.5 = (1.728)(0.5) = 0.864. \end{align*} We can jump right to $t=10$ and determine that \begin{align*} x_{10} &= 1.2^{10} 0.5 \approx (6.192)(0.5) = 3.096. \end{align*} We can even go all the way out to $t=100$ without any additional effort, since \begin{align*} x_{100} &= 1.2^{100} 0.5, \end{align*} this gives us something like 41 million.
The reason we could solve this dynamical system was because it is so simple. It is a linear dynamical system because the right hand side is a linear function of $x_t$. In general, we can write such a linear system as \begin{align*} x_{t+1} &= a x_t\\ x_0 &= b, \end{align*} where $a$ and $b$ are just two numbers, called parameters. If you substitute $a=1.2$ and $b=0.5$, you have the system we began with. Let's leave the parameters as arbitrary values, though. We can still solve the linear system. The solution is \begin{align*} x_t = a^t b. \end{align*} To go from the initial condition $x_0=b$ to $x_t$, we just have to multiply by $a$ $t$ times, or multiply by $a^t$.
We can now easily solve a system like \begin{align*} y_{t+1} &= 0.7 y_t\\ y_0 &= 1730. \end{align*} The solution is $y_t = 0.7^t 1730$.
The solution to the system \begin{align*} q_{n+1} &= 2 q_n\\ q_0 &=3 \end{align*} is $q_n = 2^n 3$.
In all these examples, the dynamical system was given in what we call “function iteration form.” They were written so that the value at the next time step was a function of the value at the previous time step: \begin{align*} x_{n+1} = f(x_n). \end{align*} In these cases, $f$ was a linear function of the form $f(x) = ax$.
Often, though, when deriving a discrete dynamical system, we start with a dynamical system in terms of the change in the value of the state variable, such as \begin{align*} x_{n+1} - x_n &= 0.3 x_n\\ x_0 &= 300, \end{align*} which could represent a population that increases by 30% in each time step. We say such a dynamical system is in “difference form” because the left hand side $x_{n+1}-x_n$ is the difference in the state variable across a time step.
If we start with a system in difference form, it isn't difficult to change it to function iteration form. We can solve for $x_{n+1}$ by just adding $x_n$ to both sides of the equation. If we add $x_n$ to both sides of the above system, the right hand side is $0.3 x_n + x_n = 1.3x_n$. The dynamical system converted to function iteration form is \begin{align*} x_{n+1} &= 1.3 x_n\\ x_0 &= 300. \end{align*} Now, we see that in each time step, we must multiply by 1.3. The solution is \begin{align*} x_n = 1.3^n x_0, \end{align*} and we can plug in $x_0=300$.
Similarly, if we were modeling a population that started with 500 individuals and decreased by 20% in each year, we could come up with a dynamical system in difference form: \begin{align*} p_{t+1} - p_t &= -0.2 p_t\\ p_0 &= 500, \end{align*} where $p_t$ is the population size in year $t$. To convert it to function iteration form, add $p_t$ to both sides \begin{align*} p_{t+1} &= 0.8 p_t\\ p_0 &= 500. \end{align*} The solution is \begin{align*} p_t = 0.8^t 500. \end{align*}