構造高斯消去法計算矩陣廣義特征值問題

構造高斯消去法計算矩陣廣義特征值問題

通過計算，只能通過d、e計算資源值的范圍[d、e]。在將范圍k分為k后，資源值確定為精度，其中k=[log2（2）e-d）。由于二分法收斂速度較慢，僅為線性收斂，因此在實際算法設計中，經常采用割線法、牛頓迭代、Laguerre迭代或廣義Raleigh商迭代進行加速。3.2實對稱矩陣廣義特征值問題對于實對稱矩陣廣義特征值問題Ax=λBx，可以直接計算矩陣A-λB的各級順序主子式，r=1,2，…，nλ．這樣計算得到的序列邀Pr（λ）妖也具有在上節(jié)敘述的Sturm序列性質，從而可以利用二分/多分法進行計算。但由于矩陣A-λB的三項遞推式很難得到，因而必須采用其它方式計算矩陣的Sturm序列。一種方式就是：計算矩陣A-λB的因子分解A-λB=UTDU，其中U為單位上三角矩陣。那么小于λ的特征值個數等于對角矩陣D的負元素的個數。更加常用的一種方式是采用一種變形的高斯消去法計算各級順序主子式序列的變號數。該方法不是按列而是按行消去對角線以下的元素，從而隨時可以計算順序主子式的符號，進而確定矩陣（A,B）小于λ的特征值個數。在按行消元的過程中，同時按列選主元，進行行交換，保證數值的穩(wěn)定性。作者在計算對稱帶狀矩陣特征值問題和廣義特征值問題時就利用了變形高斯消去法計算Sturm序列。4基于dc算法的矩陣廣義特征值問題算法分治（Divide-and-Conquer）算法簡稱為DC算法，是一種較新的適合并行計算的矩陣廣義特征值問題算法。DC算法的基本思想是將大問題分解為兩個易于計算的子問題，先求解子問題，然后構成一個比原問題容易求解的廣義特征值問題。對于子問題，仍可以對其繼續(xù)利用DC算法，使矩陣規(guī)模達到很小，以便于計算。4.1t,s的特征值的計算對于對稱三對角矩陣廣義特征值問題（2），取k≈n/2，并令：其中Ti、Si是對稱三對角矩陣，Si正定。下面的定理揭示了（T^,S^）和（T,S）的特征值之間的聯(lián)系。定理1：設λ1燮λ2燮Λ燮λn是（T,S）的特征值，λ^1燮λ^2燮Λ燮λ^n是（T^,S^）的特征值，則：λ^i-1燮λi燮λ^i+1,i=2,3，…，n-1,由以上定理可知，（T^,S^）的特征值是（T,S）的特征值的很好近似。因此，從（T^,S^）的特征值出發(fā)，經過若干次Laguerre迭代就可以得到（T,S）的特征值，每個特征值的計算都是獨立的，從而可以是并行的。關于廣義實對稱三對角矩陣特征值問題，作者提出了一種新的分治算法,它同樣將矩陣劃分為兩個子矩陣,但k1+k2=n-1，兩個子矩陣分別為原矩陣的左上角和右下腳的兩個主子矩陣，可以為特征值λi提供相對更加精確的特征區(qū)間（λ^i+1，λ^i），因而可以減少計算時間。4.2．2.2特征值及特征關于對稱帶狀矩陣廣義特征值問題，作者提出了如下的劃分策略：其中Ai,Bi∈R,k1+k2=n。并證明了如下定理。定理2：設λ1燮λ2燮Λ燮λn是矩陣對（A,B）的特征值，λ^1燮λ^2燮Λ燮λ^n是矩陣對(A^,B^)的特征值,則λ^i-r燮λi燮λ^i+r,i=1,2，…,n。其中，當i燮0時，λ^i=-∞；當i>n時，λ^i=∞。根據以上定理，就可以利用（3）式計算Sturm序列和3.1節(jié)介紹的二分/多分法計算特征值和特征向量。為了減少計算時間，可以利用廣義Rayleigh商迭代進行加速。5同倫連續(xù)法5.1．a,t模式同倫連續(xù)法是求解矩陣廣義特征值問題的一種新的并行算法。對于對稱矩陣廣義特征值問題Ax=λBx，令A(t)=(1-t)A0+tA,B(t)=(1-t)B0+tB，其中（A0,B0）是選定的便于計算且特征值與（A,B）的特征值比較接近的矩陣。構照同倫映射：對于微分方程（6），可以采用一般的計算微分方程的方法進行求解。6基于rocs的ts算法前面介紹的計算廣義特征值問題的各種算法都要對矩陣進行變換，然后進行求解。另外還有一類算法，只用到矩陣與向量相乘而不作矩陣變換，此類算法就是迭代法。典型的迭代法有Lanczos、Davidson、Arnoldi、子空間迭代、Rayleigh商逆迭代等算法。下面主要介紹Lanczos算法。假設計算實對稱矩陣廣義特征值問題（1），該問題可以寫為B-1Ax=λx，采用三項遞推公式可產生列矩陣Q，使得B-1AQ=QT+R,其中Q=(q1,q2,…,qm),Q是B正交的：QTBQ=I,T=[βi,αi,βi+1],R=βm+1qm+1ekT是殘差矩陣，初始向量‖q1‖=1。Lanczos算法可以描述如下：Step1：初始化。選取初始向量Step2：迭代。然后計算T的特征對（λ,y），則(λ,Qy)是(A,B)的特征對。業(yè)已證明對于Lanczos方法，T常含有(A,B)的極端特征值近似。所以在一定條件下，Lanczos算法是近似對稱矩陣特征值和廣義特征值問題的一個好算法。但是，Lanczos算法數值穩(wěn)定性不好