求解多右端對稱線性方程組的一種極小向后擾動塊方法

朱景福，李欣，郭東山

(廣東石油化工學院 理學院，廣東 茂名 525000)

本文研究多右端對稱線性方程組AX=B，其中A∈Rn×n為非奇異對稱矩陣；X,B∈Rn×s的數值求解方法。

多右端線性方程組在許多領域都有著重要的應用背景，如控制論、結構力學、電磁場等領域，都涉及多右端線性方程組的求解。多右端線性方程組的求解研究主要有精確解的研究和數值解的研究。在數值解法中常見的迭代法有種子投影方法[1,2]和塊迭代法。塊迭代法主要有塊CG方法(BCG)[3]、塊GMRES方法(BGMRES)[4]及其變形、塊QMR方法(BQMR)[5]、塊EN方法(BEN)[6]、塊Lanczos方法[7]等，這些塊方法都是建立在塊krylov方法[8](krylov子空間方法[9]的推廣)的基礎之上的。在利用krylov子空間方法求解線性方程組AX=b(即AX=B的右端項矩陣B只有1列)時，通常用殘量范數作為判斷算法終止的條件。若近似解的精確度比較高，則殘量范數較小，反之不一定。為了克服用殘量作為算法終止條件的不足，采用極小向后擾動范數代替殘量作為算法終止的條件，Kasenally[10]給出了求解大型非對稱線性方程組的廣義極小向后擾動方法。Cao[11]推廣了廣義極小向后擾動方法，給出了求解大型非對稱線性方程組的總體GMBACK方法。

本文研究多右端對稱線性方程組AX=B的右端項矩陣B的列數s>1時的求解方法。新方法在采用塊Lanczos方法的過程中結合極小向后擾動技術，討論AX=B的左端矩陣A的向后擾動形式和極小向后擾動范數的求法，將極小向后擾動范數作為迭代終止的判定條件，提出求解多右端對稱線性方程組的一種新算法，并對新算法做殘量分析，通過數值對比實驗驗證新方法的有效性。

1 預備知識

首先給出本文所用到的符號約定如下：本文涉及的矩陣A均為n階實對稱矩陣，λ1,λ2,…,λn為A的特征值，x1,x2,…,xn為相應的標準正交特征向量，并且λ1≥λ2≥…≥λn。En表示n階單位矩陣，在不產生混淆的情況下用E表示?！珹‖F、‖A‖2分別表示矩陣A的Frobenius范數和2-范數。xT和XT分別表示向量x和矩陣X的轉置。νec(A)表示矩陣A的列拉直(列展開)。A?B表示A與B的Kronecker積(直積，張量積)。A+表示矩陣A的Moore-Penrose廣義逆。

引理1 設A∈Cm×n，則‖A‖F=‖νec(A)‖2。

引理2設A∈Cm×n，B∈Cn×p，C∈Cp×q則νec(ABC)=(CT?A)νec(B)[12]。

引理4設A∈Cm×n，B∈Cp×q，C∈Cm×q，矩陣方程AXB=C有解的充要條件為AA+CB+B=C，在有解的情況下，AXB=C的通解為X=A+CB++Y-A+AYBB+

(1)

其中Y∈Cn×p是任意的；如果AXB=C無解，則AXB=C的最小二乘解仍為式(1)的形式，并且AXB=C的極小最小二乘解為X=A+CB+[12]。

選取方程組AX=B的初始矩陣X0，并由QR分解得到X0=Q1T1。

塊Lanczos方法(BLanczos方法)過程如下[7]：

可得

(2)

2 極小向后擾動塊方法

2.1 向后擾動分析

本文把方程組AX=B的近似解看作向后擾動方程組(A-Δ)X=B的精確解，其中Δ稱為AX=B的向后擾動。下面討論在用塊Lanczos方法解方程組AX=B時，考慮把極小化向后擾動范數作為算法終止的判定條件，以克服Lanczos過程產生的特征向量失去正交性的不足，構造求解式AX=B的新算法。

證明：設Xk為方程(A-Δ)X=B的解，則AXk-B=ΔXk所以-Rk=ΔXk

(3)

(4)

證畢。

2.2 極小向后擾動塊Lanczos方法(BMINBACK方法)

本文以極小向后擾動范數式(4)作為新算法迭代終止的判定條件，給出求解方程組AX=B的極小向后擾動塊Lanczos方法(BMINBACK方法)，算法過程如下：

3 數值實驗

本文的數值實驗均在主頻1.8 GHz的酷睿i7CPU、內存8 GB、Win10企業版操作系統的筆記本電腦上采用Matlab R2014a編程實現。

例1 已知對稱矩陣

圖1 BMINBACK算法殘量隨迭代次數的變化

由圖1可知，采用BMINBACK方法求解方程組AX=B計算的殘量達到小數點后5位，驗證了極小向后擾動塊方法是有效的。

例2 已知矩陣A、多右端項B和初始估計X0(同例1)，當n=100，k=8時，多右端項B的列數s變化時，BLanczos方法和BMINBACK方法的殘量結果見表1。

由表1可知，在求解方程組AX=B時，BMINBACK方法計算速度接近BLanczos方法的計算速度，BMINBACK方法的殘量略高于BLanczos方法的殘量，但BMINBACK方法的執行過程中，采用了極小向后擾動范數作為循環迭代的條件，克服了BLanczos方法采用殘量范數作為迭代條件而容易引起算法中斷的不足，進一步驗證了新方法是有效性的。

表1 BLanczos方法與BMINBACK方法殘量sBMINBACK方法CPU/s殘量范數BLanczos方法CPU/s殘量范數20.08761.81×10-50.01603.73×10-640.08832.35×10-70.00171.68×10-860.09559.45×10-50.00252.24×10-1080.13226.31×10-50.00271.69×10-7

4 結論

本文提出了求解多右端對稱線性方程組的新方法——極小向后擾動塊方法(BMINBACK方法)，并對新算法做了殘量分析。數值實驗結果表明，新算法求解方程組的殘量范數達到小數點后5位，在新算法的執行過程中，采用極小向后擾動范數作為循環迭代的條件，克服了BLanczos方法以殘量范數作為循環迭代條件而容易引起算法中斷的不足。而新方法的殘量不是特別小，在滿足一定精度的要求下，理論和數值實驗說明了新方法的有效性。