海森伯格约化

上海森伯格矩阵几乎是上三角的：它允许主对角线及以上、外加紧贴其下的一条次对角线上有非零元，但更往下的一切都为零。它是仅靠正交相似、又不预先解出特征值问题所能达到的最接近三角的形态。海森伯格约化就是把任意矩阵变成这种近三角形状的预处理步骤。

约化由一连串两侧施加的 Householder 反射完成：A 变为 H = Q^T A Q，一个正交相似变换，故 H 与 A 有完全相同的特征值。关键是你无法以此一路推到三角——那会直接把特征值交给你，而对一般矩阵没有有限算法能做到。那一条次对角线就是不可约的残余。代价是固定的 O(n^3)，只做一次。

回报体现在它对 QR 算法的作用上。对满矩阵作一步 QR 要 O(n^3)，但对海森伯格矩阵作一步 QR 只需 O(n^2)，而海森伯格结构被每一步保持。于是你付一次 O(n^3) 来约化，然后跑许多廉价的 O(n^2) 迭代。没有这一约化，QR 算法会慢得无可救药。

对称性使它更上一层。若 A 对称，其海森伯格形也必对称，而只有一条次对角线的对称矩阵就是三对角矩阵。故对称情形约化为一个三对角矩阵，在它上面每步 QR 只需 O(n)，整个特征问题变得极其廉价——这正是快速对称特征求解器的基石。