矩陣奇異值分解與非齊次線性方程組系數(shù)矩陣的廣義逆求解

吳 華, 邵廣周

(1.長安大學(xué) 理學(xué)院,西安 710064; 2.長安大學(xué) 地質(zhì)工程與測繪學(xué)院,西安 710054)

0 引 言

在實際線性反演問題中,對于任意非齊次線性方程組Ax=b有解,則稱其為相容的,否則稱之為不相容或矛盾的.廣義逆理論把求解任意非齊次超定、欠定或混定線性方程組的解全部概括統(tǒng)一起來[1].如果能夠找到其系數(shù)矩陣A的Moore-Penrose逆A+,就可得到問題對應(yīng)的解.由于A+存在且唯一,所得的解x=A+b也是唯一的[2].矩陣廣義逆在解線性方程組、矩陣方程組中有著廣泛的應(yīng)用,文獻(xiàn)[3]通過研究相關(guān)矩陣方程的性質(zhì)找出了解存在的條件.文獻(xiàn)[4]基于內(nèi)積理論對線性矛盾方程組最小二乘解問題進(jìn)行了理論推導(dǎo).本文則從矩陣奇異值分解算法著手,給出非齊次線性方程組的自然解.

1 矩陣奇異值分解

對任意秩為p的m×n階矩陣A,可分解成如下形式[5]

(1)

其中,Λ為對角矩陣,對角線元素λ1,λ2,…,λp為正的非增序列,其平方是矩陣ATA和AAT的p個非零特征值,稱對角線元素λi為奇異值.U和V分別為m×m和n×n的正交矩陣,對應(yīng)的特征向量相互正交(即UUT=UTU=I,VVT=VTV=I),U對應(yīng)的特征向量張成數(shù)據(jù)空間.V對應(yīng)的特征向量張成模型空間.

其中,Up,Vp分別為U,V的前p列,則可將A寫為

(2)

由(2)式知,在進(jìn)行奇異值分解后,矩陣A可用不含零特征值向量U0和V0的矩陣的乘積來表示,可見奇異值分解是把數(shù)據(jù)空間和模型空間分解為非零空間和零空間兩部分.非零特征值對應(yīng)的特征向量Up和Vp張成非零空間,U0和V0則張成零空間.

現(xiàn)以正交矩陣U為例進(jìn)一步說明奇異值分解的作用,考查Up和U0的性質(zhì)以及彼此之間的關(guān)系:

類似地,矩陣V,Vp和V0也具有上述性質(zhì).

2 非齊次線性方程組的自然解

3 奇異值分解算法實現(xiàn)

3.1 Householder變換

奇異值分解是一種正交變換,算法實現(xiàn)時可通過一系列正交變換來完成,其關(guān)鍵算法是Householder變換,該算法可將矩陣A對角化[6].

Householder變換最關(guān)鍵的步驟是如何構(gòu)造正交矩陣Q(滿足QQT=QTQ=I),具體可按下式來實現(xiàn):

(3)

其中,u為任意非零向量.顯然,QT=Q,則

表明Q是一個正交矩陣,稱矩陣Q為Householder矩陣.接下來的問題是該如何選擇u.

現(xiàn)設(shè)一個已知的n維非零向量為v,存在正交矩陣Q使得

Qv=-sign(v1)‖v‖e1,

(4)

其中,e1為單位向量基,即e1=[1,0,0,…,0]T.sign(v1)表示取向量v的第一個元素的符號,即

則向量u可按下式構(gòu)造

u=v+sign(v1)‖v‖e1.

(5)

將(5)式代入(3)式所得到的矩陣Q就能夠滿足(4)式.現(xiàn)通過如下例子進(jìn)行證明.

例對于列向量v=[1,3,4,3,1]T進(jìn)行Householder變換.

解① 構(gòu)造向量u:

u=v+sign(v1)‖v‖e1=[1,3,4,3,1]T+1·6·[1,0,0,0,0]T=[7,3,4,3,1]T;

② 計算uuT和uTu:

③ 計算正交矩陣Q:

④ 計算Qv:

⑤ 根據(jù)式(16)計算Qv:

Qv=-sign(v1)‖v‖e1=-1·6·[1,0,0,0,0]T=[-6,0,0,0,0]T.

上述算例表明,對于任意向量v,按照(5)式構(gòu)造向量u,再按照(3)式構(gòu)造矩陣Q,然后左乘以向量v,即可將向量v映射到單位向量基e1上.也就是說,可將向量v轉(zhuǎn)變?yōu)榈谝粋€元素等于sign(v1)‖v‖,而其余元素均為零的向量.

3.2 奇異值分解編程算法步驟

(i)首先利用Householder變換把矩陣A逐步轉(zhuǎn)換為雙對角陣.設(shè)U1為一個Householder矩陣,將U1左乘以A,將其第一列元素化為除第一個元素之外其他元素全為零的向量.現(xiàn)以一個6×5的矩陣A為例,考察這一過程:

(6)

再設(shè)V1也是一個Householder矩陣,將其右乘以矩陣U1A,可將(6)式中用圓圈表示的元素化為零,即

同理,采用上述方法逐步選擇Householder矩陣U2和V2,把(6)式中用圓圈表示的元素化為零.當(dāng)A被左乘五次、右乘三次時,就變成了雙對角陣

對于一般的m×n矩陣,利用Householder變換可逐步將其化為如下雙對角矩陣:

其中

由于右乘變換矩陣Vj后又會將上一步的計算結(jié)果矩陣左下角已被化為零的元素轉(zhuǎn)換為非零元素,通常不能用Householder變換一次性將矩陣A化為對角矩陣.

(ii) 接下來,再采用一系列平面旋轉(zhuǎn)變換把上一步得到的雙對角矩陣B逐次化為對角矩陣Λ,其中Λ為奇異值矩陣.列旋轉(zhuǎn)變換矩陣的構(gòu)造可按如下步驟進(jìn)行:

首先構(gòu)造如(7)式所示的矩陣V12,右乘以矩陣B.

(7)

其中

并計算BV12.

再構(gòu)造如(8)式所示的矩陣U12,左乘以矩陣B.

(8)

同理,構(gòu)造平移旋轉(zhuǎn)矩陣

構(gòu)造平移旋轉(zhuǎn)矩陣

逐次迭代可得

最后,將奇異值按非增序列排序,在上述迭代過程中,如果某個次對角線元素|ej|≤ε,可將ej看作為0.如果對角線元素|sj|≤ε,可將sj看作為0,即此時奇異值為零,其中ε為精度要求.

4 結(jié) 論

本文給出了非齊次線性方程組的奇異值分解算法,通過Householder正交變換將方程組系數(shù)矩陣A逐步迭代變換為對角矩陣,從而得到系數(shù)矩陣的奇異值,進(jìn)而得到非齊次線性方程組的自然解,該方法使得非齊次線性方程組的求解更容易進(jìn)行計算機(jī)編程實現(xiàn).

致謝作者非常感謝相關(guān)文獻(xiàn)對本文的啟發(fā)以及審稿專家提出的寶貴意見.