krylov子空間算法(共14頁)

1、Krylov子空間的定義：定義：令，由所生成的子空間稱之為由與A所生成的m維Krylov子空間，并記。主要思想是為各迭代步遞歸地造殘差向量，即第n步的殘差向量通過系數(shù)矩陣A的某個多項式與第一個殘差向量相乘得到。即。但要注意，迭代多項式的選取應該使所構造的殘差向量在某種內(nèi)積意義下相互正交，從而保證某種極小性（極小殘差性），達到快速收斂的目的。Krylov子空間方法具有兩個特征：1.極小殘差性，以保證收斂速度快。2.每一迭代的計算量與存儲量較少，以保證計算的高效性。投影方法線性方程組的投影方法方程組,A是的矩陣。給定初始,在m維空間K(右子空間）中尋找x的近似解滿足殘向量與m維空間L(左子空間）正

2、交，即，此條件稱為Petrov-Galerkin條件。當空間K=L時，稱相應的投影法為正交投影法，否則稱為斜交投影法.投影方法的最優(yōu)性：. (誤差投影)設A為對稱正定矩陣,為初始近似解,且K=L,則為采用投影方法得到的新近似解的充要條件是 其中,2. (殘量投影)設A為任意方陣,為初始近似解,且,則為采用投影方法得到的新近似解的充要條件是其中矩陣特征值的投影方法對于特征值問題,其中A是nn的矩陣，斜交投影法是在m維右子空間K中尋找和復數(shù)滿足,其中L為m維左子空間.當L=K時，稱此投影方法為正交投影法.誤差投影型方法：取L=K的正交投影法 非對稱矩陣的FOM方法（完全正交法）對稱矩陣的IOM方法

3、和DIOM方法 對稱矩陣的Lanczos方法對稱正定矩陣的CG方法殘量投影型方法：取L=AK時的斜交投影法GMERS方法（廣義最小殘量法）重啟型GMERS方法、QGMERS、DGMERSArnoldi方法標準正交基方法：Arnoldi方法是求解非對稱矩陣的一種正交投影方法。Arnoldi算法就是對非對稱矩陣A，產(chǎn)生Krylov子空間的一組標準正交基的方法。該算法構造的一組標準正交基和Hessenberg矩陣，基于Gram-Schmit正交化方法首先，選取一個Euclid范數(shù)為1的向量,對,通?？扇。谝阎那闆r下,不妨設線性無關(否則構造完畢),則可求出與每個都正交的向量而不難看出，再記，得到

4、與都正交的向量，重復此過程，即可得到一組標準正交基。若期間某個j使得，則說明v的次數(shù)是j，且是A的不變子空間。Arnoldi算法：（1） 取向量，滿足（2） 按（2）式計算，再按（1）式計算（3） 按（3）式計算，若，則停止，否則按（4）式計算（4） 若，則，轉(zhuǎn)（2），否則停止 （1） （2） （3） （4）定理：如果記以為列構成的矩陣為,由定義的(m+1)m階上Hessenberg矩陣（假設一個階矩陣A，在時，它的，那么這個矩陣A就叫做Hessenberg矩陣）為,刪除最后一行得到的矩陣為，則： 在Arnoldi算法中，可能有較大舍入誤差，改寫：修正的Arnoldi算法：（1） 取向量，滿足

5、（2） 計算（3） 依次對，計算與（4） 計算，若，則停止，否則計算（5） 若，則，轉(zhuǎn)（2），否則停止FOM（完全正交化）方法非對稱矩陣的FOM方法：解方程組的投影法的矩陣表示設階矩陣與的列分別構成K與L的一組基。記，有當非奇異時，有，從而得到迭代公式：FOM算法：（1）計算，置（2）計算（3）依次對，計算與（4）計算，若，則置，轉(zhuǎn)（6）（5）計算，若，則置，轉(zhuǎn)（2）（6）按下式計算不難看出，當采用上述FOM算法時，需要存儲所有的，(i=1,2,m)，當m增大時，存儲量以量級增大.而FOM計算量是.可見其代價十分高昂.因此我們考慮重啟的FOM算法重啟型FOM算法：（1） 計算（2） 生成的一組

6、標準正交基，得到（3） 按下式計算，若滿足精度要求，則停止，否則置，轉(zhuǎn)（1）。IOM方法非對稱矩陣的IOM方法所謂不完全正交化方法(IOM),是指在正交化過程中,僅與最近k個正交,這樣做雖然破壞的正交性,但是降低了計算量.當然k選得越小，對每個j對應的計算量也越小,但可能要選更大的m才能取得滿足精度要求的近似解.IOM算法僅僅是把FOM算法的第三步改為，計算與。 但采用IOM后，仍然需要存儲,因為在第(vi)步中仍然需要這些向量.解決這個問題可以考慮采用H的LU分解，通過自身分解的迭代更新以減少每一步的存儲量DIOM算法：（1） 計算，置（2） 計算（3） 對，依次計算與（4） 計算（5） 按

7、（4）式更新的LU分解，若，則停止（6） 按（3）式計算，按（2）式計算，其中時，（7） 按（1）式計算，若符合精度要求，則停止，否則，轉(zhuǎn)（2） （1） （2） （3） （4）Lanczos方法Lanczos方法是求解大規(guī)模稀疏對稱矩陣端部特征問題的一種常用的正交投影方法。它在Krylov子空間上對對稱矩陣采用Rayleign-Ritz方法，得到某些特征值和特征向量的近似?；舅枷胧墙o定一初始向量，逐步地構造出由該初始向量和對稱陣生成的Krylov子空間的標準正交基。通過簡單的三項遞推公式將大規(guī)模對稱陣投影為小規(guī)模對稱三對角陣，然后用此三對角陣的特征對來得出原始矩陣的近似特征對。由于三對角陣好

8、的結構和小的維數(shù)，在準確運算下，每一步所需存儲量和計算量是常量，不會隨著子空間維數(shù)的增加而改變。Lanczos算法：（1） 計算，置（2） 計算，其中當時（3） 計算與（4） 計算，若，則置轉(zhuǎn)（5），否則置，若，則，轉(zhuǎn)（2）（5） 置，計算（6） 計算Lanczos雙正交化方法 在雙正交化過程中，取 容易看出A和在其中扮演對偶的角色，此方法特別適用于需要求解兩個系數(shù)矩陣分別是A和的方程組.基于Lanczos雙正交化過程的雙共軛梯度法BiCG算法：（1） 計算，選取使得，置方向向量，并置m=0（2） 計算與向量，如果滿足精度要求，則停止（3） 計算參數(shù)，與向量，置m=m+1,轉(zhuǎn)（2）CG方法CG

9、法用來解對稱且正定方程組十分有效，但若是拿來解非對稱或是非正定的線性方程組則會發(fā)生中斷。它是借由迭代的方式產(chǎn)生一序列的方向向量用來更新迭代解以及殘向量，雖然產(chǎn)生的序列會越來越大，但是卻只需要存儲少數(shù)的向量。當系數(shù)矩陣A相當大而且稀疏，此時CG法幾乎就是高斯消去法。CG法理論上雖然保證最多n步能解出線性方程組的解，但是若系數(shù)矩陣是病態(tài)的，此時累進誤差會讓CG法在n步后無法求得充分精確的近似解。CG算法：（1）計算，選取，置（2）計算參數(shù)，更新向量與殘向量，若滿足精度要求，則停止（3）計算，置，轉(zhuǎn)（2）CG法是解正定對稱線性方程組最有效的方法之一，該方法充分利用了矩陣A的稀疏性，每次迭代的主要計算

10、量是向量乘法。 GMRES方法GMRES算法要求系數(shù)矩陣A是非奇異，非對稱的n維方陣。GMRES算法利用Arnoldi變換構造一正交基來表示Krylov子空間。GMRES方法把方程組的求解化為一個極小問題的求解，不去直接求,轉(zhuǎn)而去解此極小問題，這是GMRES方法的獨到之處。 GMRES算法的收斂性完全取決于系數(shù)矩陣A的特征值的性質(zhì)。GMRES算法：（1） 計算，置（2） 計算（3） 依次對，計算與（4） 計算，若，則置，轉(zhuǎn)（6）（5） 計算，若，則置，轉(zhuǎn)（2）（6） 求，計算求解最小二乘問題的算法：（1） 令，（2） 計算，置（3） 置向量，計算（表示矩陣第i行從i+1列到m列的元素構成的列向

11、量）（4） 置，計算（5） 若，轉(zhuǎn)（2）（6） 依次對，計算所得到的即為所求的 GMRES算法允許Krylov子空間維數(shù)增加到n，而且總是在最大迭代次數(shù)n內(nèi)終止運算；另一種重啟型GMRES算法嚴格要求子空間維數(shù)為一個定值m，在進行了m次迭代后，以得到的最后迭代結果作為初始點重新進行Arnoldi變換，當殘余向量滿足時，終止計算。綜合考慮時間和空間復雜度，重啟型的GMRES算法更適合。重啟型GMRES算法：（1） 計算（2） 生成的一組標準正交基，得到（3） 求，計算，若滿足精度要求，則停止，否則置，轉(zhuǎn)（1） 同樣可以采取不完全正交的方法，在正交化過程中,僅與最近k個正交就能得到QGMRES方法

12、。為了避免存儲，可以對進行QR分解.這種算法被稱為DQGMRES。QGMRES算法：（1） 計算（2） 計算（3） 對，計算與（4） 計算，若，則置，轉(zhuǎn)（6）（5） 計算，若，則置，轉(zhuǎn)（2）（6） 求，計算Krylov子空間方法解矩陣特征值問題Arnoldi方法求解非對稱矩陣特征值由定理： 而，則有如下結論：（1） 若，則是A的不變子空間，從而的所有特征值是A的特征值子集。（2） 若，則的特征值對是，即，由上述定理可得： 以上討論說明,可以用的特征值 (又稱Ritz值)來近似A的特征值,用向量(又稱Ritz向量)來近似相應的特征向量.事實上, 為A在Krylov子空間上的正交投影. 由于是上H

13、essenberg陣，它的特征值求解難度遠小于原問題,例如可以采取分解法來求解.求解矩陣特征值的Arnoldi方法：（1） 給定m，取向量，滿足（2） 計算（3） 依次對，計算與（4） 計算，若，則停止，否則計算（5） 若，則，轉(zhuǎn)（2）（6） 計算的特征值對及A關于的Ritz向量Arnoldi算法構造標準正交基存在的問題： 1需要存儲所有的基向量,當m很大時,存儲量大 2理論上為了保證收斂速度,m越大越好Lanczos方法求解對稱矩陣特征值 A是對稱陣時,是三對角陣，仍然采用的特征值來近似A的特征值，相應的Ritz向量來近似A的特征向量. 問題轉(zhuǎn)化為三對角陣特征值的求解問題，而它的求解，復雜度

14、大大減小，有很多成熟的辦法，如分而治之法，QR法等，可以在并行機上達到tO(logN)的量級.求解對稱矩陣特征值的Lanczos方法：（1）計算，置（2） 計算，其中當時（3） 計算與（4） 計算，若，則置轉(zhuǎn)（5），否則置，若，則，轉(zhuǎn)（2）（5） 計算的特征對及A的關于的Ritz向量預條件法 Krylov子空間方法的收斂性一般都和矩陣的特征值分布有關，特征值分布越集中，收斂速度越快，若特征值分布較分散，則收斂的很慢，此時可以采用預條件子來改善矩陣的特征值分布. 選取矩陣使得A的特征值比A集中，并且容易求得，于是將原問題化為問題,這是左預條件法，還可采用右預條件法和分裂預條件法在求解矩陣特征值問題時，可以利用chebyshev多項式來加快收斂 所謂多項式加速,就是采用作為迭代初始向量,其中 為多項式,如果, 其中為A的特征值對應的特征向量則。 將特征值按實部遞減順序排列,其中為r個“想要”的特征值,將“不想要”的特征值點集用S表示.如果多項式,能使得S盡可能小,則相當于讓求解過程產(chǎn)生加速.而Chebyshev多項式由于它的特殊性質(zhì),恰好能滿足這種要求.不過，至今,仍