白雪婷，楊琴樂

廣義極小殘余算法（GMRES）是求解由科學和工程問題得到的大規(guī)模稀疏線性方程組Ax=b最常用的方法之一，具有廣闊的應(yīng)用前景［1-2］.實際應(yīng)用中存在著許多對標準的GMRES 改進后的算法［3-4］.其中 WGMRES 算法就是一種對GMRES 改進后的算法，由ESSAI于1998 年提出.該方法用D 內(nèi)積來代替歐氏內(nèi)積，由此即可通過加權(quán)Arnoldi 過程來加快那些遠離零的殘余向量的收斂，進而改善GMRES（m）的收斂性［5］. 為了進一步提高WGMRES 算法收斂性，SABERI 和 NAJAF 提出快速 GMRES 算法［6］.丁伯倫和陳光喜提出微變形 WGMRES 算法［7］.楊圣煒和盧琳章研究的加權(quán)Simple GMRES 算法則是以Simple GMRES 算法為基礎(chǔ)，結(jié)合WGMRES 得到的，該方法計算量小于 WGMRES 算法［8］.

在實際執(zhí)行WGMRES（m）算法時，選取合適的加權(quán)因子可以加快算法收斂.此外，參數(shù)m的選擇對算法的收斂性也尤為重要，m選擇過小容易出現(xiàn)收斂慢甚至不收斂的現(xiàn)象，m選擇過大會造成存儲空間的浪費.基于此，文章首先給出一種新的加權(quán)因子，然后通過對原理型GMRES 算法和循環(huán)型GMRES算法的深入研究，指出適當?shù)淖兓瘏?shù)m可以改善GMRES 的收斂性，而且在一定程度上可以有效避免m取值過小或過大帶來的一些弊端.

1 預備知識

考慮線性方程組

其中 ：A∈Rn×n為非奇異大型矩陣 ，x,b∈Rn.取任意向量x0∈Rn，令x=x0+z，則有等價方程組

其中：r0=b-Ax0是初始殘量.

給定m＞0 ，取m維子空間Km=span{r0,Ar0,…,Am-1r0} ，Lm=AKm，基分別為其中vi,wi∈Rn. 利用Galerkin 原理取zm∈Km，使 (r0-Azm)⊥Lm，即(r0-Azm,wi)=0 ，這就構(gòu)成 GMRES 算法 .

定義1 設(shè)D={d1,d2,…,dn} 是一個對角矩陣，di＞0(i=1,2,…,n)，稱di為加權(quán)因子.取任意向量u,v∈Rn，則它們的內(nèi)積可記為：

相應(yīng)的加權(quán)范數(shù)定義如下：

加權(quán)Arnoldi 過程如下：

①取v1=r0‖r0‖D；

②對于k=1,2,…,m，計算

③如果hk+1,k=0 ，則停止，否則

引理 1［5］向量v1,v2,…,vm構(gòu)成子空間Km={v1,Av1,…,Am-1v1} 的一組D正交基.

引 理 2［5］令Vm=(v1,v2,…,vm)是n×m矩陣，Hm是m×m上海森伯格矩陣，其非零元由算法確定，則有

2 主要結(jié)果

2.1 WGMRES（m）算法

WGMRES（m）算法定義了新的內(nèi)積，旨在通過加權(quán)Arnoldi 過程加快那些遠離零的殘余向量的收斂.因此，對角矩陣D=diag(d1,d2,…,dn) 中的元素di即加權(quán)因子d的選擇是決定WGMRES（m）算法收斂快慢的重要因素之一.ESSAI 建議選取加權(quán)因子D=diag(d1,d2,…,di) ，其中 (r0)i表示殘余向量r0的第i個元素.這樣，‖d‖2=n，且當所有di都相等時向量D-范數(shù)就變成歐氏范數(shù).顯然，當 ‖r0‖→0 時，計算di比較困難.

文章給出一種新的加權(quán)因子，當線性方程組的系數(shù)矩陣A的階數(shù)為偶數(shù)時，取其中i=1,2,…,n-1 ，當系數(shù)矩陣A的階數(shù)為奇數(shù)時，取其中i=1,2,…,n-1 ，dn=1. 此時仍有

WGMRES（m）算法步驟：

①選擇x0∈Rn，m∈N+(m＜n).給定誤差上界ε＞0 ；

②選取di(i=1,2,…,n)，使得計算r0=b-Ax0，v1=r0β，β=‖r0‖D；

⑤計算zm=Vm ym，xm=x0+zm；

⑥若 ‖rm‖=‖r0-Azm‖＜ε，則迭代終止，否則x0=xm，轉(zhuǎn)向②.

2.2 VRP-WGMRES（m）算法

原理型GMRES 算法表明參數(shù)m的取值越靠近系數(shù)矩陣A的階數(shù)n，得到的解越接近方程組（1）的精確解.但是，不難看出，當n>>1 時，若仍取m≈n，將引起存儲空間的過多需求，這是不現(xiàn)實的.循環(huán)型GMRES（m）算法建議選用一個固定的適當大小的參數(shù)m來完成GMRES（m），通過多次迭代可得方程組近似解，這在一定程度上克服了使用原理型GMRES 算法求解方程組時所面臨的困難.但在實際執(zhí)行GMRES（m）算法時，參數(shù)m取值過小可能出現(xiàn)收斂慢甚至不收斂的情況，如何選取一個理想的m至今未給出合理建議.本文以WGMRES 為基礎(chǔ)，結(jié)合原理型GMRES 和循環(huán)型GMRES（m）的優(yōu)點，提出VRP-WGMRES（m）算法，該算法中參數(shù)m可以取一個較小初值.

VRP-WGMRES（m）算法思想：適當變化參數(shù)m，通過迭代使 ‖rm‖=‖r0-Azm‖＜ε.

VRP-WGMRES（m）算法：

① 選擇x0∈Rn，m∈N+(m＜＜n). 給定誤差上界ε＞0 ；

②選擇di(i=1,2,…,n)，使得計算r0=b-Ax0，v1=r0β，β= ‖r0‖D；

⑤計算zm=Vm ym，xm=x0+zm；

⑥若 ‖rm‖=‖r0-Azm‖＜ε，則迭代終止，否則x0=xm，m=m+1(m≤n)，轉(zhuǎn)向②.

3 數(shù)值算例

分別用 GMRES（m），WGMRES（m）和DGMRES（m）三種算法求解線性方程組（1）.圖1和圖3中1-WGMRES（m），2-WGMRES（m）分別表示加權(quán)因子d取文獻［4］中所給值和本文所給值時對應(yīng)的WGMRES（m）算法.圖2和圖4 中WGMRES（m）表示加權(quán)因子d取本文所給值時對應(yīng)的算法.

算例1 考察單位正方形區(qū)域 Ω={(x,y)|0 ＜x,y＜ 1} 上 Possion 方程

用正方形網(wǎng)格h=0.02 來求解上述問題.采用五點差分格式離散后可得線性方程組Ax=b，其中A為對稱矩陣.取初始向量x0=(0 ,0,…,0)T，給定誤差為 ε=1.0e-10.圖 1 給出了m=6時，1-WGMRES（m）和2-WGMRES（m）的收斂關(guān)系圖.圖2給出了m=6時，GMRES（m），WGMRES（m）和DWGMRES（m）三種算法的收斂關(guān)系.表1 和表2 給出了當重啟動參數(shù)m取不同值，殘量范數(shù)達到給定誤差時三種算法的數(shù)值結(jié)果.

從圖1 可以看出，當加權(quán)因子d取本文所給值時，WGMRES（m）收斂且速度較快，這既說明文章選取的加權(quán)因子優(yōu)于文獻［4］中所給的加權(quán)因子，又表明本文提出的加權(quán)因子是合理的.

圖1 加權(quán)因子d 取不同值時收斂關(guān)系圖

圖2 三種算法的收斂關(guān)系圖

從表1 可以看出，當殘量范數(shù)達到給定誤差時，對最初給定的m，DWGMRES（m）算法收斂最快；當參數(shù)m發(fā)生微小變化時，GMRES（m）的迭代次數(shù)波動較大，WGMRES（m）次之，DWGMRES（m）變化最小，這說明本文提出的新算法有很好的穩(wěn)定性.此外，不難發(fā)現(xiàn)，當最初給定的參數(shù)m取值較小時，新算法有更快的收斂速度和更高的計算精度.這表明使用文中所給算法求解方程組得到的近似解更接近精確解.

算例 2［6］求解線性方程Ax=b，選擇b使得x=(1 , 1,…,1)T是Ax=b的解，矩陣A為：

取初始向量為x0=(0 ,0,…,0)T，給定誤差為ε=1.0e-6.圖 3 給出了當n=100，m=10 時 1-WGMRES（m）和2-WGMRES（m）的收斂關(guān)系圖. 圖 4 給出了當m=10 時，GMRES（m），WGMRES（m）和DWGMRES（m）的收斂關(guān)系.表3 和表4 給出了當殘量范數(shù)達到給定誤差，重啟動參數(shù)m取不同值時，三種算法的數(shù)值結(jié)果.

圖3 加權(quán)因子d 取不同值時收斂關(guān)系圖

表1 ε =1.0e-10 且m 取不同值時三種算法迭代次數(shù)比較

表2 ε =1.0e-10 且m 取不同值時三種算法計算精度比較

表3 n =100，ε =1.0e-6 且m 取不同值時三種算法迭代次數(shù)比較

表4 n =100，ε =1.0e-6 且m 取不同值時三種算法計算精度比較

從圖3 可知，當加權(quán)因子d取本文所給值時，WGMRES（m）收斂，當加權(quán)因子d取文獻［4］中的值時，WGMRES（m）算法失敗，只能得到初始殘量從圖4和表3、表4可知，文章所提出的DWGMRES（m）算法有更好的穩(wěn)定性、更快的收斂速度以及更高的計算精度，可以用DWGMRES（m）算法來求解方程組.

圖4 三種算法的收斂關(guān)系圖

4 結(jié)論

針對WGMRES（m）算法，本文給出了一種新的加權(quán)因子，并驗證了其合理性和有效性.通過對WGMRES（m）算法中參數(shù)m作適當變化，提出了DWGMES（m）算法，數(shù)值試驗結(jié)果表明新方法的穩(wěn)定性，收斂速度以及計算精度優(yōu)于GMRES（m）和WGMRES（m）算法，并可以有效地避免參數(shù)選擇較小時GMRES（m）算法收斂慢甚至不收斂的現(xiàn)象.