第 XXII–XXV 讲 · 特征值问题与 SVD 的数值算法
特征值与特征向量没法"解出来"——五次以上多项式没有求根公式，特征值只能是迭代逼近。这一组讲建立现代特征值算法的完整逻辑链：化简 → 平移迭代 → 收敛，最后用 SVD 一统特征值与最小二乘。
化简：先变成海森堡形
满矩阵直接做幂迭代太贵。第一步用 Householder 相似变换把矩阵化为上海森堡形（次对角线以下全零）：
相似变换保特征值，$Q$ 记录变换累积。海森堡形上每次 QR 迭代只要 $O(n^2)$（满矩阵要 $O(n^3)$）——化简是"先付一次性 $O(n^3)$，换每步十倍加速"。
QR 算法：带平移的迭代
$H'$ 与 $H$ 相似（正交相似），若 $\mu$ 接近某特征值，则 $H'$ 的对应次对角元迅速趋零——切出这个特征值，对剩余块继续。Wilkinson 位移取尾块 $2\times2$ 的特征值中靠近末元的那个，保证几乎总是二次以上收敛。实矩阵避免复数运算用 Francis 双重位移。隐式 QR（bulge chasing）只在海森堡形上"追一个凸包"完成等效变换，是工程实现的真身。
对称情形与 SVD
对称阵上海森堡形退化为三对角，QR 迭代更便宜；对称三对角的另一种快刀是分而治之与 MRRR（工业库的默认）。而SVD 的两个算法通道：其一，对 $A^TA$（对称）做特征值算法得奇异值平方根（浪费且条件数平方，只作教学）；其二，Golub-Kahan 双对角化 $A = UBV^T$（$B$ 双对角）后对 $B^TB$ 追 QR 迭代——LAPACK 的 GESVD 即此路线。
老师的提醒
- 只要特征值不要特征向量时，能省一半以上时间与内存——接口里"只要特征值"的开关就是为这设计的。
- 重特征值（相近特征值）附近特征向量对扰动敏感（特征向量条件数 $\sim 1/\text{gap}$），比较向量结果时先看 gap。
自检
- 为什么特征值问题必须迭代？
- 海森堡化简买到了什么？
- Wilkinson 位移的思想是什么？
更深一层：QR 算法的"幂迭代加速史"
QR 算法不是天上掉下来的，它是幂迭代的系统化升级，这条演进线值得走一遍：幂迭代 $v \leftarrow Av/\|Av\|$ 收敛到最大特征向量，速率 $(\lambda_2/\lambda_1)^k$——$\lambda_2$ 接近 $\lambda_1$ 时慢到绝望。逆迭代加位移 $\sigma$：$(A - \sigma I)^{-1}$ 的幂迭代，收敛率 $|(\lambda_2 - \sigma)/(\lambda_1 - \sigma)|$——位移贴近特征值时飞快，但需要解方程。子空间加速：同时追 $p$ 个向量（正交化防塌缩），收敛看 $\lambda_{p+1}/\lambda_1$——QR 算法正是"对整个海森堡矩阵同时做子空间迭代"的隐式实现。位移加速：Wilkinson 位移让每次迭代后次对角元平方衰减。这条链上每一步都解决前一步的具体痛点——数值算法的演进从来是"问题驱动"而非"天才空降"。
推导细读：海森堡形是"一次付清的过路费"
满矩阵做一次 QR 迭代要 $O(n^3)$，迭代几十次天文数字。海森堡化（$10n^3/3$ 的 Householder 化简）一次性把矩阵变成"次对角线以下全零"的形态，此后每次 QR 迭代只需 $O(n^2)$——迭代几十次的总成本反超满矩阵一次的成本。更妙的是海森堡形在 QR 迭代下不变（不变子空间结构），一次付费永久受益。这个"化简-迭代"二段式是大规模特征值算法的通用架构：对称阵化三对角、非对称化海森堡、SVD 化双对角——同一个架构模式的三次复用。
在真实世界里：特征值计算的工程面孔
- 振动模态分析：有限元刚度/质量广义特征值 $\mathbf{K}\phi = \omega^2\mathbf{M}\phi$，只取最低几十阶 → Lanczos + 位移变换，ARPACK 打包好了；
- 主成分分析：协方差阵 top-k 特征 → 对称分而治之或随机化 SVD（大矩阵更快）；
- Google PageRank：$10^{10}$ 维矩阵的最大特征向量 → 幂迭代（网页链接矩阵的特殊结构让最古老的方法最有效）——算法的"高低贵贱"取决于矩阵从哪来。
常见误区与辨析
- "特征值算出来就对"：非对称矩阵特征值条件数可以巨大（非正规矩阵），结果敏感是问题的性质不是算法的错——先看伪谱再下结论。
- "QR 算法就是反复做 QR 分解"：文字对，理解错——关键是带位移的隐式移位迭代与海森堡保持；朴素 QR 既慢又不稳定。
- "对称矩阵随便用通用求法"：对称有专用的分而治之/MRRR，比通用 QR 快好几倍且精度可控——用错工具的代价在特征值问题里特别明显。
专题深入：QR 算法的"幂迭代加速史"完整版
QR 算法的演进链值得完整走一遍：幂迭代 $v \leftarrow Av/\|Av\|$ 收敛到最大特征向量，速率 $(\lambda_2/\lambda_1)^k$——$\lambda_2$ 接近 $\lambda_1$ 时慢到绝望。逆迭代加位移 $\sigma$：$(A - \sigma I)^{-1}$ 的幂迭代——位移贴近特征值时飞快，但需要解方程。子空间加速：同时追 $p$ 个向量（正交化防塌缩），收敛看 $\lambda_{p+1}/\lambda_1$——QR 算法正是"对整个海森堡矩阵同时做子空间迭代"的隐式实现。Wilkinson 位移让每次迭代后次对角元平方衰减。这条链上每一步都解决前一步的具体痛点——数值算法的演进从来是"问题驱动"而非"天才空降"。
数学细节展开：海森堡化简是"一次付清的过路费"
海森堡化（$10n^3/3$ 的 Householder 化简）一次性把矩阵变成"次对角线以下全零"，此后每次 QR 迭代只需 $O(n^2)$——迭代几十次的总成本反超满矩阵一次的成本。海森堡形在 QR 迭代下不变（不变子空间结构）——一次付费永久受益。这个"化简-迭代"二段式是大规模特征值算法的通用架构：对称阵化三对角、非对称化海森堡、SVD 化双对角——同一个架构模式的三次复用。
工程案例细节：特征值计算的工程面孔
- 振动模态分析：$\mathbf{K}\phi = \omega^2\mathbf{M}\phi$ 只取低阶 → Lanczos + 位移变换（ARPACK 打包好了）；
- PCA：协方差阵 top-k → 对称分而治之或随机化 SVD；
- PageRank：$10^{10}$ 维矩阵最大特征向量 → 幂迭代（链接矩阵的特殊结构让最古老的方法最有效）——算法的"高低贵贱"取决于矩阵从哪来。
常见误区与辨析（补充）
- "特征值算出来就对"：非对称矩阵特征值条件数可以巨大——非正规矩阵的结果敏感是问题的性质不是算法的错。
- "对称矩阵随便用通用求法"：对称有专用的分而治之/MRRR，比通用 QR 快好几倍且精度可控——用错工具的代价在特征值问题里特别明显。
例题
对 $A = \begin{pmatrix} 2 & 1\\ 1 & 3\end{pmatrix}$ 从 $\mathbf{q}_0 = (1, 1)^T/\sqrt2$ 做两步幂迭代（精确归一化），估计最大特征值对应的 Rayleigh 商。
解答
第一步：$A\mathbf{q}_0 = \frac{1}{\sqrt2}(3, 4)^T$，$\|\cdot\| = \frac{5}{\sqrt2}$，$\mathbf{q}_1 = (3,4)^T/5$。
第二步：$A\mathbf{q}_1 = \frac{1}{5}(2\cdot3+4,\ 3+12)^T = (10, 15)^T/5 = (2,3)^T$，$\|\cdot\| = \sqrt{13}$，$\mathbf{q}_2 = (2,3)^T/\sqrt{13}$。
Rayleigh 商：
真值 $\lambda_{max} = \frac{5+\sqrt5}{2} \approx 3.618$——两步已到 3 位有效数字（收敛率 $\approx (\lambda_2/\lambda_1)^2 = 0.382^2$，快）。