EE263 Lecture 13 Jordan canonical form

课程主页：https://see.stanford.edu/Course/EE263

这次回顾第十三讲，这一讲结束了特征值和对角化，介绍了约当标准型。

例子：马尔可夫链

马尔可夫链的概率分布满足

$$p(t+1)=P p(t)$$

注意到

$$\begin{aligned} p_{i}(t)&= \operatorname{Prob}(z(t)=i) \\ P_{i j}&=\operatorname{Prob}(z(t+1)=i | z(t)=j) \end{aligned}$$

所以

$$\begin{aligned} \sum_{i=1}^{n} p_{i}(t)&=1\\ \sum_{i=1}^{n} P_{i j}&=1 \end{aligned}$$

第二个事实可以写成矩阵形式

$$\left[\begin{array}{lll}{1} & {1} & {\cdots} & {1}\end{array}\right] P=\left[\begin{array}{llll}{1} & {1} & {\cdots} & {1}\end{array}\right]$$

即$\left[\begin{array}{llll}{1} & {1} & {\cdots} & {1}\end{array}\right]$为$P$的特征值$1$对应的左特征向量，因此

$$\operatorname{det}(I-P)=0$$

$P$同样有非零的右特征向量$v\neq 0$满足

$$Pv= v$$

我们可以选择$v$，使得$v_i \ge 0$，因此我们可以将$v$正规化，使得

$$\sum_{i=1}^{n} v_{i}=1$$

解释：$v$是平稳分布，即，如果$p(0)=v$，那么对$t\ge 0$，我们都有$p(t)=v$

对角化

假设$v_{1}, \dots, v_{n}$是$A\in \mathbb R^{n\times n}$的线性无关特征向量组：

$$A v_{i}=\lambda_{i} v_{i}, \quad i=1, \ldots, n$$

矩阵形式为

$$A\left[\begin{array}{llll}{v_{1}} & {\cdots} & {v_{n}}\end{array}\right]=\left[\begin{array}{lll}{v_{1}} & {\cdots} & {v_{n}}\end{array}\right]\left[\begin{array}{ccc}{\lambda_{1}} & {} & {} \\ {} & {\ddots} & {} \\ {} & {} & {\lambda_{n}}\end{array}\right]$$

定义

$$\begin{aligned} T&=\left[\begin{array}{lll}{v_{1}} & {\cdots} & {v_{n}}\end{array}\right]\\ \Lambda&=\operatorname{diag}\left(\lambda_{1}, \ldots, \lambda_{n}\right) \end{aligned}$$

那么

$$\begin{aligned} A T&=T \Lambda\\ T^{-1} A T&=\Lambda \end{aligned}$$

• 因为$v_{1}, \dots, v_{n}$线性无关，所以$T$可逆
• 使用$T$的相似变换将$A$对角化

反过来，如果存在$T=\left[v_{1} \cdots v_{n}\right]$，使得

$$T^{-1} A T=\Lambda=\operatorname{diag}\left(\lambda_{1}, \ldots, \lambda_{n}\right)$$

那么$AT=T\Lambda$，即

$$A v_{i}=\lambda_{i} v_{i}, \quad i=1, \ldots, n$$

所以$v_{1}, \dots, v_{n}$是$A$的线性无关特征向量组。

我们称$A$可对角化，如果

• 存在$T$，使得$T^{-1} A T=\Lambda$为对角矩阵
• $A$有线性无关的特征向量组

（如果$A$无法对角化，有时称其为defective）

不是所有矩阵都可对角化

例子：

$$A=\left[\begin{array}{ll}{0} & {1} \\ {0} & {0}\end{array}\right]$$

不同的特征值

事实：如果$A$有不同特征值，即对于$i\neq j$，$\lambda_i \neq \lambda_j$，那么$A$可对角化，反过来并不成立——即使$A$有重复的特征值，但它也有可能对角化。

对角化和左特征向量

将$T^{-1} A T=\Lambda$写成$T^{-1} A=\Lambda T^{-1}$，或

$$\left[\begin{array}{c}{w_{1}^{T}} \\ {\vdots} \\ {w_{n}^{T}}\end{array}\right] A=\Lambda\left[\begin{array}{c}{w_{1}^{T}} \\ {\vdots} \\ {w_{n}^{T}}\end{array}\right]$$

其中$w_{1}^{T}, \ldots, w_{n}^{T}$是$T^{-1}$的行，因此

$$w_{i}^{T} A=\lambda_{i} w_{i}^{T}$$

即，$T^{-1}$的行为左特征向量，并且

$$w_{i}^{T} v_{j}=\delta_{i j}$$

即，根据这种方式选择的左右特征向量为对偶基。

modal form

假设$A$可以由$T$对角化，定义新的坐标系$x=T \tilde{x}$，所以

$$\dot x=Ax \quad \Leftrightarrow \quad T \dot{\tilde{x}}=A T \tilde{x} \quad \Leftrightarrow \quad \dot{\tilde{x}}=T^{-1} A T \tilde{x} \quad \Leftrightarrow \quad \dot{\tilde{x}}=\Lambda \tilde{x}$$

在新的坐标下，系统为对角阵的形式：

轨迹由$n$个独立模式组成，即

$$\tilde{x}_{i}(t)=e^{\lambda_{i} t} \tilde{x}_{i}(0)$$

因此被称为modal form

Real modal form

当特征值是复数的时候，系统可以化为Real modal form的形式：

$$S^{-1} A S=\operatorname{diag}\left(\Lambda_{r},\left[\begin{array}{cc}{\sigma_{r+1}} & {\omega_{r+1}} \\ {-\omega_{r+1}} & {\sigma_{r+1}}\end{array}\right], \ldots,\left[\begin{array}{cc}{\sigma_{n}} & {\omega_{n}} \\ {-\omega_{n}} & {\sigma_{n}}\end{array}\right]\right)$$

其中$\Lambda_{r}=\operatorname{diag}\left(\lambda_{1}, \ldots, \lambda_{r}\right)$为实特征值，并且

$$\lambda_{i}=\sigma_{i}+j \omega_{i}, \quad i=r+1, \ldots, n$$

为复特征值。

框图为

对角化的作用

对角化简化了很多矩阵表达式。

resolvent：

$$\begin{aligned}(s I-A)^{-1} &=\left(s T T^{-1}-T \Lambda T^{-1}\right)^{-1} \\ &=\left(T(s I-\Lambda) T^{-1}\right)^{-1} \\ &=T(s I-\Lambda)^{-1} T^{-1} \\ &=T \operatorname{diag}\left(\frac{1}{s-\lambda_{1}}, \cdots, \frac{1}{s-\lambda_{n}}\right) T^{-1} \end{aligned}$$

幂（即离散情形的解）：

$$\begin{aligned} A^{k} &=\left(T \Lambda T^{-1}\right)^{k} \\ &=\left(T \Lambda T^{-1}\right) \cdots\left(T \Lambda T^{-1}\right) \\ &=T \Lambda^{k} T^{-1} \\ &=T \operatorname{diag}\left(\lambda_{1}^{k}, \ldots, \lambda_{n}^{k}\right) T^{-1} \end{aligned}$$

（对于$k<0$，只有$A$可逆的时候上式才成立，即所有的$\lambda_i \neq 0$）

指数（连续情形的解）：

$$\begin{aligned} e^{A} &=I+A+A^{2} / 2 !+\cdots \\ &=I+T \Lambda T^{-1}+\left(T \Lambda T^{-1}\right)^{2} / 2 !+\cdots \\ &=T\left(I+\Lambda+\Lambda^{2} / 2 !+\cdots\right) T^{-1} \\ &=T e^{\Lambda} T^{-1} \\ &=T \operatorname{diag}\left(e^{\lambda_{1}}, \ldots, e^{\lambda_{n}}\right) T^{-1} \end{aligned}$$

函数的解析函数

对于任意解析函数$f : \mathbb{R} \rightarrow \mathbb{R}$，即有多项式序列给出的函数

$$f(a)=\beta_{0}+\beta_{1} a+\beta_{2} a^{2}+\beta_{3} a^{3}+\cdots$$

我们可以对$A\in \mathbb R^{n\times n}$定义$f(A)$为

$$f(A)=\beta_{0} I+\beta_{1} A+\beta_{2} A^{2}+\beta_{3} A^{3}+\cdots$$

将$A=T \Lambda T^{-1}$带入，我们有

$$\begin{aligned} f(A) &=\beta_{0} I+\beta_{1} A+\beta_{2} A^{2}+\beta_{3} A^{3}+\cdots \\ &=\beta_{0} T T^{-1}+\beta_{1} T \Lambda T^{-1}+\beta_{2}\left(T \Lambda T^{-1}\right)^{2}+\cdots \\ &=T\left(\beta_{0} I+\beta_{1} \Lambda+\beta_{2} \Lambda^{2}+\cdots\right) T^{-1} \\ &=T \operatorname{diag}\left(f\left(\lambda_{1}\right), \ldots, f\left(\lambda_{n}\right)\right) T^{-1} \end{aligned}$$

通过对角化求解

假设$A$可对角化，考虑LDS$\dot{x}=A x$，并且$T^{-1} A T=\Lambda$，那么

$$\begin{aligned} x(t) &=e^{t A} x(0) \\ &=T e^{\Lambda t} T^{-1} x(0) \\ &=\sum_{i=1}^{n} e^{\lambda_{i} t}\left(w_{i}^{T} x(0)\right) v_{i} \end{aligned}$$

因此：任何轨迹都可以表示为modal的线性组合。

解释：

• （左特征向量）将初始状态$x(0)$分解为modal元素$w_i^Tx(0)$
• $e^{\lambda_i t}$项将第$i$个model向前推进$t$秒
• 将状态重建为（右）特征向量的线性组合

应用

当$x(0)$为何值时，当$t\to \infty$时，我们有$x(t)\to 0$？

将特征值分为实部负和非负的两部分，负数部分

$$\Re \lambda_{1}<0, \ldots, \Re \lambda_{s}<0$$

其余部分为

$$\Re \lambda_{s+1} \geq 0, \ldots, \Re \lambda_{n} \geq 0$$

由

$$x(t)=\sum_{i=1}^{n} e^{\lambda_{i} t}\left(w_{i}^{T} x(0)\right) v_{i}$$

我们得到$x(t)\to 0$的条件为

$$x(0) \in \operatorname{span}\left\{v_{1}, \ldots, v_{s}\right\}$$

或者等价的，

$$w_{i}^{T} x(0)=0, \quad i=s+1, \ldots, n$$

离散时间系统的稳定性

假设$A$可对角化，考虑离散时间LDS

$$x(t+1)=A x(t)$$

如果$A=T \Lambda T^{-1}$，那么$A^{k}=T \Lambda^{k} T^{-1}$，因此对任意的$x(0)$

$$x(t)=A^{t} x(0)=\sum_{i=1}^{n} \lambda_{i}^{t}\left(w_{i}^{T} x(0)\right) v_{i} \rightarrow 0 \quad \text { as } t \rightarrow \infty$$

我们必然有

$$\left|\lambda_{i}\right|<1, \quad i=1, \ldots, n$$

我们将在后面看到，当$A$无法对角化的时候，上述事实依然成立，因此我们有：$x(t+1)=A x(t)$稳定当且仅当$A$的所有特征值的模长小于$1$

Lecture 12 约当标准型

约当标准型

约当标准是对角化的推广。

任意矩阵$A \in \mathbb{R}^{n \times n}$通过相似变换可以化为如下形式

$$T^{-1} A T=J=\left[\begin{array}{lll}{J_{1}} & {} \\ {} & {\cdots} & {} \\ {} & {} & {J_{q}}\end{array}\right]$$

其中

$$J_{i}=\left[\begin{array}{cccc}{\lambda_{i}} & {1} & {} & {} \\ {} & {\lambda_{i}} & {\cdots} & {} \\ {} & {} & {\ddots} & {1} \\ {} & {} & {} & {\lambda_{i}}\end{array}\right] \in \mathbb{C}^{n_{i} \times n_{i}}$$

被称为大小为$n_i$，特征值为$\lambda_i$的约当块（所以$n=\sum_{i=1}^{q} n_{i}$）

约当标准型有如下性质：

• $J$为上三角bidiagonal
• $J$为对角矩阵为约当标准型的特殊情形，此时有$n$个约当块，并且$n_i =1$
• 约当标准型唯一（考虑置换的情形下）
• 可能有很多个约当块的特征值相同

备注：约当标准为理论工具，数值计算中从不使用！

注意$J$的特征值多项式为

$$\mathcal{X}(s)=\operatorname{det}(s I-A)=\left(s-\lambda_{1}\right)^{n_{1}} \cdots\left(s-\lambda_{q}\right)^{n_{q}}$$

因此不同特征值$\Rightarrow n_{i}=1 \Rightarrow A$可对角化。

$\operatorname{dim} \mathcal{N}(\lambda I-A)$为特征值为$\lambda$的约当块的数量，更一般的，我们有

$$\operatorname{dim} \mathcal{N}(\lambda I-A)^{k}=\sum_{\lambda_{i}=\lambda} \min \left\{k, n_{i}\right\}$$

所以根据$\operatorname{dim} \mathcal{N}(\lambda I-A)^{k},k=1,2,\ldots$，我们可以判断和$\lambda $有关的约当块的数量。

关于约当标准型有如下事实：

• $\lambda I-A=T(\lambda I-J) T^{-1}$

• 对大小为$3$的分块：

  $$\lambda_{i} I-J_{i}=\left[\begin{array}{rrr}{0} & {-1} & {0} \\ {0} & {0} & {-1} \\ {0} & {0} & {0}\end{array}\right] \quad\left(\lambda_{i} I-J_{i}\right)^{2}=\left[\begin{array}{ccc}{0} & {0} & {1} \\ {0} & {0} & {0} \\ {0} & {0} & {0}\end{array}\right] \quad\left(\lambda_{i} I-J_{i}\right)^{3}=0$$

• 对其他大小为$3$的分块（$k\ge 2$），我们有

  $$\left(\lambda_{i} I-J_{j}\right)^{k}=\left[\begin{array}{ccc}{\left(\lambda_{i}-\lambda_{j}\right)^{k}} & {-k\left(\lambda_{i}-\lambda_{j}\right)^{k-1}} & {(k(k-1) / 2)\left(\lambda_{i}-\lambda_{j}\right)^{k-2}} \\ {0} & {\left(\lambda_{j}-\lambda_{i}\right)^{k}} & {-k\left(\lambda_{j}-\lambda_{i}\right)^{k-1}} \\ {0} & {0} & {\left(\lambda_{j}-\lambda_{i}\right)^{k}}\end{array}\right]$$

广义特征向量

假设

$$T^{-1} A T=J=\operatorname{diag}\left(J_{1}, \ldots, J_{q}\right)$$

将$T$表达为

$$T=\left[T_{1} T_{2} \cdots T_{q}\right]$$

其中$T_{i} \in \mathbb{C}^{n \times n_{i}}$为和第$i$个约当块$J_i$有关的$T$的列，我们有

$$A T_{i}=T_{i} J_{i}$$

令

$$T_{i}=\left[\begin{array}{llll}{v_{i 1}} & {v_{i 2}} & {\cdots} & {v_{i n_{i}}}\end{array}\right]$$

那么我们有

$$A v_{i 1}=\lambda_{i} v_{i 1}$$

即，$T_i$的第一列为$\lambda_i $对应的特征向量。

对$j=2, \ldots, n_{i}$，

$$A v_{i j}=v_{i j-1}+\lambda_{i} v_{i j}$$

向量$v_{i 1}, \dots v_{i n_{i}}$被称为广义特征向量。

约当标准型LDS

考虑LDS

$$\dot{x}=A x$$

通过坐标变换

$$x=T \tilde{x}$$

我们可以化为

$$\dot{\tilde{x}}=J \tilde{x}$$

因此系统被分解为独立的“约当块系统”$\dot{\tilde{x}}_{i}=J_{i} \tilde{x}_{i}$

约当块有时被称为约当链

Resolvent，约当块的指数

考虑特征值为$\lambda_i$的$k\times k$的约当块的resolvent

$$\begin{aligned} \left(s I-J_{\lambda}\right)^{-1} &=\left[\begin{array}{cccc}{s-\lambda} & {-1} & {} & {} \\ {} & {s-\lambda} & {\ddots} & {} \\ {} & {} & {\ddots} & {-1} \\ {} & {} & {} & {s-\lambda}\end{array}\right]^{-1}\\ &=\left[\begin{array}{cccc}{(s-\lambda)^{-1}} & {(s-\lambda)^{-2}} & {\dots} & {(s-\lambda)^{-k}} \\ {} & {(s-\lambda)^{-1}} & {\dots} & {(s-\lambda)^{-k+1}} \\ {} & {} & {\ddots} & {\vdots} \\ {} & {} & {} & {(s-\lambda)^{-1}}\end{array}\right]\\ &=(s-\lambda)^{-1} I+(s-\lambda)^{-2} F_{1}+\cdots+(s-\lambda)^{-k} F_{k-1} \end{aligned}$$

其中$F_i$为第$i$个上对角线全为$1$的矩阵。

利用逆拉普拉斯变换，得到指数形式为

$$\begin{aligned} e^{t J_{\lambda}} &=e^{t \lambda}\left(I+t F_{1}+\cdots+\left(t^{k-1} /(k-1) !\right) F_{k-1}\right)\\ &=e^{t \lambda} \left[ \begin{matrix}{1} & {t} & {\cdots} & {t^{k-1} /(k-1) !} \\ {} & {1} & {\cdots} & {t^{k-2} /(k-2) !} \\ {} & {} & {\ddots} & {\vdots} \\ {} & {} & {} & {1} \end{matrix}\right] \end{aligned}$$

约当块产生：

• $e^{tA}$中$t^{p} e^{t \lambda}$的项