第二节QR分解学习教案

会计学1第二节第二节QR分解分解(fnji)第一页，共32页。由于由于x 1,x 2, ,x n x 1,x 2, ,x n 线性无关线性无关(wgun)(wgun)，将它们用，将它们用SchmidtSchmidt正交正交证明证明设设A A是一个实满秩矩阵是一个实满秩矩阵, A, A的的n n个列向量为个列向量为 x x 1 1, ,x x 2 2, , , ,x x n n 定义定义:设设.nnCA如果存在如果存在n阶酉矩阵阶酉矩阵Q和和n阶上三角矩阵阶上三角矩阵R R，使得，使得QRA 则称之为则称之为A A的的QRQR分解或酉三角分解分解或酉三角分解当当 时，则称为时，则称为A的正三角分解的正三角分解nnRA化方法得标准正交向量化方法得标准正交向量e e 1 1, ,e e 2 2, , , ,e e n n第1页/共32页第二页，共32页。nnnnnnebebebxebebxebx221122211221111其中其中nibii, 2 , 1,0从而从而(cng r)有有nnnnnnbbbbbbeeexxx222112112121第2页/共32页第三页，共32页。nnnnnbbbbbbReeeQ2221121121,令令IQQT则则则则如果如果再证唯一性再证唯一性,11RQQRA由此得由此得DQRRQQ1111式中式中D=R1R-1D=R1R-1仍为具有正对角仍为具有正对角(du jio)(du jio)元的上三角矩阵。由于元的上三角矩阵。由于 DDDQDQQQITTT11即即D D为正交矩阵，因此为正交矩阵，因此(ync)D(ync)D为单位矩阵（正规上三角为对角阵）为单位矩阵（正规上三角为对角阵）故故RDRRQDQQ111,第3页/共32页第四页，共32页。说明：说明：1若不要求若不要求R具有正对角元，则具有正对角元，则A的不同的不同(b tn)QR分解仅在正交矩阵的列和上三角矩阵分解仅在正交矩阵的列和上三角矩阵R的对应行相差模为的对应行相差模为1的因子。的因子。该定理的证明过程给出了利用该定理的证明过程给出了利用(lyng)Schmidt(lyng)Schmidt正交化方法求可逆矩阵正交化方法求可逆矩阵QRQR分解的方法。分解的方法。例例 求矩阵求矩阵(j zhn)A(j zhn)A的的QRQR分解分解110201221A解解，则，则记记122,102,011321xxx2 2若若A A为满秩复矩阵，则存在酉矩阵为满秩复矩阵，则存在酉矩阵Q Q与复非奇异上三角矩阵与复非奇异上三角矩阵R R，使，使A = QR A = QR 第4页/共32页第五页，共32页。TyyyxyyyxTyyyxyyxyyxyyxyxyxy2 , 1 , 121 , 1, 131231132),(),(1),(),(33121),(),(2211222311131112将将 正交化正交化321,xxxTyyTyyTyyeee2 , 1 , 11 , 1, 10 , 1 , 1663332221332211单位化单位化第5页/共32页第六页，共32页。336233132121122322eeexeexex整理整理(zhngl)得得,03633663322663322Q令令363300302222RQRA 则则第6页/共32页第七页，共32页。例例1 1：利用：利用SchmidtSchmidt正交化方法正交化方法(fngf)(fngf)求矩阵的求矩阵的QRQR分解分解212240130A设设,2 , 2, 1,1 , 4 , 3,2 , 0 , 0321TTTxxx则则 321,xxx线性无关，首先线性无关，首先(shuxin)将它们正交化得：将它们正交化得：,2 , 0 , 011Txy1),(),(221112yxyyyyx2),(),(1),(),(3322231113yyxyyyyxyyyxTyyx0 ,56,5851213Tyx0 , 4 , 31212再单位再单位(dnwi)化：化：,1 , 0 , 02111Tye,0 ,54,535122Tye第7页/共32页第八页，共32页。,0 ,53,542133Tye于是于是(ysh)：1112eyx21212521eeyyx32132132251eeeyyyx从而从而(cng r) QRA00153540545302150212,1 , 0 , 02111Tye,0 ,54,535122Tye第8页/共32页第九页，共32页。O+OTIHR2)(3)(H则则记记即：该变换将向量即：该变换将向量 变成了以变成了以 为法向量的平面的对称向量为法向量的平面的对称向量 。HouseholderHouseholder变换又称为反射变换或镜像变换，有明变换又称为反射变换或镜像变换，有明显的几何意义。在显的几何意义。在 中，给定一个向量中，给定一个向量 ，令，令 表示表示 关于平面关于平面 （以（以 为法向量）为法向量）的反射变换所得像，的反射变换所得像，如图所示，如图所示，3R第9页/共32页第十页，共32页。定义定义 设设 是一个单位向量，令是一个单位向量，令nCHIH2)(则称则称H H是一个是一个(y )Householder(y )Householder矩阵或矩阵或HouseholderHouseholder变换。变换。性质设性质设H H是一个是一个(y )Householder(y )Householder矩阵，则矩阵，则（1 1）H H是是HermiteHermite矩阵，矩阵， ；（2 2）H H是酉矩阵，是酉矩阵， ；（3 3）H H是对合矩阵，是对合矩阵， ；（4 4）H H是自逆矩阵是自逆矩阵（5 5）diagdiag( (I I, ,H H ) ) 也是一个也是一个HouseholderHouseholder矩阵矩阵; ;（6 6）det Hdet H = -1 = -1。HHHIHHHIH2HH1第10页/共32页第十一页，共32页。其中其中(qzhng) (qzhng) 为实数。为实数。定理定理 设设 是一个是一个(y )(y )单位向量，则对于任意的单位向量，则对于任意的nCu nCxauHx uaxxaH,2nC当当 时，取单位向量时，取单位向量 使使0 auxnC0 xHauxxxxIxHHH)(22)(存在存在(cnzi)Householder(cnzi)Householder矩阵矩阵H H，使得，使得证明证明 当当x=0 x=0时，任取单位向量时，任取单位向量则则则则002)(HIxH第11页/共32页第十二页，共32页。所以所以(suy) (suy) 当当 时，取时，取aux ,2auxauxxauxauxauxIxIxHHT22)(22)(uuaxuauaxxxauxauxHHHHH2)()(由于由于(yuy)(yuy)auauxauxauxxauxxxHHH)()()()(2)()()()()(2auxauxauxxauxxHHxauxxuaxxxxuauaxxxHHHHHHH)(2)(222第12页/共32页第十三页，共32页。推论推论1 1 对于任意的对于任意的 ，存在，存在HouseholderHouseholder矩阵矩阵H H，使使nCx1aeHx其中其中 为实数。为实数。12,eaxxaH) 1,(,2)(uuRuuuIHTnT1aeHx2xa 推论推论2 2 对于任意的对于任意的 ，存在，存在HouseholderHouseholder矩阵矩阵H HnRx上述结论表明，可以利用上述结论表明，可以利用HouseholderHouseholder变换将任意向量变换将任意向量化为与第一自然基向量化为与第一自然基向量 平行的向量（共线）平行的向量（共线）。 nRx1e，其中，其中(qzhng)(qzhng)使得使得(sh (sh de)de)得得第13页/共32页第十四页，共32页。例例2 2 用用HouseholderHouseholder变换变换(binhun)(binhun)将向量将向量化为与化为与 平行的向量。平行的向量。Tiix2,232xTe0, 0, 11iexH21iaeaxxaH2,12ia325301211iiaexaex13ieHx 因此因此(ync)(ync)解解 由于由于(yuy)(yuy)为了使为了使为实数，取为实数，取令令112102145105101512iiiiIHH则则也可取也可取 或或3aia3说明说明第14页/共32页第十五页，共32页。1 1 将矩阵将矩阵A A按列分块按列分块 , ,取取nA,2121121111111,aeaeaHIH111200*,11121111BaHHHAHn利用利用(lyng)Householder(lyng)Householder矩阵求矩阵的矩阵求矩阵的QRQR分解的步骤：分解的步骤：则则第15页/共32页第十六页，共32页。2 2 将矩阵将矩阵 按列分块，按列分块，)1()1(1nnCBnB,32122221221222,bebebuHuuIH222222001HHT2211200*0*)(CaaAHH)2()2(2nnCC取取则则其中其中(qzhng)(qzhng)第16页/共32页第十七页，共32页。121nHHHQ则则 A=QRA=QR依次进行依次进行(jnxng)(jnxng)下去，得到第下去，得到第n-1n-1个个n n阶的阶的HouseholdHousehold矩阵矩阵Hn-1Hn-1，使得，使得RaaaAHHHnn*2112133因因 为自逆矩阵，令为自逆矩阵，令 iH第17页/共32页第十八页，共32页。例例2：已知矩阵：已知矩阵(j zhn),112240130A利用利用(lyng)Householder(lyng)Householder变换求变换求A A的的QRQR分解分解因为因为,2 , 0 , 01T记记, 2211a令令21111111eaeaT1 , 0 , 121则则HIH1112,001010100从而从而(cng r)1302402121AH记记,3 , 4T则则, 5222b令令22222221ebeb,3 , 1101THIH2222,433451第18页/共32页第十九页，共32页。记记,43034000100122HHT则则RAHH20015021212取取0053404305121HHQ则则QRA第19页/共32页第二十页，共32页。x 2yx O我们知道，平面坐标系我们知道，平面坐标系 中的旋转角为中的旋转角为 变换可变换可表示为表示为2RT T是正交矩阵，称为是正交矩阵，称为(chn wi)(chn wi)平面旋转矩阵。平面旋转矩阵。将其推广到一般的将其推广到一般的n n维酉空间中维酉空间中，可以得到初等旋转变换，也称为可以得到初等旋转变换，也称为(chn wi)(chn wi)GivensGivens变换。变换。cossinsincos,2121TxxTyy第20页/共32页第二十一页，共32页。定义定义(dngy) (dngy) 设设记记n n阶矩阵阶矩阵(j zhn)(j zhn)nCsc,122 sc)()()()(111111lklkcsscTkl由由 所确定的线性变换称为所确定的线性变换称为GivensGivens变换或初等旋转变换。变换或初等旋转变换。klT称称 为为GivensGivens矩阵或初等旋转矩阵；矩阵或初等旋转矩阵；klT容易验证，容易验证，GivensGivens矩阵是矩阵是酉矩阵酉矩阵，且，且 。 1detklT第21页/共32页第二十二页，共32页。定理定理 对于任意向量对于任意向量 ，存在，存在GivensGivens变换变换 ，使，使得得 的第的第l l个分量为个分量为0 0，第，第k k个分量为个分量为非负实数，其余分量不变。非负实数，其余分量不变。nCxklTxTklTnklTnyyyxTxxxx,2121),( ,lkjxycxsxyxsxcyjjlkllkk证明证明(zhngmng) (zhngmng) 记记由由GivensGivens矩阵矩阵(j zhn)(j zhn)的定义可得的定义可得第22页/共32页第二十三页，共32页。当当 时，取时，取c c=1,=1,s s=0=0，则，则T Tkl kl = = I I, ,此时此时022lkxx),(, 0lkjxyyyjjlk当当 时，取时，取022lkxx2222,lkllkkxxxsxxxc),(002222222222lkjxyxxxxxxxxyxxxxxxxxxxyjjlklklklkllklklllkkkk, ,结论结论(jiln)(jiln)成立。成立。则则第23页/共32页第二十四页，共32页。与第一自然与第一自然(zrn)(zrn)基基向量向量推论推论 给定一个向量给定一个向量 ，则存在一组，则存在一组GivensGivens矩阵矩阵 ， 使得使得nCxnTTT11312,1212131exxTTTnnCx1eTnxxxx,2112TTnxxxxxT, 0 ,3222112称为用称为用GivensGivens变换变换(binhun)(binhun)化向量化向量证明证明(zhngmng) (zhngmng) 设设由上述定理存在由上述定理存在GivensGivens矩阵矩阵使得使得共线。共线。第24页/共32页第二十五页，共32页。依 此 继 续 下 去 ， 可 以依 此 继 续 下 去 ， 可 以(ky)(ky)得出得出TnxxxxxxTT, 0, 0,433222112131222221121310, 0,exxxxxTTTTnn对于对于 又存在又存在GivensGivens矩阵矩阵 ，使得，使得xT1213T第25页/共32页第二十六页，共32页。例例3 3 用用GivensGivens变换化向量变换化向量 与第一与第一(dy)(dy)自然基向量共线自然基向量共线 Tiix2,25,2222121xxixix5,5211isic1000525055212iiiiT20512xT解解 由于由于(yuy)(yuy)取取则构造则构造(guzo)Givens(guzo)Givens矩阵矩阵第26页/共32页第二十七页，共32页。3, 2, 5232131xxxx32,3522sc11213133003,3503201032035exTTTxT12对于对于由于由于(yuy)(yuy)取取则则第27页/共32页第二十八页，共32页。nA,21nTTT11312,121112131eTTTn2111112131,0*aBaATTTn利用利用GivensGivens矩阵矩阵(j zhn)(j zhn)求矩阵求矩阵(j zhn)(j zhn)的的QRQR分解的步骤：分解的步骤：先将矩阵先将矩阵(j zhn)A(j zhn)A按列分块，按列分块，11 1 对于对于存在存在(cnzi)(cnzi)一组一组GivensGivens矩阵矩阵于是于是nnCA使得使得第28页/共32页第二十九页，共32页。nB321*nTTT22423,22222232420, 0,*,*bbTTTTn又存在又存在(cnzi)(cnzi)一组一组GivensGivens矩阵矩阵使得使得(sh de)(sh de)2 2 将矩阵将矩阵 按列分块按列分块)1(1*nnCB第29页/共32页第三十页，共32页。33令令 。依次进行依次进行(jnxng)(jnxng)下去，得到下去，得到21112123200*0*CbaATTTTnn)2()2(2nnCCRcbaATTTTTnnnnn*21121232, 1HnnHnHHnHTTTTTQ, 1223112因此因此(ync)(ync)其中其中(qzhng)(qzhng)，则则A=QRA=QR第30页/共32页第三十一页，共32页。说明：利用说明：利用(lyng)Givens矩阵进行矩阵进行QR分解，需要作分解，需要作 个初等个初等21nn旋转旋转(xunzhun)(xunzhun)矩阵的连乘积，矩阵的连乘积，当当n较大较大(jio d)时，计算量较大时，计算量较大(jio d)，因此，因此常用镜像变换来进行常用镜像变换来进行QRQR分解分解第31页/共32页第三十二页，共32页。