\chapter{Stability of Dynamical Systems}
Our next task is to investigate stability properties of the equilibrium points of the BSUB model. In our analysis we use stability in the sense of Lyapunov which we define next. We refer the reader for more information on the subject of the stability in the sense of Lyapunov to LaSalle~\cite{lasalle86}.
\begin{defn}
An isolated equilibrium point $\tilde{\b x}$ of a dynamic system model is said to be stable in the sense of Lyapunov if for any scalar $\epsilon >0$, there is a $\delta >0$ such that 
\[
\| \b x(0)-\tilde{\b x} \| < \delta 
\Rightarrow
\| \b x(k)-\tilde{\b x} \| < \epsilon ,
\quad \mbox{for all} \quad k \ge 0.
\]
\end{defn}
If the equilibrium point $\tilde{\b x}$ is not stable then it is called {\em unstable}.
\begin{defn}[Asymptotic stability]
An isolated equilibrium point $\tilde{\b x}$ is said to be asymptotically stable if in addition to being stable in the sense of Lyapunov, there exists $d>0$ so that $\b x(k)\rightarrow \tilde{\b x}$ as $k \rightarrow \infty$ if 
$\|\b x(0)-\tilde{\b x}\|<d.$
\end{defn}

In our further stability analysis of the equilibrium points we use the Invariant Set Theorem. We refer to LaSalle~\cite[page 9]{lasalle86} or Luenberger~\cite[page 346]{luenberger79} for discussions of the Invariant Set Theorem and its variants. The LaSalle Invariant Set Theorem, also known as the Invariance Principle, was already used by Cohen and Grossberg~\cite{cohen83} in their analysis of a general class of continuous neural networks. However, the results of Cohen and Grossberg cannot be used directly to analyze discrete-time neural networks. A discrete-time version of the Cohen-Grossberg theorem was developed by Marcus and Westervelt~\cite{marcus89} which can be applied to the analysis of the BSB as well as the generalized BSB neural models. The Invariant Set Theorem was also used by Golden in his study of the BSB model. We now discuss the Invariance Principle of LaSalle. Our discussion is based on the exposition of LaSalle~\cite{lasalle86}.

Consider a dynamic system modeled by the difference equation
\[
\b x(k+1)=\b F(\b x(k)),
\]
where $k=0,1,\ldots$, 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)$.

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}$. 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$.

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

Consider a 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 $G$ if
\[
\rho\left(\b x^k,G\right)=\inf \left\{\|\b x^k-\b y\|:\b y \in G \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$

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$

To complete the discussion of stability of dynamic systems we present now a continuous version of LaSalle's Invariance Principle. We use Barbalat's lemma in our proof.
\begin{lemma}[Barbalat's lemma]
Let $f$ be a differentiable real function such that $\dot{f}$ is uniformly continuous. Suppose $\lim_{t \rightarrow \infty}{\dot{f}(t)}$ exists. Then,
\[
\lim_{t \rightarrow \infty}{\dot{f}(t)}=0.
\] 
\end{lemma}
{\bf Proof}\quad Since $\dot{f}$ is uniformly continuous for every $\epsilon>0$ there is a $\delta_{\epsilon}$ such that if $|t_1-t_2|<\delta_{\epsilon}$ then $|\dot{f}(t_1)-\dot{f}(t_2)|<\epsilon$ .

Let $\delta=\delta_\epsilon$ then for any $t$ and $a$ such that $|t-a|<\delta$ we have $|\dot{f}(t)-\dot{f}(a)|<\frac{\epsilon}{2}$. If $\dot{f}(t)>\epsilon$ then we get
\[
\epsilon-\dot{f}(a)<|\epsilon-\dot{f}(a)|<|\dot{f}(t)-\dot{f}(a)|<\frac{\epsilon}{2}.
\]
So we proved that for every $\epsilon>0$ there is a $\delta>0$ such that if $|t-a|<\delta$ and $\dot{f}(t)>\epsilon$ then $\dot{f}(a)>\frac{\epsilon}{2}$. 
We need to show that $\lim_{t \rightarrow \infty}{\dot{f}(t)}=0$. We use a proof by contradiction. Suppose it is not true. Then there is a sequence $t_n$ such that for every $n>0$ $\dot{f}(t_n)>\epsilon>0$ for some positive $\epsilon$, because $\dot{f}(t)$ is bounded away from $0$. We showed previously that we can choose a $\delta$ such that if $|t_n-a|<\delta$ and $\dot{f}(t_n)>\epsilon$  then $\dot{f}(a)>\frac{\epsilon}{2}$. Then, 
\[
\int_{t_n}^{t_n+\delta}\dot{f}(t)dt>\int_{t_n}^{t_n+\delta}\frac{\epsilon}{2}dt=\delta \frac{\epsilon}{2}. 
\]
However,
\[
\int_{t_n}^{t_n+\delta}\dot{f}(t)dt=f(t_n +\delta)-f(t_n)
\]
so we get 
\[
f(t_n +\delta)-f(t_n)>\delta \frac{\epsilon}{2}>0 \quad \mb{for every} \quad n 
\]
which contradicts our assumption that $\lim_{t\rightarrow \infty}{f(t)}$ exists. The proof is now complete.\\
\hspace*{5.5in}$\Box$
\begin{thm}
Given a model of a dynamic system $\dot{\b x}=\b F(\b x)$, 
with $\b F$ continuous and let $V(\b x)$ be a real valued function with continuous first partial derivatives. Assume that
\begin{itemize}
\item for some $l>0$ the region
\[
\Omega_l=\{\b x:V(\b x)<l\}
\]
is bounded, and
\item $\dot{V}(\b x)\le 0$ in $\Omega_l$.
\end{itemize}
Let $R$ be the set of all points in $\Omega_l$ where $\dot{V}(\b x)=0$, and $M$ be the largest invariant set in $R$. Then every trajectory $\b x(t)$ originating in $\Omega_l$ tends to $M$ as $t\to \infty$.
\end{thm}
{\bf Proof}\quad We prove the Theorem in two steps. First step is to prove that $\dot{V}$ converges to $0$ for any trajectory starting from a point in $\Omega_l$.

Let $\b x_0$ be in $\Omega_l$. Then the trajectory $\b x(t)$ stays in $\Omega_l$ for every $t$ because $\dot{V}\leq 0$ implies that $V(\b x(t))\leq V(\b x(0))<l$ for every $t$. $V(\b x)$ is continuous in $\b x$ because it is differentiable with respect to x, therefore it is lower bounded on $\Omega_l$, which is bounded. Then $V(\b x(t))$ is also lower bounded for every $t$, since it is inside $\Omega_l$. If $V(\b x(t))$ is lower bounded and decreasing then it converges to a limit.

We can also show that $\dot{V}$ is uniformly continuous in $t$. By Chain Rule we have $\dot{V}(t)=\nabla V(\b x(t)) \dot{\b x}(t)$. $\nabla V$ is continuous on $\Omega_l$ therefore it is uniformly continuous. So we need to show that $\dot{\b x}(t)=\b F(\b x(t)) $ is uniformly continuous. Since $\b F$ is uniformly continuous we only need to show that $\b x(t)$ is uniformly continuous.

Let $t$ and $s$ be in $\Omega_l$. Then, 
\begin{eqnarray*}
|\b x(t)-\b x(s)|&=&\left|\int_s^t\dot{\b x}(p)dp\right|\\
&\leq&\int_s^t|\dot{x}(p)|dp\\
&\leq&\int_s^t\max_{\Omega_l}|\b F|dp\\
&\leq& |t-s|\max_{\Omega_l}|\b F|.
\end{eqnarray*}
Now we have for every $\epsilon>0$ a $\delta_{\epsilon}>0$ such that whenever $|t-s|<\delta_{\epsilon}$ we have
\[
|\b x(t)-\b x(s)|\leq\delta_{\epsilon} \max_{\Omega_l}|\b F|. 
\]
If  $\max_{\Omega_l}|\b F|= c$ then $\delta_{\epsilon}=\frac{\epsilon}{c}$ will satisy the definition of the uniform continuity of $\b x(t)$, which completes the proof of the uniform continuity of $\dot{V}(\b x(t))$.

We showed that $V(\b x(t))$ satisfies the conditions of Barbalat's lemma, which implies that $\dot{V}(\b x(t))$ converges to $0$, that is all system trajectories starting within $\Omega_l$ converge to the set $R$.

In the second part we will show that the trajectories cannot converge to anywhere in the set $R$, they must converge to an invariant set in $R$. Let's define a family of operators:
\[
\b F_k(\b x(t))=\b x(t+k)
\]
For every $k$ the operator $\b F_k$ is uniformly continuous, since it is continuous on a compact set. Let's call a point $\b p$ in $R$ a limit point if there is a subsequence of a trajectory, $\b x(t_i)$ which converges to $\b p$. The set of limit points in $R$ will be called $\mb{Lim}\, R$.We will show that if $\b p$ is a limit point then $\b F_k(\b p)$ is also a limit point for any $k$, which implies that $\mb{Lim}\, R$ is an invariant set.

Suppose that $\b F_k(\b p)$ is not in $\mb{Lim}\, R$. Then there  is $\bar{\epsilon}>0$ and an $s>0$ such that for every $t>s$ we have
\[
\|\b x(t)-\b F_k(\b p)\|>\bar{\epsilon}.
\]
Since $\b p$ is in $\mb{Lim}\, R$ we have for every $\delta>0$ that
\[
\|\b p-\b x(t_n)\|<\delta
\]
for sufficiently big $n$. The uniform continuity of $\b F_k$ gives us a $\delta_{\bar{\epsilon}}$ such that for every $\|\b p-\b x(t_n)\|<\delta_{\bar{\epsilon}}$ we have
\[
\|\b F_k(\b p)-\b F_k\b x(t_n)\|<\bar{\epsilon}.
\]
But
\[
\|\b F_k(p)-\b F_k(\b x(t_n))\|=\|\b F_k(\b p)-\b x(t_n+k)\|<\bar{\epsilon}.
\]
This inequality holds for any $k$, which gives us the contradiction because we had that
\[
\|\b F_k(\b p)-\b x(t)\|>\bar{\epsilon}
\]
for any $t$ big enough.

With this we proved that the trajectories tend to an invariant set $\mb{Lim}\, R$, which is in $R$ so they tend to the largest invariant set in $R$. The proof of LaSalle's Invariance Principle is now complete.\\
\hspace*{5.5in}$\Box$