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 這類庫例程底層所調用的，也是你永遠不該自己寫稠密特徵求解器的原因。