QR分解及其应用.doc

《矩阵分析与应用》专题报告――QR分解及应用学生姓名：卢楠、胡河群、朱浩2015年11月25日1 目录引言3QR分解42.1QR分解的性质42 QR分解算法5采用修正Gram-Schmidt法的QR分解5HouseholderQR分解6采用Givens旋转的QR分解8QR分解在参数估计中的应用93．1基于QR分解的参数估计问题93.2基于Householder变换的快速时变参数估计123 3.3基于Givens旋转的时变参数估计14QR分解在通信系统中的应用164.1基于QR分解的稳健干扰对齐算法16基于QR分解的MIMO置信传播检测器19总结21参考文献221 引言矩阵分解是指将一个矩阵表示为结构简单或具有特殊性质的若干矩阵之积或之和，大体上可以分为满秩分解、QR分解和奇异值分解矩阵分解在矩阵分析中占有很重要的地位，常用来解决各种复杂的问题而QR分解是工程中应用最为广泛的一类矩阵分解QF分解是目前求一般矩阵全部特征值的最有效并广泛应用的方法，一般矩阵先经过正交相似变换成为Hessenberg矩阵，然后再应用QF分解求特征值和特征向量它是将矩阵分解成一个正交矩阵Q与上三角矩阵R,所以称为QR分解。

参数估计是在已知系统模型结构时，用系统的输入与输出数据计算系统模型参数的过程它在系统辨识和无线通信领域有着广泛的应用18世纪末德国数学家C.F.高斯首先提出参数估计的方法，他用最小二乘法计算天体运行的轨道20世纪60年代，随着电子计算机的普及，参数估计有了迅猛的发展参数估计有很多方法，如矩估计、极大似然法、一致最小方差无偏估计、最小风险估计、同变估计、最小二乘法、贝叶斯估计、极小极大熵法等其中最基本的是最小二乘法和极大似然法本文将重点介绍QR分解及其在参数估计和通信系统中的应用QR分解2.1QR分解的性质定理2.1.1(QR分解)若aRmn，且mn,则存在列正交矩阵QRmn和上三角矩阵RRmn使得A=QR当mn时，Q是正交矩阵如果A是非奇异的nn矩阵，则R的所有对角线元素均为正，并且在这种情况下Q和R二者是唯一的若A是复矩阵，则Q和R取复值注意到ATA=(QR)T(QR)=RTR,因此可以得出结论：G=RT是ATA的下三角Cholelskey因子由于这个原因，在关于估计的文献中，矩阵R常称为平方根滤波器(算子)下面的引理称为矩阵分解引理，它在矩阵的QR分解的应用中是一个很有结果引理2.2.1若A和B是任意两个mn矩阵，则AHA=BHB(2.1.1)当且仅当存在一个mm酉矩阵Q，使得QA=B(2.1.2)证明充分性证明：若QA=B，并且Q是酉矩阵，则BHB=AHQHQA=AHA。

必要性证明：令A和B的奇异值分解分别为A=UAAVAHB=UBBVBH式中，UA和UB均为mm酉矩阵；Va和Vb都是nn酉矩阵；而mn矩阵A和B分别包含了矩阵A和B的非负奇异值由于HHHAA=VAAAVAHBHB=VBHBQ=UbUaHhHh易知QA=UbUaA=UbUaUaaVa=UbbVb=B这就证明了引理的必要条件［10］2.2QR分解算法采用修正Gram-Schmidt法的QR分解矩阵A的QR分解可以利用Gram-Schmidt正交化方法实现Gram-Schmidt正交1的向量q1,q2,...,qn的方法将向量a1标准正交化的结果取作q1，即R1q1a1q仁Rn(2.2.1)然后，从a2中除去与a1平行的向量,再进行标准正交化，并将结果取作q2，化方法原本是一种由n个向量a1,a2,...,an构造互相正交且范数为则有进而，又从a3除去与a1Hq1a2R22Ia2q1R12(a2q1R2)/R22R12q2和a?(2.2.2)平行的两个分量，再进行标准正交化，并使用该结果作q3，即有R|3Hq1a3R23Hq2a3R33a3q1R13q2R23q3(a3q1R3q2尺3)■R33(2.2.3)如此继续，则对于qk(2kn)有RjkqjHak,1jk1Rkkakqk(ak容易验证，qi是标准正交基，即满足Hqiqju(225)其中，ij为Kronecker函数。

如果令mn矩阵A的列向量ai，a2,...，an,则以qi,q2,...,qn为列向量的矩阵Q与A之间有下列关系：A=QR(2.2.6)又由于qi组成标准正交基，所以QHQ=In将A与Q重写在同一矩阵，应用以上Gram-Schmidt正交化的方法叫做经典Gram-Schmidt正交化法⑹2.2.1 HouseholderQR分解Householder变换可以实现任意mn矩阵A的QR分解，其原理是使用变维向量的Householder变换，使得该向量除第一个元素外，其他元素皆为0根据Householder变换的相关知识，欲使一个p维向量xx1,x2,...,x^的第1个元素后面的所有元素变为0，则p维的Householder向量应取xe1X1)(2.2.7)X1X1式中(2.2.8)假定mn矩阵A的列分块形式为可以计算得到U1Wm此时，H1Iu1u1TA1H1Aa1(1),a2(1)a(1)n(2.2.9)变换后，矩阵A1的第1列a1⑴的第一个元素等于a12122a21...am112，而该列的其他元素全部为0第二步针对矩阵A1的第2列aj，令Pm1和xa2；),a3；),...a(1)T,am2又可按照式(227)和式(2.2.8)求出(m-1)维向量Wm1。

此时，取U20Wm1又可得到h2IT典u?u2A2H2A1H2H1Aa1(1),⑵(2)a2,...,an(2.2.10)首先令xaiai1,a21,・・.,am1T，并取Pm，则按照式(227)和式(228),变换后，矩阵A2的第1列与Ai的第1列相同，而第2列ai⑴的第一个元素等于aj,第二个元素等于a22)am212，而该列的其他元素全部为0类似地，又可针对矩阵A2的第3列设计Householder变换矩阵出，使得A2的第一、二个元素保持不变，其他元素组成的m-2维向量xa3?,a43，…,换为除第一个元素外的全部元素变为0假定矩阵A经过k-1次Householder变换后，已变成A(k1)，即A(k1)Hk1A(k2)Hk1...H1A(k1)(k1)(k1)a1,a2,・・・，an并且其前k-1列具有以下变换结果：ajk1)a；：1〉,…,ajo,...,因此，第k次Householder变换的目的就是保持前k列的下述变换：k=2,3，…j=1,2,・・・k-1k-1列不变，实现A(k1)列第akkk0M0(k1)ak,k(k1)H%%1,kkMa(k1)m,k这相当于对矩阵A(k1)进行Householder变换HkA(k1)时取Ik100H%kn次Householder变换后，即可实现QR分解。

223采用Givens旋转的QR分解Givens旋转也可以用来计算分解的思想：QR分解这里以43矩阵为例，说明GivensQR(3,4)(2,3)(1,2)0(3,4)000000(2,3)0(3,4)0000000000000其中，表示用Givens旋转进行变化你的元素从上述说明中易得出结论：如果令Gj代表约化过程中的第j次Givens旋转，则QtA=R是上三角矩阵，其中Q=GtGt「LGi，而t是总的旋转次数QR分解在参数估计中的应用3.1基于QR分解的参数估计问题现在以系统辨识为例，说明如何利用矩阵的QR分解进行系统参数的递推估计令系统在k时刻的输入为xk，系统输出的观测值由卷积方程piXki0iekxT6ek(3.1.1)给出，其中，表示离散卷积,代表k时刻的观测误差，且Xkxk,x1丄，k1,L,xkTP(3.1.2)若将k1,2,L,n的所有观测数据组成一向量，则ynAn6en(3.1.3)Anx，yny1,y2丄，ynT1,x2,L,xn0系统辨识问题的提法是：已知系统输入k1,2,L,n，估计系统参数向量6[7]0ene1,e2丄，ek和输出观测值在时变系统的辨识中,n时刻的系统参数向量6的情况下，使用增加的xn1,y，其中,则要求在已估计n1值，通过简单的运算，递推出n1时刻的系统参数向量n10n时刻的系统辨识问题可以简化为最小二乘问题m6nAn6仆:(3.1.4)求解，并且其解由“法方程”AnTAn6AnTyn或Rxx6n心(3.1.5)确定。

式中，RxxAnTAn代表系统输入Xk的协方差矩阵，rn人.丁丫・直接求解式（3.1.5）的方法叫做协方差方法例如，先计算协方差矩阵Rxx的Cholesky分解RxxGG『,然后利用回带法解三角矩阵G也GRn直接得到6n然而，由于RxxAnTAn的条件数是An的条件数的平方，因此，直接计算式（3.1.5）的得到的解有可能是严重病态的（即条件数很大），即使An本身的条件数并不大，不是严重病态的在系统参数向量9的自适应递推辨识中，标准的递推最小二乘RLS法和分解（其中,UtDU分解法都是针对协方差矩阵Rxx进行更新的虽然utdu但是这些递推辨识方U为上三角矩阵，D为对角矩阵）在数值上比较稳定,法也同样存在条件数变大的毛病相比之下,An的QR分解可以保持原问题的条件数不变不妨令式中，QnQnTAnRnO(3.1.6)是nn正交矩阵，R上三角矩阵，而0为p1维零矩阵由于正交变换可以保持被变换向量的Euclidean长度或范数不变，所以式（3.1.4）的最小二乘冋题可等价与作minQnAn9QnTyn(3.1.7)(3.1.8)QnTyn且yn为p11向量，％为nP11向量，它们可以从QnTyn直接分块minRn9y式中(3.1.9)得到。

一旦获得了入，即可由RnOnyn得到O解此方程需要nn1/2次计算，并且最小残差值等于|%|假定增加了两个已知数值xn1和yn1，我们来讨论如何更新系统参数的估计，即使用已估计的参数向量3和简单的运算，得到1时刻的新估计On1为了减少过去数据数据对参数估计的影响，对数据X和yk米取指数加权，即n1时刻的数据矩阵和观测数据向量分别取作AnTXn1,yn1ynyn1(3.1.10)式中，01称为遗忘因子，且Xn1Xn1,xn丄，Xn于是,可以写出式(3.1.4)在n1时刻的形式为Bn1argmOnAn10yn1argminAn°ynyn1TXn1乍一看，上式似乎没有什么特别吸引人之处，其实不然这是因为,引理所述，式(3.1.11)的极小化变量等价为下述式的极小化变量,合于递推更新引理3.1.2r若A。