QR分解

第一节QR分解QR分解也称为正交三角分解矩阵QR分解是一种特殊的三角分解，在解决矩阵特征值的计算、最小二乘法等问题中起到重要作用。主要内容：1·矩阵的QR分解--Schmidt正交化方法2·矩阵的QR分解--Householder变换、Givens变换QR分解定理任意一个满秩实(复）矩阵A，都可唯一地分解A=QR，其中Q为正交（酉）矩阵，R是具有正对角元的上三角矩阵。由于x1,x2,…,xn线性无关，将它们用Schmidt正交证明设A是一个实满秩矩阵,A的n个列向量为x1,x2,…,xn定义:设.nnCA如果存在n阶酉矩阵Q和n阶上三角矩阵R，使得QRA则称之为A的QR分解或酉三角分解当时，则称为A的正三角分解nnRA化方法得标准正交向量e1,e2,…,ennnnnnnebebebxebebxebx221122211221111其中nibii,,2,1,0从而有nnnnnnbbbbbbeeexxx222112112121nnnnnbbbbbbReeeQ2221121121,令IQQT则则如果再证唯一性,11RQQRA由此得DQRRQQ1111式中D=R1R-1仍为具有正对角元的上三角矩阵。由于DDDQDQQQITTT11即D为正交矩阵，因此D为单位矩阵（正规上三角为对角阵）故RDRRQDQQ111,说明：1·若不要求R具有正对角元，则A的不同QR分解仅在正交矩阵的列和上三角矩阵R的对应行相差模为1的因子。该定理的证明过程给出了利用Schmidt正交化方法求可逆矩阵QR分解的方法。例求矩阵A的QR分解110201221A解，则记122,102,011321xxx2·若A为满秩复矩阵，则存在酉矩阵Q与复非奇异上三角矩阵R，使A=QRTyyyxyyyxTyyyxyyxyyxyyxyxyxy2,1,121,1,131231132),(),(1),(),(33121),(),(2211222311131112将正交化321,,xxxTyyTyyTyyeee2,1,11,1,10,1,1663332221332211单位化336233132121122322eeexeexex整理得,03633663322663322Q令363300302222RQRA则例1：利用Schmidt正交化方法求矩阵的QR分解212240130A设,2,2,1,1,4,3,2,0,0321TTTxxx则321,,xxx线性无关，首先将它们正交化得：,2,0,011Txy1),(),(221112yxyyyyx2),(),(1),(),(3322231113yyxyyyyxyyyxTyyx0,56,5851213Tyx0,4,31212再单位化：,1,0,02111Tye,0,54,535122Tye,0,53,542133Tye于是：1112eyx21212521eeyyx32132132251eeeyyyx从而QRA00153540545302150212,1,0,02111Tye,0,54,535122TyeHouseholder变换O+OTIHR2)(3)(H则记即：该变换将向量变成了以为法向量的平面的对称向量。Householder变换又称为反射变换或镜像变换，有明显的几何意义。在中，给定一个向量，令表示关于平面（以为法向量）的反射变换所得像，如图所示，3R定义设是一个单位向量，令nCHIH2)(则称H是一个Householder矩阵或Householder变换。性质5.1.1设H是一个Householder矩阵，则（1）H是Hermite矩阵，；（2）H是酉矩阵，；（3）H是对合矩阵，；（4）H是自逆矩阵（5）diag(I,H)也是一个Householder矩阵;（6）detH=-1。HHHIHHHIH2HH1其中为实数。定理设是一个单位向量，则对于任意的nCunCxauHxuaxxaH,2nC当时，取单位向量使0auxnC0xHauxxxxIxHHH)(22))((存在Householder矩阵H，使得证明当x=0时，任取单位向量则则002))((HIxH所以当时，取aux,2auxauxxauxauxauxIxIxHHT22))((22)(uuaxuauaxxxauxauxHHHHH2)()(由于auauxauxauxxauxxxHHH)()()()(2)()()()()(2auxauxauxxauxxHHxauxxuaxxxxuauaxxxHHHHHHH)(2)(222推论1对于任意的，存在Householder矩阵H，使nCx1aeHx其中为实数。12,eaxxaH)1,(,2)(uuRuuuIHTnT1aeHx2xa推论2对于任意的，存在Householder矩阵HnRx上述结论表明，可以利用Householder变换将任意向量化为与第一自然基向量平行的向量（共线）。nRx1e，其中使得得例2用Householder变换将向量化为与平行的向量。Tiix2,,232xTe0,0,11iexH21iaeaxxaH2,12ia325301211iiaexaex13ieHx因此解由于为了使为实数，取令112102145105101512iiiiIHH则也可取或3aia3说明[1]首先将矩阵A按列分块,取nA,,,2121121111111,aeaeaHIH111200**,,,11121111BaHHHAHn利用Householder矩阵求矩阵的QR分解的步骤：则[2]将矩阵按列分块，)1()1(1nnCBnB,,,32122221221222,bebebuHuuIH2222~22~001HHT2211200**0***)(CaaAHH)2()2(2nnCC取则其中121nHHHQ则A=QR依次进行下去，得到第n-1个n阶的Household矩阵Hn-1，使得RaaaAHHHnn***21121[3]因为自逆矩阵，令iH例2：已知矩阵,112240130A利用Householder变换求A的QR分解因为,2,0,01T记,2211a令21111111eaeaT1,0,121则HIH1112,001010100从而1302402121AH记,3,4T则,5222b令22222221ebeb,3,1101THIH2222~,433451记,430340001~00122HHT则RAHH20015021212取0053404305121HHQ则QRAGivens变换x2yxO我们知道，平面坐标系中的旋转角为变换可表示为2RT是正交矩阵，称为平面旋转矩阵。将其推广到一般的n维酉空间中，可以得到初等旋转变换，也称为Givens变换。cossinsincos,2121TxxTyy定义设记n阶矩阵nCsc,122sc)()()()(111111lklkcsscTkl由所确定的线性变换称为Givens变换或初等旋转变换。klT称为Givens矩阵或初等旋转矩阵；klT容易验证，Givens矩阵是酉矩阵，且。1detklT定理对于任意向量，存在Givens变换，使得的第l个分量为0，第k个分量为非负实数，其余分量不变。nCxklTxTklTnklTnyyyxTxxxx,,,,,,,2121),(,lkjxycxsxyxsxcyjjlkllkk证明记由Givens矩阵的定义可得当时，取c=1,s=0，则Tkl=I,此时022lkxx),(,0lkjxyyyjjlk当时，取022lkxx2222,lkllkkxxxsxxxc),(002222222222lkjxyxxxxxxxxyxxxxxxxxxxyjjlklklklkllklklllkkkk,结论成立。则与第一自然基向量推论给定一个向量，则存在一组Givens矩阵，使得nCxnTTT11312,,,1212131exxTTTnnCx1eTnxxxx,,,2112TTnxxxxxT,,,0,3222112称为用Givens变换化向量证明设由上述定理存在Givens矩阵使得共线。依此继续下去，可以得出TnxxxxxxTT,,,0,0,433222112131222221121310,,0,exxxxxTTTTnn对于又存在Givens矩阵，使得xT1213T例3用Givens变换化向量与第一自然基向量共线Tiix2,,25,,2222121xxixix5,5211isic1000525055212iiiiT20512xT解由于取则构造Givens矩阵3',2,5'232131xxxx32,3522sc11213133003,3503201032035exTTTxT12对于由于取则nA,,,21nTTT11312,,,121112131eTTTn2111112131,0*aBaATTTn利用Givens矩阵求矩阵的QR分解的步骤：先将矩阵A按列分块，1[1]对于存在一组Givens矩阵于是nnCA使得nB321****nTTT22423,,,22222232420,,0,*,*bbTTTTn又存在一组Givens矩阵使得[2]将矩阵按列分块)1(1*nnCB[3]令。依次进行下去，得到21112123200**0***CbaATTTTnn)2()2(2nnCCRcbaATTTTTnnnnn***21121232,1HnnHnHHnHT