矩阵特征值

阐述

对于方阵 $A$，方程 $\det(A-\lambda I)=0$ 是一个 $n$ 次多项式，它有 $n$ 个根。如果能找到相应的 $n$ 个线性无关的向量 $X=(x_1,\cdots,x_n)$，则有 $AX=X\Lambda$，也就是

$$A=X\Lambda X^{-1}$$

这就完成了矩阵的对角化。

不是所有的矩阵都能对角化，实践中大多数矩阵能够对角化，不过有可能会出现特征向量几乎平行的情况，此时 $X$ 的条件数非常大，对应的向量也不是一组很好的基。除非矩阵是正规矩阵。

特征值问题本质上是非常困难的，因为至少比高次方程的求解要更困难。Abel-Ruffini 定理指出，对于高于 5 次的多项式没有通用的求根公式，所以特征值问题也只能是迭代的。并且，也不能通过直接计算特征多项式的系数来求解，因为多项式的根可能病态地依赖于多项式系数。

幂法

理论解法

对足够大的 $n$，对 $A^n$ 进行 QR 分解，那么得到的矩阵 $Q=(q_1,\cdots,q_n)$ 就是按特征值降序排列的特征向量。不过，由于 $A^n$ 的条件数非常大，QR 分解得不到什么有用的数据，这种方法并不实用。

QR 迭代法

让 $A^{(0)}=A$，然后在每一步迭代中，

• $A^{(k-1)}=Q^{(k)}R^{(k)}$
• $A^{(k)}=R^{(k)}Q^{(k)}$

这样矩阵会收敛到上三角矩阵，而 $\hat Q^{(k)}=Q^{(1)}\cdots Q^{(k)}$ 收敛到 $A$ 的特征向量。

显然，如果 $QR$ 从 Hessenberg 分解后的矩阵开始会更快，特别是对 Hermite 矩阵，每步只需要 $\Theta(n)$ 运算。

位移

可以在 QR 分解时减去 $\mu_kI$，然后在乘积时加上 $\mu_kI$ 来加速收敛：

Arnoldi 算法

解法选择

• 1000 × 1000 以内，使用稠密解法（LAPACK）
• 其他使用 Krylov 方法
  • Arnoldi / Lanczos
  • LOBPCG
  • Jacobi-Davidson

这些方法通常对「极限」的特征值比较有效；对于内部的特征值，可以用 $(A-\mu I)^{-1}$.

实例

性质

相关内容

奇异值分解

由于 $AA^*,A^*A$ 肯定是 Hermite 矩阵，对这些矩阵解特征值问题就得到了奇异值分解

Schur 分解

任何矩阵都可以

$$A=QTQ^*$$

• 如果 A 是 Hermite 矩阵，那 $T=T^*$，这时 Schur 分解和奇异值分解等价
• 因为 A 和 T 相似，所以 $T$ 的对角元就是 $A$ 的特征值

参考文献