求解大型稀疏線性方程組的加權(quán)擬極小殘差算法

陳曉花

(蘭州財(cái)經(jīng)大學(xué) 隴橋?qū)W院，甘肅 蘭州 730101)

0 引言

對(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ò)程

算法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)

2 加權(quán)QMR算法

2.1 加權(quán)Lanczos雙D-正交過(guò)程

下面利用上述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)

2.2 加權(quán)擬極小殘差算法(WQMR)

(15)

算法3 WQMR算法

3 數(shù)值算例

算例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ù)與殘差圖

4 結(jié)論

利用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)中.