廣義特徵值問題

對於形式如下的特徵值問題：

求數λ，使方程Ax=λBx有非零解x，這裡A為n階實對稱矩陣，B為n階實對稱正定矩陣，x為n維列向量，則稱該問題為矩陣A相對於矩陣B的廣義特徵值問題，稱滿足上式要求的數λ為矩陣A相對於矩陣B的特徵值，而與λ相對應的非零解x稱為屬於λ的特徵向量。

基本介紹

• 中文名：廣義特徵值問題
• 外文名：Generalized Eigenvalue Problems

等價形式

由於B正定，故廣義特徵值問題可轉化為下面兩種形式

（1）用B^-1 左乘原式兩端得：

B^-1 Ax=λx

這樣就把廣義特徵值問題等價地化為了矩陣B^-1 A的普通特徵值問題，雖然B^-1，A都是對稱矩陣，但其乘積一般不再是對稱矩陣。

（2）對於正定矩陣B進行Cholesky分解，得B=GG^T，其中G是下三角矩陣，於是原式可以寫為：

Ax=λGG^Tx

令y=G^Tx，則有x=（G^-1 ）^Ty，整理得

Sy=λy

其中S=G^-1 A（G^-1 ）^T是對稱矩陣

（3）計算矩陣B的譜分解B=X△X^T ，其中X是正交矩陣，△是對角矩陣。因此原式等價於：

X^TAXy=λ△y，其中y=X^Tx，進而轉化為：Dz=λz，其中D=△^-1/2X^TAX△^1/2，z=△^1/2y

但是當矩陣A，B均為稀疏對稱矩陣時，（2）（3）算法均丟失了矩陣的稀疏性，引起了計算量和存儲量的增加。

並行算法

（1）二分/多分法

二分/多分法是計算實對稱矩陣特徵值問題最常用的並行算法，尤其適合計算部分特徵值問題，大多數情況下只需計算給定區間內的特徵值或給定序號的特徵值，因而二分/多分法是一個很好的選擇。

（2）分治算法

分治算法簡稱為DC算法，是一種較新的比較適合計算的矩陣廣義特徵值問題算法。DC算法的基本思想是將大問題分解為兩個易於計算的子問題，先求解子問題，然後構成一個比原問題容易求解的廣義特徵值問題。對於子問題，仍可繼續利用DC算法，使矩陣規模達到很小，以便於計算。

（3）同倫連續法

同倫連續法是求解矩陣廣義特徵值問題的一種新的並行算法。

（4）疊代法

前面介紹的計算廣義特徵值問題的各種算法都要對矩陣進行變換，然後進行求解。另外還有一類算法，只用到矩陣與向量相乘而不作矩陣變換，此類算法就是疊代法。典型的疊代法有 Lanczos 、Davidson、 Arnoldi 、子空間疊代、 Rayleigh商逆疊代等算法。