陳曉花
(蘭州財(cái)經(jīng)大學(xué) 隴橋?qū)W院,甘肅 蘭州 730101)
對(duì)于大規(guī)模線性稀疏系統(tǒng)
Ax=b
(1)
其中A∈Rn×n是稀疏且非奇異矩陣,x,b(∈Rn)為n維向量,其求解近年來(lái)傾向于運(yùn)用迭代法.在眾多迭代法中,目前最為活躍和有發(fā)展前途的方法是Krylov子空間方法.而Krylov子空間中有兩類(lèi)方法應(yīng)用比較廣泛,一類(lèi)是基于Arnoldi過(guò)程構(gòu)造Krylov子空間
Km(A,r0)=span(r0,Ar0,…,Am-1r0)
(2)
的正交基的方法,如目前應(yīng)用最多的GMRES(Generalized minimum residual method)算法[1],F(xiàn)OM算法等,對(duì)這類(lèi)算法的研究也是目前國(guó)內(nèi)外研究的熱點(diǎn),如Azeddine Essai在文獻(xiàn)[2]中提出了一種稱為Weighted GMRES的方法,利用加權(quán)技術(shù)加快了GMRES算法的收斂速度;另一類(lèi)是基于Lanczos雙正交化過(guò)程產(chǎn)生Krylov子空間
Km(A,v1)=span(v1,Av1,…,Am-1v1)
(3)
和
Km(AT,ω1)=span{ω1,ATω,…,(AT)m-1ω1}
(4)
的算法,如QMR(Quassi Minimal Residual)算法[3],BiCG(Bi-orthogonal Conjugate Gradient)算法,BiCGSTAB算法等.本文結(jié)合文獻(xiàn)[2]中的加權(quán)思想,對(duì)QMR算法進(jìn)行了改進(jìn),即得到了WeightedQMR算法.數(shù)值試驗(yàn)表明,對(duì)某些問(wèn)題該算法的收斂速度優(yōu)于QMR算法.
算法1 Lanczos雙正交過(guò)程[3]
(1)選取兩個(gè)向量v1,w1,使得(v1,w1)=1.
(2)令β1=δ1≡0,w0=v0≡0.
(3)Forj=1,2,…,m,Do:
(4)αj=(Avj,wj)
(11)EndDo.
構(gòu)造三對(duì)角矩陣Tm如下:
令Vm=[v1,…,vm],Wm=[w1,…,wm],則有如下的命題成立:
命題1[3]如果上述算法1在m步之前不會(huì)發(fā)生中斷,則{vi}(i=1,2,…,m)和{wi}(i=1,2,…,m)分別是子空間:
Km(A,v1)=span(v1,Av1,…,Am-1v1)
(5)
和Km(AT,ω1)=span{ω1,ATω,…,(AT)m-1ω1}的基,向量{vi}(i=1,2,…,m)與{wi}(i=1,2,…,m)滿足關(guān)系式(vj,wi)=0,i≠j,1≤i,j≤m,(vi,wi)=1,1≤i≤m且有如下的等式成立:
(6)
(7)
(8)
下面利用上述D-內(nèi)積的定義,給出加權(quán)的Lanczos雙D-正交化過(guò)程.
算法2 Lanczos雙D-正交過(guò)程
(3)Forj=1,2,…,m,Do:
(11)EndDo.
(9)
其中
(10)
(11)
(12)
(13)
若i =0 (14) (15) 算法3 WQMR算法 算例1 本例中矩陣取自矩陣市場(chǎng)(http://math.nist.gov/MatrixMarket/),條件數(shù)為3.5319e+004,非零元素個(gè)數(shù)為2423,階數(shù)為153,其結(jié)構(gòu)如圖1所示,其迭代次數(shù)與殘差圖如圖2所示: 圖1 算例1矩陣結(jié)構(gòu)圖 圖2 迭代次數(shù)與殘差圖 算例2 矩陣結(jié)構(gòu)如下: A=01-10???1-10?è??????÷÷÷÷100×100,迭代次數(shù)與殘差如圖3:圖3 迭代次數(shù)與殘差如圖 算例3 矩陣結(jié)構(gòu)如下: A=1111-111??-1???1???1??1-11?è?????????÷÷÷÷÷÷÷300×300,計(jì)算結(jié)果如圖4:圖4 計(jì)算結(jié)果比較 算例4 系數(shù)矩陣為如下三對(duì)角矩陣: A=3-2-13-2?????-2-13?è????????÷÷÷÷÷÷200×200迭代次數(shù)與殘差圖如圖5:圖5 迭代次數(shù)與殘差圖 利用D-內(nèi)積改進(jìn)Lanczos雙正交過(guò)程,得到加權(quán)的Lanczos雙D-正交過(guò)程,進(jìn)而得到加權(quán)擬極小殘差算法(WQMR),數(shù)值算例表明,對(duì)于某些帶狀矩陣,該算法是有效的,且收斂性優(yōu)于QMR算法.但該算法的優(yōu)越性很大程度上是依賴于權(quán)值d,對(duì)給定的矩陣A,如何選取最優(yōu)的權(quán)值d,目前還在研究當(dāng)中.2.2 加權(quán)擬極小殘差算法(WQMR)
3 數(shù)值算例
4 結(jié)論