QR 算法

QR 算法是求稠密矩阵全部特征值的标准方法，其表述简单得近乎神奇。把 A_0 = A 分解为 Q_0 R_0（正交矩阵乘上三角矩阵），再把两个因子反序乘回得到 A_1 = R_0 Q_0。重复：分解 A_1 = Q_1 R_1，令 A_2 = R_1 Q_1，如此继续。令人惊讶的是，序列 A_0, A_1, A_2, …… 收敛到（块）上三角形，特征值一一走上对角线。

为何奏效：每一步都是相似变换，A_{k+1} = R_k Q_k = Q_k^T A_k Q_k，故每个 A_k 都与 A 有相同的特征值。这个迭代暗地里在所有特征向量上同时运行幂法的一个精巧版本；正交因子逐渐把矩阵旋转成 Schur 形，其中特征值落在对角线上。

朴素地做，这每步要 O(n^3) 且收敛缓慢——毫无用处。两项改进使它成为实用标准。其一，先把 A 一次性约化为海森伯格形（上三角加一条次对角）；QR 步随即保持海森伯格结构，只需 O(n^2)。其二，使用位移：不分解 A_k，而是分解 A_k - mu I，mu 取在某个特征值附近巧选之值，这大幅加速收敛——临近尾声时达三次。现代实现用隐式双位移（Francis）步在实算术中处理复特征值对。

对对称矩阵，算法优美地特化：海森伯格形变为三对角形，对称 QR 算法以后向稳定和惊人的速度求出全部特征值与特征向量。这正是像 LAPACK 的 syev 和 geev 这类库例程底层所调用的，也是你永远不该自己写稠密特征求解器的原因。