数值线代 II · 特征值算法
对标：Trefethen & Bau Lectures 24–29 ｜ 前置：nla-01、本科高代 V、数值 II（幂法） 特征值问题有个先天限制：五次以上多项式无求根公式（Abel——本科高代 I/抽代的定理在此变成算法约束）⇒ 特征值算法必然是迭代的。本页从幂法家族到工业标准 QR 迭代，机理讲透。
1. 为什么必须迭代
特征值 = 特征多项式的根；反之任何多项式都是某伴随矩阵的特征多项式——求特征值 ⊇ 求根，故无有限步精确算法（Abel–Ruffini 的数值推论）。⚠️ 但"经由特征多项式求特征值"是数值犯罪：根对系数病态（Wilkinson 多项式——数值 I 的名例正是为此准备的）；正确路线是直接对矩阵做正交相似变换。
2. 幂法家族（数值 II 的升级版）
幂法：\(x_{k+1} = Ax_k/\|Ax_k\|\) → 主特征向量，速率 \(|\lambda_2/\lambda_1|^k\)（本科已证）。两个换挡装置：
- 反幂法：对 \((A - \mu I)^{-1}\) 用幂法——收敛到距 \(\mu\) 最近的特征值（谱被 \(\frac{1}{\lambda - \mu}\) 重排，最近者变最大）：有好的特征值近似时提取特征向量的标准手段；
- Rayleigh 商迭代：每步用当前向量的 Rayleigh 商 \(\mu_k = \frac{x^\top Ax}{x^\top x}\) 更新位移——对称阵上三次收敛【引用】（有效数字每步三倍：Rayleigh 商本身二阶精确 + 反幂法放大，正反馈）。
3. QR 迭代（工业标准）
朴素版：\(A_k = Q_kR_k\)（QR 分解），\(A_{k+1} = R_kQ_k\)。 为什么有效【机理，两层】：① \(A_{k+1} = Q_k^\top A_kQ_k\)——正交相似（谱不变，nla-01 的美德）；② 它暗中等价于对整组基做幂法（同时迭代：\(A^k\) 的 QR 分解与 \(\prod Q_i\) 的关系【骨架】）——各特征值按模长梯度逐个"沉淀"到对角线，下三角以 \(|\lambda_{i+1}/\lambda_i|^k\) 归零。
从 \(O(n^4)\) 到实用的三件工程：
① 先化 Hessenberg 形（上三角 + 一条次对角线；Householder 有限步可达——"能有限步做的先做完"）：每步 QR 从 \(O(n^3)\) 降到 \(O(n^2)\)；
② 位移：对 \(A_k - \mu_kI\) 迭代（Wilkinson 位移取右下 \(2\times2\) 块的特征值）——收敛从线性提到（对称时）三次，机理同 Rayleigh 商迭代；
③ 缩减：次对角元一旦归零即分块，问题越算越小。
合成品即 LAPACK 的 eig：实践中 \(O(n^3)\) 拿全谱——"你每次调 np.linalg.eig 都在跑这套三件套"。
对称特殊化：Hessenberg 形变三对角、全程保对称，配合 Wilkinson 位移有收敛性定理保证【引用】；另有分治法与 MRRR 等竞品。SVD 的算法：对 \(\begin{pmatrix}0 & A\\ A^\top & 0\end{pmatrix}\) 或双对角化后走同族迭代（不要通过 \(A^\top A\)——条件数平方，nla-01 戒律重申）。
扰动理论衔接（矩阵分析预告）：对称阵特征值完美稳定（Weyl：\(|\lambda_i(A+E) - \lambda_i(A)| \leq \|E\|\)——ma-01 将证）；非对称可以病态（伪谱语言【引用 Trefethen】）；特征向量的稳定性由谱隙决定（相邻特征值近则向量剧烈旋转——PCA 主轴在特征值接近时不可信的数学出处，统计 V 实务警告的定理版）。
4. 练习与要点
例 1（同时迭代的体感） 对 \(2\times2\) 矩阵手跑三轮朴素 QR 迭代，观察次对角元按 \(|\lambda_2/\lambda_1|\) 比例衰减——机理②的最小实证。
例 2（位移的威力） 同题加 Wilkinson 位移：一轮内次对角元近零——线性 vs 三次收敛的手感对比（迭代次数从几十到个位数的工业差距）。
例 3（谱隙与主轴稳定性） 协方差谱 \(\{10, 9.9, 1\}\)：前两个主成分方向对数据扰动极敏感（隙 0.1），而"前二维子空间"整体稳定（与第三隙 8.9）——报告 PCA 时"子空间可信、单轴不可信"的定量依据（Davis–Kahan 定理的实用读法【引用】）。\(\blacksquare\)
下一页：大规模稀疏世界的王者——Krylov 子空间方法：CG 的收敛性证明、GMRES 与预条件的艺术。