07 Hessenberg 化、位移 QR 与 Francis 迭代

1. QR 迭代在做什么

无位移 QR 迭代为

A_{k} = Q_{k} R_{k}, A_{k + 1} = R_{k} Q_{k} .

因为

A_{k + 1} = Q_{k}^{*} A_{k} Q_{k},

每一步都是酉相似变换，特征值不变。累积的 $Q$ 同时执行一种子空间迭代；在合适条件下， $A_{k}$ 趋向上三角 Schur 形。

2. 先约化为上 Hessenberg 形

若每步都对稠密 $A_{k}$ 做 QR，成本为 $O (n^{3})$ ，总成本过高。先用 Householder 相似变换得到

H = Q^{*} A Q,

其中 $H$ 只有第一条次对角线以下为零。一次约化成本 $O (n^{3})$ ；Hessenberg 矩阵每步 QR 只需 $O (n^{2})$ ，且结构在迭代中保持。

对 Hermite 矩阵，Hessenberg 形进一步退化为三对角矩阵。

3. 位移加速收敛

位移 QR 为

H_{k} - μ_{k} I = Q_{k} R_{k}, q q u a d H_{k + 1} = R_{k} Q_{k} + μ_{k} I .

常见选择：

Rayleigh 位移： $μ_{k} = (H_{k})_{n n}$ 。
Wilkinson 位移：取右下 $2 \times 2$ 子块中更接近 $(H_{k})_{n n}$ 的特征值。

位移越接近正在收敛的特征值，次对角元素通常衰减越快。

4. 亏损与分块

当

| h_{i + 1, i} | \leq c u (| h_{i i} | + | h_{i + 1, i + 1} |)

时，可把 $h_{i + 1, i}$ 置零，将问题分成两个较小块。好的亏损判据应考虑局部尺度，而不是只用固定绝对阈值。

实矩阵的实 Schur 形允许 $2 \times 2$ 对角块，以表示共轭复特征值对。

5. 隐式 Q 定理与 Francis 双位移

对实 Hessenberg 矩阵，直接使用一对复位移会引入复运算。Francis 双位移使用右下 $2 \times 2$ 子块的迹 $s$ 与行列式 $t$ ，隐式作用多项式

p (H) = H^{2} - s H + t I .

只需用 $p (H) e_{1}$ 的前三个分量构造第一个 Householder 反射。该反射在 Hessenberg 带外制造一个小“鼓包”，随后用一系列局部反射把鼓包向右下追赶并移出矩阵。

隐式 Q 定理保证：只要第一列和 Hessenberg 结构确定，这串正交相似变换就等价于显式双位移 QR，但无需形成 $p (H)$ 或完整 QR 分解。

6. 从 Schur 形恢复特征向量

若

A = Q T Q^{*},

先在上三角/准上三角 $T$ 上通过回代求特征向量 $y$ ，再令 $x = Q y$ 。接近重根时，回代和特征向量本身都可能病态，需要缩放以避免溢出。

7. 扰动视角

若 $A = X Λ X^{- 1}$ 可对角化，Bauer-Fike 定理给出

min_{λ \in σ (A)} | \tilde{λ} - λ | \leq κ_{2} (X) ∥ E ∥_{2}

对 $A + E$ 的任一特征值 $\tilde{λ}$ 成立。非正规矩阵即使特征值算法后向稳定，前向特征值误差也可能因 $κ (X)$ 大而显著。

8. QR 迭代与子空间迭代的关系

记累积正交矩阵

{\hat{Q}}_{k} = Q_{0} Q_{1} \dots Q_{k - 1} .

则

A^{k} = {\hat{Q}}_{k} {\hat{R}}_{k}

可看成对 $A^{k}$ 的 QR 分解。其前若干列张成的空间与同时迭代多个向量的子空间迭代一致。QR 算法不是凭空出现的技巧，而是把“所有起始向量同时做幂迭代”组织成保持相似性的矩阵迭代。

9. Hessenberg 化的实现细节

第 $k$ 步 Householder 只作用于 $A_{k + 1 : n, k}$ ，但为了相似变换必须左右同时更新：

A \leftarrow H_{k} A H_{k}^{*} .

左更新制造第 $k$ 列的零，右更新保证特征值不变。反射向量可存入已被消零的下三角位置；若需要 Schur 向量，再把这些反射累积为 $Q$ 。约化阶段为 $O (n^{3})$ ，但只求特征值时无需显式形成完整 $Q$ 。

10. 隐式 Q 定理的含义

若两个酉矩阵把同一个不可约 Hessenberg 矩阵变为 Hessenberg 形，且它们的第一列相同，那么除去对角单位模因子，它们本质相同。于是 QR 步无需显式分解 $H - μ I$ ：只要构造与该分解第一列一致的局部变换，再维护 Hessenberg 形，后续变换就被唯一确定。

这正是“隐式位移”的依据：把位移信息塞进第一个向量，再通过凸起追赶完成整步相似变换。

11. 更稳健的亏损判据

简单判据只比较 $| h_{i + 1, i} |$ 与相邻对角元。在对角元很小时，更稳健的实现还会参考附近上三角元素和局部 2-范数，避免错误切断强耦合块。亏损一旦成立，应把该元素精确置零，从而把活动块拆开；这既降低计算量，也明确了已收敛结构。

实 QR 中的 $2 \times 2$ 块若对应一对共轭特征值，应保留为实 Schur 块。强迫它继续迭代到两个实 $1 \times 1$ 块既不可能也会破坏收敛逻辑。

12. Schur 重排与条件数

Schur 分解不唯一，可以通过相邻块交换把选定特征值移动到左上角：

Q^{*} A Q = (\begin{matrix} T_{11} & T_{12} \\ 0 & T_{22} \end{matrix}) .

$Q_{1}$ 的列空间就是对应的不变子空间。交换是否敏感由两个三角块的分离度控制，可通过 Sylvester 算子

T_{11} X - X T_{22}

的最小增益衡量。两组谱接近时，重排及其不变子空间本身就病态。

13. 复杂度与可靠性验收

一般稠密特征值算法的典型总成本为 $O (n^{3})$ ：Hessenberg 化占固定主项，随后约 $O (n)$ 次、每次 $O (n^{2})$ 的 QR 扫描。只求特征值比累积 Schur 向量便宜。

验收至少包括

\frac{∥ A Q - Q T ∥_{F}}{∥ A ∥_{F}}, ∥ Q^{*} Q - I ∥_{F},

以及 $T$ 的上三角/准上三角结构。单独与另一软件比较特征值，不能发现 Schur 向量累积或局部更新索引错误。

14. 自检

[ ] 能解释 Hessenberg 预处理如何把每步成本降为 $O (n^{2})$ 。
[ ] 能写出位移 QR 的相似关系。
[ ] 能说明实 Schur 形为何允许 $2 \times 2$ 块。
[ ] 能用“制造鼓包—追赶鼓包”描述 Francis 双位移。
[ ] 能说明隐式 Q 定理为什么允许不显式做 QR 分解。
[ ] 会用分解残差、正交误差和结构误差验收实现。

下一章：对称特征值与 SVD 算法。

07 Hessenberg 化、位移 QR 与 Francis 迭代 ​

1. QR 迭代在做什么 ​

2. 先约化为上 Hessenberg 形 ​

3. 位移加速收敛 ​

4. 亏损与分块 ​

5. 隐式 Q 定理与 Francis 双位移 ​

6. 从 Schur 形恢复特征向量 ​

7. 扰动视角 ​

8. QR 迭代与子空间迭代的关系 ​

9. Hessenberg 化的实现细节 ​

10. 隐式 Q 定理的含义 ​

11. 更稳健的亏损判据 ​

12. Schur 重排与条件数 ​

13. 复杂度与可靠性验收 ​

14. 自检 ​