周昱潔, 彭振赟, 尚邵陽
(桂林電子科技大學 數學與計算科學學院,廣西 桂林 541004)
矩陣方程的求解是數值代數領域的重要課題之一,在工程技術、控制理論和圖像處理等方面有極大的實用價值。矩陣方程
AX=B
(1)
是最簡單也是研究最多的矩陣方程類型,求解方法主要包括直接解法和迭代解法2大類。Bjerhammar[1]利用矩陣的廣義逆研究了該矩陣方程在一般矩陣集合中的求解問題,并給出了有解的充要條件和通解的表達式。Allwright[2]采用凸分析的方法對矩陣方程(1)在對稱半正定矩陣集合中的反問題進行了研究,給出了最小二乘解存在的條件,但未給出解的具體表達式。謝冬秀[3]通過引入新的內積并應用閉凸錐逼近理論得出了該矩陣方程存在半正定最小二乘解的充要條件以及通解的表達式。文獻[4-6]分別就中心對稱矩陣、廣義(反)對稱和廣義(反)自反矩陣、(反)對稱正交矩陣集合對該矩陣方程進行了研究。彭亞新[7]首次利用共軛梯度算法的思想,構造了共軛殘差算法求解矩陣方程(1)的一般解、(反)對稱解及中心對稱解等。郭孔華[8]通過構造正交投影迭代法,進一步研究了矩陣方程(1)的幾種對稱性解及其最佳逼近問題。在矩陣方程(1)有解的情況下,Ding等[9]參照Jacobi迭代法和Gauss-Seidel迭代法提出了一種更廣義的基于梯度的迭代算法,因收斂因子μ的存在保證了算法的收斂性,但由于該基于梯度的迭代算法只使用當前迭代近似解來決定新的迭代近似解,在求解大規模矩陣方程時可能出現收斂速度緩慢的情況。
鑒于此,提出一種求解矩陣方程(1)及其最小二乘問題的多步迭代算法,即通過前m+1個迭代近似解的特定線性組合[10-14]來估計下一步迭代近似解,并證明了算法的收斂性。數值結果表明,本算法相對于基于梯度的迭代算法具有更好的收斂效果。
基于梯度的迭代算法[9]:給定初始近似解X0,按照迭代格式
Xk+1=Xk+μAT(B-AXk)
(2)
計算矩陣方程(1)的第k+1步迭代近似解,其中:
λmax(ATA)為對稱矩陣ATA的最大特征值。
基于梯度的迭代算法是單步迭代算法,當矩陣A為列滿秩矩陣時,由該算法得到的矩陣序列{Xk}收斂到矩陣方程(1)的唯一解:
X*=(ATA)-1ATB=A+B。
基于梯度的迭代算法也是不動點迭代法[14],令
g(X)=(I-μATA)X+μATB,
則基于梯度的迭代算法的迭代格式(2)可改寫為
Xk+1=g(Xk)。
算法1令
f(X)=g(X)-X,
則求解矩陣方程(1)在Rn×n內的多步迭代算法為:
2)若‖f(Xk)‖F≤ε,則程序運行終止,此時,Xk即為矩陣方程(1)在Rn×n內的解;
3)令mk=min{m,k};
(3)
5)令
(4)
為了方便討論算法1的收斂性,給出如下引理。
引理1[15]若x*為線性方程組Ax=b的解,且x*∈R(AT),則x*是線性方程組Ax=b的最小Frobenius范數解。
引理2若X*為矩陣方程AX=B的解,且X*=ATH,H為任意矩陣,則X*為矩陣方程AX=B及其最小二乘問題的最小Frobenius范數解。
設m×n階矩陣A的奇異值分解為
(5)
其中:U=(U1,U2),U1∈Rr×m為m階正交矩陣;V=(V1,V2),V1∈Rr×n為n階正交矩陣;Σ=diag(δ1,δ2,…,δr)>0,r=rank(A),則X=ATH等價于X=VH。
引理3若X*為矩陣方程AX=B的解,且X*=VH,則X*為矩陣方程AX=B及其最小二乘問題的最小Frobenius范數解。
對于算法1,有如下收斂性定理。
證明由矩陣函數f(X)和g(X)的定義可知:
f(Xk+1)=μATB-μATAXk+1。
(6)
f(Xk+1)=μATB-μATAXk+1=μATB-μATA×
因此,
(7)
所以式(7)可轉化為
‖f(Xk+1)‖F≤‖I-μATA‖2·‖f(Xk)‖F。
‖f(Xk+1)‖F≤c‖f(Xk)‖F≤…≤ck+1‖f(X0)‖F。
因此,當k→∞時,有‖f(Xk)‖F→0,f(Xk)→0,由算法1產生的矩陣序列{Xk}收斂于與矩陣方程(1)等價的法方程ATAX=ATB在Rn×n內的解。若A為列滿秩矩陣,則算法1產生的矩陣序列{Xk}收斂于矩陣方程(1)在Rn×n內的唯一解A+B;若A為非列滿秩矩陣,且其奇異值分解為式(5),則由算法1產生的矩陣序列{Xk}收斂于矩陣方程ATAX=ATB在Rn×n內的一個解
如何加強圖書、音像、網絡教學、學術、創作展演等信息資源的整合,利用教學輔助條件,滿足人才培養目標;如何把教學平臺、實踐平臺和信息平臺等方面的條件有機的融合貫通,把“學校大課堂,傳媒大舞臺”的教學模式,融入到圖書館的工作中,就必須營造全方位的服務支撐節點,進一步深化圖書館服務,提升精準服務水平。
(8)
其中G為適當階數的任意矩陣。矩陣方程AX=B的最小二乘解同樣地可表示為式(8),則由算法1產生的矩陣序列{Xk}收斂于矩陣方程(1)在Rn×n內的一個最小二乘解。
定理2當選取初始矩陣X0=ATH,或直接令初始矩陣X0=0,則由算法1產生的矩陣序列{Xk}收斂于矩陣方程(1)的唯一的最小Frobenius范數最小二乘解X*=A+B。進一步地,若X*為矩陣方程(1)的解或其最小二乘問題的解,則有
(9)
其中,
c=‖I-μATA‖2<1。
若X*為矩陣方程(1)的解,則有ATAX*=ATB,因此有
f(Xk)=μATB-μATAXk=-μATA(Xk-X*)=
-[I-(I-μATA)](Xk-X*)。
因
‖f(Xk+1)‖F≤c‖f(Xk)‖F≤…≤ck+1‖f(X0)‖F,
其中c=‖I-μATA‖2<1,則有
(1-c)‖Xk-X*‖F≤‖f(Xk)‖F≤
c‖f(Xk-1)‖F≤…≤ck‖f(X0)‖F≤
ck(1+c)‖X0-X*‖F。
因此,有
定理3若矩陣方程AX=B有解,則由算法1產生的矩陣序列{Xk}收斂于矩陣方程(1)在Rn×n內的一個解,當選取初始矩陣為X0=ATH,或直接取X0=0時,由算法1產生的矩陣序列{Xk}收斂于矩陣方程(1)唯一的最小Frobenius范數最小二乘解為X*=A+B。若X*為矩陣方程(1)的解,則誤差估計式(9)成立。
矩陣方程(1)有解時,其解的表達式與其最小二乘解的表達式相同,則與定理1和定理2一樣可以證明關于算法1的收斂性定理3。
數值算例中矩陣A、B均由MATLAB軟件隨機產生,所有數據均在Window7 64-bit MATLAB R2013a環境下獲得。對于多步迭代算法1,實驗中初始矩陣X0選取為零矩陣,終止準則為‖f(Xk)‖F<10-6。
例1給定矩陣A∈R7×5和B∈R7×5:
A=
B=
由于矩陣A為列滿秩矩陣,矩陣方程AX=B有唯一精確解。應用基于梯度的迭代算法和多步迭代算法1均可得矩陣方程(1)在Rn×n內的唯一精確解:
X*=A+B=
表1 基于梯度的迭代算法在選取不同收斂因子μ的數值結果
表2 多步迭代算法1在選取不同收斂因子μ和正整數m的數值結果
由表1、表2可得如下結論:
2)對于多步迭代算法1,當m=2或m=3時,其數值結果受2個收斂因子μ和m的共同影響,難以選擇最佳收斂因子,當4≤m≤6時,其數值結果只受收斂因子m的影響,且m≥5時收斂效果最佳。
3)多步迭代算法的收斂性比基于梯度的迭代算法好,當2種算法的收斂因子μ取相同數值時,多步迭代算法有明顯的加速收斂效果。
表3 不同矩陣維數下基于梯度的迭代算法的數值結果
由表3、表4可得如下結論:
1)隨著矩陣A的規模增大,多步迭代算法的收斂性始終比基于梯度的迭代算法要好。對于同一矩陣方程,多步迭代算法有明顯的加速收斂效果。
2)對于大規模矩陣方程AX=B,固定收斂因子μ,當m≥6時,多步迭代算法1的收斂效果最佳。
3)由于多步迭代算法使用前m+1個迭代近似解的線性組合,隨著矩陣維數的增加,雖然加速效果依然明顯,但運行時間也相對增加。因此,收斂因子m的選擇并非越大越好,應根據矩陣方程的規模大小適當選取收斂因子μ和m,以達到最佳的收斂效果。
通過研究矩陣方程AX=B及其最小二乘問題,提出了一種使用前m+1個迭代近似解的線性組合來決定下一步迭代近似解的多步迭代算法。該算法能夠使新的迭代近似解更接近原問題的精確解,從而
表4 不同矩陣維數下算法1在選取不同參數因子m的數值結果
減少迭代次數,達到更快收斂到問題的精確解的目的。數值實驗驗證了算法的有效性,且比基于梯度的迭代算法具有更好的收斂效果。該算法應用到其他類型的矩陣方程時的收斂效果還有待進一步研究。