\chapter{Discrete-Time System Stability}
\section{Notation and Definitions}
In this chapter we analyze stability of dynamic systems modeled by the difference equation
\[
\b x(k+1)=\b F(\b x(k)),
\]
where $k\in {\cal Z}_{+}$, ${\cal Z}_{+}$ denotes the set of nonnegative integers, $\b x:{\cal Z}_{+}\to \mb{\Bb R}^n$, that is, $\b x(k)$ is the state of the system at time $k$, and $\b F:\mb{\Bb R}^n \to \mb{\Bb R}^n$. We assume that the function $\b F$ is continuous on $\mb{\Bb R}^n$, that is, if $\b x^j \to \b y$ then $\b F(\b x^j) \to \b F(\b y)$.

If $\b x$ is a vector, then $\b F(\b x)$ is a vector and is the value of the function $\b F$ at $\b x$. If $\b x$ is a function, the symbol $\b F \b x$ denotes the composition of functions
\[
\left(\b F \b x\right)(k)=\b F(\b x(k)).
\]
Thus the equation $\b x(k+1)=\b F(\b x(k))$ can also be written as $\b x(k+1)=\b F \b x(k)$.

The solution to the initial value problem
\[
\b x(k+1)=\b F \b x(k), \quad \b x(0)=\b x^0
\]
is
\begin{eqnarray*}
\b x(k)&=& \b x^k\\
&=&\b F^k\left(\b x^0\right),
\end{eqnarray*}
where $\b F^k$ is the $k$th iterate of $\b F$, that is, $\b F^0=\b I_n$, and $\b F^k=\b F \b F^{k-1}$.

A state $\tilde{\b x} \in \mb{\Bb R}^n$ is a {\em fixed point\/} or an {\em equilibrium state\/} of the system $\b x(k+1)=\b F \b x(k)$ if $\b F\left(\tilde{\b x}\right)=\tilde{\b x}$. Thus the solution of the system that starts at $\tilde{\b x}$ stays at $\tilde{\b x}$ for all $k\ge 0$.

A subset ${\cal A} \subset \mb{\Bb R}^n$ is called {\em invariant\/} if $\b F({\cal A}) \subset {\cal A}$, that is, if $\b x \in {\cal A}$ then $\b F(\b x) \in {\cal A}$. It is clear that an equilibrium solution is invariant.

The solution through $\b x^0$ is bounded if there is a constant $M$ such that $\|\b F^k\left(\b x^0\right)\| \le M$ for all $k \ge 0$.

Consider again a particular solution $\b F^k\left(\b x^0\right)$. A point $\b y \in \mb{\Bb R}^n$ is a {\em limit point\/} or a {\em point of accumulation\/} of $\b F^k\left(\b x^0\right)$ if there is a subsequence $k_i$ such that $\b F^{k_i}\left(\b x^0\right) \to \b y$. The set of all limit points of $\b F^k\left(\b x^0\right)$ is called the {\em limit set\/} and denoted $\Omega\left(\b x^0\right)$.

A sequence $\{\b x^k\}$ is said to approach a set ${\cal A}$ if
\[
\rho\left(\b x^k,{\cal A}\right)=\inf \left\{\|\b x^k-\b y\|:\b y \in{\cal A} \right\} \to 0.
\]
\begin{lemma}
\label{lemma_lim_set}
Let $\b F$ be continuous. If $\b F^k\left(\b x^0\right)$ is bounded for all $k \ge 0$, then $\Omega\left(\b x^0\right)$ is non-empty, compact invariant set. Furthermore, $\b F^k\left(\b x^0\right) \to \Omega\left(\b x^0\right)$ as $k \to \infty$.
\end{lemma}
{\bf Proof}\quad Since $\left\{\b x^k\right\}$ is bounded, by the Bolzano-Weierstrass theorem there is at least one limit point of $\left\{\b x^k\right\}$ and so $\Omega\left(\b x^0\right)$ is non-empty and bounded. The set $\Omega\left(\b x^0\right)$ contains only its limit points and hence it is closed. Since it is also bounded, it is compact.

We now show that $\Omega\left(\b x^0\right)$ is invariant.  For this let $\b y \in \Omega\left(\b x^0\right)$. Hence, there is a subsequence $k_i$ such that $\b x^{k_i} \to \b y$. Since $\b F$ is continuous, $\b x^{k_i + 1} = \b F\left(\b x^{k_i}\right) \to \b F(\b y)$ as $i \to \infty$. Therefore $\b F(\b y) \in \Omega\left(\b x^0\right)$ which implies that $\Omega\left(\b x^0\right)$ is invariant. Note that we do not have to have $\b y=\b F(\b y)$.

Finally, we show that $\b F^k\left(\b x^0\right) \to \Omega\left(\b x^0\right)$ as $k \to \infty$. We prove the statement by contradiction. First observe that $\rho\left(\b x^k,\Omega\left(\b x^0\right)\right)$ is bounded since both $\left\{\b x^k\right\}$ and $\Omega\left(\b x^0\right)$ are. Assume that $\rho\left(\b x^k,\Omega\left(\b x^0\right)\right)$ does not converge to zero. Then, there is a subsequence $k_i$ such that $\b x^{k_i} \to \b y$ and $\rho\left(\b x^{k_i},\Omega\left(\b x^0\right)\right) \to a>0$. But since $\b y \in \Omega\left(\b x^0\right)$,
\[
\rho\left(\b x^{k_i},\Omega\left(\b x^0\right)\right)\le \|\b x^{k_i}-\b y\| \to 0,
\]
and thus $\rho\left(\b x^{k_i},\Omega\left(\b x^0\right)\right) \to 0$ which is a contradiction. The proof of the lemma is now complete.\\
\hspace*{5.5in} $\Box$

\section{LaSalle's Invariance Principle}
Let $V:\mb{\Bb R}^n \to \mb{\Bb R}$. Define the {\em Lyapunov difference\/} of $V$ relative to $\b x(k+1)=\b F \b x(k)$, or $\b F$, as
\[
\Delta V(\b x)=V\left(\b F(\b x)\right)-V(\b x).
\]
If $\b x(k)$ is a solution of $\b x(k+1)=\b F \b x(k)$, then the Lyapunov difference of $V$ relative to $\b F$ is
\[
\Delta V(\b x(k))=V\left(\b x(k+1)\right)-V(\b x(k)).
\]
If $\Delta V(\b x(k))\le 0$, then $V$ is non-increasing along solutions of the system.

We say that $V$ is a {\em Lyapunov\/} function for $\b x(k+1)=\b F \b x(k)$ on a set ${\cal G} \subseteq \mb{\Bb R}^n$ if
\begin{enumerate}
\item $V$ is continuous on $\mb{\Bb R}^n$, and
\item $\Delta V(\b x(k))\le 0$ for all $\b x(k) \in {\cal G}$.
\end{enumerate}
\begin{thm}[LaSalle's Invariance Principle]
If
\begin{enumerate}
\item $V$ is a Lyapunov function for $\b x(k+1)=\b F \b x(k)$ in ${\cal G}$, and
\item the solution $\b F^k\left(\b x^0\right)$ is bounded and in ${\cal G}$,
\end{enumerate}
then, there is a number $c$ such that $\b F^k\left(\b x^0\right) \to {\cal M} \cap V^{-1}(c)$, where ${\cal M}$ is the largest invariant set contained in the set ${\cal E}=\left\{\b x \in \mb{\Bb R}^n:\Delta V = 0\right\}\cap \bar{\cal G}$, where $\bar{\cal G}$ denotes the closure of ${\cal G}$.
\end{thm}
{\bf Proof} \quad Since $\b x^k=\b F^k\left(\b x^0\right)$ is bounded and in ${\cal G}$, by Lemma~\ref{lemma_lim_set} the limit set $\Omega\left(\b x^0\right)$ is non-empty and in ${\cal G}$. Furthermore, $\b x^k$ tends to $\Omega\left(\b x^0\right)$. Now $\left\{V\left(\b x^k\right)\right\}$ is non-increasing and bounded below, so $V\left(\b x^k\right) \to c$ for some $c$. If $\b y \in \Omega\left(\b x^0\right)$, then there is a subsequence $k_i$ such that $\b x^{k_i} \to \b y$, and hence $V\left(\b x^{k_i}\right) \to V(\b y)$, that is, $V(\b y)=c$. Thus $V\left(\Omega\left(\b x^0\right) \right)=c$, and hence $\Omega\left(\b x^0\right) \subset V^{-1}(c)$. Since $V\left(\Omega\left(\b x^0\right) \right)=c$ and $\Omega\left(\b x^0\right)$ is invariant, we have $\Delta V\left(\Omega\left(\b x^0\right)\right)=0$. In summary
\[
\b x^k \to \Omega\left(\b x^0\right) \subset \left\{\b x \in \mb{\Bb R}^n: \Delta V=0 \right\}\cap \bar{\cal G} \cap V^{-1}(c).
\]
Since $\Omega\left(\b x^0\right)$ is invariant we have $\Omega\left(\b x^0\right) \subset {\cal M}$, and the proof of the theorem is complete.\\
\hspace*{5.5in} $\Box$\\
Using the above theorem we can study stability properties of difference equations.

The general approach of the LaSalle Invariance Principle can be used to prove a result concerning the instability of isolated equilibrium states. An equilibrium point $\tilde{\b x}$ is isolated if there is an $\varepsilon >0$ such that there is no other equilibrium point, other than $\tilde{\b x}$, in the ball $B_{\varepsilon}\left(\tilde{\b x}\right)$.
\begin{thm}
Let $\tilde{\b x}$ be an isolated equilibrium state of $\b x(k+1)=\b F \b x(k)$. Let $\Delta V$ be positive definite with respect to $\tilde{\b x}$, and let $V$ take positive values arbitrarily close to $\tilde{\b x}$, and $V\left(\tilde{\b x}\right)=0$, then $\tilde{\b x}$ is unstable.
\end{thm}
{\bf Proof} \quad We prove the theorem by contradiction. We thus assume that $\tilde{\b x}$ is stable. Let $\varepsilon > 0$ be so small that $\Delta V(\b x) >0$ for all $\b x \in B_{\varepsilon}\left(\tilde{\b x}\right)\setminus \left\{\tilde{\b x}\right\}$. Since by assumption $\tilde{\b x}$ is stable, there is $\delta > 0$ so that if $\b x^0 \in B_{\delta}\left(\tilde{\b x}\right)$ then $\b x^k = \b F^k\left(\b x^0\right) \in B_{\varepsilon}\left(\tilde{\b x}\right)$ for all $k \ge 0$. By assumption there is a point $\b x^0$ such that $V\left( \b x^0 \right) >0$. Since $\b x^k$ is bounded and remains in $B_{\varepsilon}\left(\tilde{\b x}\right)$, by Lemma~\ref{lemma_lim_set} the sequence $\left\{\b x^k\right\}$ tends to $\left\{\b x:\Delta V(\b x) = 0 \right\} \cap B_{\varepsilon}\left(\tilde{\b x}\right)=\tilde{\b x}$. Another way to arrive at the above observation is as follows. Note that $-V$ is a Lyapunov function because $\Delta (-V)<0$. Since $\b x^k$ is bounded we can apply the Invariance Principle to conclude that $\b x^k$ tends to $\left\{ \b x:\Delta (-V(\b x))=0 \right\}$. But $\left\{ \b x:\Delta (-V(\b x))=0 \right\}=\left\{\tilde{\b x}\right\}$. Thus, indeed $\b x^k \to \tilde{\b x}$. Using the above we conclude that $V\left(\b x^k\right) \to V\left(\tilde{\b x} \right) = 0$. However, $\Delta V\left(\b x^k\right) > 0$ and so
\[
V\left(\b x^k\right) \ge V\left(\b x^{k-1}\right)\ge \cdots V\left(\b x^0\right) > 0.
\]
Hence $V\left(\b x^k\right)>0$. The above contradiction completes the proof.\\
\hspace*{5.5in} $\Box$
