krylov子空間算法(共14頁)

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

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

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

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

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

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

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

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

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

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

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

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

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

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