Deterministic Dynamical Systems

In a deterministic dynamical system, we write $x_{n+1}=f(x_n)$ for $n>0,x\in {\mathbb{R}}^d$
In a linear dynamical system, $f$ is a linear function $f(x)=Ax$ (if the system is affine then $f(x)=Ax+B$)

A solution to a deterministic system is a sequence of numbers $(x_0,x_1,x_2,\dots )$ such that $x_{n+1}=f(x_n)$ $\forall n>0$

So if $f(x)=Ax$ then we have a sequence defined by $x_n=A^n{x}_0$ (this is trivial but we can use induction if necessary)

In $d=1$,

• If $|a|>1$ then $|x_m|\to \infty$, oscillating if $a$ is negative
• If $|a|<1$ then $x$ will decay to $0$

Note that the space of solutions in our linear dynamical system is a vector space (addition and scaling defined)
The dimension of this space, which is the number of linearly independent solutions, is equal to $d$

Let’s look at the equation $x_{m+2}=\alpha x_{n+1}+\beta x_n$
This can actually be written as $y_{n+1}=A{y}_n,y_n\in {\mathbb{R}}^2$!
We just write $A=\left(\begin{array}{cc}\alpha & \beta \\ 1& 0\end{array}\right)$

The cool thing is this means the solution is still $y_n=A^n{y}_0$

Assuming we can still write $x_n=a^n{x}_0$, we can substitute to obtain $a^2=\alpha a+\beta$, a quadratic equation
So we have $a=\frac{\alpha \pm \sqrt{\Delta }}{2}$

If $\Delta >0$, we have two solutions $x_n={\left(\frac{\alpha \pm \sqrt{\Delta }}{2}\right)}^n$. Are these linearly independent?
Only if there is no solution to ${\lambda }_1{x}_n+{\lambda }_2{y}_n=0$ besides ${\lambda }_1={\lambda }_2=0$. This is true, which we can find simply from the cases $n=0,1$.
This is neat, since it means we’ve found a basis for the space

Conclusion: Any solution can be written as $x_n={\lambda }_1{\left(\frac{\alpha +\sqrt{\Delta }}{2}\right)}^n+{\lambda }_2{\left(\frac{\alpha -\sqrt{\Delta }}{2}\right)}^n$ (naturally $x_0={\lambda }_1+{\lambda }_2$)

Example:
$x_{n+2}=x_{n+1}+x_n$
$x_0=0$
$x_1=1$

We have $\alpha =\beta =1$, so $\Delta =5$
$a=\frac{1\pm \sqrt{5}}{2}$

$0={\lambda }_1+{\lambda }_2$
$1={\lambda }_1\left(\frac{1+\sqrt{5}}{2}\right)+{\lambda }_2\left(\frac{1-\sqrt{5}}{2}\right)=\frac{1}{2}({\lambda }_1+{\lambda }_2)+\frac{\sqrt{5}}{2}({\lambda }_1-{\lambda }_2)=\frac{\sqrt{5}}{2}({\lambda }_1-{\lambda }_2)$
So ${\lambda }_1=\frac{\sqrt{5}}{5}$ and ${\lambda }_2=-\frac{\sqrt{5}}{5}$

$x_n=\frac{\sqrt{5}}{5}{\left(\frac{1+\sqrt{5}}{2}\right)}^n-\frac{\sqrt{5}}{5}{\left(\frac{1-\sqrt{5}}{2}\right)}^n$

Observation: This is all related to diagonalization of matrices
Specifically, $a$ is just the eigenvalues of $A$
The nice thing about diagonalizing $A$ to $P^{-1}AP$ is that we can take powers trivially

Now what if $\Delta =0$? We know one solution is ${\left(\frac{\alpha }{2}\right)}^n$
In class Jonathan showed how we can derive $n{\left(\frac{\alpha }{2}\right)}^n$ as another solution, in which case any solution can be written as ${\lambda }_1{\left(\frac{\alpha }{2}\right)}^n+{\lambda }_{2}n{\left(\frac{\alpha }{2}\right)}^n$

Now what if we have $x_{n+2}=\alpha x_{n+1}+\beta x_n+f(n)$, where $f(n)=C{\lambda }^n$?
Solutions to this are the sum of a particular solution and a general solution to $x_{n+2}=\alpha x_{n+1}+\beta x_n$

1. If ${\lambda }^2-\alpha \lambda -\beta \ne 0$ then a particular solution is of form $D{\lambda }^n$, where $D=\frac{C}{{\lambda }^2-\alpha \lambda -\beta }$
2. If ${\lambda }^2-\alpha \lambda -\beta =0$ and $\Delta \ne 0$, there is a particular solution of type $Dn{\lambda }^n$
3. Otherwise if $\Delta =0$, there is a particular solution of type $D{n}^2{\lambda }^n$