矩陣方程AXB+CXD=F的最小二乘解的多步迭代算法

王 杰， 彭振赟， 李 濤

(桂林電子科技大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,廣西 桂林 541004)

約束矩陣方程

AXB+CXD=F

(1)

是數(shù)值代數(shù)中研究比較多的一類(lèi)矩陣方程,在自動(dòng)控制理論、金融理論、信息論和振動(dòng)理論等領(lǐng)域具有重要的應(yīng)用。對(duì)矩陣方程(1)應(yīng)用直接法求解時(shí)，通常要求矩陣A、B、C及D能夠同時(shí)相似于某種標(biāo)準(zhǔn)形；將矩陣方程(1)轉(zhuǎn)化為線(xiàn)性方程組迭代求解時(shí)，迭代矩陣的階數(shù)為原矩陣階數(shù)的平方，除了計(jì)算量較大之外，其收斂性問(wèn)題也較復(fù)雜。因此，求解矩陣方程(1)的主要方法是迭代算法。李海合等[1]和張凱院等[2]通過(guò)引入?yún)?shù)提出了一種求解矩陣方程(1)的不動(dòng)點(diǎn)迭代算法。Ding等[3]基于求解線(xiàn)性方程組的雅可比迭代算法和高斯-塞德?tīng)柕惴ㄋ枷胩岢隽艘环N求解矩陣方程(1)的不動(dòng)點(diǎn)迭代算法。當(dāng)未知矩陣X具有結(jié)構(gòu)約束條件時(shí)，求解矩陣方程(1)的方法主要是共軛梯度算法，如劉大瑾等[4]討論了中心對(duì)稱(chēng)解及其最佳逼近解的求解，周海林[5]討論了廣義雙對(duì)稱(chēng)解的求解，尚麗娜等[6]討論了中心對(duì)稱(chēng)最小二乘解，孫合明等[7]討論了自反和反自反解及其最佳逼近解的求解，Liu[8]討論了廣義中心對(duì)稱(chēng)解及其最優(yōu)逼近解的求解，Yuan等[9]討論了最小二乘Hermitian解及其最小二乘Hermitian解的求解，閆熙等[10]討論了唯一解的參數(shù)迭代方法，并給出了最優(yōu)參數(shù)的確定方法。鑒于此，討論矩陣方程(1)及其最小二乘解的求解問(wèn)題，即考慮如下2個(gè)問(wèn)題：

問(wèn)題1給定矩陣A、C∈Rm×n,B、D∈Rn×p和F∈Rm×p，求X∈Rn×n，使得

其中：‖A‖F(xiàn)為矩陣A的Frobenius范數(shù)；SE為問(wèn)題1的解集合。

提出了一種求解問(wèn)題1的多步迭代算法，證明了由多步迭代算法產(chǎn)生的矩陣序列收斂于問(wèn)題1矩陣方程的最小Frobenius范數(shù)解，通過(guò)修改系數(shù)矩陣F，證明了由多步迭代算法產(chǎn)生的矩陣序列收斂于問(wèn)題2的解，同時(shí)給出了提出的多步迭代算法與不動(dòng)點(diǎn)算法和共軛梯度算法的數(shù)值比較。

1 求解問(wèn)題1和問(wèn)題2的多步迭代算法

顯然，問(wèn)題1的法方程為

AT(AXB+CXD)BT+CT(AXB+CXD)DT=

ATFBT+CTFDT,

(2)

因此，求解問(wèn)題1等價(jià)于求解矩陣方程(2)，且矩陣方程(2)一定有解。利用共軛梯度算法求解矩陣方程(2)時(shí)，其完整的迭代格式如下：

算法1共軛梯度算法求解問(wèn)題1

1) 輸入A、B、C、D、F，初始矩陣X0∈Rn×n，令k=0;

2) 計(jì)算

R0=AT(F-AX0B-CX0D)BT+

CT(F-AX0B-CX0D)DT,

P0=AT(AR0B+CR0D)BT+

CT(AR0B+CR0D)DT;

3) 若‖Rk‖F(xiàn)<ε,則停止，否則，k=k+1；

4) 計(jì)算

5) 返回步驟3)。

算法2不動(dòng)點(diǎn)迭代算法求解問(wèn)題1

1) 輸入A、B、C、D、F，初始矩陣X0∈Rn×n，誤差精度ε>0，令k=0；

2) 計(jì)算

Xk+1=Xk-μ[AT(AXkB+CXkD-F)BT+

CT(AXkB+CXkD-F)DT],

Rk+1=AT(AXk+1B+CXk+1D-F)BT+

CT(AXk+1B+CXk+1D-F)DT,

其中,

0<μ<

λmax(A)為矩陣A的最大特征值;

3) 若‖Rk+1‖F(xiàn)<ε，則停止，否則，令k=k+1，轉(zhuǎn)步驟2)。

令

(3)

算法3求解問(wèn)題1的多步迭代算法

1) 輸入矩陣A、B、C、D、F，整數(shù)m>0，誤差精度ε>0，取初始矩陣X0∈Rn×n；

2) 計(jì)算f(X0)=g(X0)-X0，令k=0；

3) 若‖f(Xk)‖F(xiàn)<ε，則停止，此時(shí)Xk為問(wèn)題1的解；

4) 令mk=min(m,k)；

5) 計(jì)算γk=(γ1,γ2,…,γmk-1)T∈Rmk-1，使

(4)

其中，‖x‖2為向量x的2-范數(shù)；

6) 令

(5)

7) 令k=k+1，轉(zhuǎn)步驟3)。

為了證明多步迭代算法3的收斂性，先證明如下引理。

引理1若y0為線(xiàn)性方程My=b及其最小二乘問(wèn)題的解，且y0∈R(MT)，則y0為線(xiàn)性方程組My=b及其最小二乘問(wèn)題的最小Frobenius范數(shù)解。

證明將M奇異值分解為

則U=(U1,U2)和V=(V1,V2)為正交矩陣，那么矩陣A的Moore-Penrose廣義逆為

矩陣方程AXB+CXD=F等價(jià)于線(xiàn)性方程組(BT?A+DT?C)vec(X)=vec(F)，其中，A?B表示矩陣A和B的Kronecker積，vec(A)表示矩陣A的拉直算子，由引理1易證引理2成立。

引理2若X矩陣方程AXB+CXD=F的解，且vec(X)∈R(B?AT+D?CT)，則X是矩陣方程AXB+CXD=F及其最小二乘問(wèn)題的最小Frobenius范數(shù)解。

定理1對(duì)任意初始矩陣X0∈Rn×n，由算法3所產(chǎn)生的矩陣序列{Xk}收斂于問(wèn)題1的解。進(jìn)一步地，若任意初始矩陣X0=ATHBT+CTHDT，H∈Rm×p為任意矩陣，則由算法3所產(chǎn)生的矩陣序列{Xk}收斂于問(wèn)題1的最小Frobenius范數(shù)解。

證明由式(3)和(5)可知，

f(Xk+1)=g(Xk+1)-Xk+1=-μ[AT(AXk+1B+

CXk+1D-F)BT+CT(AXk+1B+CXk+1D-F)DT]=

μ(BBT?ATA+CCT?DTD){f(Xk)-

因而，有

vec[f(Xk+1)]=[I-μ(BBT?ATA+CCT?DTD)]

進(jìn)而有

‖f(Xk+1)‖F(xiàn)≤‖I-μ(BBT?ATA+CCT?DTD)‖2·

其中，‖A‖2為矩陣A的譜范數(shù)。γk=(γ1,γ2,…,γmk)∈Rmk-1為最小二乘問(wèn)題(4)的解, 因而有

‖f(Xk)‖F(xiàn),

由于

0<μ<

則有

c=‖I-μ(BBT?ATA+CCT?DTD)‖2<1，

因此，有

‖f(Xk+1)‖F(xiàn)≤c‖f(Xk)‖F(xiàn)≤…≤ck+1‖f(X0)‖F(xiàn)，

故可得

‖f(Xk+1)‖F(xiàn)→0,k→∞。

因此，算法3所產(chǎn)生的矩陣序列{Xk}收斂于問(wèn)題Ⅰ的解。

進(jìn)一步地，若X0=ATHBT+CTHDT，H∈Rm×p為任意矩陣，則有vec(X0)∈R(B?AT+D?CT)。由算法3可知，對(duì)于任意的k都有vec(Xk)∈R(B?AT+D?CT)，因此，由引理2可知，算法3所產(chǎn)生的矩陣序列{Xk}收斂于問(wèn)題1的最小Frobenius范數(shù)解。

證明顯然，式(2)等價(jià)于矩陣方程：

(6)

命題成立。

2 數(shù)值實(shí)驗(yàn)

所有數(shù)據(jù)均通過(guò)MATLAB R2016a，Windows 7 64 bit Intel?CoreTMi5-6500處理器、3.20 GHz的PC獲得。算法1～3中的誤差精度均固定為ε=10-7，初始矩陣選取適當(dāng)階數(shù)的零矩陣，算法2、3中的參數(shù)μ選取

多步迭代算法3中m=10，共軛梯度算法、不動(dòng)點(diǎn)迭代算法和多步迭代算法的最大迭代次數(shù)限制為Imax=50 000。已知矩陣A、B、C、D、F和X0以MATLAB格式給出：

A=randn(m,n),B=randn(n,p),

C=randn(m,n),D=randn(n,p),

F=randn(m,p),X0=randn(n,n),

則得到共軛梯度算法、不動(dòng)點(diǎn)迭代算法和多步迭代算法的10次試驗(yàn)的平均值如表1所示，其中IT為算法迭代次數(shù)，CPU為算法求解所用的時(shí)間。

表1 共軛梯度算法、不動(dòng)點(diǎn)迭代算法和多步迭代算法的數(shù)值比較

由表1數(shù)據(jù)及其他實(shí)驗(yàn)數(shù)據(jù)可得以下結(jié)論：

1)當(dāng)初始矩陣A、B、C、D、F為方陣，即m=n時(shí),共軛梯度算法和多步迭代算法的收斂效果明顯優(yōu)于不動(dòng)點(diǎn)迭代算法。

2)當(dāng)初始矩陣為長(zhǎng)方形矩陣,即m≠n≠p，多步迭代算法有較為明顯的優(yōu)勢(shì)，相比共軛梯度算法和不動(dòng)點(diǎn)迭代算法，不僅迭代次數(shù)大大減少，收斂速度也大幅加快?？偟膩?lái)說(shuō)，多步迭代算法通過(guò)加速，明顯優(yōu)于共軛梯度算法和不動(dòng)點(diǎn)迭代算法。

3 結(jié)束語(yǔ)

通過(guò)對(duì)矩陣方程AXB+CXD=F及其最小二乘問(wèn)題的研究，提出了一種多步迭代算法，用以求解矩陣方程的最小二乘解，此算法通過(guò)前mk步的線(xiàn)性組合求解下一步的解，不僅得到的結(jié)果更加精確，而且極大地減少了迭代次數(shù)，加快了收斂速度。該算法應(yīng)用到其他類(lèi)型矩陣方程的收斂效果，以及如何選取最優(yōu)收斂因子μ和向量數(shù)mk使多步迭代算法達(dá)到最好的收斂效果，還有待進(jìn)一步研究。