非線性矩陣方程雙對稱解的牛頓-MCG算法

(福建工程學(xué)院 應(yīng)用技術(shù)學(xué)院，福建 福州 350000)

雙對稱矩陣在信息理論、馬爾可夫過程、物理工程等領(lǐng)域中有廣泛應(yīng)用，很多學(xué)者研究了矩陣方程(組)的雙對稱解問題[1-9]。在控制理論、隨機(jī)濾波分析[10-12]等領(lǐng)域，會遇到形如求矩陣方程

X+E1X-1F1+E2X-2F2+E3X-3F3=G(1)

的特殊解問題，其中Ei,Fi,G,X∈Rn×n(i=1,2,3)。本文擬用牛頓-修正共軛梯度算法(牛頓-MCG算法)求解矩陣方程(1)的雙對稱解。

1 求解方程(1)雙對稱解的牛頓算法

定義1劃分n階單位矩陣I=(e1,e2,…,

en)，稱Sn=(en,en-1,…,e1)為n階次單位矩陣。若X∈Rn×n滿足SnXSn=X且XT=X，稱X為雙對稱矩陣，用BSRn×n表示雙對稱矩陣集合。

令X=X-1,則方程(1)可以改為

X-1+E1XF1+E2X2F2+E3X3F3=G

為了方便書寫，引入下列矩陣函數(shù)：

因?yàn)?/p>

E3(XYX+X2Y+YX2)F3-X-1YX-1

所以記

E3(XYX+X2Y+YX2)F3-X-1YX-1

E3(XY2+Y2X+YXY+Y3)F3

容易導(dǎo)出

ψ(X+Y)=ψ(X)+φX(Y)+γX(Y)

(2)

這里φX(Y)是ψ(X)在“點(diǎn)X”沿著“方向Y”的Frechet導(dǎo)數(shù)。

引理1[8]設(shè)X∈BSRn×n是方程(1)的近似解，則求方程(1)雙對稱解X可轉(zhuǎn)化為求校正值Y∈BSRn×n使得ψ(X+Y)=O，并可以線性化為求Y∈BSRn×n使得

φX(Y)=-ψ(X)

(3)

在引理1中，φX(Y)=-ψ(X)的解Y∈BSRn×n一般不是ψ(X+Y)=O的精確解，從而由X*=X+Y確定的X*∈BSRn×n也不是ψ(X)=O的精確解，但是可以看作一個近似解。借鑒牛頓算法的原理，建立求方程(1)雙對稱解的牛頓算法如下：

第1步：給定矩陣X(k)∈BSRn×n，置k∶=1。

第2步：若ψ(X(k))=O，計算停止；否則，求Y(k)∈BSRn×n，使得

φX(k)(Y(k))=-ψ(X(k))

第3步：計算X(k+1)=X(k)+Y(k)，置k∶=k+1，轉(zhuǎn)第2步。

文獻(xiàn)[13]中給出了關(guān)于牛頓迭代法求非線性矩陣方程的收斂性結(jié)論：假設(shè)X*是方程(3)的解，則由牛頓算法生成的矩陣序列{X(k)}收斂于X*。此外，牛頓算法的關(guān)鍵是求解線性矩陣方程(3)。但由于截斷誤差的存在，對牛頓法中的某個迭代步k，矩陣方程(3)可能沒有雙對稱解，此時可求它的最小二乘雙對稱解，這也是牛頓-MCG算法的一個特點(diǎn)。

2 求線性矩陣方程(3)雙對稱解的MCG算法

記

A1=E1,B1=F1,A2=E2X,B2=F2,A3=E2,B3=XF2，

A4=E3X,B4=XF3,A5=E3X2,B5=F3,A6=E3,B6=X2F3，

A7=-X-1,B7=X-1,F=-(X-1+E1XF1+E2X2F2+E3X3F3-G)

下面建立求方程(3)雙對稱解和最小二乘雙對稱解的MCG算法，考慮方程(3)的一般形式

(4)

其中Ai,Bi,Ci,Di,F∈Rn×n(i=1,2,…,7)。

問題Ⅰ當(dāng)方程(4)有雙對稱解時，求Y∈BSRn×n，使其滿足方程(4)。

問題Ⅱ當(dāng)方程(4)無雙對稱解時，求Y∈BSRn×n，使得

(5)

當(dāng)方程(4)有雙對稱解時，稱問題Ⅰ相容；否則稱問題Ⅰ不相容。

參考文獻(xiàn)[8]的算法原理，通過修改矩陣Qk的類型，在共軛梯度法的基礎(chǔ)上建立求解問題Ⅰ的MCG算法如下。引入記號：

算法1(求解問題I的MCG算法)

第1步：任意給定初始矩陣Y(k)∈BSRn×n，置k∶=1，計算

第2步：如果Rk=O，或者Rk≠O而Qk=O，則停止計算；否則計算

第3步：計算

βk+1Qk

第4步：置k∶=k+1，轉(zhuǎn)第2步。

顯然，算法1中的矩陣Y(k),Qk∈BSRn×n。下面給出算法1的基本性質(zhì)，證明算法1在有限步計算之后停止，具體證明過程參考文獻(xiàn)[14]。

性質(zhì)2設(shè)k≥2，對算法1中的矩陣Ri和Qj，有

定理1設(shè)問題Ⅰ有雙對稱解，任意給定初始矩陣Y(1)∈BSRn×n，算法Ⅰ可在有限步計算后求得問題Ⅰ的一組解。問題Ⅰ無雙對稱解的充要條件是存在正整數(shù)k，使得在算法1得到的Rk≠O而Qk=O。

定理2設(shè)問題Ⅰ有雙對稱解，選取初始矩陣Y(1)∈BSRn×n如下

(?H∈Rn×n)

則在有限步迭代計算后可得問題Ⅰ的唯一極小范數(shù)解。

3 求解問題Ⅱ的MCG算法

根據(jù)定理1，在算法1中，當(dāng)Rk≠O而Qk=O時，算法1中斷，表明線性方程(4)無雙對稱解，需要求解方程(4)最小二乘雙對稱解。下面把問題Ⅱ的求解轉(zhuǎn)化為求解等價正規(guī)方程雙對稱解問題。參照算法1，建立求方程(4)最小二乘雙對稱解的迭代算法。

引進(jìn)記號：

f(Y)=w(μ(Y))+[w(μ(YT))]T+

Sn(w(μ(SnYSn))+[w(μ(SnYTSn))]T)Sn

N=w(F)+[w(F)]T+Sn(w(F)+[w(F)]T)Sn

定理3問題Ⅱ的解等價于線性矩陣方程f(Y)=N的雙對稱解，而且此線性矩陣方程必有雙對稱解。

證 問題Ⅱ的求解等價于求Y∈BSRn×n，使得

(6)

下面證明求極小值問題(6)等價于求矩陣方程f(Y)=N雙對稱解。將矩陣方程組

(7)

參照算法1以及文獻(xiàn)[11]的算法原理，建立求矩陣方程f(Y)=N雙對稱解，即求解問題Ⅱ的MCG算法如下。

算法2(求解問題Ⅱ的MCG算法)

第1步：給定矩陣Y(k)∈BSRn×n，置k∶=1，計算

第2步：若Rk=O，則停止計算；否則計算

第3步：計算

第4步：置k∶=k+1，轉(zhuǎn)第2步。

易見，在算法2中矩陣Y(k),Qk∈BSRn×n，對于算法2有類似于算法1的收斂定理。

定理4給定初始矩陣Y(1)∈BSRn×n，算法2在有限步迭代計算后可得問題Ⅱ解，即矩陣方程(4)最小二乘雙對稱解。

4 數(shù)值算例

下面給出兩個算例，在例1中，通過改變矩陣的階數(shù)，說明文中建立的算法1和算法2是可行的，且具有很高的效率。在例2中，通過和文獻(xiàn)[15]的算法(簡稱Li算法)作比較，說明本文中建立的牛頓-MCG算法適用范圍更廣，且能求出此類矩陣雙對稱約束解。用t表示計算時間(s)、n代表矩陣的階數(shù)、k1代表算法1迭代次數(shù)、k12代表算法1中斷次數(shù)、k2代表算法2迭代次數(shù)、error代表實(shí)際誤差的范數(shù)。

采用如下計算步驟：

第1步：給定矩陣X(1)∈BSRn×n，置k∶=1。

第2步：若ψ(X(k))=O，計算停止；否則，采用算法1求矩陣方程(4)的雙對稱解；若方程(4)無雙對稱解，則采用算法2求Y(k)∈BSRn×n，使得

‖φX(k)(Y(k))+ψ(X(k))‖=min

第3步：計算X(k+1)=X(k)+Y(k)，置k∶=k+1，轉(zhuǎn)第2步。

例1 用本文建立的算法1和算法2求矩陣方程(1)的一組雙對稱解和最小二乘雙對稱解，取方程(1)系數(shù)矩陣均為n階方陣，系數(shù)矩陣、終止準(zhǔn)則如下：

E1=E2=F1=F2=I，E3=-2IT,F3=2I，G=I，X1=I，ε=10-9(終止準(zhǔn)則)，

選取初始矩陣Y1=O，按計算步驟求得矩陣方程(1)的雙對稱解，結(jié)果如表1(MATLAB軟件2014版-PIV3.0 GHz微機(jī))。

表1 方程(1)的雙對稱解計算結(jié)果

當(dāng)n=4時，可得矩陣方程(1)的雙對稱解為

例2 用本文算法1、算法2和文獻(xiàn)[15]的Li算法求方程(1)的特例X-A*X-3A=Q，取該特例方程系數(shù)矩陣、初始矩陣X1、終止準(zhǔn)則如下：

A=I，G=I，X1=I，ε=10-9(終止準(zhǔn)則)，

(1)選取初始矩陣Y1=O，按照算法1和Li算法求陣方程X-A*X-3A=Q的一組雙對稱解，結(jié)果如表2。

表2 算法1與Li算法比較結(jié)果

(2)當(dāng)矩陣G為元素全為1的n階方陣時，文獻(xiàn)[15]中的Li算法失效，因?yàn)榫仃嘒不正定，不滿足文獻(xiàn)[15]中算法條件。但本文中的牛頓-MCG算法有效，能求出方程(1)的雙對稱解，結(jié)果如表3。

從表1可以看出，算法1和算法2求解矩陣方程(1)是有效的，當(dāng)方程(1)有雙對稱解時，可以求出其雙對稱解。當(dāng)算法1中斷時，可以通過算法2計算方程(1)的最小二乘雙對稱解。從表2，3可以看出，與文獻(xiàn)[15]中的Li算法比較，本文建立的牛頓-MCG算法適應(yīng)范圍更廣，能求出矩陣方程(1)特例方程的雙對稱解。

表3 牛頓-MCG算法求方程(1)特例的雙對稱解計算結(jié)果

5 結(jié)論

本文建立基于牛頓算法和共軛梯度算法原理建立的單變量非線性矩陣方程(1)雙迭代算法，文中采用的MCG算法不同于通常的共軛梯度法，它不要求涉及的等價線性矩陣方程(3)的系數(shù)矩陣對稱正定、可逆或者列滿秩，因此總是可行的。本文建立的迭代算法僅要求方程(1)有雙對稱解，不要求方程(1)的雙對稱解唯一，也不要求由牛頓算法每一步迭代計算導(dǎo)出的矩陣方程有雙對稱解。將牛頓-MCG算法運(yùn)用于其他非線性矩陣方程，這是下一步的研究的重點(diǎn)。