求解奇異線性方程組的兩種預(yù)條件QMR算法

王 芳，程俊榮

（溫州大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，浙江溫州 325035）

求解奇異線性方程組的兩種預(yù)條件QMR算法

王 芳，程俊榮

（溫州大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，浙江溫州 325035）

主要討論求解奇異線性方程組的兩種預(yù)條件QMR算法，證明了相應(yīng)的收斂性．?dāng)?shù)值試驗表明，在收斂速度上，兩種預(yù)條件QMR算法比預(yù)條件GMRES算法具有明顯的優(yōu)越性．

奇異線性方程組；預(yù)條件；恰當(dāng)分裂；QMR算法

考慮求解相容奇異線性方程組：

其中，A∈Rn×n，x∈Rn，b∈R（A），r=rank（A）＜n ，R（A）和N（A）分別表示A的值域與核，AΤ表示A的轉(zhuǎn)置．對（1）的求解，本文通過預(yù)條件技術(shù)，轉(zhuǎn)化為對其下述預(yù)條件方程組的求解：

其中，M∈Rn×n為奇異的預(yù)條件子，M+表示M的Moore-Penrose逆，即滿足MM+M=M ，M+MM+=M+，（MM+）T=MM+，（M+M）T=M+M 的唯一矩陣．

Freund等人[1-4]提出基于Look-ahead Lanczos的兩種QMR算法（擬極小化殘量法），并用其求解index（A）=1的奇異線性方程組（1），其中index（A）表示A的零特征值所對應(yīng)的若當(dāng)子塊的最大維數(shù)，通常也稱為A的指標(biāo)．文獻[5]提出，通過恰當(dāng)分裂可以構(gòu)造具有值域?qū)ΨQ性質(zhì)的預(yù)條件，并證明了預(yù)條件GMRES[6]算法（廣義最小殘量法）的收斂性．對求解奇異線性方程組的預(yù)條件QMR算法，目前還未見有關(guān)文獻對其進行討論．本文將證明兩種預(yù)條件QMR算法求解奇異線性方程組（1）的收斂性，并通過數(shù)值試驗，比較這兩種預(yù)條件QMR算法與預(yù)條件GMRES算法的收斂速度．

1 求解奇異線性方程組的兩種預(yù)條件QMR算法

定義1[7]A的一個分裂A=M-N滿足R（A）=R（M），N（A）=N（M），則稱此分裂為恰當(dāng)分裂．

對于奇異線性方程組（1），我們可通過恰當(dāng)分裂構(gòu)造預(yù)條件奇異線性方程組（2）．因R（A）=R（M），故由文獻[8]引理2.2可知N（M+A）=N（A），故預(yù)條件奇異線性方程組（2）與奇異線性方程組（1）同解．

1.1 相關(guān)引理

引理1[8]若A∈Rn×n，則下列命題等價：

1）R（A）=R（AT）；

2）N（A）=N（AT）；

3）A+A=AA+；

4）A+=A#．

其中A#表示A的群逆，即滿足AA#A=A ，A#AA#=A#，AA#=A#A 的唯一矩陣．由引理1可知，若A為值域?qū)ΨQ矩陣，即R（A）=R（AT），則index（A）=1．

引理2[5]若A=M-N是恰當(dāng)分裂，則M+A為值域?qū)ΨQ矩陣．

1.2 兩種QMR算法

由于篇幅限制，本節(jié)只簡單介紹兩種QMR算法，Look-ahead Lanczos算法請參考文獻[1]．

算法1 擬極小化殘量法（QMR）算法

4）計算xk=x0+Vk（Rk）-1tk；

5）當(dāng)xk達到精度時停止．

算法2 TFQMR算法（不需要矩陣轉(zhuǎn)置的QMR算法）：tfqmr（x,b,A,ε,k max）

2）當(dāng)k＜k max 時，

iv. τ=τθc,η=c2αk-1，

v. x=x+ηd，

e）y1=w+βy2，u1=Ay1；

f）v=u1+β（u2+βv）．

1.3 兩種QMR算法求解預(yù)條件奇異線性方程組

理4和引理5可知，x=（M+A）+M+b+P x是奇異線性方程組（1）的解．又有N（M+A）,R（M+A）0 x0∈R（AT），所以x0∈R（M+A），故PN（M+A）,R（M+A）x0=0．余下證明同定理1．

2 數(shù)值實驗

其中rank（A）=r，A11和R=（A11A11T+BBT）-1A11M11-1A11（A11TA11+CTC）-1是階數(shù)為r的非奇異矩陣，P和Q為置換矩陣．

以下數(shù)值試驗均在Intel（R） Core（TM） i5 CPU 2.40GHz，內(nèi)存為2.00 GB的個人計算機上完成，取初始向量x0=0，停機準則為：

在GMRES（20）算法中迭代步數(shù)k=（i-1）×20+j ，其中i表示重啟次數(shù)，j表示最后一次重啟的迭代步數(shù)．

例1 矩陣A是如下矩陣（見文獻[5]）：

圖1 幾種算法的迭代曲線

例2 矩陣A是如下矩陣（見文獻[10]），其中h=1/m，n=m2，α±=1±dh/2，取m=64，d=10，即得A是4 096×4 096階矩陣，rank（A）=4 095．

選擇隨機向量作為奇異線性方程組（1）的右端向量b，為使（1）相容，用Ab代替b，下面根據(jù)引理6構(gòu)造預(yù)條件子M．

在計算M+時，使用丟失寬度為0.01的不完全LU分解來近似A11-1．分別采用QMR算法與預(yù)條件QMR算法、TFQMR算法與預(yù)條件TFQMR算法、預(yù)條件GMRES（20）算法，得迭代曲線，如圖1（D、E、F）所示．

由圖1A、圖1B可知，兩種QMR算法不收斂，而預(yù)條件QMR算法有很好的收斂性．由圖1D、圖1E可知，兩種QMR算法雖然收斂，但預(yù)條件QMR算法的收斂速度更快．由圖1F可知，在收斂速度上，求解奇異線性方程組（1），兩種預(yù)條件QMR算法比預(yù)條件GMRES（20）算法具有明顯的優(yōu)越性．

[1] Parlett B N, Taylor D R, Liu Z A. A look-ahead Lanczos algorithm for unsymmetrices [J]. Math Comp, 1985, 44：105-124.

[2] Freund R, Nachtigal N. QMR：a quasi-minimal residual methods for non-Hermitian linear systems [J]. Numer Math, 1991, 60：315-339.

[3] Freund R. A transpose-free quasi-minimal residual algorithm for non-Hermitian linear systems [J]. SIAM J Sci Comput, 1993, 14：470-482.

[4] Freund R, Hochbruck M. On the use of two OMR algorithms for solving singular systems and applications in markovchain modeling [J]. Numer Linear A lgebra Appl, 1994, 1：403-420.

[5] Zhang N. A note on preconditioned GMRES for solving singular linear systems [J]. BIT Numer Math, 2010, 50：207-220.

[6] Saad Y, Schultz M H. GMRES：A generalized m inimal residual algorithm for solving nonsymmetric linear systems [J]. SIAM J Sci Stat Comput, 1986, 7：858-869.

[7] Berman A, Plemmons R. Cones and iterative methods for best least squares solutions of linear systems [J]. SIAM J Numer Anal, 1974, 11：145-154.

[8] Zhang N, Wei Y. On the convergence of general stationary iterative methods for Range-Hermitian singular linear systems [J]. Numer Linear A lgebra Appl, 2010, 17：139-154.

[9] Kelley C T. Iterative methods for linear and nonlinear equations [M]. Philadelphia：SIAM, 1995：60-66.

[10] Zhang S L, Oyanagi Y, Sugihara M. Necessary and sufficient conditions for the convergence of Orthom in（k） on singular and inconsistent linear systems [J]. Numer Math, 2000, 87：391-405.

The Two Preconditioned QMR Algorithms for Solving Singular Linear Equations

WANG Fang, CHENG Junrong
（College of Mathematics and Information Science, Wenzhou University, Wenzhou, China 325035）

This paper mainly discusses the two preconditioned QMR algorithms for solving singular linear equations and thus proves the corresponding convergence. Numerical experiments show that these two algorithms have better convergence speed than the preconditioned GMRES algorithm.

Singular Linear Equations；Preconditioned；Proper Splitting；QMR Algorithm

O241.6

A

1674-3563（2013）01-0024-07

10.3875/j.issn.1674-3563.2013.01.005 本文的PDF文件可以從xuebao.wzu.edu.cn獲得

（編輯：王一芳）

2011-04-13

浙江省自然科學(xué)基金（Y1110451）

王芳（1987- ），女，安徽宿州人，碩士研究生，研究方向：計算數(shù)學(xué)