第四章矩阵的分解精选PPT.ppt

《第四章矩阵的分解精选PPT.ppt》由会员分享，可在线阅读，更多相关《第四章矩阵的分解精选PPT.ppt（61页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章 矩阵的分解第1页，此课件共61页哦主要内容v三角分解vQR分解v满秩分解v奇异值分解第2页，此课件共61页哦Gauss消去法消去法 vGauss消去法的矩阵形式消去法的矩阵形式：求解求解矩阵方程矩阵方程 Ax=b 可采用可采用Gauss主元素消去法。主元素消去法。其其基基本本思思想想是是化化系系数数矩矩阵阵A为为上上三三角角矩矩阵阵，或或化化增增广广矩阵矩阵A|b为上阶梯形矩阵。为上阶梯形矩阵。v这种消去法有三种形式：这种消去法有三种形式：按自然顺序选主元素法，按自然顺序选主元素法，按列选主元素法按列选主元素法总体选主元素法。总体选主元素法。第3页，此课件共61页哦步骤步骤1 1：设：

2、设A(0)=A，其元素，其元素aij(0)=aij，若若A的的1阶顺序主子式阶顺序主子式 1=a11(0)0，令，令ci1=ai1(0)/a11(0),构造矩阵构造矩阵 ，则，则计算计算A(1)=L1-1A(0),其其第一列主元素下的元素全为零，而第一列主元素下的元素全为零，而 A(0)=L1A(1)；设设第4页，此课件共61页哦步步2.2.若若A的的2阶顺序主子式阶顺序主子式 2=a11(0)a22(1)0，令，令ci2=ai2(1)/a22(1),构造构造矩阵矩阵L2=，则，则 计算计算A(2)=L2-1A(1),其其前两列主元以下的元素全为零前两列主元以下的元素全为零；重复上述过程，在步

3、重复上述过程，在步n-1-1后得到的后得到的A(n-1)为上三角阵。为上三角阵。第5页，此课件共61页哦第6页，此课件共61页哦矩阵三角分解矩阵三角分解v定义：若方阵定义：若方阵A=LU，其中，其中L为下三角矩阵，为下三角矩阵，U为上三角矩阵，则为上三角矩阵，则称称A可以作三角分解或可以作三角分解或LU(LR)分解。若分解。若A=LDU，其中，其中L为单位为单位下三角矩阵，下三角矩阵，U为单位上三角矩阵，为单位上三角矩阵，D为对角矩阵，则称为对角矩阵，则称A可以可以作作LDU分解。分解。v定理：满秩定理：满秩n阶矩阵阶矩阵A可作三角分解的充要条件可作三角分解的充要条件v证明：必要性，设证明：必

4、要性，设 A=LU第7页，此课件共61页哦充分性：充分性：对对A的阶数用数学归纳法：的阶数用数学归纳法：n=1:归纳假设：归纳假设：n=k时结论成立时结论成立Lk,Uk可逆可逆当当n=k+1 时时第8页，此课件共61页哦定理：定理：A可作三角分解可作三角分解用构造法证明：用构造法证明：第9页，此课件共61页哦三角分解的唯一性三角分解的唯一性第10页，此课件共61页哦v定理：定理：可作三角分解的充要条件，也是有唯一的可作三角分解的充要条件，也是有唯一的Doolittle分解、唯一的分解、唯一的Crout分解及唯一的分解及唯一的LDU分解的充要条件：分解的充要条件：Doolittle分解分解Cro

5、ut分解分解第11页，此课件共61页哦证明：可逆可逆可逆可逆可逆可逆可逆可逆第12页，此课件共61页哦再证唯一性。设A有两个LDU分解以 同时左乘上式两边，以 同时右乘上式两边：第13页，此课件共61页哦主元素LU分解v避免由于主对角线元素为0使分解过程无法继续v保证计算精度第14页，此课件共61页哦消元过程消元过程回代过程回代过程矩阵三角分解的应用矩阵三角分解的应用 若矩阵若矩阵A存在三角分解存在三角分解A=LU，则求解线性方程组，则求解线性方程组即可转化为消元过程和回代过程即可转化为消元过程和回代过程第15页，此课件共61页哦Cholesky分解分解v对对于于正正定定实实对对称称矩矩阵阵，

6、其其各各阶阶主主子子式式都都大大于于零零，因因此有唯一此有唯一LDU分解分解 A=LDU=AT=UTDLT 于于是是L=UT，由由正正定定性性知知，D的的每每个个元元素素大大于于零零，因因此此存在对角阵存在对角阵H，使得，使得D=H2，令，令G=LH，则，则A=GGT称此分解为正定实对称矩阵的称此分解为正定实对称矩阵的Cholesky分解分解第16页，此课件共61页哦Cholesky分解算法分解算法(一一)v令令A=(aij)，G-(gij)为下三角矩阵，则由为下三角矩阵，则由A=GGT可得：可得：因此递推公式因此递推公式第17页，此课件共61页哦Cholesky分解算法分解算法(二二)v令令

7、A=(aij)，D=diag(d1,d2,dn)，L-(lij)为下三角矩阵，则由为下三角矩阵，则由A=LDLT 可得：可得：递推公式：递推公式：第18页，此课件共61页哦Cholesky分解的应用例分解的应用例1v自适应有限脉冲响应数字滤波器可表示为则有第19页，此课件共61页哦Cholesky分解的应用例分解的应用例2vAR随机过程参数估计则有第20页，此课件共61页哦分块矩阵的块三角分解分块矩阵的块三角分解 矩阵A 的块LU分解、块LDU分解和块UL分解分别为其中=A22-A21A11-1A12和=A11-A12A22-1A21第21页，此课件共61页哦分块矩阵的块三角分解分块矩阵的块三

8、角分解 于是有：例：设 ，则有det(Im+AB)=det(In+BA)证明：注：若 ，则有第22页，此课件共61页哦矩阵的矩阵的QR分解分解 v定义定义：如果实(复)非奇异矩阵A能够化成正交(酉)矩阵Q与实(复)非奇异上三角矩阵R的乘积，即A=QR，则称为A的QR分解分解v矩阵的矩阵的QR分解分解的三个常用方法的三个常用方法：（1）基于G-S正交化；（2）基于Givens旋转；（3）基于Householder变换。第23页，此课件共61页哦矩阵的矩阵的QR分解分解v定定理理：设A是n阶实(复)非奇异矩阵，则存在正交(酉)矩阵Q和实(复)非奇异上三角矩阵R使A=QR；且除去相差一个对角元素的绝

9、对值(模)全等于1的对角矩阵因子外，QR分解是惟一的 v证明：设A=(1,2,n)，其正交化向量序列为第24页，此课件共61页哦即第25页，此课件共61页哦令则A=QR，Q为正交矩阵，R为上三角矩阵。再证唯一性，设有两个Q-R分解：A=QR=Q1R1则由：R1R-1=Q1-1Q，知R1R-1既是上三角矩阵又是正交矩阵，因此必然是对角矩阵，且对角线元素的绝对值为1。第26页，此课件共61页哦QR分解分解推广定理推广定理 设A是mn列满秩实(复)矩阵，则A有QR分解AQR，其中Q是mn实(复)矩阵，且满足QTQ=I(QHQ=I)，R是n阶实(复)非奇异上三角矩阵该分解除去相差一个对角元素的绝对值(

10、模)全等于1的对角矩阵因子外是唯一的。第27页，此课件共61页哦v定义定义:设实数c与s满足c2+s2=1，称为Givens矩阵矩阵(初等旋转矩阵初等旋转矩阵)，Givens矩阵确定的线性变换称为Givens变换变换当c2+s2=1时，存在角度，使得ccos，ssin。GivensGivens变换变换ij第28页，此课件共61页哦Givens矩阵的性质矩阵的性质v性质1 Givens矩阵是正交矩阵，且detTij=1和Tij(c,s)-1=Tij(c,s)T=Tij(c,-s)。v性质2 设x=1,2,nT，y=Tijx=1,2,nT，则有i=ci+sj，j=-si+cj，k=k(ki,j).

11、当i2+j20时，选取c=i/i2+j20.5，s=j/i2+j20.5，就可使i=i2+j20.50，j=0。v定理：设x=1,2,nT，则存在有限个Givens矩阵的乘积，记作T，使得Tx=|x|e1第29页，此课件共61页哦推推论论：设非零列向量x Rn及单位列向量z Rn，则存在有限个Givens矩阵的乘积，记作T，使得Tx=|x|z。证证：根据定理，存在T(1)=T1n(1)T12(1)，使得T(1)x=|x|e1；存在T(2)=T1n(2)T12(2)，使得T(2)z=|z|e1=e1；于是有T(1)x=|x|e1=|x|T(2)z或者 T(2)-1T(1)x=|x|z于是 T=T

12、(2)-1T(1)=T1n(2)T12(2)-1T1n(1)T12(1)=(T12(2)T(T1n(2)T T1n(1)T12(1)是有限个Givens矩阵的乘积 第30页，此课件共61页哦Householder变换变换v定义定义：设单位列向量：设单位列向量u Rn，称，称H=I-2uuT为为Householder矩阵矩阵(初等反射矩初等反射矩阵阵)，由，由Householder矩阵确定的线性变换称为矩阵确定的线性变换称为Householder变换变换(初等反初等反射变换射变换)v对单位向量对单位向量u，及任意与，及任意与u垂直的列向量垂直的列向量w，有，有Hu=(I-2uuT)u=u-2uu

13、Tu=-uHw=(I-2uuT)w=w-2uuTw=w因此，变换因此，变换H是关于与是关于与u垂直平面的镜像。垂直平面的镜像。v基本性质基本性质：(1)HT=H(对称矩阵对称矩阵)，(2)HTH=I（正交矩阵），（正交矩阵），(3)H2=H(对合矩阵对合矩阵)，(4)H-1=H(自逆矩阵自逆矩阵)，(5)detH=-1。uwxHx第31页，此课件共61页哦Householder变换的性质变换的性质 v定理定理：任意给定非零列向量：任意给定非零列向量x Rn(n1)及单位列向量及单位列向量z Rn，则存在，则存在Houscholder矩阵矩阵H，使得，使得Hx=|x|z。v证明：令证明：令 定义

14、矩阵定义矩阵H=I-2uuT，则有，则有ux|x|z第32页，此课件共61页哦Givens变换与变换与Householder变换的联系变换的联系 v定理：初等旋转矩阵定理：初等旋转矩阵(Givens变换变换)是两个初等反射矩阵是两个初等反射矩阵(Householder变换变换)的乘积的乘积 证：对证：对Tij()，取，取Hu=I-2uuT和和Hv=I-2vvT，其中单位向量，其中单位向量u=(0,0,sin(0.25),0,0,cos(0.25),0,0)和单位向和单位向量量v=(0,0,sin(0.75),0,0,cos(0.75),0,0)，则有，则有Tij()=Hv Huv初等反射矩阵不

15、能由若干个初等旋转矩阵的乘积表初等反射矩阵不能由若干个初等旋转矩阵的乘积表示示 第33页，此课件共61页哦基于基于Givens旋转旋转的的QR分解分解定定理理：任何n阶实非奇异矩阵A(aij)可通过左连乘初等旋转矩阵化为上三角矩阵。证证 步l.detA0使A的第1列b(1)=(a11,a21,an1)T 0；存在有限个Givens矩阵的乘积T1，使得T1b(1)=|b(1)|e1和 T1A=步2.detA(1)0使A(1)的第1列b(2)=(a22(1),a32(1),an2(1)T 0；存在有限个Givens矩阵的乘积T2，使得T2b(2)=|b(2)|e1和 T2A(1)=第34页，此课件

16、共61页哦步n-1.detA(n-2)0使A(n-2)的第1列b(n-1)=(an-1,n-1(n-2),an,n-1(n-2)T0；存在有限个Givens矩阵的乘积Tn-1使Tn-1b(n-1)=|b(n-1)|e1和 Tn-1A(n-2)=步n.令 则有A=QR，其中上三角阵R=TA，Q=T-1。因为T是有限个Givens矩阵的乘积，而Givens矩阵都是正交矩阵，所以T是正交矩阵，Q=T-1=TT也是正交矩阵。第35页，此课件共61页哦基于基于Householder变换变换的的QR分解分解定理定理：任何n阶实非奇异矩阵A(aij)可通过左连乘Househoulder矩阵化为上三角矩阵。算

17、法算法：类同基于Givens旋转的QR分解，仅需用Hi取代相应的Ti(i=1,2,n-2)，并把T换成 Hi=In+1-I-uuT是n+1-i阶Househoulder矩阵，使得 都是n阶Househoulder矩阵。因此，S是有限个Househoulder矩阵的乘积，必是正交矩阵。第36页，此课件共61页哦定理定理：设：设 为任意矩阵，则存在为任意矩阵，则存在使得使得其中其中 B 为列满秩矩阵，为列满秩矩阵，C为行满秩矩阵为行满秩矩阵(我们称此分解为我们称此分解为矩阵的满矩阵的满秩分解秩分解)。证明证明：假设矩阵：假设矩阵 A 的前的前 r 个列向量是线性无关的，对矩阵个列向量是线性无关的，

18、对矩阵 A 只实只实施初等变行换可以将其化成施初等变行换可以将其化成矩阵的满秩分解矩阵的满秩分解第37页，此课件共61页哦即存在即存在 使得使得于是有于是有其中其中 如果如果 A 的前的前 r 列线性相关，那么只需对列线性相关，那么只需对 A 作初等列变换作初等列变换(只需做只需做交换两列的变换交换两列的变换)使得前使得前 r 个列是线性无关的。然后重复上面的过程即个列是线性无关的。然后重复上面的过程即可。这样存在可。这样存在A=Ar,An-r=B,BD第38页，此课件共61页哦 从而从而且满足且满足其中其中第39页，此课件共61页哦例例 分别求下面三个矩阵的满秩分解分别求下面三个矩阵的满秩分

19、解解解 （1）对此矩阵只实施初等行变换可以得到对此矩阵只实施初等行变换可以得到 第40页，此课件共61页哦由此可知由此可知 rank(A)=2，且该矩阵第一列，第三列是线性无关的。，且该矩阵第一列，第三列是线性无关的。选取选取第41页，此课件共61页哦（2）对此矩阵只实施初等行变换可以得到对此矩阵只实施初等行变换可以得到所以所以 rank(A)=1，且此矩阵的第三，第四，第五列任意一列都是线，且此矩阵的第三，第四，第五列任意一列都是线性无关的，所以选取哪一列构成列满秩矩阵均可以。性无关的，所以选取哪一列构成列满秩矩阵均可以。选取选取也可以选取也可以选取第42页，此课件共61页哦（3）对此矩阵只

20、实施初等行变换可以得到对此矩阵只实施初等行变换可以得到 所以所以rank(A)=2，且容易看出此矩阵的第二列和第四列是线性无关的，且容易看出此矩阵的第二列和第四列是线性无关的，选取选取第43页，此课件共61页哦 由上述例子可以看出由上述例子可以看出矩阵的满秩分解形式并不唯一矩阵的满秩分解形式并不唯一。一般地一般地我们选取阶梯型矩阵主元所在的列对应的列向量构成列满秩矩阵，我们选取阶梯型矩阵主元所在的列对应的列向量构成列满秩矩阵，将阶梯型矩阵全为零的行去掉后即可构成行满秩矩阵。将阶梯型矩阵全为零的行去掉后即可构成行满秩矩阵。但是不同但是不同的分解形式之间有如下联系：的分解形式之间有如下联系：定理定

21、理：如果：如果 A=BC=B1C1 均为矩阵均为矩阵 A 的满秩分解，那么的满秩分解，那么（1）存在矩阵）存在矩阵 满足满足（2）第44页，此课件共61页哦引理引理 1：对于任何一个矩阵对于任何一个矩阵 A 都有都有引理引理 2：对于任何一个矩阵对于任何一个矩阵 A 都有都有 AAH 与与 AHA 都是半正定的都是半正定的Hermite-矩阵。矩阵。设设 ，i是是 AAH 的特征值，的特征值，i i是是AHA 的特征值，它的特征值，它们都是实数。如果记们都是实数。如果记矩阵的奇异值分解矩阵的奇异值分解第45页，此课件共61页哦特征值特征值i与与i之间有如下关系。之间有如下关系。定理定理：设：设

22、 ，那么，那么同时，我们称同时，我们称为矩阵为矩阵A的的正奇异值正奇异值，简称，简称奇异值奇异值。例例 求下列矩阵的奇异值求下列矩阵的奇异值第46页，此课件共61页哦解解 （1）由于）由于显然显然 AAH 的特征值为的特征值为5，0，0，所以，所以 A 的奇异值为的奇异值为 （2）由于）由于显然显然 AAH 的特征值为的特征值为 2，4，所以，所以 A 的奇异值为的奇异值为 。第47页，此课件共61页哦定理定理 设设 ，是是 A 的的 r 个奇异值，那么存在个奇异值，那么存在 m 阶酉矩阵阶酉矩阵 V 和和 n 阶酉矩阵阶酉矩阵 U 使得使得其中其中第48页，此课件共61页哦证明证明：由于由于

23、 rank(A)=r，所以，所以 AHA 的特征值为的特征值为因为因为 AHA 是一个共轭对称阵，所以存在是一个共轭对称阵，所以存在 n 阶酉矩阵阶酉矩阵 U 满足满足将酉矩阵将酉矩阵 U 按列进行分块，记按列进行分块，记 U=U1,U2，其中，其中于是有于是有第49页，此课件共61页哦从而有从而有记记 ，则有，则有 选取选取 使得使得 是酉矩阵，则是酉矩阵，则 由上述式子可得由上述式子可得第50页，此课件共61页哦这里，要注意这里，要注意 。（证完）。（证完）我们称此定理为我们称此定理为奇异值分解定理奇异值分解定理。称表达式。称表达式为为矩阵矩阵 A 的奇异值分解式的奇异值分解式。注意下面的

24、关系式注意下面的关系式即即由此可知由此可知 U 的列向量就是的列向量就是 AHA 的标准正交特征向量；而的标准正交特征向量；而 V 的列向量就是的列向量就是 AAH 的的标准正交特征向量。标准正交特征向量。第51页，此课件共61页哦例例：求下列矩阵的奇异值分解表达式求下列矩阵的奇异值分解表达式解解：（：（1）容易计算容易计算特征值为特征值为5,0，对应的两个标准正交特征向量为，对应的两个标准正交特征向量为第52页，此课件共61页哦由这两个标准正交特征向量组成矩阵，那么有由这两个标准正交特征向量组成矩阵，那么有令令第53页，此课件共61页哦于是可得奇异值分解式为于是可得奇异值分解式为第54页，此

25、课件共61页哦（2）容易计算容易计算，那么，那么 A 的非零奇异值为的非零奇异值为 ，AHA 对应于特征值对应于特征值2，5的标的标准特征向量为准特征向量为由这两个标准正交特征向量组成矩阵，那么有由这两个标准正交特征向量组成矩阵，那么有第55页，此课件共61页哦第56页，此课件共61页哦于是可得奇异值分解式为于是可得奇异值分解式为第57页，此课件共61页哦练习练习：求下面矩阵的奇异值分解式：求下面矩阵的奇异值分解式第58页，此课件共61页哦推论推论：设设 ，是是 A 的的 r 个奇异值，个奇异值，那么存在次酉矩阵那么存在次酉矩阵 使得使得:A=Vr U UrH 其中其中因此可以得到三种满秩分解

26、：因此可以得到三种满秩分解：1.A=(Vr)UrH2.A=Vr(UrH)3.A=(Vr 1/21/2)()(1/21/2UrH)第59页，此课件共61页哦矩阵正交相抵的概念矩阵正交相抵的概念 1.定义定义：设A，BRmn，如果存在m阶正交矩阵U和n阶正交矩阵V，使B=U-1AV，则称A和B正交相抵正交相抵。2.正交相抵是正交相似概念的推广。3.正交相抵是等价关系，它所形成的等价类称为正交相抵等价类 4.正交相抵矩阵有相同的奇异值 5.矩阵A相抵于对角的 阵。第60页，此课件共61页哦矩阵分解的应用矩阵分解的应用1.利用利用SVD性质的满秩分解；性质的满秩分解；2.基于模型的三维形状重建；基于模型的三维形状重建；3.基于基于SVD的图像压缩；的图像压缩；4.基于基于QR分解的参数估计；分解的参数估计；5.矩阵的低秩逼近；矩阵的低秩逼近；6.标准正交变换（标准正交变换（KLT）；）；7.迷向圆变换（标准白化变换）；迷向圆变换（标准白化变换）；8.盲信号分离盲信号分离BSS；9.主分量分析主分量分析PCA；10.Pisarenko谐波分解谐波分解PHD。第61页，此课件共61页哦