海森伯格約化

上海森伯格矩陣幾乎是上三角的：它允許主對角線及以上、外加緊貼其下的一條次對角線上有非零元，但更往下的一切都為零。它是僅靠正交相似、又不預先解出特徵值問題所能達到的最接近三角的形態。海森伯格約化就是把任意矩陣變成這種近三角形狀的預處理步驟。

約化由一連串兩側施加的 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)，整個特徵問題變得極其廉價——這正是快速對稱特徵求解器的基石。