第四章矩阵的分解优秀PPT.ppt

第四章 矩阵的分解第一页，本课件共有61页主要内容v三角分解vQR分解v满秩分解v奇异值分解第二页，本课件共有61页Gauss消去法消去法 vGauss消去法的矩阵形式消去法的矩阵形式：求解求解矩阵方程矩阵方程 Ax=b 可采用可采用Gauss主元素消去法。主元素消去法。其其基基本本思思想想是是化化系系数数矩矩阵阵A为为上上三三角角矩矩阵阵，或或化化增增广广矩矩阵阵A|b为上阶梯形矩阵。为上阶梯形矩阵。v这种消去法有三种形式：这种消去法有三种形式：按自然顺序选主元素法，按自然顺序选主元素法，按列选主元素法按列选主元素法总体选主元素法。总体选主元素法。第三页，本课件共有61页步骤步骤1 1：设：设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)；设设第四页，本课件共有61页步步2.2.若若A的的2阶顺序主子式阶顺序主子式 2=a11(0)a22(1)0，令，令ci2=ai2(1)/a22(1),构造构造矩阵矩阵L2=，则，则 计算计算A(2)=L2-1A(1),其其前两列主元以下的元素全为零前两列主元以下的元素全为零；重复上述过程，在步重复上述过程，在步n-1-1后得到的后得到的A(n-1)为上三角阵。为上三角阵。第五页，本课件共有61页第六页，本课件共有61页矩阵三角分解矩阵三角分解v定义：若方阵定义：若方阵A=LU，其中，其中L为下三角矩阵，为下三角矩阵，U为上三角矩阵，为上三角矩阵，则称则称A可以作三角分解或可以作三角分解或LU(LR)分解。若分解。若A=LDU，其中，其中L为为单位下三角矩阵，单位下三角矩阵，U为单位上三角矩阵，为单位上三角矩阵，D为对角矩阵，则称为对角矩阵，则称A可以作可以作LDU分解。分解。v定理：满秩定理：满秩n阶矩阵阶矩阵A可作三角分解的充要条件可作三角分解的充要条件v证明：必要性，设证明：必要性，设 A=LU第七页，本课件共有61页充分性：充分性：对对A的阶数用数学归纳法：的阶数用数学归纳法：n=1:归纳假设：归纳假设：n=k时结论成立时结论成立Lk,Uk可逆可逆当当n=k+1 时时第八页，本课件共有61页定理：定理：A可作三角分解可作三角分解用构造法证明：用构造法证明：第九页，本课件共有61页三角分解的唯一性三角分解的唯一性第十页，本课件共有61页v定理：定理：可作三角分解的充要条件，也是有唯一的可作三角分解的充要条件，也是有唯一的Doolittle分解、唯一的分解、唯一的Crout分解及唯一的分解及唯一的LDU分解的充要条件：分解的充要条件：Doolittle分解分解Crout分解分解第十一页，本课件共有61页证明：可逆可逆可逆可逆可逆可逆可逆可逆第十二页，本课件共有61页再证唯一性。设A有两个LDU分解以 同时左乘上式两边，以 同时右乘上式两边：第十三页，本课件共有61页主元素LU分解v避免由于主对角线元素为0使分解过程无法继续v保证计算精度第十四页，本课件共有61页消元过程消元过程回代过程回代过程矩阵三角分解的应用矩阵三角分解的应用 若矩阵若矩阵A存在三角分解存在三角分解A=LU，则求解线性方程组，则求解线性方程组即可转化为消元过程和回代过程即可转化为消元过程和回代过程第十五页，本课件共有61页Cholesky分解分解v对对于于正正定定实实对对称称矩矩阵阵，其其各各阶阶主主子子式式都都大大于于零零，因此有唯一因此有唯一LDU分解分解 A=LDU=AT=UTDLT 于于是是L=UT，由由正正定定性性知知，D的的每每个个元元素素大大于于零零，因因此存在对角阵此存在对角阵H，使得，使得D=H2，令，令G=LH，则，则A=GGT称此分解为正定实对称矩阵的称此分解为正定实对称矩阵的Cholesky分解分解第十六页，本课件共有61页Cholesky分解算法分解算法(一一)v令令A=(aij)，G-(gij)为下三角矩阵，则由为下三角矩阵，则由A=GGT可得：可得：因此递推公式因此递推公式第十七页，本课件共有61页Cholesky分解算法分解算法(二二)v令令A=(aij)，D=diag(d1,d2,dn)，L-(lij)为下三角矩阵，则由为下三角矩阵，则由A=LDLT 可得：可得：递推公式：递推公式：第十八页，本课件共有61页Cholesky分解的应用例分解的应用例1v自适应有限脉冲响应数字滤波器可表示为则有第十九页，本课件共有61页Cholesky分解的应用例分解的应用例2vAR随机过程参数估计则有第二十页，本课件共有61页分块矩阵的块三角分解分块矩阵的块三角分解 矩阵A 的块LU分解、块LDU分解和块UL分解分别为其中=A22-A21A11-1A12和=A11-A12A22-1A21第二十一页，本课件共有61页分块矩阵的块三角分解分块矩阵的块三角分解 于是有：例：设 ，则有det(Im+AB)=det(In+BA)证明：注：若 ，则有第二十二页，本课件共有61页矩阵的矩阵的QR分解分解 v定义定义：如果实(复)非奇异矩阵A能够化成正交(酉)矩阵Q与实(复)非奇异上三角矩阵R的乘积，即A=QR，则称为A的QR分解分解v矩阵的矩阵的QR分解分解的三个常用方法的三个常用方法：（1）基于G-S正交化；（2）基于Givens旋转；（3）基于Householder变换。第二十三页，本课件共有61页矩阵的矩阵的QR分解分解v定定理理：设A是n阶实(复)非奇异矩阵，则存在正交(酉)矩阵Q和实(复)非奇异上三角矩阵R使A=QR；且除去相差一个对角元素的绝对值(模)全等于1的对角矩阵因子外，QR分解是惟一的 v证明：设A=(1,2,n)，其正交化向量序列为第二十四页，本课件共有61页即第二十五页，本课件共有61页令则A=QR，Q为正交矩阵，R为上三角矩阵。再证唯一性，设有两个Q-R分解：A=QR=Q1R1则由：R1R-1=Q1-1Q，知R1R-1既是上三角矩阵又是正交矩阵，因此必然是对角矩阵，且对角线元素的绝对值为1。第二十六页，本课件共有61页QR分解分解推广定理推广定理 设A是mn列满秩实(复)矩阵，则A有QR分解AQR，其中Q是mn实(复)矩阵，且满足QTQ=I(QHQ=I)，R是n阶实(复)非奇异上三角矩阵该分解除去相差一个对角元素的绝对值(模)全等于1的对角矩阵因子外是唯一的。第二十七页，本课件共有61页v定义定义:设实数c与s满足c2+s2=1，称为Givens矩阵矩阵(初等旋转矩阵初等旋转矩阵)，Givens矩阵确定的线性变换称为Givens变换变换当c2+s2=1时，存在角度，使得ccos，ssin。GivensGivens变换变换ij第二十八页，本课件共有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).当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第二十九页，本课件共有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(2)-1T(1)=T1n(2)T12(2)-1T1n(1)T12(1)=(T12(2)T(T1n(2)T T1n(1)T12(1)是有限个Givens矩阵的乘积 第三十页，本课件共有61页Householder变换变换v定义定义：设单位列向量：设单位列向量u Rn，称，称H=I-2uuT为为Householder矩阵矩阵(初等初等反射矩阵反射矩阵)，由，由Householder矩阵确定的线性变换称为矩阵确定的线性变换称为Householder变变换换(初等反射变换初等反射变换)v对单位向量对单位向量u，及任意与，及任意与u垂直的列向量垂直的列向量w，有，有Hu=(I-2uuT)u=u-2uuTu=-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第三十一页，本课件共有61页Householder变换的性质变换的性质 v定理定理：任意给定非零列向量：任意给定非零列向量x Rn(n1)及单位列向量及单位列向量z Rn，则存，则存在在Houscholder矩阵矩阵H，使得，使得Hx=|x|z。v证明：令证明：令 定义矩阵定义矩阵H=I-2uuT，则有，则有ux|x|z第三十二页，本课件共有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初等反射矩阵不能由若干个初等旋转矩阵的乘积表示初等反射矩阵不能由若干个初等旋转矩阵的乘积表示 第三十三页，本课件共有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)=第三十四页，本课件共有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也是正交矩阵。第三十五页，本课件共有61页基于基于Householder变换变换的的QR分解分解定理定理：任何n阶实非奇异矩阵A(aij)可通过左连乘Househoulder矩阵化为上三角矩阵。算法算法：类同基于Givens旋转的QR分解，仅需用Hi取代相应的Ti(i=1,2,n-2)，并把T换成 Hi=In+1-I-uuT是n+1-i阶Househoulder矩阵，使得 都是n阶Househoulder矩阵。因此，S是有限个Househoulder矩阵的乘积，必是正交矩阵。第三十六页，本课件共有61页定理定理：设：设 为任意矩阵，则存在为任意矩阵，则存在使得使得其中其中 B 为列满秩矩阵，为列满秩矩阵，C为行满秩矩阵为行满秩矩阵(我们称此分解为我们称此分解为矩阵的满矩阵的满秩分解秩分解)。证明证明：假设矩阵：假设矩阵 A 的前的前 r 个列向量是线性无关的，对矩阵个列向量是线性无关的，对矩阵 A 只实施初等变行换可以将其化成只实施初等变行换可以将其化成矩阵的满秩分解矩阵的满秩分解第三十七页，本课件共有61页即存在即存在 使得使得于是有于是有其中其中 如果如果 A 的前的前 r 列线性相关，那么只需对列线性相关，那么只需对 A 作初等列变换作初等列变换(只需只需做交换两列的变换做交换两列的变换)使得前使得前 r 个列是线性无关的。然后重复上面的过程个列是线性无关的。然后重复上面的过程即可。这样存在即可。这样存在A=Ar,An-r=B,BD第三十八页，本课件共有61页 从而从而且满足且满足其中其中第三十九页，本课件共有61页例例 分别求下面三个矩阵的满秩分解分别求下面三个矩阵的满秩分解解解 （1）对此矩阵只实施初等行变换可以得到对此矩阵只实施初等行变换可以得到 第四十页，本课件共有61页由此可知由此可知 rank(A)=2，且该矩阵第一列，第三列是线性无关的。选，且该矩阵第一列，第三列是线性无关的。选取取第四十一页，本课件共有61页（2）对此矩阵只实施初等行变换可以得到对此矩阵只实施初等行变换可以得到所以所以 rank(A)=1，且此矩阵的第三，第四，第五列任意一列都是线性，且此矩阵的第三，第四，第五列任意一列都是线性无关的，所以选取哪一列构成列满秩矩阵均可以。无关的，所以选取哪一列构成列满秩矩阵均可以。选取选取也可以选取也可以选取第四十二页，本课件共有61页（3）对此矩阵只实施初等行变换可以得到对此矩阵只实施初等行变换可以得到 所以所以rank(A)=2，且容易看出此矩阵的第二列和第四列是线性无关的，且容易看出此矩阵的第二列和第四列是线性无关的，选取选取第四十三页，本课件共有61页 由上述例子可以看出由上述例子可以看出矩阵的满秩分解形式并不唯一矩阵的满秩分解形式并不唯一。一般一般地我们选取阶梯型矩阵主元所在的列对应的列向量构成列满地我们选取阶梯型矩阵主元所在的列对应的列向量构成列满秩矩阵，将阶梯型矩阵全为零的行去掉后即可构成行满秩矩秩矩阵，将阶梯型矩阵全为零的行去掉后即可构成行满秩矩阵。阵。但是不同的分解形式之间有如下联系：但是不同的分解形式之间有如下联系：定理定理：如果：如果 A=BC=B1C1 均为矩阵均为矩阵 A 的满秩分解，那么的满秩分解，那么（1）存在矩阵）存在矩阵 满足满足（2）第四十四页，本课件共有61页引理引理 1：对于任何一个矩阵对于任何一个矩阵 A 都有都有引理引理 2：对于任何一个矩阵对于任何一个矩阵 A 都有都有 AAH 与与 AHA 都是半正定的都是半正定的Hermite-矩阵。矩阵。设设 ，i是是 AAH 的特征值，的特征值，i i是是AHA 的特征值，它们的特征值，它们都是实数。如果记都是实数。如果记矩阵的奇异值分解矩阵的奇异值分解第四十五页，本课件共有61页特征值特征值i与与i之间有如下关系。之间有如下关系。定理定理：设：设 ，那么，那么同时，我们称同时，我们称为矩阵为矩阵A的的正奇异值正奇异值，简称，简称奇异值奇异值。例例 求下列矩阵的奇异值求下列矩阵的奇异值第四十六页，本课件共有61页解解 （1）由于）由于显然显然 AAH 的特征值为的特征值为5，0，0，所以，所以 A 的奇异值为的奇异值为 （2）由于）由于显然显然 AAH 的特征值为的特征值为 2，4，所以，所以 A 的奇异值为的奇异值为 。第四十七页，本课件共有61页定理定理 设设 ，是是 A 的的 r 个奇异值，那么存在个奇异值，那么存在 m 阶酉矩阵阶酉矩阵 V 和和 n 阶酉矩阵阶酉矩阵 U 使得使得其中其中第四十八页，本课件共有61页证明证明：由于由于 rank(A)=r，所以，所以 AHA 的特征值为的特征值为因为因为 AHA 是一个共轭对称阵，所以存在是一个共轭对称阵，所以存在 n 阶酉矩阵阶酉矩阵 U 满足满足将酉矩阵将酉矩阵 U 按列进行分块，记按列进行分块，记 U=U1,U2，其中，其中于是有于是有第四十九页，本课件共有61页从而有从而有记记 ，则有，则有 选取选取 使得使得 是酉矩阵，则是酉矩阵，则 由上述式子可得由上述式子可得第五十页，本课件共有61页这里，要注意这里，要注意 。（证完）。（证完）我们称此定理为我们称此定理为奇异值分解定理奇异值分解定理。称表达式。称表达式为为矩阵矩阵 A 的奇异值分解式的奇异值分解式。注意下面的关系式注意下面的关系式即即由此可知由此可知 U 的列向量就是的列向量就是 AHA 的标准正交特征向量；而的标准正交特征向量；而 V 的列向量就是的列向量就是 AAH 的标准正交特征向量。的标准正交特征向量。第五十一页，本课件共有61页例例：求下列矩阵的奇异值分解表达式求下列矩阵的奇异值分解表达式解解：（：（1）容易计算容易计算特征值为特征值为5,0，对应的两个标准正交特征向量为，对应的两个标准正交特征向量为第五十二页，本课件共有61页由这两个标准正交特征向量组成矩阵，那么有由这两个标准正交特征向量组成矩阵，那么有令令第五十三页，本课件共有61页于是可得奇异值分解式为于是可得奇异值分解式为第五十四页，本课件共有61页（2）容易计算容易计算，那么，那么 A 的非零奇异值为的非零奇异值为 ，AHA 对应于特征值对应于特征值2，5的标的标准特征向量为准特征向量为由这两个标准正交特征向量组成矩阵，那么有由这两个标准正交特征向量组成矩阵，那么有第五十五页，本课件共有61页第五十六页，本课件共有61页于是可得奇异值分解式为于是可得奇异值分解式为第五十七页，本课件共有61页练习练习：求下面矩阵的奇异值分解式：求下面矩阵的奇异值分解式第五十八页，本课件共有61页推论推论：设设 ，是是 A 的的 r 个奇异值，个奇异值，那么存在次酉矩阵那么存在次酉矩阵 使得使得:A=Vr U UrH 其中其中因此可以得到三种满秩分解：因此可以得到三种满秩分解：1.A=(Vr)UrH2.A=Vr(UrH)3.A=(Vr 1/21/2)()(1/21/2UrH)第五十九页，本课件共有61页矩阵正交相抵的概念矩阵正交相抵的概念 1.定义定义：设A，BRmn，如果存在m阶正交矩阵U和n阶正交矩阵V，使B=U-1AV，则称A和B正交相正交相抵抵。2.正交相抵是正交相似概念的推广。3.正交相抵是等价关系，它所形成的等价类称为正交相抵等价类 4.正交相抵矩阵有相同的奇异值 5.矩阵A相抵于对角的 阵。第六十页，本课件共有61页矩阵分解的应用矩阵分解的应用1.利用利用SVD性质的满秩分解；性质的满秩分解；2.基于模型的三维形状重建；基于模型的三维形状重建；3.基于基于SVD的图像压缩；的图像压缩；4.基于基于QR分解的参数估计；分解的参数估计；5.矩阵的低秩逼近；矩阵的低秩逼近；6.标准正交变换（标准正交变换（KLT）；）；7.迷向圆变换（标准白化变换）；迷向圆变换（标准白化变换）；8.盲信号分离盲信号分离BSS；9.主分量分析主分量分析PCA；10.Pisarenko谐波分解谐波分解PHD。第六十一页，本课件共有61页