于春肖，井丁卉，楊艷芳

(燕山大學(xué) 理學(xué)院 河北 秦皇島 066004)

0 引言

在工程領(lǐng)域中，很多問題最終都可歸結(jié)為求解大型線性方程組。由Sadd提出的GMRES(m)算法是求解大型線性方程組最有效的方法之一，被廣泛應(yīng)用到工程領(lǐng)域[1-4]。隨著GMRES(m)算法的廣泛應(yīng)用，為加快GMRES(m)算法的收斂速度，很多學(xué)者對(duì)該算法進(jìn)行優(yōu)化與改進(jìn)，一種方法是采用預(yù)處理技術(shù)[5-7]，通過加權(quán)技術(shù)，即WGMRES(m)算法來加快算法的收斂性。孫蕾等利用殘量多項(xiàng)式預(yù)處理方法，建立右端多項(xiàng)式預(yù)處理GMRES(m)算法[8];于春肖等通過深入探討算法的收斂性與方程組系數(shù)矩陣的密切關(guān)系[9],提出一種預(yù)條件廣義極小殘余新算法；楊圣煒等通過引用加權(quán)技術(shù)，提出了加權(quán)SGMRES算法(WSGMRES算法)[10]；在此基礎(chǔ)上，仲紅秀等利用加權(quán)策略和分析基底條件數(shù)，對(duì)塊simple GMRES方法進(jìn)行了改進(jìn)，提出加權(quán)simple GMRES算法[11]；Yu等通過改變m的取值來加快收斂，進(jìn)而提出VRP-GMRES(m)算法[12-13]；郝雪景等利用截?cái)嗉夹g(shù)，基于不完全正交的Arnoldi過程提出截?cái)嘈妥儏?shù)廣義極小殘余算法(VRP-IGMRES(m))[14]。本文利用截?cái)嗉夹g(shù)[15-16]，提出一種不完全正交的WIGMRES(m)算法，并結(jié)合數(shù)值算例，分析該算法的高效性。

1 WGMRES(m)算法

加權(quán)Arnoldi過程：

1)取v1=r0/‖r0‖D；

結(jié)合GMRES(m)算法和加權(quán)Arnoldi過程，WGMRES(m)算法計(jì)算步驟如下：

1)選取x0∈Rn，m∈N+(m

5)若‖rm‖=‖r0-Azm‖<ε，則x=xm，迭代停止，否則x0=xm，轉(zhuǎn)向步驟2)。

2 WIGMRES(m)算法

當(dāng)m很大時(shí)，考慮到在構(gòu)造krylov子空間的基向量和Hessenberg矩陣時(shí)要用到長遞推公式，導(dǎo)致算法計(jì)算量和存儲(chǔ)量過大，因此在WGMRES(m)算法的基礎(chǔ)上進(jìn)行改進(jìn)，提出一種新型截?cái)嘈退惴?，即WIGMRES(m)算法，該算法僅對(duì)Avj前面的至多q個(gè)向量進(jìn)行正交，vj0,…,vj，j0=max{1,j-q-1}正交，其中q

1)選取x0∈Rn，m∈N+(m

(1)

4)求解最小二乘問題

(2)

得ym，其中e1=(1,0,…,0)T∈Rm+1；

5)構(gòu)造近似解，xm=x0+Vmym；

6)計(jì)算殘余向量的模，‖rm‖=‖b-Axm‖；

7)重啟動(dòng)判斷，若‖rm‖<ε，則精確解x=xm，迭代停止；否則，置x0=xm，m=m+1，轉(zhuǎn)2)。

3 WIGMRES(m)算法的收斂性

為證明算法WIGMRES(m)的收斂性態(tài)，本文將WIGMRES(m)算法和WGMRES(m)算法聯(lián)系起來，證明WIGMRES(m)的收斂性，為方便討論，令WIGMRES(m)算法的殘余向量的模為rm(WIG),WGMRES(m)算法殘余向量的模為rm(WG)。

定理1假設(shè)Vm+1列滿秩，則WIGMRES(m)算法和WGMRES(m)算法在Km(r0,A)上的殘值范數(shù)滿足

‖rm(WIG)‖≤S(Vm+1)‖rm(WG)‖，

(3)

證畢。

4 數(shù)值算例

算例1考慮一維波動(dòng)方程

(4)

方程(4)的精確解為u(x,y)=sin(πx)e-π2y+sin(3πx)e-9π2y，如圖1(a)所示。將區(qū)域沿x方向和y方向n等分，其中采用隱式差分法求解方程(4)，可得方程組

u(x,y)=sin(πx)e-π2y+sin(3πx)e-9π2y。

取n=20,m=10,q0=9時(shí)，用WIGMRES(m)算法求解一維波動(dòng)方程，計(jì)算結(jié)果如圖1(b)所示。由圖1知，問題(4)的數(shù)值解和精確解是一致的，說明WIGMRES(m)算法的正確性。

取n=30,m=15考慮截?cái)嘀笜?biāo)q0在1～14內(nèi)取值，得到截?cái)嘀笜?biāo)對(duì)殘余范數(shù)和計(jì)算時(shí)間的圖像如圖2、3 所示，殘余范數(shù)隨著截?cái)嘀笜?biāo)的增大波動(dòng)后趨于平緩，計(jì)算時(shí)間隨著截?cái)嘀笜?biāo)的增大而緩慢增大，說明截?cái)嘀笜?biāo)越小,截?cái)嘈Ч矫黠@。

圖2 截?cái)嘀笜?biāo)對(duì)殘余范數(shù)的影響Figure 2 Effect of truncation index on residual norm

圖3 截?cái)嘀笜?biāo)對(duì)計(jì)算時(shí)間的影響Figure 3 The impact of truncation indicators on calculation time

算例2考慮二維泊松方程

(5)

其中：Ω={(x,y)|0

方程(5)的精確解為u(x,y)=sin πxsin πy，如圖4(a)所示。將區(qū)域沿x方向和y方向n等分，其中采用五點(diǎn)差分法求解方程(5)，可得方程組取n=100,m=10截?cái)嘀笜?biāo)q0=9時(shí)，用WIGMRES(m)求解二維泊松方程的數(shù)值解如圖4(b)所示，根據(jù)圖4可知，數(shù)值解與精確解一致，因此說明算法WIGMRES(m)的正確性。

圖4 溫度分布Figure 4 Temperature distribution

Ax=b,A∈R(n-1)2×(n-1)2,x,b∈R(n-1)2。

取n=50,q0=5時(shí)，且m在4～14內(nèi)取值，當(dāng)重啟動(dòng)參數(shù)取不同的值時(shí)，GMRES(m)算法、WGMRES(m)算法和WIGMRES(m)算法的數(shù)值結(jié)果如表1、2所示，當(dāng)參數(shù)m發(fā)生變化時(shí)，GMRES(m)算法的迭代次數(shù)最多，WGMRES(m)算法次之，WIGMRES(m)算法最少且WIGMRES(m)算法的計(jì)算精度最高，由此證明WIGMRES(m)算法在保證精度的情況下計(jì)算效率大大提高。

表1 m取不同值時(shí)三種算法的迭代次數(shù)比較Table 1 Comparison of the number of iterations of the three algorithms with different values of m

表2 m取不同的值時(shí)三種算法的計(jì)算精度比較Table 2 Comparison of the calculation accuracy of the three algorithms with different values of m

取n=40,q0=5，且m在6～18內(nèi)取值，執(zhí)行WIGMRES(m)和WGMRES(m)兩種算法，當(dāng)重啟動(dòng)參數(shù)m取不同值，得到兩種算法的迭代時(shí)間和迭代次數(shù)變化(圖5、6)。根據(jù)圖5、6可知，新算法WIGMRES(m)更加穩(wěn)定，且以較高的精度快速收斂。當(dāng)m=10時(shí)，不同網(wǎng)格下的兩種算法的計(jì)算時(shí)間如表3所示，表格顯示隨著n的不斷增大，相同網(wǎng)格下，WIGMRES(m)算法總比WGMRES(m)算法的計(jì)算時(shí)間少，由此說明，WIGMRES(m)算法的優(yōu)越性。

圖5 兩種算法迭代次數(shù)的比較Figure 5 Comparison of the number of iterations of the two algorithms

圖6 兩種算法迭代時(shí)間的比較Figure 6 Comparison of iteration time of two algorithms

表3 不同網(wǎng)格下兩種算法計(jì)算時(shí)間的比較(m=10)Table 3 Comparison of calculation time of two algorithms on different grids (m=10)單位：s

5 結(jié)論

本文在WGMRES(m)算法的基礎(chǔ)上，通過采用截?cái)嗉夹g(shù)，提出WIGMRES(m)新算法，并證明該算法的收斂性。通過數(shù)值算例證明WIGMRES(m)新算法得出的結(jié)果與精確解十分吻合，證明了該算法的有效性。同時(shí)當(dāng)參數(shù)m取不同值時(shí)三種算法的迭代次數(shù)和計(jì)算精度的變化情況，以及WIGMRES(m)和WGMRES(m)兩種算法對(duì)計(jì)算效率和計(jì)算精度的影響，結(jié)果表明新算法在計(jì)算效率和計(jì)算精度方面均有很大提高。