求解奇異線性系統(tǒng)的右預(yù)處理MINRES 方法

洪琳依

(溫州大學(xué)數(shù)理學(xué)院，浙江溫州 325035)

本文討論如下大型稀疏線性方程組的求解：

A∈Rn×n，x,b∈Rn，r= rank(A)＜n，其中A是對稱的，且b∈R(A)，我們稱之為相容線性系統(tǒng).

下面介紹一下本文使用的符號.R(.)表示對應(yīng)矩陣的值域，N(.)表示矩陣的零空間，rank(.)表示矩陣的秩，AT表示A的轉(zhuǎn)置，Im為m階的單位矩陣，R(A)⊥表示R(A) 的正交補，⊕表示直和，A+為滿足如下條件的Moore-Penrose 廣義逆[1]：

MINRES（Minimal Residual）是求解大型對稱線性系統(tǒng)的流行方法之一.最近，Sugihara 等人[2]采用右預(yù)處理MINRES 方法對奇異線性系統(tǒng)Ax=b進行了求解，其預(yù)處理子是非奇異的.眾知，構(gòu)造預(yù)處理子的一個基本原則是讓預(yù)處理子能夠逼近線性系統(tǒng)的系數(shù)矩陣，而奇異線性系統(tǒng)的系數(shù)矩陣是奇異的，所以選取奇異矩陣作為奇異線性系統(tǒng)的預(yù)處理子是合理的想法.本文主要關(guān)注奇異右預(yù)處理子的構(gòu)造并用其加速MINRES 算法.下面首先給出MINRES 的簡單介紹.

給定初始的x(0)∈Rn，記初始的殘差r(0)=b?Ax(0)，則MINRES 按如下方式搜索近似解x(k)：

1 右預(yù)處理的MINRES 算法

引理1[3]A的分裂：A=M?N，若R(A)=R(M)，N(A)=N(M)，則稱分裂A=M?N為恰當(dāng)分裂.

接下來將要討論的預(yù)處理子M皆滿足上述的恰當(dāng)分裂，且M為對稱正半定（SPSD）矩陣.對（1）經(jīng)過M右預(yù)處理后，系統(tǒng)可以轉(zhuǎn)化為求解以下方程組：

直接用MINRES 方法來求解（3）是不可行的，因為AM+不是對稱矩陣.因此考慮構(gòu)造一個新的半范數(shù).

因為所討論的A和M都是對稱的，所以有：

因此AM+在(,)M+下是自伴的，可以通過找到

來求解（3）.下面給出奇異右預(yù)處理MINRES 算法.

2 右預(yù)處理的MINRES 的收斂分析

引理2[4]若R(A)=R(M+)，則有：1）R((M+A)T) =R(AT)；2）R(M+A)=R(MT).

引理3[5]若A∈Rn×n，且是非奇異的，則用GMRES（Generalized Minimal Residual）算法求解Ax=b時，迭代至多在第n步收斂.

定理2 對于線性系統(tǒng)Ax=b，A∈Rn×n且對稱，m是矩陣A的秩，m＜n.若A=M?N是恰當(dāng)分裂，M是SPSD 矩陣，當(dāng)利用奇異右預(yù)處理MINRES 方法求解時，對于 ?b∈R(A)，?x(0)∈R(A)，迭代至多在第m步收斂.

易得A1是對稱的.由引理2 可得：

由文獻[5]可知，GMRES 與MINRES 的不同是，GMRES 是基于Arnoldi 過程，而MINRES是基于Lanczos 過程.而Lanczos 過程可以看成是當(dāng)矩陣是對稱時Arnoldi 過程的一種簡化.所以對于對稱的矩陣，GMRES和MINRES可以看成是等價的.所以根據(jù)引理3可以得到，利用MINRES求解，迭代至多在第m步收斂.

故對于 ?b∈R(A),?x(0)∈R(A)，利用奇異右預(yù)處理求解奇異線性系統(tǒng)時，迭代至多在第m步收斂.證畢.

下面給出算法2.

3 數(shù)值實驗

根據(jù)上面的理論分析，通過一些數(shù)值實驗來證明用奇異右預(yù)處理MINRES 迭代法求解奇異線性系統(tǒng)的有效性和可行性.考慮如下奇異鞍點問題：

“+”表示CPU＞10 000.

第一種，預(yù)處理子為I時，即不做預(yù)處理，記為PI.

第三種，預(yù)處理子是根據(jù)HSS（Hermite/ 反Hermite 分裂）[7]迭代法得到的預(yù)處理子，并取最優(yōu)參數(shù)，記為PHSS.

當(dāng)n=64 時，應(yīng)用4 種不同的預(yù)處理子，根據(jù)奇異右預(yù)處理MINRES 迭代算法求解算例1和算例2 得到的比較圖見圖1 和圖2.表1、表2 給出了不同預(yù)處理子下的右預(yù)處理MINRES 數(shù)值實驗得到的IT、CPU、RES 值.

表2 4 種不同預(yù)處理子下的右預(yù)處理MINRES 方法對算例2 的實驗結(jié)果

圖1 4 種不同預(yù)處理子下求解算例1 的結(jié)果（n=64）

圖2 4 種不同預(yù)處理子下求解算例2 的結(jié)果（n=64）

表1 4 種不同預(yù)處理子下的右預(yù)處理MINRES 方法對算例1 的實驗結(jié)果

由圖1、圖2 可以明顯看出，用預(yù)處理子為M的奇異右預(yù)處理MINRES 方法求解算例1 和算例2 時的收斂速度比用其他3 種預(yù)處理子的快.由表1、表2 也可得出同樣的結(jié)論.所以，無論從哪個角度比較，求解算例1 和算例2，采用以M為預(yù)處理子的奇異右預(yù)處理MINRES 方法都比采用其他3 種預(yù)處理子的更為有效.