半張量積下矩陣方程組AX=B,XC=D的最小二乘解

李 濤,周學林,李姣芬

(1.桂林電子科技大學數(shù)學與計算科學學院廣西高校數(shù)據(jù)分析與計算重點實驗室,廣西桂林 541004)

(2.桂林電子科技大學教務處,廣西桂林 541004)

1 引言

本文中所用記號Rm×n表示所有實數(shù)域上m×n階矩陣的集合;Ik為k階單位矩陣.對M ∈Rm×n,MT和M?分別表示轉置和Moore-Penrose廣義逆.對矩陣M,N ∈Rm×n,內(nèi)積定義為〈M,N〉=trace(MTN),由此導出的矩陣范數(shù)為Frobenius范數(shù),記為‖·‖.lcm{m,n}和gcd{m,n}分別表示正整數(shù)m,n的最小公倍數(shù)和最大公約數(shù).對M=[aij],N=[bij]∈Rm×n,M?N 表示矩陣M 和N 的Kronecker積[1]

M⊙N表示矩陣M與N的Hadamard積[1]

對M=[aij]∈Rm×n,矩陣的列拉直算子Vc(·)和行拉直算子Vr(·)分別表示為

定義1[2]給定矩陣A∈Rm×n,B∈Rh×k,記t=lcm{n,h}為n,h的最小公倍數(shù),矩陣A和B的半張量積可表示為

半張量積最初由程代展教授提出用以解決多線性函數(shù)的矩陣表示問題[3],隨后不僅應用在高維數(shù)據(jù)的排列以及電力系統(tǒng)非線性魯棒穩(wěn)定控制代數(shù)化等問題[4],而且為布爾網(wǎng)絡[5],密碼學[6],圖染色[7],模糊控制[8]等領域中的問題研究提供了一種新的研究工具.而這些問題的解決在某些情況下可歸結為半張量積下線性方程或矩陣方程的求解問題.如在網(wǎng)絡非合作化問題中[9],設有m個玩家,記M={1,2,···,m},玩家j的策略集是N={1,···,nj},j=1,2,···,m.現(xiàn)假定玩家 j 的混合策略是

則所求的Nash 均衡點即等價于求解下列半張量積下的矩陣方程

其中Φ已知.對于此類問題,姚娟等[10]將其歸結為半張量積下矩陣方程AX=B求解問題,并細致研究了半張量積下方程該有解的充要條件及具體解析表達式,同時在其博士論文中討論了半張量積下矩陣方程AX=B的最小二乘解.在實際應用中,如布爾網(wǎng)絡,模糊控制及網(wǎng)絡非合作化問題中,我們往往會遇見更加復雜的問題,利用半張量積工具,這類問題可歸結為如下半張量積下的矩陣方程組

方程(1.1)中的系數(shù)矩陣均來自于實測數(shù)據(jù),由于測量誤差的影響,得到的數(shù)據(jù)總是不精確的.又由于舍入誤差的影響,方程(1.1)不一定滿足類似于文[10]給出的較復雜的相容條件,因此有必要討論如下半張量積下矩陣方程組的最小二乘問題.

問題1給定矩陣A∈Rm×n,B ∈Rh×k,C ∈Ra×b和D∈Rl×d,求X?∈Rp×q滿足

對于矩陣方程(組)的求解及其最小二乘解問題,因其在生物學,工程力學,參數(shù)識別,振動理論的逆問題以及線性規(guī)劃等廣泛的應用,故已被廣泛研究.眾多學者利用矩陣分塊,廣義逆,矩陣分解等多種技巧方法將方程或方程組降維,進而給出解存在的充要條件及其具體解析表達式,或進一步討論及最小二乘解及極小范數(shù)最小二乘解.如對一般矩陣方程組

Mitra[11]基于廣義逆給出了極小秩最小二乘解;李[12–14]分別探究了方程(1.3)的自反解,廣義自反解,鏡像對稱最小二乘解,κ-厄爾米特最小二乘解;裘[15]則利用Kronecker積將其化成相應方程組,再利用廣義逆給出解的拉直形式;袁[16]利用矩陣的譜分解給出了最小二乘解和對稱最小二乘解的顯示表達式.普通矩陣乘積下矩陣方程組(1.3)的求解及其最小二乘解已得到充分研究,但半張量積下矩陣方程組(1.1)未見有研究成果,因此將半張量積概念推廣到矩陣方程組的研究工作也是有意義的.類似于文[10]處理半張量下矩陣方程AX=B的研究思路,首先將半張量積下的矩陣方程組轉化為普通乘積下的矩陣方程組,進而結合矩陣分塊、矩陣廣義逆及其矩陣分解技巧給出最小二乘解的具體解析表達式.同樣首先考慮矩陣-向量方程,即(1.1)式中X 為向量的情形,研究其最小二乘解的具體解析表達式;進而探究一般形式矩陣-矩陣方程,即(1.1)式中X為矩陣的情形,研究其最小二乘解的具體解析表達式.

本文推導過程中用到如下矩陣微分的基礎知識

2 矩陣-向量方程(1.1)的最小二乘解

本節(jié)考慮矩陣-向量型的最小二乘問解,即給定矩陣A∈Rm×n,B∈Rh×k,C∈Ra×b,和D∈Rl×d,求向量X?∈Rp滿足

由半張量積定義知,在方程(1.1)中矩陣A與B的行數(shù),矩陣X與D的行數(shù)均存在倍數(shù)關系.故可分m=h,p=l;m=h,pl;mh,p=l和mh,pl四種情形來考慮問題.經(jīng)驗證m=h,p=l和m=h,pl情況下X?的解析表達式相同,同樣mh,p=l和mh,pl情形下結果類似,故只需從m=h和mh這兩種情形下展開討論.我們的研究思路是,首先利用半張量積的定義將問題轉化為普通乘積下的最小二乘問題,再結合矩陣的微分和廣義逆給出最小二乘解X?的具體解析表達式.

2.1 簡單形式m=h

由半張量積定義,可得問題(2.1)在m=h情形下有解的必要條件.

引理1若X是問題(2.1)的解,則矩陣A,B,C,D的維數(shù)需滿足

i)和必為正整數(shù).

ii)b=d并且

證對于

有其中t=lcm{n,p}.由m=h得t=n,進而有必為正整數(shù).對于

有

因此t1=a,并且

從而必為正整數(shù).此外引理得證.

稱引理1中的條件為維數(shù)相容條件,并假定問題(2.1)滿足相容條件.將(2.1)式轉化為

其中t1=lcm{n,p},t2=lcm{1,a}.記(2.2)式的目標函數(shù)為F(X).此時有

其中As表示矩陣 A 的第 s列,Br表示矩陣B 的第r列,r=1,···,k;s=1,···,n.由一階微分必要條件知F(X?)達到極小須對函數(shù)F(X)求導,可得

結合廣義逆,可得如下結論.

定理1給定矩陣A∈Rm×n,B ∈Rh×k,C ∈Ra×b和D ∈Rl×d,則問題(2.1)在m=h情形下的唯一最小二乘解X?可表示為

例1令

則由引理1有故X?∈R3,再由定理1可得

故唯一最小二乘解X?=[0.0332,0.2373,0.2391]T.

2.2 一般情形mh

由半張量積定義,可得mh時問題(2.1)的維數(shù)相容條件.

引理2若X是問題(2.1)的解,則矩陣A,B,C,D的維數(shù)須滿足

i)必為正整數(shù)

證由半張量積的定義有

其中的公約數(shù).此外,

故可知與k互素.若則這顯然與條件矛盾.證明完畢.

假定問題(2.1)滿足相容條件.由半張量定義,問題(2.1)可轉化為

記此時問題(2.4)可轉化為m=h情形來討論,利用上一小節(jié)的結論可得

定理2給定矩陣A∈Rm×n,B ∈Rh×k,C ∈Ra×b和D ∈Rl×d,則方程(2.1)在mh情形下的最小二乘解X?的解析表達式為

其中

表示矩陣的第s列,Br表示矩陣B 的第r列,r=1,···,k;s=1,···,nh/m.

例2令

則由引理2知故最小二乘解X?∈R3,再由定理2可得

故其唯一最小二乘解X?=[0.85371.6393?1.1944]T.

3 矩陣-矩陣方程(1.1)的最小二乘解

本節(jié)討論矩陣-矩陣型最小二乘解,即給定矩陣A∈Rm×n,B∈Rh×k,C∈Ra×b和D ∈ Rl×d,求矩陣X ∈ Rp×q使得

仿照第二節(jié),也分m=h,l=p;m=h,lp;mh,l=p和mh,lp四種情況討論問題.先考慮m=h,l=p的情形,其它情形可類似討論.由半張量積的定義將(3.1)式轉化為普通乘積下的最小二乘問題,進而結合奇異值分解及廣義逆給出最小二乘解X?的解析表達式.為方便記(3.1)式中右端極小值問題中目標函數(shù)為G(X).

3.1 簡單情形m=h,p=l

引理3若X∈Rp×q是問題(3.1)的解,則系數(shù)矩陣A,B,C,D的維數(shù)滿足下列條件

(ii)且

證對于方程(1.1)有

因為m=h和l=p,則因此并且,均為整數(shù),且有均整除k.

假定問題(3.1)滿足引理3中給出的維數(shù)相容條件.對于AX=B,有

其中分別是矩陣A,B 的列分塊矩陣,t=1,···,q.通過矩陣的列拉直算子Vc(·)將上式轉化為

記

對于XC=D,有

記由(3.2)和(3.3)式可得

對G(X)進行求導得

由一階微分必要條件知,函數(shù)G(X?)達到極小值需因此

記矩陣的奇異值分解為

其中U1=[U11U12],V1=[V11V12],U2=[U21U22],V2=[V21V22]均為列正交矩陣.而Σ1=diag(σ1σ2···σs),Σ2=diag(η1η2···ηt),其中 σi≥ 0,ηj≥ 0(i=1,···,s;j=1,···,t)分別為矩陣的奇異值,

將(3.6)式代入方程(3.5)得

假定

其中矩陣 X11∈ Rs×t,X12∈ Rs×(q?t),X21∈ R(p?s)×t,X22∈ R(p?s)×(q?t).將上述分塊代入方程(3.7),方程(3.7)等價于

定理 3給定矩陣A ∈ Rm×n,B ∈ Rh×k,C ∈ Ra×b和 D ∈ Rl×d,則方程 (3.1)在m=h,p=l情形下的最小二乘解X?的解析表達式為

其中 X22 ∈ R(p?s)×(q?t)任意.

例3令

則根據(jù)引理3可得,其最小二乘解X?∈R2×3,由定理3可知

故最小二乘解

3.2 一般情形m=h,pl

由半張量積定義給出m=h,pl情形下問題(3.1)的維數(shù)相容條件.

引理4若X∈Rp×q是問題(3.1)的最小二乘解,則須滿足兩個條件

證由半張量積的定義有

因為m=h,故β|a,若β=1,則l=p,這與條件矛盾.故而必為整數(shù).并且且證明完畢.

從引理4中可看出其最小二乘解不唯一,令其所有解稱為相容解.假定問題4滿足引理4中的維數(shù)相容條件,則可得下列結果:對于AX=B,其結果類似于3.1小節(jié)有

記

其中分別是矩陣A,B 的分塊矩陣,t=1,···,q.對于XC=D,有

其中Xi是矩陣X 的第i行,分別是矩陣和矩陣D的分塊矩陣 (i=1,···,p;j=1,···,q).通過矩陣的行拉直算子 Vr(·)可將 (3.10)式進一步簡化為

簡記

則

重復3.1小節(jié)中求導的過程可得下述定理.

定理4給定矩陣A∈Rm×n,B∈Rh×k,C∈Ra×b,和D∈Rl×d.A和B 的奇異值分解如(3.6)式所示.則方程(3.1)在m=h,pl情形下的最小二乘解X?可表示為

其中 X22 ∈ R(p?s)×(q?t)任意.

例4令

則由引理4知,故其最小二乘解X?∈R2×6,再由定理4得

則可得該方程的最小二乘解為

3.3 一般情形mh,p=l

同樣首先給出mh,p=l情形下問題(3.1)的維數(shù)相容條件.

引理5若X ∈Rp×q是問題(3.1)的最小二乘解,則須滿足

i)必是正整數(shù);

ii)其中α是n和 k的公約數(shù),且

證證明過程類似于引理4.

類似于3.1小節(jié).記則又轉化為m=h,p=l的情形.

記

其中重復3.1小節(jié)的過程,則有下列結果.

定理5給定矩陣A∈Rm×n,B∈Rh×k,C∈Ra×b和D∈Rl×d.A和B 的奇異值分解如(3.6)所示.則問題(3.1)在mh情形下的最小二乘解X?可表示為

其中任意.

例5令

則由引理5知故最小二乘解X?∈R3×2,再由定理5有

則可得該方程的最小二乘解為

3.4 一般情形mh,pl

mh,pl情形下問題(3.1)的維數(shù)相容條件如下.

引理6若問題(3.1)有最小二乘解X ∈Rp×q,則需滿足

i)為正整數(shù)其中α和β1分別為n與k和a與l的公約數(shù);

證由半張量積的定義,

從上可知必為整數(shù),并且有因此此外,若β=1,則l=p,顯然與條件相悖,并且

因此證畢.

假定(3.1)滿足引理6中的維數(shù)相容條件.記此時,轉化為m=h,pl的形式,重復3.2小節(jié)的過程,則有下面結果.

定理6給定矩陣A∈Rm×n,B ∈Rh×k,C∈Ra×b和D∈Rl×d,A 和B 的奇異值分解如(3.6)所示.則問題(3.1)在mh,pl情形下的最小二乘解X?可表示為

其中任意.

4 結論

半張量積作為一種新的研究工具在多線性函數(shù)、電力系統(tǒng)、布爾網(wǎng)絡、密碼學及模糊控制等領域有廣泛地應用.本文將半張量積應用于矩陣方程求解問題,研究了半張量積下矩陣方程組AX=B,XC=D的最小二乘解,分矩陣-向量方程(X∈Rp)和矩陣-矩陣方程(X∈Rp×q)兩種情形展開討論.結合半張量積的定義給出問題有解的相容條件,即系數(shù)矩陣維數(shù)需滿足的關系式,進而將半張量積下的問題轉化為普通矩陣乘積下的矩陣方程最小二乘問題,結合廣義逆,矩陣微分及奇異值分解給出問題解的具體解析表達式.對每一種情形給出簡單的數(shù)值算例驗證理論結果的正確性.

參考文獻

[1]Horn R A,Johnson C R.Topics in matrix analysis[M].New York:Cambridge Univ.Press,1991.

[2]程代展,齊洪勝.矩陣的半張量積:理論與應用[M].北京:科學出版社,2011.

[3]Cheng D Z,Zhao Y.Semi-tensor product of matrices-a convenient new tool[J].Chin.Sci.Bull.,2011,56:2664–2674.

[4]馬進,程代展,梅生偉,盧強.基于半張量理論的電力系統(tǒng)穩(wěn)定域邊界逼近(二)應用[J].電力系統(tǒng)自動化,2006,11:7–12.

[5]Feng J E,Yao J,Cui P.Singular Boolean network:semi-tensor product approach[J].Sci.China Ser.F:Inform.Sci.,2013,56:1–14.

[6]高博.基于半張量積的幾類密碼算法的研究[D].北京:北京交通大學,2014.

[7]Xu M R,Wang Y Z.Robust graph coloring based on the matrix semi-tensor product with application to examination time tabling[J].J.Contr.The.Appl.,2014,2:187–197.

[8]Cheng D Z,Qi H S.Matrix expression of logic and fuzzy control[R].Seville:44th IEEE Conf.Dec.Control/Euro.Control Conf.(CCD-ECC),2005.

[9]Cheng D Z,He F,Xu T.On networked non-cooperative games:a semi-tensor product approach[R].Istanbul:Proc.9th Asian Control Conf.,2013.

[10]Yao J,Feng J E,Meng M.On solutions of the matrix equation AX=B with respect to semi-tensor product[J].J.Frank.Inst.,2016,353:1109–1131.

[11]Mitra S K.The matrix equations AX=C,XB=D[J].Linear Alg.Appl.,1984,59:171–181.

[12]Li F L,Hu X Y,Zhang L.Least-squares mirrorsymmetric solution for matrix equations(AX=B,XC=D)[J].Numer.Math.J.Chin.Univ.Engl.Ser.,2006,15:217–226.

[13]Li F L,Hu X Y,Zhang L.The generalized re flexive solution for a class of matrix equations(AX=B,XC=D)[J].Acta Math.Sci.Ser.B.Engl.Ed.,2008,28:185–193.

[14]Li F L,Hu X Y,Zhang L.The generalized anti-re flexive solutions for a class of matrix equations(BX=C,XD=E)[J].Comp.Appl.Math.,2008,27:31–46.

[15]Qiu Y Y,Wang A D.Least squares solutions to the equations AX=B,XC=D with some constraints[J].Appl.Math.Comp.,2008,204:872–880.

[16]Yuan Y X.Least-squares solutions to the matrix equations AX=B and XC=D[J].Appl.Math.Comp.,2010,216:3120–3125.