矩陣的分解.ppt

1、矩陣的分解,Matrix Factorization and Decomposition,矩陣分解的概述,矩陣的分解： A=A1+A2+Ak 矩陣的和 A=A1A2 Am 矩陣的乘積 矩陣分解的原則： 實(shí)際應(yīng)用的需要,理論上的需要 計(jì)算上的需要,顯示原矩陣的某些特性 矩陣化簡(jiǎn)的方法之一 主要技巧： 各種標(biāo)準(zhǔn)形的理論和計(jì)算方法 矩陣的分塊,常見(jiàn)的矩陣標(biāo)準(zhǔn)形與分解,常見(jiàn)的標(biāo)準(zhǔn)形 等價(jià)標(biāo)準(zhǔn)形 相似標(biāo)準(zhǔn)形 合同標(biāo)準(zhǔn)形,本節(jié)分解： 三角分解 滿秩分解 可對(duì)角化矩陣的譜分解,AT=A,相似標(biāo)準(zhǔn)形,等價(jià)標(biāo)準(zhǔn)形,一、矩陣的三角分解,方陣的LU和LDV分解（P.61） LU分解：AFnn， 存在下三角形矩陣L

2、，上三角形矩陣U ，使得A=LU。 LDV分解：AFnn， L、V分別是主對(duì)角線元素為1的下三角形和上三角形矩陣，D為對(duì)角矩陣，使得A=LDV。 已知的方法：Gauss-消元法 例題1 （P.61eg1）設(shè) 求A的LU和LDV分解。,結(jié)論：如果矩陣A能用兩行互換以外的 初等行變換化為階梯形，則A有LU分解。,三角分解的存在性和惟一性 定理3.1 （P.62） ： 矩陣的k 階主子式：取矩陣的前k行、前k列得到的行列式，k=1，2， ，n。 定理: AFnn有惟一LDV分解的充要條件是A的順序主子式Ak非零，k =1，2，n-1。,證明過(guò)程給出了LDV分解的一種算法。,定理3.2（P.64）設(shè)矩

3、陣AFnn ，rank（A）=k（ n），如果A的j階順序主子式不等于0， j =1，2，k,則 A有LU分解。 定理?xiàng)l件的討論 例題2 （P.65 eg2） LU分解的應(yīng)用舉例,二、矩陣的滿秩分解,定義3.2 （P.66 ） 對(duì)秩為r 的矩陣AFmn ，如果存在秩為r的矩陣 B Fmr，CFrn ，則A=BC為A 的滿秩分解。,實(shí)用方法：方法3,例題2 （ P.69，eg5）,列滿秩,行滿秩,定理3.2：任何非零矩陣AFmn都有滿秩分解。 滿秩分解的求法： 方法1： 方法2 例題1（ P.68， eg4 ） 方法3,例題3（ P.70，eg6）,三、可對(duì)角化矩陣的譜分解,將方陣分解成用譜加權(quán)

4、的矩陣和 譜：設(shè)AFnn ， 則A的譜=1，2，s。,，P具性質(zhì)：,1. 可對(duì)角矩陣的譜分解 分解分析： 分解結(jié)果：,冪等矩陣,意義：可對(duì)角化矩陣可以分解成以譜加權(quán)的冪等矩陣的加權(quán)和,2、 矩陣可以對(duì)角化的一個(gè)充要條件 定理3.5（P.73 ） 矩陣A可以相似對(duì)角化當(dāng)且僅當(dāng)矩陣A有譜分解 ，滿足條件：,充分性的證明： 在A有譜分解時(shí) Cn=V 1V 2 V n,3. 冪等矩陣的性質(zhì) 定理3 .4（P.72）PFnn ，P2=P，則 矩陣PH和矩陣（IP）仍然是冪等矩陣。 P 的譜0，1，P 可相似于對(duì)角形。 Fn = N（P） R（P） N（P）=V =0 ，R（P）=V=1 P和（I P）的

5、關(guān)系 N（I P）=R（P），R（ I P ）=N（P） Hermite 矩陣的譜分解 定理3 .6（P.73）設(shè)A是秩為k的半正定的Hermite 矩陣，則A可以分解為下列半正定矩陣的和。 A=v1v1H+v2v2H+vkvkH,Schur 分解和正規(guī)矩陣,已知：歐氏空間中的對(duì)稱矩陣A可以正交 相似于對(duì)角形。 討論：一般方陣A ，在什么條件下可以 酉相似于對(duì)角矩陣？ 在內(nèi)積空間中討論問(wèn)題，涉及： 空間 Cn、 Cnn， 酉矩陣U，UHU=I， U 1=UH 酉相似： UHAU=J U1 AU=J,重點(diǎn)：理論結(jié)果,一、 Schur 分解,1、 可逆矩陣的UR分解 定理3.7（P.74）ACnn

6、為可逆矩陣，則存在酉矩陣U和主對(duì)角線上元素皆正的上三角矩陣R，使得A=UR。（ 稱A=UR為矩陣A的酉分解） 證明：源于Schmidt正交化方法。 例題1 求矩陣A的UR分解，其中,定理3.8（P.76） ：設(shè)矩陣ACmn是列滿秩的矩陣，則矩陣A可以分解為A=QR，其中Q Cmn的列向量是標(biāo)準(zhǔn)正交的向量組，R Cnn是主對(duì)角線上元素為正數(shù)的上三角形矩陣。,QR分解,2 、Schur 分解 定理3.7（P.74 ）對(duì)矩陣ACnn，存在酉矩陣U和上三角矩陣T，使得 UHAU=T=,證明要點(diǎn)： A=PJ AP1 ， P=UR A= PJ AP1 =U（RJR1 ）UH =UTUH。,二、正規(guī)矩陣（N

7、ormal Matrices）,1、 定義3.3（P.77 ）A是正規(guī)矩陣 AHA=AAH。 常見(jiàn)的正規(guī)矩陣： 對(duì)角矩陣 對(duì)稱和反對(duì)稱矩陣：AT=A，AT=A。 Hermite矩陣和反Hermite矩陣：AH=A，AH=A 正交矩陣和酉矩陣：ATA=AAT=I，AHA=AAH=I。 例題1 （P.78，eg 10）設(shè)A為正規(guī)矩陣，B酉相似于A，證明B也是正規(guī)矩陣。,正規(guī)是酉相似的不變性質(zhì),例題2、AFmn，矩陣AHA 和矩陣AAH是正規(guī)矩陣。,2、正規(guī)矩陣的基本特性 定理3.10 （P.78 ） ： ACnn正規(guī)A酉相似于對(duì)角形。 推論：正規(guī)ACnnA有n個(gè)標(biāo)準(zhǔn)正交的特征向量構(gòu)成空間Cn 的標(biāo)

8、準(zhǔn)正交基。 定理3.11（P.80 ）（正規(guī)矩陣的譜分解） A正規(guī)A有如下譜分解：,Hermite性,3、正規(guī)性質(zhì)的應(yīng)用舉例 例題1（P.79 ，eg12） 例題2 設(shè)ARnn，AT=A，證明 A的特征值是零和純虛數(shù)。 矩陣A的秩是偶數(shù)。,矩陣的奇異值分解,Singular value decomposition (SVD),矩陣的奇異值分解,概述： 矩陣的奇異值分解是酉等價(jià)型的分解: AC mn，酉矩陣UC mm, VC nn ,使得A=U VH。 矩陣A等價(jià)于=,奇異值分解基本適用于內(nèi)積空間中與矩陣秩相關(guān)的問(wèn)題 A的奇異值分解依賴于正規(guī)矩陣A HA 的酉相似分解的。,一、矩陣A的奇異值及其

9、性質(zhì),1、矩陣AHA和AAH的性質(zhì)： AC mn，AHAC nn，AAHC mm ，都是Hermite矩陣。 定理312（P82） 秩（A）秩（AHA）=秩（AAH）。 AHA 和AAH 的非零特征值相等。 AHA和AAH 是半正定矩陣。,AHA和AAH 的特征值是非負(fù)實(shí)數(shù)：1 2 n,2、奇異值的定義： （P72） AC mn，秩（A）=r，設(shè)AHA的特征值1 2 r 0，r+1= r+2 = n =0，則矩陣的奇異值,3、特殊矩陣的奇異值： 定理313（P82）： 正規(guī)矩陣A的奇異值等于A的特征值的模長(zhǎng)。 正定的Hermite矩陣A的奇異值就是A的特征值。 酉等價(jià)矩陣的奇異值相等。,A和B

10、酉等價(jià)，則AHA和BHB酉相似。 奇異值是酉等價(jià)的不變性質(zhì)。,二、矩陣的奇異值分解,1、定理314（P83） 任何矩陣AC mn，秩（A）=r，則存在酉矩陣 UC mm，VC nn，使得,證明思想： AHA正規(guī)，VHAHAV= ，酉矩陣V。,令 ，i=1，2，r，得U1=u1，u2， ，ur 擴(kuò)充為標(biāo)準(zhǔn)正交基 酉矩陣U。,例題1 求矩陣A的奇異值分解，A= 。,例題2（P84，eg13） 求矩陣A的奇異值分解，A=,2、矩陣U，V的空間性質(zhì)： V=v 1，v2，vr ， ，v n =V1 V2C nn的列向量是空間C n的標(biāo)準(zhǔn)正交基。 V2的列向量是空間N（A）的標(biāo)準(zhǔn)正交基。 V1的列向量是空

11、間 N （A） 的標(biāo)準(zhǔn)正交基。 U=u 1，u2，ur ， ，u m =U1 U2C mm的列向量是空間C m的標(biāo)準(zhǔn)正交基。 U1 的列向量是R（A）的標(biāo)準(zhǔn)正交基。 U2的列向量是R （A）的標(biāo)準(zhǔn)正交基。 3、奇異值分解的展開(kāi)形式及其應(yīng)用 定理3 15（ P87）,左奇異向量,右奇異向量,例題：圖像的數(shù)字化技術(shù)與矩陣的奇異值分解,計(jì)算機(jī)處理圖像技術(shù)的第一步是圖像的數(shù)字化存儲(chǔ)技術(shù)，即將圖像轉(zhuǎn)換成矩陣來(lái)存儲(chǔ)。 轉(zhuǎn)換的原理是將圖形分解成象素（pixels）的一個(gè)矩形的數(shù)陣，其中的信息就可以用一個(gè)矩陣A=（a ij）mn來(lái)存儲(chǔ)。矩陣A的元素a ij是一個(gè)正的數(shù)，它相應(yīng)于象素的灰度水平（gray lev

12、el） 的度量值。 由于一般來(lái)講，相鄰的象素會(huì)產(chǎn)生相近的灰度水平值，因此有可能在滿足圖像清晰度要求的條件下，將存儲(chǔ)一個(gè)mn階矩陣需要存儲(chǔ)的mn個(gè)數(shù)減少到n+m+1的一個(gè)倍數(shù)。,壓縮數(shù)字化圖形存儲(chǔ)量的方法主要是應(yīng)用矩陣的奇異值分解和矩陣范數(shù)下的逼近。如果圖象的數(shù)字矩陣A的奇異值分解為：A=UVT， 其展開(kāi)式：,壓縮矩陣A的方法是取一個(gè)秩為k （kr）的矩陣Ak來(lái)逼近 矩陣A。 Ak按如下方法選?。?有在秩為k （kn）的所有矩陣中，矩陣Ak所對(duì)應(yīng)的圖象和矩陣A所對(duì)應(yīng)的圖象最相近。一般的，k越大圖象就越清晰。經(jīng)典的方法是選取接近k，使Ak 的存儲(chǔ)量比A的存儲(chǔ)量減少20%。,存儲(chǔ)矩陣Ak只需要存儲(chǔ)k個(gè)奇異值，k個(gè)m維向量ui和n維向量vj的所有分量，共計(jì)k（m+n+1）個(gè)元素。 如果m=n=1000，存儲(chǔ)原矩陣A需要存儲(chǔ)10001000個(gè)元素。取k=100時(shí)，圖象已經(jīng)非常清晰了，這時(shí)的存儲(chǔ)量是100（2000+1）=200100個(gè)數(shù)。 和矩陣A比較，存儲(chǔ)量減少了80%。,三、矩陣的奇異值分解和線性變換TA 矩陣AC mn可以定義線性變換 TA ： C n C m 設(shè)矩陣的奇異值分解A=U VH ，則將U和V的列分別取做空間C m 、C n的基，則變換TA的矩陣為: =VX C m ,則TAX=(U VH )VX=U(X)=U,變換TA在單位球上的象： 定理316 （ P88）,