特徵值問題與奇異值分解

對稱特徵值問題

當矩陣對稱(等於自己的轉置,A = A^T)——而科學中許多最重要的矩陣正是如此,像共變異數矩陣、剛度矩陣、圖的拉普拉斯矩陣——特徵值問題就變得像數值數學所能達到的那般乖巧。一般矩陣會出的所有岔子(複數特徵值、敏感的特徵值、非正交甚至缺失的特徵向量)統統不會發生。對稱情形是個友善的國度,理論乾淨,演算法又快又可信。

譜定理(spectral theorem)保證三件可愛的事實。特徵值全是「實數」——沒有複數對要追。特徵向量可選為「正交歸一」,所以矩陣分解為 A = Q Lambda Q^T,其中 Q 正交、Lambda 對角;這就是特徵分解,也是旋轉到一個基底,使 A 在彼此垂直的軸向上以單純的縮放作用。而且——對數值工作最關鍵的——特徵值是「完全良態」的:對 A 做大小為 epsilon 的擾動,每個特徵值最多移動 epsilon(外爾不等式 Weyl's inequality)。不像非對稱情形,這裡沒有特徵值病態可懼。瑞利商 v^T A v / (v^T v) 的值恰好落在最小與最大特徵值之間,並能從一個線性精確的特徵向量給出二次精確的特徵值估計。

因為這種結構,演算法得以特化並加速。用兩側豪斯霍爾德化為「三對角」形式(不只是海森堡),再跑帶維爾金森移位的對稱 QR(三次收斂),或分治法,或 MRRR 演算法,在 O(n^3) 內取得所有特徵對,但常數較小且保證特徵向量正交。對一個巨大稀疏對稱矩陣的少數極端特徵值,蘭索斯演算法(Lanczos)是利器。而任何矩陣 A 的 SVD,都是默默倚靠 A^T A 的對稱特徵值問題來計算的。所以對稱特徵值問題不只是一個特例——它是一般情形與奇異值機制賴以建立的根基。

共變異數矩陣對稱且半正定,所以它的特徵值全為實數且非負,特徵向量彼此正交——這些特徵向量正是主成分方向,特徵值則是沿各方向的變異數。對角化 A = Q Lambda Q^T 把你的資料旋轉到一組軸,使資料沿各軸獨立變動,而 Lambda 告訴你每個軸上承載多少變異。這就是 PCA,而它之所以乾淨地運作,正因矩陣對稱。

對稱矩陣有實特徵值、正交歸一的特徵向量,以及完全良態的特徵值——簡單而漂亮的情形。

良態的特徵「值」不保證良態的特徵「向量」:當兩個特徵值幾乎相等時,個別特徵向量是敏感的(它們可在近退化子空間內自由旋轉),即使每個特徵值本身穩定。那個不變「子空間」是良好確定的;其中個別的向量未必。

又稱
Hermitian eigenproblemsymmetric eigenvalue problem厄米特徵問題對稱特徵值分解