QR方法的探讨(07-5)依拉木江苏甫尔.20070109058

编号学士学位论文QR方法的探讨学生姓名：依拉木江·苏甫尔学号：20070109058系部：数学系专业：信息与计算科学年级：07-5班指导教师：阿米娜·沙比尔完成日期：2012年5月日学士学位论文BACHELOR’STHESIS中文摘要本文主要讨论矩阵的QR分解的三种方法,即Schmidt正交化、Givens变换、Householder变换等方法,具体构造正交矩阵Q。首先提出理论基础及算法，求出数值例题的QR分解。然后编写MATLAB程序，把如上数值例题在MATLAB环境下实现，得到的数值QR分解。最后通过比较，验证本文提出的三种方法的应用性可靠性。关键词：QR分解；Schmidt正交化；Givens变换；Householder变换学士学位论文BACHELOR’STHESIS2目录中文摘要...........................................................1引言...............................................................21QR分解的概念.....................................................22GIVENS方法.....................................................73豪斯霍尔德方法（镜像变换）......................................153.1HOUSEHOLDER矩阵和HOUSEHOLDER变换.......................153.2QR算法.....................................................184QR分解的应用...................................................20总结..............................................................22参考文献..........................................................23致谢..............................................................24学士学位论文BACHELOR’STHESIS2引言矩阵A的QR分解与基于QR分解的QR方法是求矩阵A的特征值的一种有效方法。对n阶非奇异矩阵A的n个列向量12,,...,n，使用Schmidt正交化程序可以得到A的QR分解；使用Givens变换和Householder变换也可以直接将正交矩阵Q具体构造出来。本文主要讨论得到A的QR分解的三种方法，即Schmidt正交化，使用Givens方法和Householder方法等。任何实(复)非奇异n阶矩阵可以分解成正交(西)矩阵Q和实(复)非奇异上三角矩阵R的乘积.1QR分解的概念定理1.1[1]如果实（复）非奇异矩阵能化成正交（酉）矩阵Q与实（复）非奇异上三角矩阵R的乘积，即=QR（1.1）则称式（1.1）是的QR分解。引理1.1任何实的非奇异n阶矩阵可以分解成正交矩阵Q和上三角矩阵R的乘积，且除去相差一个对角线元素之绝对值全等于1的对角矩阵因子D外，分解式（1.1）是唯一的。证明：首先证明存在性设的各列向量依次12,,...,n，由于非奇异，所以12,,...,n线性无关，将它们按照施密特正交化法正交化，得到n个标准正交的向量12,,...,n，且学士学位论文BACHELOR’STHESIS3111121212221122...nnnnnnbbbbbb这里ijb都是常数，且由正交过程知0(1,2,...,)iibin。写成矩阵形式有1212(,,...,)(,,...,)nnB,即Q=其中11121222=nnnnbbbbbb是上三角矩阵(0(1,2,...,))iibin。显然，可逆，而且1R也是上三角矩阵；由于Q的各列标准正交，所以Q为正交矩阵。从而有=QR。现在要证明唯一性,设有两种形式如（1.1）的分解式：11=QRQR（1.2）其中Q和Q１都是正交矩阵，R和R１都是非奇异上三角矩阵，由式（1.2）得1111Q=QRR=QD，式中11D=RR仍为实非奇异上三角矩阵,于是TTT11QQ=QDQD=DDＩ＝（）（）（1.3）设11121222nnnndddddDd代入式（1.3）并与单位矩阵相比较，得学士学位论文BACHELOR’STHESIS421112122223221,...01,...01nnnnddddddd从而有1122...1nnddd，即100010001D，这表明D不仅是正交矩阵，而且还是对角线元素的绝对值全为1的对角矩阵，再由式（1.2）不难得1RDR，11Q=QD显然，当规定上三角矩阵R和1R对角线上元素为正实数时，则D=I,从而QR分解唯一。例1.设110=111002写出的QR分解。解：用施密特（Schmidt）方法，令TTT123=1,1,0=11,0=0,1,2（），（，），（）T11==1,1,0（）T12221211===11,0（，）（，）（，）学士学位论文BACHELOR’STHESIS5132333121122=（，）（，）（，）（，）T31211==0,0,222（）（）单位化后得T11111=0=222（，，）T22111=,0=222（，）T3123111=0,0,1=442（）1231231104211=0421002（，，）（，，）所以11231231104211(,,)(,,)0421002学士学位论文BACHELOR’STHESIS6111110042221111=0042220011002111020222111002QR222001002定理1.2[1]设为mn复矩阵（mn），且n个列向量线性无关，则具有分解RU（1.4）其中U是mn复矩阵，且满足HUU＝Ｉ，R是n阶复非奇异上三角矩阵，且除去相差一个对角元素的模全为1的对角矩阵因子外，分解式（1.4）唯一的。施密特（Schmidt）方法的MATLAB程序如下：functionc=schmidt_sum(A,y1,n)c=zeros(length(A),1);fori=1:n-1xx=y1(:,i)'*A(:,n);yy=y1(:,i)'*y1(:,i);c=c+(xx/yy)*y1(:,i);endy1(:,n)=A(:,n)-c;c=y1(:,n);%endfunctionA=[110;1-11;002];m=length(A);y1=zeros(size(A));y=y1;y1(:,1)=A(:,1);学士学位论文BACHELOR’STHESIS7fori=2:my1(:,i)=schmidt_sum(A,y1,i);endfori=1:mkk=y1(:,i)'*y1(:,i);y(:,i)=y1(:,i)/sqrt(kk);endy其运行结果为数据分析:从如上理论方法与数值计算方法解同一个例题,其结果一致,说明用施密特（Schmidt）方法可以求非奇异矩阵A的QR分解，算法简便，有应用性价值。实用上，一般不用施密特正交化方法作QR分解。下面介绍Givens变换（初等旋转变换）、Householder变换（镜像变换）对矩阵进行QR分解，两种方法各有优缺点。2Givens方法我们知初等旋转变换的性质，即用ijR在乘矩阵时，仅影响的第i行和第j行，且选适当的ijR，就可以消去的一个非零元素。一般地说，作一次旋转可学士学位论文BACHELOR’STHESIS8以消去一个非零元素。如果在作下一次旋转时不会影响前面已化为零的元素,即不会重新又变成非零,那么,借助于初等旋转矩阵将约化成上三角矩阵就有希望。在平面解析几何中，将向量x沿顺时针旋转角度后变为向量y时（1.5图）的旋转变换为cossinsincosyxTx由于旋转变换不改变向量的模，即2222Txx，此即,,TxTxxx，所以T是正交变换，从而T是正交矩阵，且det1T。一般地说，在n维欧氏空间nR中引入旋转变换如下。定义1.2[2]设实数c与s满足221cs，称11111ijcsTsc()ij为Givens矩阵（或初等旋转矩阵（ElementaryRotationMatrix）），有时也记为(,)ijijTTcs，由Givens矩阵所确定的线性变换称为Givens变换（或初等旋转变换（ElementaryRotationTransformation））.第i行第j行xx1xy2xO1e2e（图1.5）学士学位论文BACHELOR’STHESIS9当221cs时，必有角度，使得cos,sincs（图1.6）性质1.2.1[2]Givens矩阵是正交矩阵且有1[(,)][(,)](,)TijijijTcsTcsTcs（1.5）det[(,)]1ijTcs性质1.2.2[2]设1212(,,...,),(,,...,)TTnijnxyTx则有(1.6)(,)iijjjkkcssckij式（1.6）表明，当220ij时，选取2222,(1.7)jiijijcs就可使220,0iijj。定理1.3[2]设12(,,...,)0Tnx，则存在有限多个Givens矩阵的乘积,记为T,使得12Txxe，其中1(1,0,...,0)Te。证:先考虑10的情形，对x构造Givens矩阵(,)ijTcs,其中1222221212,cs则2212123(,0,,...,)TnTx。cs1图1.6cos,sincs学士学位论文BACHELOR’STHESIS10再对12Tx构造Givens矩阵13(,)Tcs,其中22123222222123123,cs则22213121234()(,0,0,,...,)TnTTx。重复上述步骤，最后对1,112...nTTTx构造Givens矩阵1(,)nTcs，其中222121222222121211,1122...,......(...)(,0,...,0)nnnnTnncsTTTxx令11,112...nnTTTT则有12Txxe若10，考虑11...0,0(1)kkkn的情形，此时222...knx上面的步骤从1kT开始进行即得定理结论。推论1[2].设非零向量nxR及单位列向量nzR，则存在有限多个Givens矩阵的乘积，记为T，使得2Txxz。例2设(3,4,5)Tx，用Givens变换化x为1e同方向的向量。解：对x构造121234(,);,,(5