矩陣分析課件chapt4 矩陣分解例題詳解.doc

第4章 矩陣分解(I)高斯消去法 假設(shè)矩陣A 的順序主子式0 (i=1,n),則我們可以進(jìn)行以下的順序消元過(guò)程1消元過(guò)程 等價(jià)于用初等矩陣分別左乘和，即 (1)其中，,我們稱(chēng)為消元因子，為主元素；消元過(guò)程的一個(gè)重要性質(zhì)是：消元過(guò)程不改變矩陣的主子矩陣的行列式(主子式)的值。例,順序主子式為，1，5，-10,順序主子式為，1，5，-10，順序主子式為，1，5，-10引理：約化的主元素0的充要條件是矩陣A 的順序主子式0 (i=1,k);推論：若矩陣A 的順序主子式0 (i=1,k)，則，；由此有若A對(duì)稱(chēng)正定或嚴(yán)格對(duì)角占優(yōu)，而它們的順序主子矩陣也是對(duì)稱(chēng)正定或嚴(yán)格對(duì)角占優(yōu)，從而順序主子式不為0，順序高斯消去過(guò)程可進(jìn)行；2.回代過(guò)程：設(shè)， , 用高斯消去法解線(xiàn)性方程Ax=b.增廣矩陣為 ，因此，問(wèn)題的解為 3. 數(shù)值穩(wěn)定性1)選列主元 ；2)選全主元；3)高斯若當(dāng)(Gauss-Jordan)消去法，求矩陣的逆;, 求A-1.增廣矩陣為 從而4高斯順序消元法解方程的計(jì)算量1)乘除次數(shù)：2)加減次數(shù)：3)求矩陣的逆的計(jì)算量為o()(II) 順序消元過(guò)程與矩陣的三角分解(1) (2) 若 則有 ，從而，(3) 由有 故有 A=LU，其中.這時(shí)L為單位下三角矩陣。矩陣的三角分解 A=(a1,a2,an)=PR=(p1,p2,pn)R(a) LU分解(Doolittle分解)(1) 存在唯一的條件;(順序主子式不為0)(2) 公式推導(dǎo);(矩陣乘法)定義4.1 如果方陣A可分解成一個(gè)下三角矩陣L和一個(gè)上三角矩陣U的乘積，則稱(chēng)A可作三角分解. 如果方陣A可分解成A=LDU,其中L為一個(gè)單位下三角矩陣，D為對(duì)角矩陣，U是一個(gè)單位上三角矩陣。推論：若矩陣A 的順序主子式Dk0 (k=1,n-1)，則A可唯一分解為A=LDU, 其中L為一個(gè)單位下三角矩陣，D為對(duì)角矩陣，U是一個(gè)單位上三角矩陣。dk=Dk/Dk-1 (D0=1)。定理4.2 設(shè)A是n階非奇異矩陣，則存在置換矩陣P使得PA=LDU, 其中L為一個(gè)單位下三角矩陣，D為對(duì)角矩陣，U是一個(gè)單位上三角矩陣。定義4.2 設(shè)A存在唯一的LDU分解.若把A=LDU中的D和U結(jié)合起來(lái)，并且用U表示，則得到唯一的LU分解 A=LU稱(chēng)為Doolittle分解；若把A=LDU中的L和D結(jié)合成L，就得到A=LU稱(chēng)為Crout分解。LU分解的公式：lik=aik-(li1u1k+li,k-1uk-1,k)ukj= akj-(lk1u1j+lk,k-1uk-1,j)/lkkCrout分解類(lèi)似。(b)平方根法(1)對(duì)稱(chēng)矩陣的三角分解定理； (2)對(duì)稱(chēng)正定矩陣的三角分解(Cholesky分解) 遞推公式 gii=(aii-)1/2 gij=aij-(gi1gj1+gi2gj2+gi,j-1gj,j-1)/gii, ij gij=0 i1)及單位列向量zRn,則存在Householder矩陣H，使得Hx=|x| z.定理4.5 初等旋轉(zhuǎn)矩陣(Givens變換)是兩個(gè)初等反射矩陣(Householder變換)的乘積。證明：對(duì)初等旋轉(zhuǎn)矩陣Tij,取 u=(0,0,sin(q/4),0,0,cos(q/4),0,0)T v=(0,0,sin(3q/4),0,0,cos(3q/4),0,0)T 直接計(jì)算可得 Tij=HvHu從平面上看，我們可以得出 x Hq(a)= p+2q-a u 其中H=I -2uuT y q x為變換前的任意向量，用它與正半實(shí)軸的夾角a表示。 y為變換后的向量， 用它與正半實(shí)軸的夾角表示為p+2q-a。 y x q aGq(a)=q+a其中，q為旋轉(zhuǎn)角度；x為變換前的任意向量，用它與正半實(shí)軸的夾角a表示； y為變換后的向量， 用它與正半實(shí)軸的夾角表示為 q+a。我們需要證明的目標(biāo)就是找到兩個(gè)向量u1和u2使得它們對(duì)應(yīng)的Householder變換的乘積等于給定的一個(gè)旋轉(zhuǎn)變換Gq(a)。根據(jù)前面的討論我們對(duì)于H變換和G變換都可以用向量的角度表示。因此有 Hq2Hq1(a)=p+2q2-(p+2q1-a)=2(q2-q1)+a =q+a= Gq(a) l1可見(jiàn)q =2(q2-q1)成立即可。 x 這個(gè)等式在幾何成立的意思： H(u1)x u2 x和H(u2)H(u1)x之間的夾角等于二倍的 l2 u1 u1和u2之間的夾角。這在幾何上是顯然的。因?yàn)閡1對(duì)應(yīng)的垂線(xiàn)l1平分x和H(u1)x的夾角； H(u2)H(u1)x 同樣，因?yàn)閡2對(duì)應(yīng)的垂線(xiàn)l2平分H(u1)x和H(u2)H(u1)x的夾角。注意到l1和l2的夾角和向量u1和u2的夾角相等。因此結(jié)論是顯然的。 換句話(huà)說(shuō)，對(duì)于給定的旋轉(zhuǎn)變換，僅需找到夾角為旋轉(zhuǎn)角度的二分之一的兩個(gè)向量，用它們作反射變換，就可以得到旋轉(zhuǎn)變換。矩陣QR(正交三角)分解定義4.6 如果實(shí)(復(fù))矩陣A能夠化成正交矩陣Q與實(shí)(復(fù))非奇異上三角矩陣R的乘積，即 A=QR則稱(chēng)為A的QR分解。定理4.6 設(shè)A是n 階實(shí)(復(fù))非奇異矩陣，則存在正交(酉)矩陣Q與實(shí)(復(fù))非奇異上三角矩陣R使得 A=QR且除去相差一個(gè)對(duì)角元素的絕對(duì)值(模)全等于1的對(duì)角矩陣外，分解唯一。即QR分解存在唯一。證明：存在性：使用Gram-schmidt正交化過(guò)程。唯一性：A=QR=Q1R1從而P=(Q1)TQ=R-1R1注意到I=PTP所以P-1=PT,而P為上三角矩陣，其逆也為上三角矩陣，而PT為下三角矩陣， 從而P為對(duì)角矩陣.又P2=I，所以P的對(duì)角元只能為正負(fù)1。Q= Q1P, R= P R1.定理4.7 設(shè)A是mn實(shí)(復(fù))矩陣，且其n個(gè)列線(xiàn)性無(wú)關(guān)，則A有分解 A=QR其中Q是mn實(shí)(復(fù))矩陣，且滿(mǎn)足QTQ=I, R是實(shí)(復(fù))非奇異上三角矩陣R且除去相差一個(gè)對(duì)角元素的絕對(duì)值(模)全等于1的對(duì)角矩陣外，分解唯一。定理 任何n階實(shí)非奇異矩陣A可通過(guò)左連乘初等Givens旋轉(zhuǎn)矩陣化為上三角矩陣。定理4.10 任何n階實(shí)非奇異矩陣A可通過(guò)左連乘Householder矩陣化為上三角矩陣。定義4.7如果矩陣A的次對(duì)角線(xiàn)以下元素全為零，則稱(chēng)A為上Hessenberg矩陣；定理4.11： 任何實(shí)方正A都可以通過(guò)初等旋轉(zhuǎn)變換正交相似與上Hessenberg矩陣。定理4.12任何實(shí)方正A都可以通過(guò)初等反射變換正交相似與上Hessenberg矩陣。推論：任何實(shí)對(duì)稱(chēng)矩陣A都可以通過(guò)初等旋轉(zhuǎn)變換(或初等反射變換)正交相似于實(shí)對(duì)稱(chēng)三對(duì)角矩陣。思考題：任何正交矩陣Q是否存在特征值互不相同的對(duì)稱(chēng)(角)矩陣A(D)和三對(duì)角矩陣T使得AQ=QT 或 DQ=QT?其中要求T的次對(duì)角線(xiàn)的所有元素都不為零。這就是特征值的反問(wèn)題：已知Q求D和T使得DQ=QT.例如 單位矩陣Q=I就不存在，那么存在的條件是什么？在信號(hào)處理中，我們一般使用的都是哪些存在T的正交矩陣Q對(duì)應(yīng)的正交變換，為什么？Fourier 變換，小波變換都存在。這和所謂信號(hào)的頻率有關(guān)。一般說(shuō)來(lái)，Q的列按頻率由低到高排列。4.3 矩陣的滿(mǎn)秩分解復(fù)習(xí)矩陣的秩的概念和性質(zhì)定義:矩陣行或列向量的最大線(xiàn)性無(wú)關(guān)組的個(gè)數(shù)。思考題：證明矩陣的行秩和列秩相等。性質(zhì)：rank(AB) min (rank(A),rank(B)定義4.8 設(shè)A(r0),如果存在矩陣F和 G使得 A=FG 則稱(chēng)為A的滿(mǎn)秩分解。當(dāng)A為行滿(mǎn)秩或列滿(mǎn)秩矩陣時(shí)，A可分解為一個(gè)因子為單位矩陣，另一個(gè)為A本身，稱(chēng)為平凡分解。定理：設(shè)A則A的滿(mǎn)秩分解存在。證明過(guò)程即為構(gòu)造過(guò)程。證明：設(shè)A=(a1,a2,an), 取A的列向量組的一個(gè)極大線(xiàn)性無(wú)關(guān)組，不妨設(shè)為ai1,ai2,air, 則對(duì)于A(yíng)的任意i列ai可以表示為ai1,ai2,air的線(xiàn)性組合。即 ai=g1iai1+ g2iai2+ griair, i=1,2,n寫(xiě)成矩陣形式有A=FG其中F=( ai1,ai2,air), G=(g1,g2,gn), gi=(g1i, g2i, gri)T,顯然F為列滿(mǎn)秩的矩陣，G為行滿(mǎn)秩的矩陣(為什么？)。注:滿(mǎn)秩分解不唯一。定義4.9 Hermite標(biāo)準(zhǔn)形， B滿(mǎn)足1)B的前r行中每一行至少含一個(gè)非零元素，且第一個(gè)非零元素是1，而后m-r個(gè)元素為0；2)若B中第i行的第一個(gè)非零元素1在第ji列(i=1,2,r),則 j1j20), 則必有分解A=QR.其中,Q為m r矩陣， QHQ=I, 而R為r n矩陣，它的行線(xiàn)性無(wú)關(guān)。證明：作A的滿(mǎn)秩分解A=FG其中F，G.由矩陣的QR分解定理有F=QR1其中Q為m r矩陣， QHQ=I, 而R1為r階非奇異矩陣。于是 A= FG = QR1G =QR.這里R=R1G,它的r個(gè)行線(xiàn)性無(wú)關(guān)。定理(習(xí)題4.3,第4題). 設(shè)F，G， 則rank(FG)= r證明：顯然 rank(FG) r (a)如果rank(FHF)= rank(GGH) =r.則 rank(FHFGGH) =r.，從而rank(FG) r (b)這樣rank(FG)= r. 下面我們證明rank(FHF) =r (實(shí)際為習(xí)題4.3 第2題)這需要證明FHF為滿(mǎn)秩矩陣。僅需證明對(duì)任意xCr,若 FHFx =0 則 x =0 即可。事實(shí)上， 由FHFx =0可得xHFHFx=0,從而|Fx|=0,根據(jù)范數(shù)定義， Fx=0；再由F為列滿(mǎn)秩矩陣，可得x=0。這樣證明了。思考題: 設(shè)F，G， 則rank(GF)= r成立嗎？若是，證明之；若否，研究成立的條件是什么？下面利用滿(mǎn)秩分解討論線(xiàn)性方程組求解。Ax= b,設(shè)A的滿(mǎn)秩分解為A=FG， 方程變?yōu)镕Gx=b.則若bR(F), 則存在相容解。若bR(F), 則不存在相容解，這時(shí)我們可以將b投影到R(F)得到b=F(FHF)-1FHb b R(F) b這時(shí)方程求解的實(shí)際就是所謂最小二乘解。如果這樣方程組變?yōu)镚x=(FHF)-1FHb.由于G的秩為r 因此方程組Gx=(FHF)-1FHb肯定有解。如果G不為方陣，則解不惟一。這時(shí)需要求解所謂最小范數(shù)解。即 x= GH(GGH)-1(FHF)-1FHb這就是所謂最小范數(shù)最小二乘解。10個(gè)隨機(jī)逼近點(diǎn)，y= x2+r, 其中r為-0.1,0.1之間均勻分布的隨機(jī)數(shù)。根據(jù)模型y=ax2+bx+c,利用最小二乘解得到的逼近結(jié)果。紅線(xiàn)所在點(diǎn)為逼近點(diǎn)藍(lán)線(xiàn)為y= x2，綠線(xiàn)為求得的逼近解。20個(gè)隨機(jī)逼近點(diǎn)，y= x2+r, 其中r為-0.1,0.1之間均勻分布的隨機(jī)數(shù)。根據(jù)模型y=ax2+bx+c,利用最小二乘解得到的逼近結(jié)果。紅線(xiàn)所在點(diǎn)為逼近點(diǎn)藍(lán)線(xiàn)為y= x2，綠線(xiàn)為求得的逼近解。4.4 矩陣的奇異值分解1.矩陣的正交對(duì)角分解我們知道實(shí)對(duì)稱(chēng)矩陣A或Hermite矩陣A都可正交相似于對(duì)角矩陣, 即 A=QHDQ由定理4.12 任何實(shí)方陣A都可以正交相似于上Hessenberg 矩陣。 即 A=QTHQ定理：對(duì)于任何非奇異的實(shí)方陣，存在正交矩陣P和Q使得PTAQ為正對(duì)角矩陣D。即A=PDQT證明: 由于A(yíng)非奇異，因此ATA為實(shí)對(duì)稱(chēng)矩陣。于是存在正交矩陣Q使得 QT(ATA)Q=D,D為對(duì)角矩陣,其對(duì)角元為ATA的特征值,它們大于0.因此記 P=AQD1/2, 易驗(yàn)證PTP=I且A= PD1/2Q.2矩陣的奇異值分解基本事實(shí)：1.設(shè)A(r0),則AHA是Hermite 矩陣，且其特征值非負(fù)。2. rank(A)=rank(AHA)3. 設(shè)A，則A=0的充要條件為AHA=0.定義: 設(shè)A，A的奇異值為AHA的特征值的非負(fù)平方根。定理4.16 設(shè)A，則存在m階酉矩陣U和n階酉矩陣V使得UHAV=, 其中S=diag(s1,s2,sr),而si為矩陣A的全部非零奇異值?；蛘邔?xiě)為 A=UVH稱(chēng)為A的奇異值分解。證明過(guò)程略。顯然由證明過(guò)程可見(jiàn)，若A為實(shí)矩陣，則定理4.16中U和V都可以為正交矩陣。例4.15 設(shè)矩陣A=UVH，則U的列是AAH的特征向量， V的列為AHA的特征向量。反之不一定對(duì)，即設(shè)U的列是AAH的特征向量，V的列為AHA的特征向量。那么UVH =A不一定成立。定理4.17 在奇異值分解A=UVH,設(shè)U和V的列向量分別為u1,u2,um和v1,v2,vn, 則N(A)=L(vr+1,vr+2,vn)R(A)=L(u1,u2,ur)A=s1u1+s2u2+srur (廣義譜分解)。奇異值分解的統(tǒng)計(jì)意義：若x一個(gè)均值為0的n維隨機(jī)向量，A的每一行表示它的一次抽樣，則AHA的i行j 列表示隨機(jī)向量x的在m次獨(dú)立抽樣基礎(chǔ)上對(duì)相關(guān)矩陣的一個(gè)無(wú)偏估計(jì)。如果對(duì)隨機(jī)向量x進(jìn)行線(xiàn)性變換y=Vx則隨機(jī)向量y在m次獨(dú)立抽樣基礎(chǔ)上對(duì)相關(guān)矩陣的一