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

陳世軍

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

0 引言

在控制理論、隨機(jī)濾波和超分辨率圖像恢復(fù)等領(lǐng)域，會遇到形如

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

(1)

的含有未知矩陣高次逆冪的非線性矩陣方程[1-4]，其中Ei，F(xiàn)i，G，X∈Rn×n(i=1,2,3).文獻(xiàn)[5-8]研究了牛頓算法在求解線性方程和非線性方程中的應(yīng)用.程可欣等[8]研究了方程(1)的特例X-ATX-1A=Q的牛頓迭代解法，證明了牛頓迭代方法產(chǎn)生的矩陣序列包含在確定的閉球內(nèi)，且該矩陣序列收斂到閉球內(nèi)唯一的矩陣方程的解.張肖肖等[9]給出了方程(1)對稱解的雙迭代算法，其先用牛頓算法求出等價的線性矩陣方程的對稱解，然后再采用修正共軛梯度算法(MCG算法)求出由牛頓算法每一步迭代計算導(dǎo)出的線性方程的對稱解或?qū)ΨQ最小二乘解.目前，對于方程(1)的中心對稱解的研究還未見報道.為此，本文基于文獻(xiàn)[9]的算法原理，將牛頓-MCG算法推廣到求解方程(1)的中心對稱解上.

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

定義1劃分n階單位矩陣I=(e1,e2,…,en)， 稱Sn=(en,en-1,…,e1)為n階次單位矩陣.若X∈Rn×n滿足SnXSn=X， 稱X為中心對稱矩陣，用CSRn×n表示中心對稱矩陣集合.

基于文獻(xiàn)[9]的算法原理，建立求非線性矩陣方程(1)中心對稱解的牛頓-MCG算法.令X=X-1，則方程(1)可以改寫為

X-1+E1XF1+E2X2F2+E3X3F3=G.

(2)

首先用牛頓算法求方程(2)的中心對稱解，然后采用MCG算法求由牛頓算法每一步迭代計算導(dǎo)出的線性矩陣方程的中心對稱解或中心對稱最小二乘解，以此建立求方程(2)中心對稱解的牛頓-MCG算法.

根據(jù)定義2可知，當(dāng)-X-1Y的譜半徑小于1時，有

引入下列矩陣函數(shù)：

又因為

ψ(X+Y)=(X+Y)-1+E1(X+Y)F1+E2(X+Y)2F2+E3(X+Y)3F3-G=

E2YXF2+E3X3F3+E3X2YF3+E3XYXF3+E3XY2F3+E3YX2F3+E3YXYF3+

E3Y2XF3+E3Y3F3-G，

容易導(dǎo)出ψ(X+Y)=ψ(X)+φX(Y)+γX(Y).這里φX(Y)是ψ(X)在“點X”沿著“方向Y”的Frechet導(dǎo)數(shù).

引理1[9]設(shè)X∈CSRn×n是方程(1)的近似解，則求方程(1)的解X等價于求校正值Y∈CSRn×n使得ψ(X+Y)=O， 并可以線性化為求Y∈CSRn×n, 使得

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

(3)

參考文獻(xiàn)[9]的算法原理,通過修改某些矩陣的類型，建立求方程(1)中心對稱解的牛頓算法，該算法的具體步驟如下：

第1步 給定初始矩陣X(1)∈CSRn×n， 置k∶=1.

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

對于牛頓算法有如下的收斂性結(jié)論：假設(shè)X*是方程(1)的單根，且初始矩陣X(1)充分接近X*，那么牛頓算法確定的矩陣序列{X(k)}二次收斂于X*.

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(xiàn)=-(X-1+E1XF1+E2X2F2+E3X3F3-G).考慮方程(3)的一般形式：

(4)

其中Ai,Bi,Ci,Di,F∈Rn×n(i=1,2,…,7).本文解決下面兩個問題：

問題Ⅰ 設(shè)方程(4)有中心對稱解，求Y∈CSRn×n， 使Y滿足方程(4).

問題Ⅱ 設(shè)方程(4)無中心對稱解，求Y∈CSRn×n， 使

(5)

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

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

由以上步驟易見，算法1中的矩陣Y(k),Qk∈CSRn×n.下面給出算法1的基本性質(zhì)，算法1在有限步計算之后停止,具體證明可參考文獻(xiàn)[11].

引理2對任意的A∈Rn×n，Y∈CSRn×n均有tr((A+SnASn)TY)=2tr(ATY).

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

定理2設(shè)問題Ⅰ相容，選取初始矩陣Y(1)∈CSRn×n滿足

則算法1可在有限步計算后得到問題Ⅰ的唯一極小范數(shù)解，即方程(4)的唯一極小范數(shù)解.

3 求解問題Ⅱ的MCG算法

根據(jù)定理1，在算法1中當(dāng)Rk≠O而Qk=O時，算法1中斷.這表明線性方程(4)沒有中心對稱解,因此需要求解問題Ⅱ，即求線性方程(4)的中心對稱最小二乘解.下面通過構(gòu)造等價的線性矩陣方程組，將求矩陣方程(4)中心對稱最小二乘解問題轉(zhuǎn)化為求等價的正規(guī)方程中心對稱解問題；然后參照算法1，建立求矩陣方程(4)中心對稱最小二乘解的迭代算法.

定理3求解問題Ⅱ等價于求線性矩陣方程

f(Y)=N

(6)

的中心對稱解，并且方程(6)一定有中心對稱解.

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

(7)

參照算法1以及MCG算法的基本原理，建立求矩陣方程(6)中心對稱解的算法，即求解問題Ⅱ的MCG算法.求解問題Ⅱ的MCG算法(算法2)的具體步驟如下：

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

由以上步驟易見，算法2中的矩陣Y(k),Qk∈CSRn×n.對于算法2有類似于算法1的收斂定理.

定理4對任意的初始矩陣Y(1)∈CSRn×n， 算法2可在有限步計算后求得問題Ⅱ的一組解，即矩陣方程(6)的中心對稱最小二乘解.若取初始矩陣Y(1)滿足Y(1)=f(H) (?H∈CSRn×n)， 則算法2可在有限步計算后得到矩陣方程(6)的唯一極小范數(shù)中心對稱解.

4 數(shù)值算例

用上述建立的算法1和算法2求矩陣方程(1)的一組中心對稱解和中心對稱最小二乘解.取方程(1)的系數(shù)矩陣均為塊對角矩陣，且均為5n階方陣.系數(shù)矩陣、初始矩陣和終止準(zhǔn)則如下：

A為三對角矩陣，其中ai,i=3，ai,i -1=2,ai -1,i=2 (i=1,2,…,5n), 其余元素均為0;

E1=-AT，F(xiàn)1=A，E2=O，F(xiàn)2=O，E3=O，

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

選取初始矩陣Y1=2I， 按照算法1和算法2可求得矩陣方程(1)的一組中心對稱解，結(jié)果見表1.表1中， 5n為系數(shù)矩陣的階數(shù)，t為計算時間，k1為算法1的迭代次數(shù)，k12為算法1的中斷次數(shù)，k2為算法2的迭代次數(shù)，error為實際誤差的范數(shù).

表1 矩陣方程(1)的計算結(jié)果

從表1可以看出，運(yùn)用算法1和算法2求解方程(1)是有效的.當(dāng)算法1中斷時，可以通過算法2計算方程(1)的中心對稱矩陣最小二乘解.若修改算法1中矩陣Qk的類型，則可以建立求其他特殊矩陣解的迭代算法.