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