特征值与特征向量
我们在标准正交基中提到过如果线性映射 \(\mathcal{A}: \mathbb{U} \mapsto \mathbb{V}\) 中线性空间是同一个，即 \(\mathbb{U} = \mathbb{V}\)，那么我们说 \(\mathcal{A}: \mathbb{V} \mapsto \mathbb{V}\) 是线性空间 \(\mathbb{V}\) 的线性变换。 假设线性变换 \(\mathcal{A}\) 在 \(\mathbb{V}\) 中的一组基 \(M_1 = \{\boldsymbol{\alpha}_1, \cdots, \boldsymbol{\alpha}_n\}\) 下的矩阵为 \(\boldsymbol{A}\)。 在另一组基 \(M_2 = \{\boldsymbol{\beta}_1, \cdots, \boldsymbol{\beta}_n\}\) 下的矩阵为 \(\boldsymbol{B}\)，\(M_1\) 到 \(M_2\) 的过渡矩阵为 \(\boldsymbol{P}\)， 有基变换关系 \(\begin{bmatrix}\boldsymbol{\beta}_1 & \cdots & \boldsymbol{\beta}_n\end{bmatrix} = \begin{bmatrix} \boldsymbol{\alpha}_1 & \cdots & \boldsymbol{\alpha}_n \end{bmatrix} \boldsymbol{P}\)。 那么矩阵 \(\boldsymbol{A}, \boldsymbol{B}\) 有关系 \(\boldsymbol{B} = \boldsymbol{P}^{-1}\boldsymbol{A}\boldsymbol{P}\)。 因为过渡矩阵 \(\boldsymbol{P}\) 是可逆的，所以我们定义相似矩阵:
- 自反性: 任意方阵 \(\boldsymbol{A}\) 都有单位矩阵 \(\boldsymbol{I}\) 使 \(\boldsymbol{A} = \boldsymbol{I}^{-1}\boldsymbol{A}\boldsymbol{I}\)。
- 对称性: 如果\(\boldsymbol{A}\) 与 \(\boldsymbol{B}\) 相似，那么 \(\boldsymbol{B}\) 也与 \(\boldsymbol{A}\) 相似。
- 传递性: 如果\(\boldsymbol{A}\) 与 \(\boldsymbol{B}\) 相似，\(\boldsymbol{B}\) 与 \(\boldsymbol{C}\) 相似，那么 \(\boldsymbol{A}\) 与 \(\boldsymbol{C}\) 也相似。
也就是说，对于空间 \(\mathbb{V}\) 中的任意一个线性变换，我们都可以通过精心挑选基向量，将其转换成一个简单的形式。一般认为对角矩阵就是最简单的形式， 对角线上的元素就是本文要研究的特征值，对应的基向量就是所谓的特征向量。
1. 特征值和特征向量
如果线性变换 \(\mathcal{A}: \mathbb{V} \mapsto \mathbb{V}\) 将空间中的一个非零向量 \(\boldsymbol{X} \in \mathbb{V}\) 映射到它的某个倍向量上， 即 \(\mathcal{A}(\boldsymbol{X}) = \lambda \boldsymbol{X}\)。就称 \(\lambda\) 是线性变换 \(\mathcal{A}\) 的特征值，\(\boldsymbol{X}\) 是 \(\mathcal{A}\) 属于 \(\lambda\) 的特征向量。将线性变换写成矩阵的形式 \(\mathcal{A}: \boldsymbol{X} \mapsto \boldsymbol{A}\boldsymbol{X}\)， \(\lambda\) 和 \(\boldsymbol{X}\) 则是矩阵 \(\boldsymbol{A}\) 的特征值和特征向量。也就是说，如果 \(\boldsymbol{A}\boldsymbol{X} = \lambda\boldsymbol{X}\) 对于某个非零向量 \(\boldsymbol{X}\) 成立，就称 \(\lambda\) 为矩阵\(\boldsymbol{A}\)的特征值，\(\boldsymbol{X}\) 是属于特征值 \(\lambda\) 的特征向量。
如果线性变换 \(\mathcal{A}\) 在某一组基 \(N = \{\boldsymbol{\beta}_1, \cdots, \boldsymbol{\beta}_n\}\) 下的矩阵 \(\boldsymbol{B}\)是对角阵， 即 \(\boldsymbol{B} = \begin{bmatrix} \lambda_1 & & \\ & \ddots & \\ & & \lambda_n \end{bmatrix}\)，那么我们就说线性变换 \(\mathcal{A}\) 是可对角化的。 并且对于基向量有 \(\mathcal{A}(\boldsymbol{\beta}_i) = \boldsymbol{B}\boldsymbol{\beta}_i = \lambda_i \boldsymbol{\beta}_i\)。 按照定义，\(\lambda_i\) 就是线性变换 \(\mathcal{A}\) 的特征值，\(\boldsymbol{\beta}_i\) 则是 \(\boldsymbol{B}\) 属于\(\lambda_i\) 的特征向量。 线性变换 \(\mathcal{A}\) 在另一组基 \(M = \{\boldsymbol{\alpha}_1, \cdots, \boldsymbol{\alpha}_n\}\) 下的矩阵 \(\boldsymbol{A}\) 与 \(\boldsymbol{B}\) 存在相似关系， 即存在一个可逆矩阵 \(\boldsymbol{P}\) 满足 \(\boldsymbol{B} = \boldsymbol{P}^{-1}\boldsymbol{A}\boldsymbol{P}\)。我们可以作出如下推导:
$$ \left. \begin{array}{r} \boldsymbol{B}\boldsymbol{\beta}_i = \lambda_i \boldsymbol{\beta}_i \\ \boldsymbol{B} = \boldsymbol{P}^{-1}\boldsymbol{A}\boldsymbol{P} \end{array} \right\} \Longrightarrow \boldsymbol{P}^{-1}\boldsymbol{A}\boldsymbol{P} \boldsymbol{\beta}_i = \lambda_i \boldsymbol{\beta}_i \Longrightarrow \boldsymbol{A}\left(\boldsymbol{P} \boldsymbol{\beta}_i\right) = \lambda_i \left(\boldsymbol{P}\boldsymbol{\beta}_i\right) $$所以，\(\lambda_i\) 也是矩阵 \(\boldsymbol{A}\) 的特征值，\(\boldsymbol{P} \boldsymbol{\beta}_i\) 则是 \(\boldsymbol{A}\) 中属于 \(\lambda_i\) 的特征向量。 特征值是相似不变的。
2. 特征多项式
很多线性代数教科书上都会介绍一种通过特征多项式求解特征值的方法，这种方法只适合手算一些小规模矩阵的特征值。一个 \(n\) 阶方阵 \(\boldsymbol{A}\) 的特征多项式被定义为 \(\det(\lambda \boldsymbol{I} - \boldsymbol{A}) = 0\)，其中 \(\det(\lambda \boldsymbol{I} - \boldsymbol{A})\) 表示矩阵 \(\lambda \boldsymbol{I} - \boldsymbol{A}\) 的行列式，它是关于 \(\lambda\) 的 \(n\) 次多项式，\(n\)比较小的时候我们还可以通过因式分解、套公式等方法求出。阶数高了就没办法了。
这种求解特征值和特征向量的方法，有三个步骤: (1) 计算行列式\(\det(\lambda \boldsymbol{I} - \boldsymbol{A})\)得到特征多项式; (2) 对特征多项式求解一元 \(n\) 次方程，得到矩阵 \(\boldsymbol{A}\) 的特征值; (3) 对每个特征值 \(\lambda_i\) 求解方程组 \((\boldsymbol{A} - \lambda_i \boldsymbol{I})\boldsymbol{X} = \boldsymbol{0}\) 得到属于 \(\lambda_i\) 的特征向量。
假设我们要求 \(3 \times 3\) 的矩阵 \(\boldsymbol{A} = \begin{bmatrix} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{bmatrix}\) 的特征值和特征向量，可以写出求出行列式的特征多项式: $$ \left| \begin{array}{c} \lambda - 2 & - 1 & - 1 \\ - 1 & \lambda - 2 & - 1 \\ - 1 & - 1 & \lambda - 2 \\ \end{array} \right| = (\lambda - 4)(\lambda - 1)^{2} $$ 显然方程 \((\lambda - 4)(\lambda - 1)^2 = 0\) 有三个根，分别是 \(4, 1, 1\)。我们分别将 4 和 1 带入方程组 \((\boldsymbol{A} - \lambda_i \boldsymbol{I})\boldsymbol{X} = \boldsymbol{0}\)，可以求得属于 4 的特征向量是 \(\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}\)， 属于 1 的特征向量是 \(\begin{bmatrix} 1 \\ -1 \\ 0 \end{bmatrix}\) 和 \(\begin{bmatrix} 1 \\ 0 \\ -1 \end{bmatrix}\)。
我们好像很难通过计算机来写出特征多项式并对它进行因式分解写出特征值，所以上述方法一般都是手算一些小规模的矩阵，很难自动化实现。
3. QR 算法求解特征值
基于QR 分解我们可以得到一个特征值的通用解法，称为QR 算法，而且可以一次计算出所有的特征值。 该算法与蒙特卡洛、快排等算法一起被评为 20 世纪最伟大的十个计算机算法。
对于方阵 \(\boldsymbol{A}\) 我们总是可以将它分解成一个正交矩阵和一个上三角矩阵的积，即\(\boldsymbol{A} = \boldsymbol{Q}\boldsymbol{R}\)。因为 \(\boldsymbol{Q}\) 是正交矩阵，所以 \(\boldsymbol{Q}^{-1} = \boldsymbol{Q}\)，因此有 \(\boldsymbol{Q}^{-1}\boldsymbol{A}\boldsymbol{Q} = \boldsymbol{Q}^{-1}\boldsymbol{Q}\boldsymbol{R}\boldsymbol{Q} = \boldsymbol{R}\boldsymbol{Q}\)。所以矩阵 \(\boldsymbol{A}\) 与 \(\boldsymbol{R}\boldsymbol{Q}\) 相似， 它们具有相同的特征值。据说不断的对矩阵 \(\boldsymbol{A}\) 进行 QR 分解，并交换两个矩阵的顺序，得到 \(\boldsymbol{A}_{k+1} = \boldsymbol{R}_k \boldsymbol{Q}_k\)， 其中 \(k\) 表示迭代次数，迭代初值 \(\boldsymbol{A}_0 = \boldsymbol{A}\)。\(\boldsymbol{A}_{k+1}\) 就会收敛到一个近似上三角的矩阵上，该矩阵的对角线上的元素就是特征值。
我们在例程EigenNaiveQR中提供了原始的 QR 算法实现， 整个迭代过程非常简单，如下面右侧代码所示，只要三行，先通过 Householder 方法进行 QR 分解，然后交换矩阵 Q, R 相乘，最后的矩阵 mU 用于保存历次的正交矩阵满足 \(\boldsymbol{A} = \boldsymbol{U} \boldsymbol{T} \boldsymbol{U}^T\)。只要迭代的次数足够多，矩阵 mT 的对角线就是要求的特征值。
EigenNaiveQR(MatViewIn const & a, int max_iter = 100)
: mT(a.Rows(), a.Cols()), mU(a.Rows(), a.Cols())
{
assert(a.Rows() == a.Cols());
mT = a;
mU.Identity();
Iterate(max_iter);
}
void Iterate(int max_iter)
{
for (int i = 0; i < max_iter; i++) {
QR_Householder qr(mT);
mT = qr.R() * qr.Q();
mU = mU * qr.Q();
}
}
该算法在数值上非常稳定，就是收敛起来比较慢，尤其是存在重复特征值的时候。所以人们后来在此基础上开发出了很多变形。我们以后有机会再给出一些常见变形的实现。