求解奇异线性方程组的两种预条件QMR算法

王 芳，程俊荣

（温州大学数学与信息科学学院，浙江温州 325035）

求解奇异线性方程组的两种预条件QMR算法

王 芳，程俊荣

（温州大学数学与信息科学学院，浙江温州 325035）

主要讨论求解奇异线性方程组的两种预条件QMR算法，证明了相应的收敛性．数值试验表明，在收敛速度上，两种预条件QMR算法比预条件GMRES算法具有明显的优越性．

奇异线性方程组；预条件；恰当分裂；QMR算法

考虑求解相容奇异线性方程组：

其中，A∈Rn×n，x∈Rn，b∈R（A），r=rank（A）＜n ，R（A）和N（A）分别表示A的值域与核，AΤ表示A的转置．对（1）的求解，本文通过预条件技术，转化为对其下述预条件方程组的求解：

其中，M∈Rn×n为奇异的预条件子，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的零特征值所对应的若当子块的最大维数，通常也称为A的指标．文献[5]提出，通过恰当分裂可以构造具有值域对称性质的预条件，并证明了预条件GMRES[6]算法（广义最小残量法）的收敛性．对求解奇异线性方程组的预条件QMR算法，目前还未见有关文献对其进行讨论．本文将证明两种预条件QMR算法求解奇异线性方程组（1）的收敛性，并通过数值试验，比较这两种预条件QMR算法与预条件GMRES算法的收敛速度．

1 求解奇异线性方程组的两种预条件QMR算法

定义1[7]A的一个分裂A=M-N满足R（A）=R（M），N（A）=N（M），则称此分裂为恰当分裂．

对于奇异线性方程组（1），我们可通过恰当分裂构造预条件奇异线性方程组（2）．因R（A）=R（M），故由文献[8]引理2.2可知N（M+A）=N（A），故预条件奇异线性方程组（2）与奇异线性方程组（1）同解．

1.1 相关引理

引理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为值域对称矩阵，即R（A）=R（AT），则index（A）=1．

引理2[5]若A=M-N是恰当分裂，则M+A为值域对称矩阵．

1.2 两种QMR算法

由于篇幅限制，本节只简单介绍两种QMR算法，Look-ahead Lanczos算法请参考文献[1]．

算法1 拟极小化残量法（QMR）算法

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

5）当xk达到精度时停止．

算法2 TFQMR算法（不需要矩阵转置的QMR算法）：tfqmr（x,b,A,ε,k max）

2）当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算法求解预条件奇异线性方程组

理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 数值实验

其中rank（A）=r，A11和R=（A11A11T+BBT）-1A11M11-1A11（A11TA11+CTC）-1是阶数为r的非奇异矩阵，P和Q为置换矩阵．

以下数值试验均在Intel（R） Core（TM） i5 CPU 2.40GHz，内存为2.00 GB的个人计算机上完成，取初始向量x0=0，停机准则为：

在GMRES（20）算法中迭代步数k=（i-1）×20+j ，其中i表示重启次数，j表示最后一次重启的迭代步数．

例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，下面根据引理6构造预条件子M．

在计算M+时，使用丢失宽度为0.01的不完全LU分解来近似A11-1．分别采用QMR算法与预条件QMR算法、TFQMR算法与预条件TFQMR算法、预条件GMRES（20）算法，得迭代曲线，如图1（D、E、F）所示．

由图1A、图1B可知，两种QMR算法不收敛，而预条件QMR算法有很好的收敛性．由图1D、图1E可知，两种QMR算法虽然收敛，但预条件QMR算法的收敛速度更快．由图1F可知，在收敛速度上，求解奇异线性方程组（1），两种预条件QMR算法比预条件GMRES（20）算法具有明显的优越性．

[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

浙江省自然科学基金（Y1110451）

王芳（1987- ），女，安徽宿州人，硕士研究生，研究方向：计算数学