一种微变形的WGMRES算法

丁伯伦，陈光喜

桂林电子科技大学 数学与计算科学学院，广西 桂林 541004

一种微变形的WGMRES算法

丁伯伦，陈光喜

桂林电子科技大学 数学与计算科学学院，广西 桂林 541004

1 引言

对于线性代数方程组

其中A∈Rn×n为非奇异，x，b∈Rn。可以对矩阵A进行分解运算得到方程组的解。但是当式（1）为大型稀疏非对称的线性方程组时，就不能简单地对A进行分解运算了，然而迭代法则是求解该类型方程组的一个有效方法[1]。在数学计算中，常采用广义极小残量方法（GMRES）来求解该种方程组的数值解。GMRES算法是在1986年由Saad和Schultz基于Galerkin原理而提出的[2-3]，是一种求解非对称线性适定方程组的Krylov子空间的投影法。该算法的主要思想是解决每步迭代的一个最小二乘问题，并采用正交投影或者斜投影在子空间产生迭代向量进行计算[4]。

而本文所研究的WGMRES方法是在标准的GMRES方法上进行改进后的算法，即可将其看成对标准GMRES方法的一个简单的预处理。WGMRES方法的收敛性比较好，得出的计算结果也是令人满意的。文中提出了一种新的微变形的WGMRES方法，这种方法对WGMRES算法的过程进行一个简单的变形，在第k步近似解时将残量表达式引入D范数来替换原先的2范数，经过一系列变换后仍按照标准GMRES算法的一般步骤计算下去，也得到了比较精确的结果。在解决某些问题时，本文算法较标准的GMRES算法有很好的收敛性。在后面的数值实验中，将给出确切的实例来分析和验证。

2 Weighted Arnoldi过程

定义为：

则根据上面的定义可得出Weighted Arnoldi过程[5-6]。

算法1

通过算法1解出了关于D的正交基Vk=[v1，v2，…，vk]，可知其满足[7]：

且也生成了一个(k+1)×k的上Hessenberg矩阵，满足：

3 微变形的WGMRES算法

按照算法1的计算步骤，在形成第k步近似解时有：xk= x0+Vkyk，yk∈Rk。则第k步残量表达式为rk=r0-AVkyk。在此基础上可以发现这样一个特点[9]，用Vk+1乘以rk时，其满足。在此基础上将原先2范数替换为D范数，并结合算法1中得到的关系式（2）和（3），可以推导出下面的关系方程：

算法2

（1）选择初始值x0，计算残量r0=b-Ax0；

（3）通过算法1求出一组正交基Vk；

（5）形成近似解xk=x0+Vkyk，即得出 rk=b-Axk；

（6）再根据 rk的结果来决定迭代是否终止。

对于使用上述算法的计算过程中，可以提供一个迭代算法终止的标准。

定理1[9]Weighted GMRES算法在第k步终止迭代，当且仅当hk+1，k=0。

4 数值实验

在此给出三个大型非对称的稀疏矩阵，运用上述改进的算法来求大型稀疏方程组的解，并与标准的GMRES算法进行比较，通过图像来观察它们的收敛情况和收敛速度的快慢。

例1设大型稀疏非对称线性方程组（1）中的A为一个100阶的如下矩阵：

选取值x=(1，1，…，1)T，可以由b=A·x得出b的值，然后使用改进的算法求解方程组（1）。图1给出了该算法的迭代步数与残量范数的对数（以10为底）的关系。

图1 两种迭代算法关于例1中矩阵的比较

在该例中，D=diag(d)在区间（0.5，1.5）里随机选取。由图1可以看出，在第10步迭代之后，微变形的WGMRES算法收敛速度明显快于标准的GMRES算法。

例2设大型稀疏非对称线性方程组（1）中的A[10]为一个500阶的如下矩阵：

同样选取值x=(1，1，…，1)T，可以得出b的值。图2也给出了该算法的迭代步数与残量范数的对数的关系。

图2 两种迭代算法关于例2中矩阵的比较

在该例中，D=diag(d)在区间（0.5，1.5）里随机选取。由图2可以看出，微变形的GMRES算法收敛速度比标准的GMRES算法稍快。

例3再选取一个大型稀疏非对称矩阵A[11]，且A为一个1 024阶的分块矩阵，其中T1和T2分别为一个16阶的矩阵：

在这个例子中，可以选取值x=(1，2，…，1 024)T，相应的算出b的值，并在图3中给出了相应的关系结果。

图3 两种迭代算法关于例3中矩阵的比较

在该例中，矩阵阶数n＞500，则在（0，2）中随机选取，由图3可以看出，在50步迭代之前，微变形的WGMRES算法的收敛速度较标准的GMRES算法要稍慢点，但是之后收敛速度明显加快且优于标准的GMRES算法。

引理1[12]当阶数n≤500，di在区间（0.5，1.5）里取值；当n＞500时，di在区间（0，2）里取值。

5 结论

研究了加权GMRES（WGMRES）方法的一种微变形情况，在算法的计算过程中对残量表达式进行了变形。本文给出了算法的详细证明，并进行了三个数值实验的验证。实验结果说明，这种微变形的算法是行之有效的，可以得出精确解；而且在解决某些问题时，比标准的GMRES算法的收敛效果要好，可以更快地提高收敛速度。

[1]Datta B N.Numerical linear algebra and applications[M].New York：SIAM-Society for Industrial and Applie of Mathematics，1994.

[2]Saad Y，Schultz M H.GMRES：a generalized minimal residual algorithm for solving nonsymmetric linear systems[J].SIAM J Sci Statist Comput，1986，7：856-869.

[3]Saad Y.Iterative methods for sparse linear system[M].[S.l.]：PWSPublishingCompany，aDivisionofInternational Thomson Publishing Inc，1996.

[4]钟宝江.一种灵活的混合GMRES算法[J].高等计算数学学报，2001，23（3）：261-272.

[5]Saberi Najafi H，Zareamoghaddam H.A new computational GMRES method[J].Applied Mathematics and Computation，2008，199：527-534.

[6]Cao Z H，Yu X Y.A note on weighted FOM and GMRES for solving nonsymmetric linear systems[J].Applied Mathemtics and Computation，2004，151：719-727.

[7]Kincaid D R，Young D M.Variations of the GMRES iterative method[J].Applied Numerical Mathematics，2003，45：3-10.

[8]Essai A.Weighted FOM and GMRES for solving nonsymmetric linear systems[J].Numer Algorithm，1998，18：277-299.

[9]Calvetti D.GMRES-type methods for inconsistent systems[J]. Linear Algebra Appl，2000，316：157-169.

[10]Brown P N.A theoretical comparison of the Arnoldi and GMRES algorithms[J].SIAM J Sci Comput，1991，12：58-78.

[11]Sidi A，DGMRES：a GMRES-type algorithm for Drazin-inverse solution of singular nonsymmetric linear systems[J].Linear Algebra Appl，2001，335：189-204.

[12]Saberi Najafi H，Ghazvini H.Weighted restarting method in the weighted Arnoldi algorithm for computing the eigenvalues of a nonsymmetric matrix[J].Appl Math Comput，2006，175：1276-1287.

DING Bolun,CHEN Guangxi

School of Mathematics and Computing Science,Guilin University of Electronic Technology,Guilin,Guangxi 541004,China

The GMRES method is a popular iterative method for the solution of equation with a large nonsymmetric nonsingular matrix.There are some algorithms of improvement in the calculation.Weighted GMRES uses the weighted methods to accelerate the speed of convergence.The calculation process of WGMRES algorithm is introduced,then a simple deformation is made to the calculation process,and it puts forward a new calculation method.The experimental results demonstrate the method has higher convergence.

Weighted GMRES;Krylov subspace;Givens rotations;iterative method

GMRES方法是解决大型稀疏非对称的线性方程组最有效的方法，在计算中存在着许多对标准GMRES进行改进的算法。Weighted GMRES算法使用加权方式来加快GMRES算法的收敛速度。主要研究WGMRES算法的计算过程，并对此做出简单的变形，从而提出一种新的计算方法。实验结果表明，该方法具有加快收敛的效果。

Weighted GMRES算法；Krylov子空间；Givens变换；迭代方法

A

O24

10.3778/j.issn.1002-8331.1301-0047

DING Bolun,CHEN Guangxi.WGMRES method of simple deformation.Computer Engineering and Applications,2013, 49（13）：48-50.

广西可信软件重点实验室基金项目（No.KS201213）。

丁伯伦（1989—），男，硕士研究生，研究方向：新型算法及应用软件；陈光喜（1971—），男，教授，研究方向：数值代数，信息安全。E-mail：dingbolun123@126.com

2013-01-07

2013-03-01

1002-8331（2013）13-0048-03