丁伯倫，陳光喜

桂林電子科技大學 數(shù)學與計算科學學院，廣西 桂林 541004

一種微變形的WGMRES算法

丁伯倫，陳光喜

桂林電子科技大學 數(shù)學與計算科學學院，廣西 桂林 541004

1 引言

對于線性代數(shù)方程組

其中A∈Rn×n為非奇異，x，b∈Rn?？梢詫仃嘇進行分解運算得到方程組的解。但是當式（1）為大型稀疏非對稱的線性方程組時，就不能簡單地對A進行分解運算了，然而迭代法則是求解該類型方程組的一個有效方法[1]。在數(shù)學計算中，常采用廣義極小殘量方法（GMRES）來求解該種方程組的數(shù)值解。GMRES算法是在1986年由Saad和Schultz基于Galerkin原理而提出的[2-3]，是一種求解非對稱線性適定方程組的Krylov子空間的投影法。該算法的主要思想是解決每步迭代的一個最小二乘問題，并采用正交投影或者斜投影在子空間產(chǎn)生迭代向量進行計算[4]。

而本文所研究的WGMRES方法是在標準的GMRES方法上進行改進后的算法，即可將其看成對標準GMRES方法的一個簡單的預處理。WGMRES方法的收斂性比較好，得出的計算結果也是令人滿意的。文中提出了一種新的微變形的WGMRES方法，這種方法對WGMRES算法的過程進行一個簡單的變形，在第k步近似解時將殘量表達式引入D范數(shù)來替換原先的2范數(shù)，經(jīng)過一系列變換后仍按照標準GMRES算法的一般步驟計算下去，也得到了比較精確的結果。在解決某些問題時，本文算法較標準的GMRES算法有很好的收斂性。在后面的數(shù)值實驗中，將給出確切的實例來分析和驗證。

2 Weighted Arnoldi過程

定義為：

則根據(jù)上面的定義可得出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。在此基礎上可以發(fā)現(xiàn)這樣一個特點[9]，用Vk+1乘以rk時，其滿足。在此基礎上將原先2范數(shù)替換為D范數(shù)，并結合算法1中得到的關系式（2）和（3），可以推導出下面的關系方程：

算法2

（1）選擇初始值x0，計算殘量r0=b-Ax0；

（3）通過算法1求出一組正交基Vk；

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

（6）再根據(jù) rk的結果來決定迭代是否終止。

對于使用上述算法的計算過程中，可以提供一個迭代算法終止的標準。

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

4 數(shù)值實驗

在此給出三個大型非對稱的稀疏矩陣，運用上述改進的算法來求大型稀疏方程組的解，并與標準的GMRES算法進行比較，通過圖像來觀察它們的收斂情況和收斂速度的快慢。

例1設大型稀疏非對稱線性方程組（1）中的A為一個100階的如下矩陣：

選取值x=(1，1，…，1)T，可以由b=A·x得出b的值，然后使用改進的算法求解方程組（1）。圖1給出了該算法的迭代步數(shù)與殘量范數(shù)的對數(shù)（以10為底）的關系。

圖1 兩種迭代算法關于例1中矩陣的比較

在該例中，D=diag(d)在區(qū)間（0.5，1.5）里隨機選取。由圖1可以看出，在第10步迭代之后，微變形的WGMRES算法收斂速度明顯快于標準的GMRES算法。

例2設大型稀疏非對稱線性方程組（1）中的A[10]為一個500階的如下矩陣：

同樣選取值x=(1，1，…，1)T，可以得出b的值。圖2也給出了該算法的迭代步數(shù)與殘量范數(shù)的對數(shù)的關系。

圖2 兩種迭代算法關于例2中矩陣的比較

在該例中，D=diag(d)在區(qū)間（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中矩陣的比較

在該例中，矩陣階數(shù)n＞500，則在（0，2）中隨機選取，由圖3可以看出，在50步迭代之前，微變形的WGMRES算法的收斂速度較標準的GMRES算法要稍慢點，但是之后收斂速度明顯加快且優(yōu)于標準的GMRES算法。

引理1[12]當階數(shù)n≤500，di在區(qū)間（0.5，1.5）里取值；當n＞500時，di在區(qū)間（0，2）里取值。

5 結論

研究了加權GMRES（WGMRES）方法的一種微變形情況，在算法的計算過程中對殘量表達式進行了變形。本文給出了算法的詳細證明，并進行了三個數(shù)值實驗的驗證。實驗結果說明，這種微變形的算法是行之有效的，可以得出精確解；而且在解決某些問題時，比標準的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].高等計算數(shù)學學報，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—），男，教授，研究方向：數(shù)值代數(shù)，信息安全。E-mail：dingbolun123@126.com

2013-01-07

2013-03-01

1002-8331（2013）13-0048-03