丁伯倫，凌婷婷，耿紅梅

(1.揚州工業(yè)職業(yè)技術(shù)學(xué)院，江蘇 揚州 225000；2.安徽信息工程學(xué)院，安徽 蕪湖 241000)

0 引言

在科學(xué)技術(shù)與工程實踐中，如優(yōu)化控制理論、電路仿真、流體力學(xué)等領(lǐng)域，常常需要求解如下的大型稀疏線性方程組問題：

Ax=b

這里A∈Rn×n為稀疏的非奇異矩陣.

1 HGMRES算法和RRGMRES算法

GMRES算法首先是運用Arnoldi正交化過程在Krylov子空間上生成一組標(biāo)準(zhǔn)正交基v1，v2，…，vk，此時Krylov子空間可表示為：

κk(A，r0)=span{v1，v2，…，vk}=span{r0，Ar0，A2r0，…，Ak-1r0}

HGMRES是基于GMRES的一種優(yōu)化算法，在第一步中不選擇利用Arnoldi正交化過程，轉(zhuǎn)而選擇Householder變換來生成一組正交基.HGMRES算法滿足：

其中Vk=(v1，v2，…，vk)是Krylov子空間的一組標(biāo)準(zhǔn)正交基，而正交基里的元素是由(k+1)個Householder矩陣乘積得到，即：vj+1=P1P2…Pj+1ej+1.

這種方法避免采用Arnoldi正交化過程，轉(zhuǎn)而由Householder變換生成正交基，優(yōu)點是后續(xù)迭代數(shù)值穩(wěn)定性好，計算結(jié)果精確度高.

RRGMRES也是基于GMRES的一種改進(jìn)算法，前面仍利用Arnoldi正交化過程生成一組正交基，但在最后構(gòu)造殘量表達(dá)式上做出了改變：

需求解一個新的最小二乘問題即可.該算法的優(yōu)點是更能有效地減少存儲空間和運算量.所以本文將這兩種算法結(jié)合在一起，提出了一種新的算法，通過后面的數(shù)值實驗證實，這種新的算法在解的收斂性和精確度上均具有較好的效果.

2 基于Householder變換的RRGMRES算法

首先利用Householder變換生成一組標(biāo)準(zhǔn)正交基，這里的vk+1可表示為具有k+1列的k+1個Householder矩陣的乘積[4]，即：

齊海峰也從一個小工人，一步步混到了廠辦主任。官職升了，脾氣還是沒見長。妻管嚴(yán)就妻管嚴(yán)吧，半輩子不都吵過來了。

再進(jìn)行下一個過程：基于算法中第k步殘量表達(dá)式‖rk‖=‖r0-AVky‖，這里選擇對其變型，改變殘量表達(dá)式的形式[3].

這也是一個最小二乘問題，可求解得出y，進(jìn)而得出第k步近似解：xk=x0+Vky.最后根據(jù)殘量rk=b-Axk的結(jié)果來判定迭代算法是否終止[6].具體算法如下：

3)根據(jù)Householder變換遞推得到一組標(biāo)準(zhǔn)正交基Vk=(v1，v2，…，vk).

5)形成近似解xk=x0+Vkyk，得到殘量rk=b-Axk.

6)根據(jù)殘量rk設(shè)置的要求判定迭代是否終止.

3 數(shù)值實驗

下面列出一個大型稀疏矩陣，利用本文的算法求解，并使用Matlab軟件進(jìn)行數(shù)值模擬，通過觀察圖像來對比本文算法和RRGMRES算法的收斂效果.

例選取的矩陣A是一個1 024階的分塊方陣[7].

設(shè)置初始值x=(1，1，…，1)T，應(yīng)用Matlab模擬出本文算法與RRGMRES算法的迭代步數(shù)與殘量范數(shù)的關(guān)系圖.

圖1中實線表示本文算法，而虛線表示RRGMRES算法，橫坐標(biāo)表示迭代步數(shù)，縱坐標(biāo)表示相對殘量的對數(shù).當(dāng)殘量rk設(shè)置為1.092e-08時，本文算法在142步就達(dá)到要求，而RRGMRES算法則需要194步才能達(dá)到要求.可見本文算法的收斂速度要更快些.

圖1 兩種算法對比圖