Some math behind Control Theory
1. Stability
1.1. Continuous-time Stability
Definition: A square matrix $A\in\mathbb{R}^{n\times n}$ is Hurwitz-stable iff.
\begin{gather*}
Re[\lambda_i(A)]<0,\ \forall i=1,\cdots,n
\end{gather*}
This Theorem was originated from control theory. I would like to present an algebra view-point.
Proof of the Theorem
Necessary condition '$\Leftarrow$'
This is a common result in control theory in which one can prove using contradiction. Suppose there exists $P\succ 0,1\leq i\leq n$ such that \eqref{eq:continuous-time Lyapunov inequality} holds and $Re[\lambda_i(A)]\geq 0$. Consider the following dynamics: \begin{gather*} \dot{x}(t)=Ax(t), x(0)=x_0. \end{gather*} For any $x_0\neq 0,\displaystyle\lim_{t\to\infty}x(t)\neq 0$. However, consider the Lyapunov function $V(x)=x^TPx$. From \eqref{eq:continuous-time Lyapunov inequality}, it holds that: \begin{gather*} \frac{d}{dt}{V}(x)=x^T\left(PA+A^TP\right)x<0,\forall x\neq 0\\ v(x)> 0,\forall x(t)\neq 0 \end{gather*} By LaSalle's invariance principle, it holds that $x(t)\to 0$, which contradicts the condition that $\displaystyle\lim_{t\to\infty}x(t)\neq 0$.Sufficient condition '$\Rightarrow$'
Since $A$ is real, from linear algebra, there always exists invertible $Q\in\mathbb{R}^{n\times n}$ such that $A=Q^{-1}JQ$, where \begin{gather} \label{eq: similar transfrom for J} \begin{array}{c} J=diag\left\{ J_1,\cdots, J_m \right\}, J_i=\begin{bmatrix} C_i&I&0&0\\ 0&C_i&I&0\\ 0&0&\ddots&\vdots\\ 0&0&\cdots&C_i \end{bmatrix},\\ C_i=\lambda_i\in\mathbb{R}, \text{ or } C_i= \begin{bmatrix} a_i&b_i\\ -b_i&a_i \end{bmatrix}. \end{array} \end{gather} These $J_i$ are called real Jordan block. Apply the congruent transformation to \eqref{eq:continuous-time Lyapunov inequality} with $Q^{-1}$, one can find: \begin{gather*} Q^{-T}PQ^{-1}J+J^TQ^{-T}PQ^{-1}\prec0. \end{gather*} Denote $\hat{P}:=Q^{-T}PQ^{-1}$, it leads to \begin{gather} \hat{P}J+J^T\hat{P}\prec0. \label{eq: transoformed continuous-time Lyapunov equation} \end{gather} If we construct $\hat{P}$ to be also diagonally arranged with corresponding dimension: $ diag\{\hat{P}_1,\cdots,\hat{P}_m\}$, the resulting \eqref{eq: transoformed continuous-time Lyapunov equation} will be block diagonal. Therefore, it suffices to prove the case that $J$ is a single Jordan block, i.e., $m=1$.- When $C$ is real. Note here if $J$ is a scalar, then we are done. Because any $\hat{P}>0$ satisfies \eqref{eq: transoformed continuous-time Lyapunov equation}. What we are really dealing with, is the case where $\ell=dim(J)\geq 2$. To show there exists $\hat{P}$ such that \eqref{eq: transoformed continuous-time Lyapunov equation} holds, constructing $\hat{P}=diag\{\hat{p}_1,\cdots,\hat{p}_\ell\}$. With the proposed $\hat{P}$, \eqref{eq: transoformed continuous-time Lyapunov equation} becomes:
\begin{gather}
\label{eq: expended continuous-time Lyapunov function}
\begin{bmatrix}
2\hat{p}_1\lambda&\hat{p}_1&&&\\
\hat{p}_1&2\hat{p}_2\lambda&\hat{p}_2&&\\
&\hat{p}_2&\ddots&\ddots&\\
&&\ddots&\ddots&\hat{p}_{\ell-1}\\
&&&\hat{p}_{\ell-1}&2\hat{p}_\ell\lambda
\end{bmatrix}\prec0, \lambda<0. \end{gather} finite induction is used to prove such $\hat{p}$ exists. pick any $\hat{p}_\ell>0$
- For the case $\ell =2$, \eqref{eq: transoformed continuous-time Lyapunov equation} becomes: \begin{gather*} \begin{bmatrix} 2\hat{p}_1\lambda&\hat{p}_1\\ \hat{p}_1&2\hat{p}_2\lambda \end{bmatrix}\prec0\Leftrightarrow 2\hat{p}_2\lambda-\frac{1}{2}\hat{p}_1\lambda^{-1}<0\leftrightarrow 4\hat{p}_2\lambda^2>\hat{p}_1, \end{gather*} where such $\hat{p}_1$ always exists.
-
For the case that $\ell>2$, suppose $\hat{p}_\ell,\cdots,\hat{p}_{2}$ have been chosen, \eqref{eq: transoformed continuous-time Lyapunov equation} looks like:
\begin{gather*}
\begin{bmatrix}
\begin{array}{c|ccccc}
2\hat{p_1}\lambda&\hat{p}_1&&\\
\hline
\hat{p}_1& 2\hat{p}_2\lambda&\hat{p}_2&&\\
&\hat{p}_2&\ddots&\ddots&\\
&&\ddots&\ddots&\hat{p}_{\ell-1}\\
&&&\hat{p}_{\ell-1}&2\hat{p}_\ell\lambda
\end{array}
\end{bmatrix}\prec0
\end{gather*}
By Schur complement, it is equivalent to
\begin{gather*}
\begin{bmatrix}
2\hat{p_1}\lambda&\hat{p}_1\\
\hat{p}_1&\alpha
\end{bmatrix}\prec 0,
\end{gather*}
for some $\alpha<0$, in which such $\hat{p}_1$ always exists.
-
When $C=
\begin{bmatrix}
a&b\\
-b&a
\end{bmatrix}$, I would like to transfer it back to case 1. Consider $\hat{P}=diag\{\hat{p}_1,\hat{p}_1,\hat{p}_2,\hat{p}_2,\cdots,\hat{p}_\ell,\hat{p}_\ell\}$. Then \eqref{eq: transoformed continuous-time Lyapunov equation} becomes:
\begin{gather*}
\begin{bmatrix}
2\hat{p}_1\lambda&0&\hat{p}_1&0 &&&&\\
0&2\hat{p}_1\lambda&0&\hat{p}_1 &&&&\\
\hat{p}_1&0&2\hat{p}_2\lambda&0&\hat{p}_2&0\\
0&\hat{p}_1&0&2\hat{p}_2\lambda&0&\hat{p}_2 &&\\
&& \hat{p}_2&0&\ddots&\ddots&&\\
&&0&\hat{p}_2&\ddots&\ddots&\ddots&\\
&&&&\ddots&\ddots&\ddots&\ddots&\\
&&&&&&2\hat{p}_{\ell-1}\lambda&0&\hat{p}_{\ell-1}&0\\
&&&&&&0&2\hat{p}_{\ell-1}\lambda&0&\hat{p}_{\ell-1}\\
&&&&&&\hat{p}_{\ell-1}&0&2\hat{p}_\ell\lambda&0\\
&&&&&&0&\hat{p}_{\ell-1}&0&2\hat{p}_\ell\lambda
\end{bmatrix}\prec 0.
\end{gather*}
By selecting odd rows and columns and even rows and columns, one can find it gets identical expressions as in \eqref{eq: expended continuous-time Lyapunov function}.
࢘
\eqref{eq:continuous-time Lyapunov inequality} requires to solve a LMI. Even though it can be done with modern SDP solver. There is a result that only requires to solve a linear (Lyapunov) equation.
The proof is to construct such $P$ given $Q$.
Proof of the Theorem
Necessary condition '\eqref{eq:continuous-time Lyapunov inequality}$\Leftarrow$\eqref{eq:continuous-time Lyapunov equation}'
This is trivial because such $P$ will automatically satisfy \eqref{eq:continuous-time Lyapunov inequality}Sufficient condition '\eqref{eq:continuous-time Lyapunov inequality}$\Rightarrow$\eqref{eq:continuous-time Lyapunov equation}'
Construct \begin{gather*} \displaystyle P=\int_0^\infty e^{A\tau}Qe^{A^T\tau}d\tau, \end{gather*} Then it holds that \begin{gather*} \begin{aligned} A^TP+PA&=\displaystyle \int_0^\infty Ae^{A\tau}Qe^{A^T\tau}+e^{A\tau}Qe^{A^T\tau}A^Td\tau\\ &=\displaystyle \int_0^\infty \frac{d}{d\tau}e^{A\tau}Qe^{A^T\tau}d\tau\\ &=\left.e^{A\tau}Qe^{A^T\tau}\right|_0^\infty\\ &=-Q. \end{aligned} \end{gather*}1.2. Discrete-time Stability
Definition: A square matrix $A\in\mathbb{R}^{n\times n}$ is Schur-stable iff.
\begin{gather*}
|\lambda_i(A)|<1,\ \forall i=1,\cdots,n.
\end{gather*}
Similarly, the algebra view-point is provided.
Proof of the Theorem
Necessary condition '$\Leftarrow$'
This is a common result in control theory in which one can prove using contradiction. Suppose there exists $P\succ 0,1\leq i\leq n$ such that \eqref{eq:discrete-time Lyapunov inequality} holds and $|\lambda_i(A)|\geq1$. Consider the following dynamics: \begin{gather*} x(k+1)=Ax(k), x(0)=x_0. \end{gather*} For any $x_0\neq 0,\displaystyle\lim_{k\to\infty}x(k)\neq 0$. However, consider the Lyapunov function $V(x)=x^TPx$. From \eqref{eq:discrete-time Lyapunov inequality}, there exists $\alpha>0$ such that:
Sufficient condition '$\Rightarrow$'
Similar to what have done in continuous-time case, but instead of considering real Jordan block, we consider the complex case: \begin{gather*} J_i=\begin{bmatrix} \lambda_i&1&&&\\ &\lambda_i&1&&\\ &&\ddots&\ddots&\\ &&&\lambda_i&1\\ &&&&\lambda_i \end{bmatrix},\lambda_i\in\mathbb{C}. \end{gather*} For real $A\in\mathbb{R}^{n\times n}$, it holds that both $J_i$ and $\bar{J}_i$ are in the Jordan decomposition. Here, it does not matter which $J_i$ to pick, as we only focus on the module. In such case $Q$ is a complex matrix. Apply the congruent transformation to \eqref{eq:discrete-time Lyapunov inequality} with $Q^{-1}$, one can find: \begin{gather*} Q^{-H}PQ^{-1}-J^HQ^{-H}PQ^{-1}J\succ0. \end{gather*} where $Q^{H}$ is the Hermitian matrix of $Q$. Denote $\hat{P}:=Q^{-H}PQ^{-1}\in\mathbb{R}^{n\times n}$, it leads to \begin{gather} \hat{P}-J^H\hat{P}J\succ0. \label{eq: transoformed discrete-time Lyapunov equation} \end{gather} If we construct $\hat{P}$ to be also diagonally arranged with corresponding dimension: $ diag\{\hat{P}_1,\cdots,\hat{P}_m\} $, the resulting \eqref{eq: transoformed discrete-time Lyapunov equation} will be block diagonal. Therefore, it suffices to prove the case that $J$ is a single Jordan block, i.e., $m=1$. Construct $\hat{P}=diag\{\hat{p}_1,\cdots,\hat{p}_\ell\}$, \eqref{eq: transoformed discrete-time Lyapunov equation} becomes: \begin{gather} \begin{bmatrix} \hat{p}_1-\hat{p}_1|\lambda|^2&\hat{p}_1\lambda&&&\\ \hat{p}_1\bar{\lambda}&\hat{p}_2-\hat{p}_2|\lambda|^2&\hat{p}_2\lambda&&\\ &\hat{p}_2\bar{\lambda}&\ddots&\ddots&\\ &&\ddots&\ddots&\hat{p}_{\ell-1}\lambda\\ &&&\hat{p}_{\ell-1}\bar{\lambda}&\hat{p}_\ell-\hat{p}_\ell|\lambda|^2 \end{bmatrix}\succ0, |\lambda|<1. \label{eq: expended discrete-time lyapunov function} \end{gather}Trivially, if $\lambda=0$, then it becomes $\hat{P}\succ0$, which is always true. Finite induction is used to prove such $\hat{P}$ exists for any $0<|\lambda|<1$. pick any $\hat{p}_\ell>0$
- For the case $\ell =2$, \eqref{eq: transoformed discrete-time Lyapunov equation} becomes: \begin{gather*} \begin{bmatrix} \hat{p}_1-\hat{p}_1|\lambda|^2&\hat{p}_1\lambda\\ \hat{p}_1\bar{\lambda}&\hat{p}_2-\hat{p}_2|\lambda|^2 \end{bmatrix}\succ0\Leftrightarrow \hat{p}_2(1-|\lambda|^2)-\hat{p}_1\frac{|\lambda|^2}{1-|\lambda|^2}>0\\ \Leftrightarrow \hat{p}_1<\hat{p}_2\frac{(1-|\lambda|^2)^2}{|\lambda|^2}. \end{gather*} where such $\hat{p}_1$ always exists. < li>
- For the case that $\ell>2$, suppose
have been chosen, \eqref{eq: transoformed discrete-time Lyapunov equation} looks like: \begin{gather*} \begin{bmatrix} \begin{array}{c|ccccc} \hat{p}_1-\hat{p_1}|\lambda|^2&\hat{p}_1\lambda&&\\ \hline \hat{p}_1\bar{\lambda}& \hat{p}_1-\hat{p_1}|\lambda|^2&\hat{p}_2\lambda&&\\ &\hat{p}_2\bar{\lambda}&\ddots&\ddots&\\ &&\ddots&\ddots&\hat{p}_{\ell-1}\lambda\\ &&&\hat{p}_{\ell-1}\bar{\lambda}&\hat{p}_\ell-\hat{p}_\ell|\lambda|^2 \end{array} \end{bmatrix}\succ0 \end{gather*} By Schur complement, it is equivalent to \begin{gather*} \begin{bmatrix} \hat{p}_1-\hat{p_1}|\lambda|^2&\hat{p}_1\lambda\\ \hat{p}_1\bar{\lambda}&\alpha \end{bmatrix}\succ 0, \end{gather*} for some $\alpha>0$, in which such $\hat{p}_1$ always exists such that $\hat{p}_1<\frac{\alpha(1-|\lambda|^2)}{|\lambda|^2}$.
࢘
Similarly, \eqref{eq:discrete-time Lyapunov inequality} requires to solve a LMI. Even though it can be done with modern SDP solver, there is a result that only requires to solve a linear (Lyapunov) equation.
The proof is to construct such $P$ given $Q$.
Proof of the Theorem
Necessary condition '\eqref{eq:discrete-time Lyapunov inequality}$\Leftarrow$\eqref{eq:discrete-time Lyapunov equation}'
This is trivial because suchSufficient condition '\eqref{eq:discrete-time Lyapunov inequality}$\Rightarrow$\eqref{eq:discrete-time Lyapunov equation}'
Construct \begin{gather*} \displaystyle P=\sum_{k=0}^\infty (A^{T})^kQA^k, \end{gather*} Then it holds that \begin{align*} P-A^TPA&=\displaystyle \sum_{k=0}^\infty (A^{T})^kQA^k-\sum_{k=0}^\infty (A^{T})^{k+1}QA^{k}\\ &=Q. \end{align*}1.3. Relation between Continuous-time and Discrete-time Stability
While the proof for the theorems are very technical, but if one knows discrete-time version, the continuous-time version can be deduced easily. The other way around is a little hard to show, but there are some relations.
Suppose we already knows \eqref{eq:discrete-time Lyapunov inequality} holds iff. $A$ is Schur stable. Then for a given matrix $B\in\mathbb{R}^{n\times n}$, we would like to find that $B$ is Hurwitz stable iff. the condition \eqref{eq:continuous-time Lyapunov inequality} holds.
Approximate the left hand plane using a large circle
Observation: Given a matrix $A$, its eigenvalues lie in the discUse $e^{Bt}$ for sufficiently small $t$
Another way to find \eqref{eq:continuous-time Lyapunov inequality} from \eqref{eq:discrete-time Lyapunov inequality} is to exploit the matrix exponential : $e^{Bt}$. For Hurwitz stable matrix $B$, it should hold that the matrix $e^{Bt}$ is Shur stable for sufficiently small $t<\frac{1}{\max\{|\lambda(b)|\}}$, see Analytic function of a matrix for detail. Taking $e^{Bt}$ into \eqref{eq:discrete-time Lyapunov inequality}: \begin{gather*} P-(e^{Bt})^TPe^{Bt}\succ0. \end{gather*} By the definition of the matrix exponential, for sufficiently small (not zero!) $t$, above equation can be expanded using power series. One can gather the terms of magnitude $\varepsilon$ and disregard the higher order term: \begin{gather*} P-\left[ I+Bt+o(t) \right]^TP\left[ I+Bt+o(t) \right]\succ0\\ -t(B^TP+PB)+o(t)\succ0. \end{gather*} The notation $o(t)$ stands for the matrix term that is of higher order of $t$, e.g., $t^2,t^3.\cdots$. When $t\to 0$, the above inequality becomes \eqref{eq:continuous-time Lyapunov inequality}.Use Euler Approximation
A simliar idea can be find using the Euler method, instead of using matrix exponential $e^{Bt}$, we use
Möbius transformation
I learn this fourth way in complex analysis class, where there is something called Linear fractional transformation, or Möbius transformation, which is in the form: \begin{gather*} f(z)=\frac{az+b}{cz+d}, \end{gather*} which maps lines and circles to lines and circles. One can check that the following mapping maps the left half plane to the unit circle centered at $0$: \begin{gather*} f(z)=\frac{1+z}{1-z},\\ \left|f(z)\right|^2=\left| \frac{1+z}{1-z} \right|^2=\frac{1+z}{1-z}\cdot \frac{1+\bar{z}}{1-\bar{z}}=\frac{1+2Re(z)+|z|^2}{1-2Re(z)+|z|^2}<1. \end{gather*}Therefore, given a Hurwitz stable matrix $B$, the matrix $A=(I+B)(I-B)^{-1}$ is Schur stable. A rigorous proof of this claim can be either inspect the Jordan decomposition applied to $(I-B)^{-1}$, or apply the Sylvester's formula to $A$. Take $A$ into \eqref{eq:discrete-time Lyapunov inequality}:
\begin{gather*} P-(I-B)^{-T}(I+B)^TP(I+B)(I-B)^{-1}\succ0,\\ (I-B)^TP(I-B)-(I+B)^TP(I+B)\succ0,\\ -2B^TP-2PB\succ0, \end{gather*} which is \eqref{eq:continuous-time Lyapunov inequality}.Suppose we already knows \eqref{eq:continuous-time Lyapunov inequality} holds iff. $A$ is Hurwitz stable. Then for a given matrix $B\in\mathbb{R}^{n\times n}$, we would like to deduce that $B$ is Schur stable iff. the condition \eqref{eq:discrete-time Lyapunov inequality} holds.
Logarithm of a matrix
This is an idea inspired by Logarithm of a matrix. First, let us claim that, for any Schur stable matrix $A$, fix any sampling time $T_s>0$, there exists Hurwitz stable $B$ such that \begin{gather*} e^{BT_s}=A. \end{gather*} Please note that such $B$ always exists, and can be found using Logarithm of a matrix if there is no eigenvalues of $A$ lie on negative real line. As matter of fact there are infinite choices of such $B$, because the image of Logarithm is the strip $-\pi< Im(z) <\pi$, any strips shifted by $2\pi$ will also work. there is a slight issue of continuity when the eigenvalue matrix $b$ lies on negative real axis. but here we are only considering existence $a$, so pick corresponding line $im(a)="\pi$" or both moreover, one can rotate $a$ to $ra^tr,r^tr="1$," such that eigenvalues do not lie avoid this trouble. anyway, always exists and should be well defined. now let us consider continuous-time dynamics: \begin{gather*} \dot{y}(t)="By(t)." \end{gather*} if take look $y(t)$ every other $t_s$ second: $x(k)="y(kT_s)$," able find exact expression: x(k+1)="e^{BT_s}x(k),x(0)=y(0)."Möbius transformation
Since we can map all the eigenvalues from left hand plane to a unit circle, the inverse is also viable. Consider the following transfermation: \begin{gather*} f(z)=\frac{z-1}{z+1},\\ \begin{aligned} f(z)+\overline{f(z)}&= \frac{z+1}{z-1}+\frac{\bar{z}+1}{\bar{z}-1}\\ & =\frac{z+1}{z-1}\cdot \frac{\bar{z}-1}{\bar{z}-1}+\frac{\bar{z}+1}{\bar{z}-1}\cdot\frac{z-1}{z-1}\\ &=\frac{2|z|^2-2}{|z|^2-2Re(z)+1}<0. \end{aligned} \end{gather*}Therefore, given a Schur stable matrix $B$, the matrix $(B+I)(B-I)^{-1}$ is Hurwitz stable. Similarly, arigorous proof of this claim can be either inspect the Jordan decomposition applied to $(I-B)^{-1}$, or apply the Sylvester's formula to $A$. Take $A$ into \eqref{eq:continuous-time Lyapunov inequality}: \begin{gather*} P(B-I)(B+I)^{-1}+(B+I)^{-T}(B^T+I)P\prec0,\\ (B^T+I)P(B-I)+(B^T-I)P(B+I)\prec0,\\ 2B^TPB-2P\prec0. \end{gather*} which is \eqref{eq:discrete-time Lyapunov inequality}.