12 矩阵的QR分解.docx

12 矩阵的QR分解第十一讲 矩阵的QR分解 一、Givens矩阵与Givens变换 1. 定义：设实数c与s满足c2+s2=1，称 é1êêêêêêêTij=êêêêêêêêëùúúúú(i)úúúúúúú(j)úúú 1úûO1c1MO1-sLc1OMLsij(i<j) 为Givens矩阵，也记作Tij=Tij(c,s). 由Givens矩阵所确定的线性变换称为Givens变换. 说明：实数c+s=1，故存在q，使 22c=cosq,s=sinq. y=Tijx中Tij确定了将向量x变成y的一种变换，正是écosqy=êë-sinqGivens变换. 二阶情况下，sinqùúx 确定的正是平面直角坐标系中cosqû绕原点的一个旋转变换. 以上实Givens矩阵也可推广成为复初等旋转矩阵. Tiké1êêêêêêê=êêêêêêêêëO1cejq1jq2L1seMjq3O1Mjq4-seLce1Oùúúúú(i)úúúúúúú(k)úúú 1úûi22kq1,q2,q3,q4为其中c与s仍为满足c+s=1的实数，实角度，j=-1. 2j(q1+q4)显然，det(Uik)=ce+se2j(q2+q3)； ； 当q1+q4=q2+q3时，det(Uik)=ej(q1+q4)当q1+q4=q2+q3=2np时，det(Uik)=1. 2. 性质 ùT(c,s)éijëû-1ù=éT(c,s)ijëûT=Tij(c,-s), -s=-sin(q)=sin(-q),，detéTc,s()ijëû设x=éëx1,x2,L,xnùû， y=Tijx=éëh1,Th2,L,hnùû，则有 Tìhi=cxi+sxjï íhj=-sxi+cxjï(k¹i,j)îhk=xk当x+x¹0时，总可以选c=2i2jxix+x2i2j，s=xjx+x2i2jìh=x2+x2ïiij，使í ïîhj=0®Tijx= éx,L,x,i-1ë1x+x2i2j,xi+1,L,xj-1,0,xj+1,L,xnùûTT定理1 设x=éëx1,x2,L,xnùû¹0，则存在有限个Givens矩阵的乘积T，使得Tx=xe1. 说明：x=x=xHx22=xx (x为实向量时)；Tx； Te1=1,0,0,L,0. 证：先考虑x1¹0的情形： 构造T12(c,s):c=x1x1+x222,s=x2x1+x2T22， T12x=éx12+x22,0,x3,x4,L,xnù. ëû对T12x再考虑 T13(c,s):c=x1+x222222,s=x3x1+x2+x3222， Tx1+x2+x3222éT13T12x=x1+x2+x3,ë0,0,x4,L,xnù û依此类推，构造 T1k(c,s):c=x1+L+xk22222, x1+x2+L+xks=xkx+x+L+x21222k， T1k(T1,k-1LT13T12x) 222é=x1+x2+L+xk,ë0,0,L0,xk+1,L,xnùûT 直至k=n. 令T=T1nT1,n-1LT12，则有 222éTx=x1+x2+Lxn,ë0,0,L,0ù=xe1 . ûT再考虑x1=0的情形： 若x1=x2=L=xk-1=0,xk¹0(1<k£n) ， 则从第一个不为零的xk开始运用上述方法即可. 证毕 . 推论：对于任何非零列向量xÎRn及任何单位列向量z(z=1)，均存在着有限个Givens矩阵的乘积T，使Tx=xz. 证：由上述定理，对x存在有限个Givens矩阵T(1)12,T(1)13,L,T(1)1n(1)1n的乘积 LT(1)13T(1)=TT(1)1,n-1T(1)12，使 T(1)x=xe1 . (2)(2)(2)对z同理存在有限个Givens矩阵T12,T13,L,T1n的乘积 T(2)=T(2)1nT(2)1,n-1LT(2)13T(2)12，使T(2)(2)z=ze1=e1 ， ÞTÞT(1)x=xe1=xT(2)z=T(xz) (2)-1T(1)x=xz， (2)1,n-1即 (TT(2)1nLT(2)12)(T-1(1)1nT(1)1,n-1LT(1)12)x=xz 其中 (T(2)1nT(2)1n-1LT213(2)12)(T(21n-1(1)1n-1T(1)1n-1LT(1)(1)12) (1)=T=T212)(T-1T)-1LTT)T1nT1n-1LT12 T(1)(2)12)(T)(2)13LT(2)1n)T(1)1nT(1)1n-1LT(1)12为有限个Givens矩阵的乘积. 证毕. 例1. 用Givens变换将向量x=(1,-3,5)变换为与e1=(1,0,0)T同方向. 解：对x构造T12(c,s):c=T12x=(10,0,5)， T110,s=-310，则 对T12x构造T13(c,s):c=T13(T12x)=(35,0,0) T1035,s=535，则 于是 é10êê35=ê0ê5ê-ê35ë01053501035éùêúêúêúêúêúêúûêë1103100-3101100ù0úúú0 úú1úúûT=T13T12éêêê=êêê-êë1353105350-33511015350ùú35úú0ú ú10ú35úû5Tx=35e1. 例2. 用Givens变换将向量x=(2,3,0,5)变换为与e1=(1,0,0,0)同方向. T解：对x构造T12(c,s):c=T12x=(13,0,0,5)， T213,s=313，则 对T12x构造T14(c,s):c=T14(T12x)=(38,0,0,0) T1338,s=538，则 于是 T=T14T12éêêê=êêêê-êë13380053801000010ùéúê38úê0úêúê-0úê13úêúê38úûë521331300313213000010ù0úúú0úú0ú1úûéêêê-ê=êêêê-ë238313010494-3382130154940010ùú38úú0ú ú0ú13úú38û5Tx=38e1. 二、 QR分解 1. 定义：如果实非奇异矩阵A可化为正交矩阵Q与实非奇异上三角矩阵R的乘积，即A=QR，则称上式为A的QR分解. 2. 求QR分解的方法 Gram-schmidt正交化方法: 定理2. 设A是n阶非奇异矩阵，则存在正交矩阵Q与实非奇异上三角矩阵R使得A=QR，且除去相差一个对角元素的绝对值全为1的对角因子外，上述分解唯一. 证：设A记为A=éëa1,a2,L,anùû，由A非奇异Þa1,a2,L,an线性无关. 采用Gram-schmidt正交化方法将它们正交化： 先对a1,a2,L,an正交化，可得 ìb1=a1ïïb2=a2-k21b1ï íb3=a3-k31b1-k32b2ïLLïïîbn=an-kn1b1-kn2b2-L-kn,n-1bn-1其中 ai,ak=(j)ij(j<i)b , j,bj) (bi,bj)=0,i¹j 将上式改写为 ìa=bï11ïa=kï221b1+b2ía3=k31b1+k32b2+b3ïïMïîan=kn1b1+kn2b2+L+kn,n-1bn-1+bn 再对b1,b2,L,bn单位化，可得 qi=1bbi(i=1,2,L,n)，即 bi=biqii用矩阵形式表示为 . é1k21Lkn1ùêéëa1a2Lanùû=éëb1b12Lbnùûêêêë=éëb1b2LbnùûCébê1=éëq1q2Lqêb2nùûêOêêë=QR其中 Q=éëq1q2Lqnùû, R=(diagéëb1b2Lbnùû)×C Q是正交矩阵 R是实上三角矩阵 唯一性: 采用反证法。 设存在两个QR分解，A=QR=Q1R1，则Lkún2úOMúkúnn-1ûùúúúCbúnúûQ=Q1R1R-1=Q1D 式中D=R1R-1仍为实非奇异上三角矩阵. 于是 I=QQ=(Q1D)THT(Q1D)=HDT(QT1Q1D=DD H)TÞD为正交矩阵. 于是 éa11êD=êêêëa12a22LLOa1nùúaij=0ìa2nïú í2Múïîaij=1úannû(i<j)(i=j)故，D只能为对角阵，且D是对角元素绝对值全为1的对角阵. 这一证明方法可推广为： 定理3. 设A是m´n的实矩阵，且其n个列线性无关，则A具有分解 A=QR 其中Q是m´n实矩阵，且满足QQ=I(QQ=I)，R是n阶实非奇异上三角TH矩阵. 该分解除了相差一个对角元素的绝对值全为1的对角矩阵因子外，上述分解唯一. 例3. 使用Schmidt正交化方法求矩阵 é1êA=2êêë12122ùú2 ú1úû的QR分解. 解：令a1=(1,2,1),a2=(2,1,2),a3=(2,2,1), TTTé1êA=2êêë12122ùú2=(a1,a2,a3)， ú1úû 先正交化： b1=a1， æ2öæ1öæ1ö(a2,b1)ç÷6ç÷ç÷b2=a2-b1=1-2=-1ç÷6ç÷ç÷ (b1,b1)ç2÷ç1÷ç1÷èøèøèø=a2-b1b3=a3-(a3,b1)(b1,b1)b1-(a3,b2)(b2,b2)b2 æ1æ2öæ1öæ1öç2ç÷7ç÷1ç÷ç=2-2-1=ç0ç÷6ç÷3ç÷ç1÷ç1÷ç1÷ç1èøèøèøç-è2ö÷÷÷ ÷÷ø=a3-76b1-13b2 æ1öç÷6ç÷11ç2÷b1=b1=ç在单位化：q1= ÷|b1|66ç÷ç1÷ç÷è6øæ1ç3ç111çq2=b2=b2=ç-|b2|33çç1çè3æçç11q3=b3=b3=ç|b3|2ççç-è1ö÷÷÷÷， ÷÷÷øö÷2÷0÷ 1÷÷÷2ø于是 a1=b1，a2=b1+b2，a3=76b1+13b2+b3， b1=6q1,b2=3q2,b3=2q3 éê11êA=(a1,a2,a3)=(b1,b2,bê3)ê01êê00êëé7ùê11ê6ú=(6q1ú1,3q2qêú2,3)ê01ê3ú ê001úêúëúûéé1ê60ùê10úê=(q1,q2,q3)ê030úê1êê0êë002úúûêê00êë7ù6ú1úú3ú 1úúúû7ù6ú1úú3ú 1úúúûé1ê6êê2=ê6êê113-131ùéúê62úêúê00úêúê1úê0-16307ùú6ú1ú 3úú2úêë6é1êê6Q=ê2êê6ê1êë6313-13132úûëê1ù2úú0úú，-1úú2úûéê6êR=êê0êê0êëúû67ù6ú1ú3ú3ú. ú02úúû