構(gòu)造高斯消去法計(jì)算矩陣廣義特征值問(wèn)題

構(gòu)造高斯消去法計(jì)算矩陣廣義特征值問(wèn)題

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