Besides continuous dynamical systems using differential equations,
discrete dynamical systems defined by maps are also popular in modelling (Fibonacci number
for the population of animals), taking the form \(x_{n+1} =f(x_n)\) with
\(x \in \mathbb{R}^k\) and \(f: \mathbb{R}^k \to \mathbb{R}^k\).
These systems are easier to deal with numerically, but more difficult analytically (precisely
because of the discrete phase space).
If there are parameters in the map, we write
\begin{equation*}
x_{n+1} = f(x_n, \mu),
\end{equation*}
with \(\mu \in \mathbb{R}^m, f: \mathbb{R}^k \times \mathbb{R}^m \to \mathbb{R}^k\).
Given an initial condition \(x_0\), the trajectory is the sequence
\((x_0, x_1, x_2, \dots), \)
i.e, a discrete set of points in phase space \(\mathbb{R}^n\).
We often write
\begin{equation*}
x_{n} = f(x_{n-1}) = f(f(x_{n-2})) =
\underbrace{f(f(\cdots(f(}_\text{$n$ times}x_0))\cdots))
= \underbrace{ f \circ f \circ f \circ \dots \circ f }_\text{$n$ times}(x_0),
\end{equation*}
where \(f^n\) means the \(n^{th}\) iteration of \(f\),
which is NOT \(\left[ f(x_0) \right]^n\), the \(n\)-th power of \(f(x_0)\).
Similar to their continuous
counterparts, we are mainly interested in the fixed points and periodic orbits
of maps to understand their local behaviours, as a starting point for more complicated
situations.
A {\be{fixed point}} of the discrete dynamical system \(x_{n+1}=f(x_n)\) is a solution of
\begin{equation*}
x = f(x).
\end{equation*}
Periodic orbits are defined similarly: they satisfy
\begin{equation*}
x_{n+p} = x_n\ ~\mbox{for all}~ n\geq 0,
\end{equation*}
and \(p\) is called the period. Any point in the periodic orbit with period \(p\)
is just a fixed point of \(f^p\), that is,
\begin{equation*}
x = f^p (x) = \underbrace{f\circ f\circ \cdots f}_{\mbox{$p$ times}}(x)
\end{equation*}
another algebraic equation!
A period-\(p\) orbit is usually listed as a sequence of \(p\) points
\((x_1^*,x_2^*,\cdots,x_p^*)\) such that
\[
x_2^*=f(x_1^*),\quad
x_3^*=f(x_2^*),\quad \cdots,\quad
x_1^*=f(x_p^*),
\]
while each of the point \(x_k^*\) satisfies \(x=f^p(x)\).
Because of the periodicity, the period-\(p\) orbit \((x_2^*,x_3^*,\cdots,x_p^*,x_1^*)\)
is the same as \((x_1^*,x_2^*,\cdots,x_p^*)\), and we only need to choose
one orbit out of the \(p\) equivalent ones.
As with ODEs, we are interested in qualitative properies like
special solutions and their stabilities, invariant sets,
long term behaviours and the dependence of these properties
on parameters.
Example 3.14 Consider the simplest linear map \(x_{n+1} = ax_n + b\). If \(a = 1\), then
\(x_n = x_{n-1}+b = \cdots = x_0 + nb\) and there is no fixed point, unless \(b=0\).
Otherwise if \(a\neq 1\), the only fixed point is \(x^* = b/(1-a)\). From the fact that
\[
x_n - x^* = ax_{n-1}+b-\frac{b}{1-a} = ax_{n-1}-\frac{ab}{1-a} = a\left(
x_{n-1}-x^*
\right),
\]
we get \(x_n-x^* = a^n(x_0-x^*)\) and
\[
x_n = x^* + a^n (x_0-x^*) = a^n x_0 + \frac{1-a^n}{1-a}b.
\]
It is also easy to check that, if \(a\neq 1\), there is no non-trivial period-2 orbits (check
it!)---any period-2 orbit \((x_1,x_2)\) satisfies \(x_1=x_2=x^*\).
Example 3.15 (Compound interest)
Let \(P_n\) be the principal at \(n\)-th month with initial
principal \(P_0\), monthly interest rate \(r\) and monthly payment \(M\), then \(P_n\)
satisfies the relation
\[
P_{n+1} = (1+r)P_n - M.
\]
From the previous example, we get (with \(a= 1+r, b = -M\))
\(
P_n = (1+r)^nP_0 - \frac{M}{r}\big( (1+r)^n-1\big).
\)
For a given continuous dynamical system (i.e., the ODE \(\dot{x}=f(x)\)), we can define an discrete
dynamical system in the following ways shown in Figure 3.21. For any given time interval \(T>0\), we can take
\(x_n = x(nT)\), the solution of the ODE at \(t=nT\). Then the sequence \((x_0,x_1,x_2,\cdots)\) is a
dynamical system.
Alternatively, we can define the discrete points at the intersection
of \(x(t) \in \mathbb{R}^n \) with a \(n-1\) dimensional surface,
called return maps or Poincare maps.
Figure 3.21
Two ways to get discrete dynamical systems from continuous ones,
either by \(x_n=x(nT)\) or the return map.
Maps also appear in the numerical approximations of ODEs. For example, if we want to
consider the solution of \(\dot{x} = x(1-x)\) at time \(t=0,h,2h,\cdots\) (\(h\) is called the
time step, which is usually small) and denote
\(x_n \approx x(nh)\), then by Taylor expansion,
\[
x_{n+1} = x(nh+h) = x(nh) + hx'(nh) + \frac{h^2}{2!}x''(nh) + \cdots
= x_n + h(1-x_n)x_n + O(h^2).
\]
Therefore, to the leading order, we get the discrete map \(x_{n+1} = x_n + h x_n(1-x_n)\).
Similarly, for discrete dynamical system governed by \(x_{n+1}=f(x_n)\),
a set \(\Lambda \subseteq \mathbb{R}\) is invariant iff \(x_0 \in \Lambda\)
implies \(x_n \in \Lambda\) for all \(n \ge 0\). In fact,
to show \(\Lambda\) is invariant, we only need to show
that, if \(x_n \in \Lambda\), then \(x_{n+1} \in \Lambda\).
Example 3.16 (Logistic map)
The logistic map \(x_{n+1} = \mu x_n(1-x_n)\) is the simplest discrete dynamical system
exhibiting chaotic behaviours (for some parameters of \(\mu\)). We will study in detail how these
behaviours and the associated bifurcations depend on the parameter \(\mu\).
We can show that the interval
\(\Lambda = [0,1]\) is invariant when \(\mu \in [0,4]\). In fact, for
\(x_n \in [0,1]\) and \(\mu \in [0,4]\), then
\)x_{n+1}=\mu x_n(1-x_n)\geq 0\) and
\[
x_{n+1} = \mu
(x_n-x_n^2)=\mu\left[\frac{1}{4}-\left(x_n-\frac{1}{2}\right)^2\right]
\leq \frac{\mu}{4} \leq 1.
\]
Example 3.17 (2D system) Consider the system
\begin{equation*}
x_{n+1} = x_n \; f(y_n), \qquad y_{n+1} = g(x_n, y_n).
\end{equation*}
The line \(x=0\) is invariant (\(x_n=0 \implies x_{n+1}=0\)), and on \(x=0\), \(y_{n+1} = g(0, y_n)\).
Linear Maps:
The local behaviours of discrete maps can also be inferred from linearisation
near fixed points. Let \(x^*\) be a fixed point of \(x_{n+1}=f(x_n)\) with \(x^*=f(x^*)\). If \(x\) is close to
\(x^*\) such that \(y_n=x_n-x^*\) is small, then
\[
y_{n+1} = x_{n+1}-x^* = f(x_n) - f(x^*) \approx Df(x^*)(x-x^*)=Df(x^*)y_n.
\]
Therefore, the linearised equation is
\(
y_{n+1} = Ay_n,
\)
with the constant matrix \(A=Df(x^*)\). The solution can be written as
\(
y_n = A^n y_0.
\)
If the matrix can be diagonalised as \(A=S\Lambda S^{-1}\) (the columns of \(S\) are eigenvectors of \(A\)), then
\(A^n = S\Lambda^n S^{-1}\).
The change of variable \(z_n=S^{-1}y_n\) leads to the normal form
\[
z_{n+1} = S^{-1}y_{n+1} = S^{-1}Ay_n = S^{-1}AS (S^{-1}z_n) = \Lambda z_n,
\]
where the matrix power \(\Lambda^n\) in the solution \(z_n=\Lambda^n z_0\) can be calculated easily.
For example,
\[
\Lambda = \begin{pmatrix} \lambda_1 & & & \cr & \lambda_2 & & \cr
& & \ddots & \cr & & & \lambda_m
\end{pmatrix} \mapsto
\Lambda^n = \begin{pmatrix} \lambda_1^n & & & \cr & \lambda_2^n & & \cr
& & \ddots & \cr & & & \lambda_m^n
\end{pmatrix}
\]
and
\[
\Lambda=\begin{pmatrix} \lambda & 1 \cr 0 & \lambda \end{pmatrix} \mapsto
\Lambda^n=\begin{pmatrix} \lambda^n & (n+1)\lambda^{n-1} \cr 0 & \lambda^n \end{pmatrix}.
\]
The general solution of \(x_{n+1}=Ax_n\) when \(A\) has \(m\) distinct eigenvalues \(\lambda_m\) with
eigenvectors \(e_m\) is
\[
x_n = \sum_{j=1}^m c_j \lambda^n_j e_j.
\]
Here the coefficients \(c_j\) are determined from the initial condition (\(n=0\) in the previous equation)
\[
x_0 = \sum_{j=1}^m c_je_j.
\]
We can start with the simplest case
to motivate the criteria of stability. For linear ODES, the canonical example is the
scalar ODE \(\dot{x}=\lambda x\) with solution \(x(t)=x_0e^{\lambda t}\).
Therefore, the stability of the ODE is determined by \(\exp(\lambda t)\) as \(t\) goes to infinity,
or equivalently the boundary \(\mbox{Re}\lambda =0\). Similarly, if we look at the simplest
map \(x_{n+1}=\lambda x_n\), then \(x_n = \lambda^nx_0\). The stability is determined
by \(\lambda^n\) as \(n\) goes to infinity, or equivalently the boundary \(|\lambda|=1\)
(\(|\lambda|<1\) implies stability in the corresponding eigenspace). Now we can proceed for general cases in general dimensions.
Example 3.18(Saddle)
In Normal Form coordinates, the map is
\[
\begin{pmatrix}
x_{n+1} \\ y_{n+1}
\end{pmatrix}=\begin{pmatrix}
\lambda_1 & 0 \\ 0 & \lambda_2
\end{pmatrix}
\begin{pmatrix}
x_{n} \\ y_{n}
\end{pmatrix} \qquad
\text{ with }\qquad |\lambda_1| < 1 < |\lambda_2|. \] These two components \(x_{n+1}=\lambda_1 x_n, y_{n+1}=\lambda_2 y_n \) can be solved explicitly, to give \[x_{n}=\lambda_1^n x_0, \qquad \qquad y_{n}=\lambda_2^n y_0.\] We can take modulus on the solutions, \[ \frac{|x_n|}{|x_0|}=|\lambda_1|^n, \ \frac{|x_n|}{|x_0|}=|\lambda_1|^n. % \mbox{or }\qquad %\left| \frac{x_n}{x_0}\right|=%\left| \frac{y_n}{y_0}\right|^{\ln |\lambda_1|/\ln |\lambda_2|}. \] That is, the solution \((x_n,y_n)\) lies on the generalised hyperbola \[ \left\{ (x,y) \left|\ \left| \frac{x}{x_0}\right|=\left| \frac{y}{y_0}\right|^{\ln |\lambda_1|/\ln |\lambda_2|} \right. \right\}. \] The motion of these hyperbolas is discrete; an orbit hops along the relevant curve or curves as shown in Figure~\ref{fig:hops}. If an eigenvalue is negative then the orbit of a point will oscillate between negative and positive values in that eigen-direction as indicated in Figure~\ref{fig:hops}(b).
Saddles for discrete time equations (a) \(0 < \lambda_1< 1 < \lambda_2\); (b) \(-1< \lambda_1<0, \lambda_2>1\)
Example 3.19 (Focus)
The map in normal form is
\[
\begin{pmatrix}
x_{n+1} \\ y_{n+1}
\end{pmatrix}=\begin{pmatrix}
\rho & -\omega \\ \omega & \rho
\end{pmatrix} \begin{pmatrix}
x_{n} \\ y_{n}
\end{pmatrix}.
\]
The geometric interpretation is clearer if we write the coefficient matrix as
\[
\begin{pmatrix}
\rho & -\omega \\ \omega & \rho
\end{pmatrix} =
\sqrt{\rho^2 + \omega^2} \;
\begin{pmatrix}
\frac{\rho}{ \sqrt{\rho^2 + \omega^2}} & -\frac{\omega}{ \sqrt{\rho^2 + \omega^2}}
\\ \frac{\omega}{ \sqrt{\rho^2 + \omega^2}} & \frac{\rho}{ \sqrt{\rho^2 + \omega^2}}
\end{pmatrix}
5 = \underbrace{\lambda}_\text{dilation} \underbrace{\begin{pmatrix}
\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \\
\end{pmatrix}}_\text{rotation by $\theta$}
\]
where \(\lambda = \sqrt{\rho^2+\omega^2}\) and \(\theta=\tan^{-1}(\omega/\rho)\).
If we define \(z_n = x_n + iy_n\), then in complex notation
\begin{multline*}
\quad z_{n+1} = x_{n+1}+i y_{n+1}
= \lambda \big[
(x_n \cos \theta -y_n \sin \theta) + i(x_n\sin\theta+y_n\cos\theta)
\big] \cr
= \lambda \big( \cos \theta + i\sin \theta\big)(x_n+iy_n)
=\lambda e^{i\theta}z_n.\quad
\end{multline*}
Therefore, the solution can be written as
\(z_{n} = \lambda^n e^{i n \theta} z_0 \), or equivalently
\[
x_n = \lambda^n (x_0\cos n\theta-y_0\sin n\theta),\quad
y_n = \lambda^n (x_0\sin n\theta+y_0\cos n\theta).
\]
Therefore, the solution \((x_n,y_n)\) converges to the origin if and only if
\(\lambda=\sqrt{\rho^2+\omega^2}<1\).
