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

王帥麗

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

本文討論求解線性方程組：

本文用T A表示A的轉(zhuǎn)置，Ir為r階的單位矩陣，用R()A和N()A分別表示A的值域和A的零空間．

本文主要討論奇異線性系統(tǒng)的右預(yù)處理GMRES（The Generalized Minimal Residual）方法并做收斂性分析．眾知，矩陣乘法不滿足交換律，尤其是奇異矩陣乘法逆序律的復(fù)雜性，導(dǎo)致左、右預(yù)處理系統(tǒng)的系數(shù)矩陣其條件數(shù)有時候差異很大．從而，對某些問題，若做左預(yù)處理效果不理想時，可以考慮做右預(yù)處理[1-2]．

由Saad等[3]提出的GMRES方法是解決大型非對稱線性系統(tǒng)最流行的方法之一，用GMRES方法可以進行求解非奇異線性系統(tǒng)，也可以求解奇異線性系統(tǒng)[1,4]．

定義1[5]設(shè)B∈Rn×n，我們稱滿足r(Bi)=r(Bi+1)的最小非負整數(shù)i為B的指標，記作：

B的Drazin逆記為BD，并滿足：

定義2 對于任意矩陣A∈Rn×n，如果R(A)=R(AT)，那么稱A為值域?qū)ΨQ矩陣．

引理1[6]設(shè)A∈Rn×n，那么值域?qū)ΨQ矩陣的等價描述如下：1）R(A)=R(AT)，2）N(A)=N(AT)，3）A+A=AA+，4）A+=A#，其中A+是A的Moore-Penrose廣義逆，即A+滿足：A+AA+=A+，AA+A=A，(AA+)T=AA+，(A+A)T=A+A．

A#是A的群逆，即A#滿足：AA#A=A，A#AA#=A#，AA#=A#A．

如果A是值域?qū)ΨQ矩陣，則A的指標為1，即index(A)=1，且；但index(A)=1，則A不一定是值域?qū)ΨQ矩陣，如：

文[6]中Zhang對線性系統(tǒng)（1）的系數(shù)矩陣做了左預(yù)處理，而本文對線性系統(tǒng)（1）的系數(shù)矩陣做右預(yù)處理，使得預(yù)處理后的系數(shù)矩陣是值域?qū)ΨQ的．對于值域?qū)ΨQ的奇異線性系統(tǒng)，用GMRES方法進行求解時，具有良好的性能．因此，我們需要找出合適的預(yù)處理子使得經(jīng)過預(yù)處理后系統(tǒng)的系數(shù)矩陣是值域?qū)ΨQ的．除此之外，本文基于恰當分裂，討論了其收斂性．

1 奇異線性系統(tǒng)的右預(yù)處理子

基于線性方程組（1）的系數(shù)矩陣A的分裂所誘導(dǎo)的分裂迭代方法，稱為定常迭代法．對于系統(tǒng)（1）的系數(shù)矩陣，當A是非奇異矩陣時，基于A的分裂：A=M-N，假設(shè)M可逆，則其迭代格式為xk+1=M-1Nxk+M-1b，k=0,1,2,…，稱M為預(yù)處理子；當系數(shù)矩陣A是奇異矩陣時，A-1不存在，因此奇異矩陣M作為預(yù)處理子更合理．經(jīng)過右預(yù)處理后的矩陣使得預(yù)處理后的線性系統(tǒng)的系數(shù)矩陣是值域?qū)ΨQ的，且 index(A?)=1，然后用GMRES方法進行求解．

設(shè)用一個奇異矩陣M作為線性系統(tǒng)（1）的右預(yù)處理子，則通過它預(yù)處理后的系統(tǒng)為：

通過求解（3）來求解（1）．

定義3A的分裂：為恰當分裂．

注意：如果A和M是非奇異的，那么由A所誘導(dǎo)的分裂均為恰當分裂．

證明：先證明1）．

首先有

由N(A)=N(M)，則

由r(BM)≤r(B)，可得

再證2）．

首先有N(M+) ?N(AM+)，由1）可得

則

由N(M+)=N(MT)，可得N(AM+)=N(MT)．

證畢．

當原方程組的系數(shù)矩陣不是值域?qū)ΨQ的，那么經(jīng)過預(yù)處理后方程組的系數(shù)矩陣是否是值域?qū)ΨQ的呢？或者當原方程組的系數(shù)矩陣是值域?qū)ΨQ的，那么經(jīng)過預(yù)處理后方程組的系數(shù)矩陣是否依舊是值域?qū)ΨQ的呢？如下定理給出預(yù)處理系統(tǒng)的系數(shù)矩陣保持值域?qū)ΨQ的充要條件．

定理2 如果A是值域?qū)ΨQ矩陣，N(A)=N(M)，那么AM+是值域?qū)ΨQ矩陣，當且僅當M是值域?qū)ΨQ的．

證明：由定理1知，N((AM+)T)=N(AT)，N(AM+)=N(MT)．

由A是值域?qū)ΨQ矩陣，則N(A)=N(AT)．又由N(A)=N(M)，有N(M)=N(AT)．則N((AM+)T)=N(AM+)，當且僅當N(M)=N(MT)．

證畢．

進一步，由如下定理說明對任一系數(shù)矩陣A，經(jīng)恰當分裂后的預(yù)處理系統(tǒng)的系數(shù)矩陣均為值域?qū)ΨQ的．

定理3 如果A=M-N是恰當分裂，那么AM+是值域?qū)ΨQ的．

證明：由定理1知：N((AM+)T)=N(AT)，N(AM+)=N(MT)．由于A=M-N是恰當分裂，則R(A)=R(M)，N(A)=N(M)，N((AM+)T)=N(AM+)，即AM+是值域?qū)ΨQ矩陣．

證畢．

引理2[7]對于線性系統(tǒng)（1）應(yīng)用GMRES，初始迭代向量x(0)∈R(A)，如果A是值域?qū)ΨQ的，那么GMRES在終止時決定的解為：x*=A+b．

定理4A=M-N是一個恰當分裂，對預(yù)處理后的系統(tǒng)（3）應(yīng)用GMRES，初始迭代向量y(0)∈R(A)，那么GMRES在終止時決定的解為：x*=A+b．

由引理2知，若y(0)∈R(AM+)，則GMRES在終止時決定的解為：y*=(AM+)+b．

下證R(AM+)=R(A)，x*=M+y*=M+(AM+)+b=A+b．

再證(AM+)+=MA+．

由于A=M-N是恰當分裂，則R(A)=R(M)，N(A)=N(M)，R(AT)=R(MT)．

又由R(M+M)=R(MT)=R(M+)，則M+M是R(M+)上的正交投影．

同理，A+A是R(A+)上的正交投影．

遠程教育理念核心在于實現(xiàn)教學(xué)過程中教師與學(xué)生的時空分離，此理念在節(jié)省教育資源，促進教育公平發(fā)展的同時，也使得學(xué)習(xí)過程更具自主和靈活，滿足不同水平學(xué)生對教學(xué)內(nèi)容的充分理解，即契合“掌握學(xué)習(xí)”理論的一般原理。慕課、微課以及雨課堂等迅速成長，成為當下教育信息化的重要方式。但簡單地將傳統(tǒng)課堂數(shù)字化網(wǎng)絡(luò)化就能取得績效是不切實際的。實現(xiàn)在線教育優(yōu)勢,教師核心素養(yǎng)是保證教學(xué)質(zhì)量，實現(xiàn)信息化教育有效推進的重要因素。

證畢．

2 恰當分裂的特征

由上節(jié)內(nèi)容可知，對于任意一致的奇異線性系統(tǒng)，我們都可以基于恰當分裂的預(yù)處理GMRES方法得到廣義逆解A+b，即基于恰當分裂選擇預(yù)處理．在本節(jié)中，我們進一步討論恰當分裂的特征及其它刻畫，同時我們還討論了恰當分裂條件下預(yù)處理系統(tǒng)系數(shù)矩陣的譜性質(zhì)．

首先，R(A)=R(M)當且僅當存在一個非奇異矩陣P1使得M=AP1，N(A)=N(M)，當且僅當存在一個非奇異矩陣P2使得M=P2A．進一步，恰當分裂可由下述命題等價刻畫．

命題1A=M-N稱為A的恰當分裂，當且僅當存在非奇異矩陣P1,P2使得M=AP1=P2A．

線性系統(tǒng)（1）的系數(shù)矩陣A，A∈Rn×n，r=rank(A) ＜n，Berman等[8]通過下面A的分解來描述恰當分裂：

其中，A11是秩為r的非奇異矩陣，P和Q是置換矩陣．

引理3[8]A由（4）式給出，那么A=M-N是一個恰當分裂，當且僅當

其中，M11是秩為r的矩陣．

引理4[6]矩陣A由（6）式給出，那么A=M-N是恰當分裂，當且僅當

其中，R是一個秩為r的非奇異矩陣，且

引理5[9]矩陣A和矩陣M分別由（6）式和（7）式給出，那么

當線性系統(tǒng)（1）的系數(shù)矩陣非奇異時，假設(shè)M可逆，則A=M-N是恰當分裂，其迭代格式位：x(k+1)=M-1Nx(k)+M-1b，有如下經(jīng)典結(jié)論成立：

進一步，當M不可逆時，有如下定理對這一結(jié)論加以推廣．

定理5 矩陣A和矩陣M分別由（6）式和（7）式給出，A=M-N是恰當分裂，那么

證明：由A=M-N是恰當分裂，則N(A)=N(M)，N(AM+)=N(M+)，易證R(A+)=

令(λ,y)是AM+的特征對，則λ≠0，y≠0，故AM+y=λy≠0．

由N(AM+)=N(M+)，則M+y≠0，即

由于A+A是R(A+)上的正交投影，有

則

所以λ是的特征值，即λ是的特征值．

證畢．

3 結(jié) 論

通過GMRES方法求解奇異線性系統(tǒng)Ax=b，是目前解決大型稀疏線性系統(tǒng)最流行的方法之一．研究表明：A無論是不是值域?qū)ΨQ矩陣，當找到預(yù)處理子M使得A=M-N是一個恰當分裂，則預(yù)處理后的系統(tǒng)的系數(shù)矩陣是值域?qū)ΨQ的，那么GMRES將收斂到一個解；同時，x*=A+b是Ax=b在y(0)∈R(A)中的唯一解．在某種程度上，我們解決一個奇異的線性系統(tǒng)，就像解決一個局部的非奇異線性系統(tǒng)一樣，或者用局部的非奇異化來求解一個奇異的線性系統(tǒng)．對于求解奇異線性系統(tǒng)，在恰當分裂條件下，我們已經(jīng)推導(dǎo)出存在左預(yù)處理子使得R(M+A)=R((M+A)T)，存在右預(yù)處理子使得R(AM+)=R((AM+)T)．進一步，利用本文的理論結(jié)果，為尋求左、右全局預(yù)處理子P、Q使得提供了可能性，這也將是我們下一步的研究工作．