Golub-Kahan 雙對角化
/ GOH-loob KAH-han /
電腦究竟如何計算 SVD A = U Sigma V^T？素樸的想法——組出 A^T A、特徵分解它得到 V 與奇異值的平方、再回推 U——是個已知的精度陷阱，因為把 A 平方也把條件數平方，把小奇異值撕個粉碎。Golub-Kahan 雙對角化是正確做法的巧妙第一階段：它用直接作用於 A、絕不組出 A^T A 的正交變換，把 A 化為一個簡單的雙對角形狀，從而保留精度。
這個化簡把 A 夾在交替從左、從右施加的豪斯霍爾德反射之間：A = U_B B V_B^T，其中 B 是「雙對角」（只在主對角線與其正上方一條對角線非零），U_B、V_B 正交。一次左反射把某一欄對角線以下歸零；一次右反射把超對角線右邊某一列歸零；交替施加恰好留下雙對角骨架。對 m×n 矩陣，這花費固定的 O(m n^2)，只做一次。關鍵事實：B 與 A 有完全相同的奇異值（正交變換保留奇異值），所以困難問題已化簡為求一個極窄頻寬的雙對角矩陣的 SVD。
第二階段接著用一個疊代過程計算雙對角 B 的 SVD，那個過程換個面貌看，就是施於 B^T B 卻「從不」組出 B^T B 的隱式移位對稱 QR 演算法（Golub-Reinsch 演算法；若要小奇異值的高相對精度，則用 dqds 演算法）。這個兩階段結構——直接正交雙對角化，再對雙對角做隱式對稱-QR——正是 LAPACK 的 SVD 常式的運作方式，交出向後穩定的奇異值與向量。它與稠密特徵值求解器是同一個架構想法（一次性化為簡單帶狀形式，再便宜地疊代），特化到 SVD。
對一個高瘦的 1000x50 資料矩陣 A，Golub-Kahan 先透過交替的左／右豪斯霍爾德反射，把它化為一個 50x50 的雙對角 B（只 50 + 49 = 99 個非零數），並累積 U_B 與 V_B。接著對 B 做幾趟隱式 QR，把超對角元素歸零，留下 50 個奇異值在對角線上——全程從不計算那個條件數會是 A 平方的 50x50 矩陣 A^T A。
第一階段：把 A 正交化簡為奇異值相同的雙對角矩陣。第二階段：對雙對角做隱式對稱-QR 掃描。
雙對角化的全部要點，就是「避免」組出 A^T A，因為它的條件數是 A 的平方——組出它會在小奇異值上損失約一半位數。反射要從兩側交替施加（不只一側），這正是產生雙對角而非三角形式的原因。