矩阵分析课件chapt4 矩阵分解例题详解.doc

第4章 矩阵分解(I)高斯消去法 假设矩阵A 的顺序主子式0 (i=1,n),则我们可以进行以下的顺序消元过程1消元过程 等价于用初等矩阵分别左乘和，即 (1)其中，,我们称为消元因子，为主元素；消元过程的一个重要性质是：消元过程不改变矩阵的主子矩阵的行列式(主子式)的值。例,顺序主子式为，1，5，-10,顺序主子式为，1，5，-10，顺序主子式为，1，5，-10引理：约化的主元素0的充要条件是矩阵A 的顺序主子式0 (i=1,k);推论：若矩阵A 的顺序主子式0 (i=1,k)，则，；由此有若A对称正定或严格对角占优，而它们的顺序主子矩阵也是对称正定或严格对角占优，从而顺序主子式不为0，顺序高斯消去过程可进行；2.回代过程：设， , 用高斯消去法解线性方程Ax=b.增广矩阵为 ，因此，问题的解为 3. 数值稳定性1)选列主元 ；2)选全主元；3)高斯若当(Gauss-Jordan)消去法，求矩阵的逆;, 求A-1.增广矩阵为 从而4高斯顺序消元法解方程的计算量1)乘除次数：2)加减次数：3)求矩阵的逆的计算量为o()(II) 顺序消元过程与矩阵的三角分解(1) (2) 若 则有 ，从而，(3) 由有 故有 A=LU，其中.这时L为单位下三角矩阵。矩阵的三角分解 A=(a1,a2,an)=PR=(p1,p2,pn)R(a) LU分解(Doolittle分解)(1) 存在唯一的条件;(顺序主子式不为0)(2) 公式推导;(矩阵乘法)定义4.1 如果方阵A可分解成一个下三角矩阵L和一个上三角矩阵U的乘积，则称A可作三角分解. 如果方阵A可分解成A=LDU,其中L为一个单位下三角矩阵，D为对角矩阵，U是一个单位上三角矩阵。推论：若矩阵A 的顺序主子式Dk0 (k=1,n-1)，则A可唯一分解为A=LDU, 其中L为一个单位下三角矩阵，D为对角矩阵，U是一个单位上三角矩阵。dk=Dk/Dk-1 (D0=1)。定理4.2 设A是n阶非奇异矩阵，则存在置换矩阵P使得PA=LDU, 其中L为一个单位下三角矩阵，D为对角矩阵，U是一个单位上三角矩阵。定义4.2 设A存在唯一的LDU分解.若把A=LDU中的D和U结合起来，并且用U表示，则得到唯一的LU分解 A=LU称为Doolittle分解；若把A=LDU中的L和D结合成L，就得到A=LU称为Crout分解。LU分解的公式：lik=aik-(li1u1k+li,k-1uk-1,k)ukj= akj-(lk1u1j+lk,k-1uk-1,j)/lkkCrout分解类似。(b)平方根法(1)对称矩阵的三角分解定理； (2)对称正定矩阵的三角分解(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 初等旋转矩阵(Givens变换)是两个初等反射矩阵(Householder变换)的乘积。证明：对初等旋转矩阵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 直接计算可得 Tij=HvHu从平面上看，我们可以得出 x Hq(a)= p+2q-a u 其中H=I -2uuT y q x为变换前的任意向量，用它与正半实轴的夹角a表示。 y为变换后的向量， 用它与正半实轴的夹角表示为p+2q-a。 y x q aGq(a)=q+a其中，q为旋转角度；x为变换前的任意向量，用它与正半实轴的夹角a表示； y为变换后的向量， 用它与正半实轴的夹角表示为 q+a。我们需要证明的目标就是找到两个向量u1和u2使得它们对应的Householder变换的乘积等于给定的一个旋转变换Gq(a)。根据前面的讨论我们对于H变换和G变换都可以用向量的角度表示。因此有 Hq2Hq1(a)=p+2q2-(p+2q1-a)=2(q2-q1)+a =q+a= Gq(a) l1可见q =2(q2-q1)成立即可。 x 这个等式在几何成立的意思： H(u1)x u2 x和H(u2)H(u1)x之间的夹角等于二倍的 l2 u1 u1和u2之间的夹角。这在几何上是显然的。因为u1对应的垂线l1平分x和H(u1)x的夹角； H(u2)H(u1)x 同样，因为u2对应的垂线l2平分H(u1)x和H(u2)H(u1)x的夹角。注意到l1和l2的夹角和向量u1和u2的夹角相等。因此结论是显然的。 换句话说，对于给定的旋转变换，仅需找到夹角为旋转角度的二分之一的两个向量，用它们作反射变换，就可以得到旋转变换。矩阵QR(正交三角)分解定义4.6 如果实(复)矩阵A能够化成正交矩阵Q与实(复)非奇异上三角矩阵R的乘积，即 A=QR则称为A的QR分解。定理4.6 设A是n 阶实(复)非奇异矩阵，则存在正交(酉)矩阵Q与实(复)非奇异上三角矩阵R使得 A=QR且除去相差一个对角元素的绝对值(模)全等于1的对角矩阵外，分解唯一。即QR分解存在唯一。证明：存在性：使用Gram-schmidt正交化过程。唯一性：A=QR=Q1R1从而P=(Q1)TQ=R-1R1注意到I=PTP所以P-1=PT,而P为上三角矩阵，其逆也为上三角矩阵，而PT为下三角矩阵， 从而P为对角矩阵.又P2=I，所以P的对角元只能为正负1。Q= Q1P, R= P R1.定理4.7 设A是mn实(复)矩阵，且其n个列线性无关，则A有分解 A=QR其中Q是mn实(复)矩阵，且满足QTQ=I, R是实(复)非奇异上三角矩阵R且除去相差一个对角元素的绝对值(模)全等于1的对角矩阵外，分解唯一。定理 任何n阶实非奇异矩阵A可通过左连乘初等Givens旋转矩阵化为上三角矩阵。定理4.10 任何n阶实非奇异矩阵A可通过左连乘Householder矩阵化为上三角矩阵。定义4.7如果矩阵A的次对角线以下元素全为零，则称A为上Hessenberg矩阵；定理4.11： 任何实方正A都可以通过初等旋转变换正交相似与上Hessenberg矩阵。定理4.12任何实方正A都可以通过初等反射变换正交相似与上Hessenberg矩阵。推论：任何实对称矩阵A都可以通过初等旋转变换(或初等反射变换)正交相似于实对称三对角矩阵。思考题：任何正交矩阵Q是否存在特征值互不相同的对称(角)矩阵A(D)和三对角矩阵T使得AQ=QT 或 DQ=QT?其中要求T的次对角线的所有元素都不为零。这就是特征值的反问题：已知Q求D和T使得DQ=QT.例如 单位矩阵Q=I就不存在，那么存在的条件是什么？在信号处理中，我们一般使用的都是哪些存在T的正交矩阵Q对应的正交变换，为什么？Fourier 变换，小波变换都存在。这和所谓信号的频率有关。一般说来，Q的列按频率由低到高排列。4.3 矩阵的满秩分解复习矩阵的秩的概念和性质定义:矩阵行或列向量的最大线性无关组的个数。思考题：证明矩阵的行秩和列秩相等。性质：rank(AB) min (rank(A),rank(B)定义4.8 设A(r0),如果存在矩阵F和 G使得 A=FG 则称为A的满秩分解。当A为行满秩或列满秩矩阵时，A可分解为一个因子为单位矩阵，另一个为A本身，称为平凡分解。定理：设A则A的满秩分解存在。证明过程即为构造过程。证明：设A=(a1,a2,an), 取A的列向量组的一个极大线性无关组，不妨设为ai1,ai2,air, 则对于A的任意i列ai可以表示为ai1,ai2,air的线性组合。即 ai=g1iai1+ g2iai2+ griair, i=1,2,n写成矩阵形式有A=FG其中F=( ai1,ai2,air), G=(g1,g2,gn), gi=(g1i, g2i, gri)T,显然F为列满秩的矩阵，G为行满秩的矩阵(为什么？)。注:满秩分解不唯一。定义4.9 Hermite标准形， B满足1)B的前r行中每一行至少含一个非零元素，且第一个非零元素是1，而后m-r个元素为0；2)若B中第i行的第一个非零元素1在第ji列(i=1,2,r),则 j1j20), 则必有分解A=QR.其中,Q为m r矩阵， QHQ=I, 而R为r n矩阵，它的行线性无关。证明：作A的满秩分解A=FG其中F，G.由矩阵的QR分解定理有F=QR1其中Q为m r矩阵， QHQ=I, 而R1为r阶非奇异矩阵。于是 A= FG = QR1G =QR.这里R=R1G,它的r个行线性无关。定理(习题4.3,第4题). 设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 (实际为习题4.3 第2题)这需要证明FHF为满秩矩阵。仅需证明对任意xCr,若 FHFx =0 则 x =0 即可。事实上， 由FHFx =0可得xHFHFx=0,从而|Fx|=0,根据范数定义， Fx=0；再由F为列满秩矩阵，可得x=0。这样证明了。思考题: 设F，G， 则rank(GF)= r成立吗？若是，证明之；若否，研究成立的条件是什么？下面利用满秩分解讨论线性方程组求解。Ax= b,设A的满秩分解为A=FG， 方程变为FGx=b.则若bR(F), 则存在相容解。若bR(F), 则不存在相容解，这时我们可以将b投影到R(F)得到b=F(FHF)-1FHb b R(F) b这时方程求解的实际就是所谓最小二乘解。如果这样方程组变为Gx=(FHF)-1FHb.由于G的秩为r 因此方程组Gx=(FHF)-1FHb肯定有解。如果G不为方阵，则解不惟一。这时需要求解所谓最小范数解。即 x= GH(GGH)-1(FHF)-1FHb这就是所谓最小范数最小二乘解。10个随机逼近点，y= x2+r, 其中r为-0.1,0.1之间均匀分布的随机数。根据模型y=ax2+bx+c,利用最小二乘解得到的逼近结果。红线所在点为逼近点蓝线为y= x2，绿线为求得的逼近解。20个随机逼近点，y= x2+r, 其中r为-0.1,0.1之间均匀分布的随机数。根据模型y=ax2+bx+c,利用最小二乘解得到的逼近结果。红线所在点为逼近点蓝线为y= x2，绿线为求得的逼近解。4.4 矩阵的奇异值分解1.矩阵的正交对角分解我们知道实对称矩阵A或Hermite矩阵A都可正交相似于对角矩阵, 即 A=QHDQ由定理4.12 任何实方阵A都可以正交相似于上Hessenberg 矩阵。 即 A=QTHQ定理：对于任何非奇异的实方阵，存在正交矩阵P和Q使得PTAQ为正对角矩阵D。即A=PDQT证明: 由于A非奇异，因此ATA为实对称矩阵。于是存在正交矩阵Q使得 QT(ATA)Q=D,D为对角矩阵,其对角元为ATA的特征值,它们大于0.因此记 P=AQD1/2, 易验证PTP=I且A= PD1/2Q.2矩阵的奇异值分解基本事实：1.设A(r0),则AHA是Hermite 矩阵，且其特征值非负。2. rank(A)=rank(AHA)3. 设A，则A=0的充要条件为AHA=0.定义: 设A，A的奇异值为AHA的特征值的非负平方根。定理4.16 设A，则存在m阶酉矩阵U和n阶酉矩阵V使得UHAV=, 其中S=diag(s1,s2,sr),而si为矩阵A的全部非零奇异值。或者写为 A=UVH称为A的奇异值分解。证明过程略。显然由证明过程可见，若A为实矩阵，则定理4.16中U和V都可以为正交矩阵。例4.15 设矩阵A=UVH，则U的列是AAH的特征向量， V的列为AHA的特征向量。反之不一定对，即设U的列是AAH的特征向量，V的列为AHA的特征向量。那么UVH =A不一定成立。定理4.17 在奇异值分解A=UVH,设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 (广义谱分解)。奇异值分解的统计意义：若x一个均值为0的n维随机向量，A的每一行表示它的一次抽样，则AHA的i行j 列表示随机向量x的在m次独立抽样基础上对相关矩阵的一个无偏估计。如果对随机向量x进行线性变换y=Vx则随机向量y在m次独立抽样基础上对相关矩阵的一