(完整版)QR分解及其应用.doc

《(完整版)QR分解及其应用.doc》由会员分享，可在线阅读，更多相关《(完整版)QR分解及其应用.doc（22页珍藏版）》请在金锄头文库上搜索。

1、矩阵分析与应用专题报告QR分解及应用学生姓名：卢楠、胡河群、朱浩2015年11月25日目录1 引言32 QR分解32.1QR分解的性质32.2 QR分解算法42.2.1 采用修正Gram-Schmidt法的QR分解42.2.2 Householder QR分解52.2.3 采用Givens旋转的QR分解63 QR分解在参数估计中的应用731 基于 分解的参数估计问题73. 2基于 变换的快速时变参数估计93. 3基于 旋转的时变参数估计114 QR分解在通信系统中的应用124.1 基于QR分解的稳健干扰对齐算法124.2基于 分解的 置信传播检测器14总结16参考文献171 引言 矩阵分解是指

2、将一个矩阵表示为结构简单或具有特殊性质的若干矩阵之积或之和，大体上可以分为满秩分解、QR分解和奇异值分解。矩阵分解在矩阵分析中占有很重要的地位，常用来解决各种复杂的问题。而QR分解是工程中应用最为广泛的一类矩阵分解。QR分解是目前求一般矩阵全部特征值的最有效并广泛应用的方法，一般矩阵先经过正交相似变换成为Hessenberg矩阵，然后再应用QR分解求特征值和特征向量。它是将矩阵分解成一个正交矩阵Q与上三角矩阵R，所以称为QR分解。 参数估计是在已知系统模型结构时，用系统的输入与输出数据计算系统模型参数的过程。它在系统辨识和无线通信领域有着广泛的应用。18世纪末德国数学家C.F.高斯首先提出参数

3、估计的方法，他用最小二乘法计算天体运行的轨道。20世纪60年代，随着电子计算机的普及，参数估计有了迅猛的发展。参数估计有很多方法，如矩估计、极大似然法、一致最小方差无偏估计、最小风险估计、同变估计、最小二乘法、贝叶斯估计、极小极大熵法等。其中最基本的是最小二乘法和极大似然法。 本文将重点介绍QR分解及其在参数估计和通信系统中的应用。2 QR分解2.1QR分解的性质定理2.1.1（QR分解）若，且，则存在列正交矩阵 和上三角矩阵 使得 。当时，是正交矩阵。如果 是非奇异的 矩阵，则 的所有对角线元素均为正，并且在这种情况下 和 二者是唯一的。若 是复矩阵，则 和 取复值。 注意到 ,因此可以得出

4、结论： 是 的下三角 因子。由于这个原因，在关于估计的文献中，矩阵 常称为平方根滤波器（算子）。 下面的引理称为矩阵分解引理，它在矩阵的QR分解的应用中是一个很有结果。 引理2.2.1 若 和 是任意两个 矩阵，则 (2.1.1)当且仅当存在一个 酉矩阵 ，使得 (2.1.2) 证明 充分性证明：若 ，并且 是酉矩阵，则 。 必要性证明：令 和 的奇异值分解分别为 式中， 和 均为 酉矩阵； 和 都是 酉矩阵；而 矩阵 和 分别包含了矩阵 和 的非负奇异值。由于 若 ,则有 和 。定义矩阵 易知 这就证明了引理的必要条件10。 2.2 QR分解算法2.2.1 采用修正Gram-Schmidt法

5、的QR分解矩阵 的QR分解可以利用Gram-Schmidt正交化方法实现。Gram-Schmidt正交化方法原本是一种由n个向量 构造互相正交且范数为1的向量 的方法。将向量 标准正交化的结果取作 ，即 (2.2.1)然后，从 中除去与 平行的向量，再进行标准正交化，并将结果取作 ，则有 (2.2.2)进而，又从 除去与 和 平行的两个分量，再进行标准正交化，并使用该结果作 ，即有 (2.2.3)如此继续，则对于 有 (2.2.4)容易验证， 是标准正交基，即满足 (2.2.5)其中， 为Kronecker 函数。如果令 矩阵 的列向量 ，则以 为列向量的矩阵 与 之间有下列关系： (2.2.

6、6)又由于 组成标准正交基，所以 将 与 重写在同一矩阵，应用以上Gram-Schmidt正交化的方法叫做经典Gram-Schmidt正交化法6。2.2.2 Householder QR分解Householder变换可以实现任意 矩阵 的QR分解，其原理是使用变维向量的Householder变换，使得该向量除第一个元素外，其他元素皆为0。根据Householder变换的相关知识，欲使一个 维向量 的第1个元素后面的所有元素变为0，则 维的Householder向量应取 (2.2.7)式中 (2.2.8) 假定 矩阵 的列分块形式为 首先令 ，并取 ，则按照式和式，可以计算得到 。此时， (2.

7、2.9)变换后，矩阵 的第1列 的第一个元素等于 ，而该列的其他元素全部为0。 第二步针对矩阵 的第2列 ，令 和 又可按照式和式求出（m-1）维向量 。此时，取 ，又可得到 (2.2.10)变换后，矩阵 的第1列与 的第1列相同，而第2列 的第一个元素等于 ，第二个元素等于 ，而该列的其他元素全部为0。 类似地，又可针对矩阵 的第3列设计Householder变换矩阵 ，使得 的第一、二个元素保持不变，其他元素组成的m-2维向量 变换为除第一个元素外的全部元素变为0。 假定矩阵 经过k-1次Householder变换后，已变成 ，即 并且其前k-1列具有以下变换结果: 因此，第k次House

8、holder变换的目的就是保持前k-1列不变，实现 列第k列的下述变换： 这相当于对矩阵 进行Householder变换 时取 n次Householder变换后，即可实现QR分解。2.2.3 采用Givens旋转的QR分解 Givens旋转也可以用来计算QR分解。这里以 矩阵为例，说明Givens QR分解的思想： 其中， 表示用Givens旋转进行变化你的元素。 从上述说明中易得出结论：如果令 代表约化过程中的第j次Givens旋转，则 是上三角矩阵，其中 ，而t是总的旋转次数。3 QR分解在参数估计中的应用31 基于 分解的参数估计问题现在以系统辨识为例，说明如何利用矩阵的 分解进行系统参

9、数的递推估计。令系统在 时刻的输入为 ，系统输出的观测值由卷积方程 (3.1.1)给出，其中， 表示离散卷积， 代表 时刻的观测误差，且 (3.1.2)若将 的所有观测数据组成一向量，则 (3.1.3)式中， ， ， 。系统辨识问题的提法是：已知系统输入 和输出观测值 ，其中， ，估计系统参数向量 7。在时变系统的辨识中，则要求在已估计 时刻的系统参数向量 的情况下，使用增加的 值，通过简单的运算，递推出 时刻的系统参数向量 。 时刻的系统辨识问题可以简化为最小二乘问题 (3.1.4)求解，并且其解由“法方程” (3.1.5)确定。式中， 代表系统输入 的协方差矩阵， 。 直接求解式的方法叫做

10、协方差方法。例如，先计算协方差矩阵 的 分解 ,然后利用回带法解三角矩阵 直接得到 。然而，由于 的条件数是 的条件数的平方，因此，直接计算式的得到的解有可能是严重病态的（即条件数很大），即使 本身的条件数并不大，不是严重病态的。 在系统参数向量 的自适应递推辨识中，标准的递推最小二乘 法和 分解法都是针对协方差矩阵 进行更新的。虽然 分解（其中， 为上三角矩阵， 为对角矩阵）在数值上比较稳定，但是这些递推辨识方法也同样存在条件数变大的毛病。相比之下， 的 分解可以保持原问题的条件数不变。不妨令 (3.1.6)式中， 是 正交矩阵， 是 上三角矩阵，而 为 维零矩阵。由于正交变换可以保持被变换

11、向量的 长度或范数不变，所以式的最小二乘问题可等价写作 (3.1.7)或 (3.1.8)式中 (3.1.9)且 为 向量， 为 向量，它们可以从 直接分块得到。 一旦获得了 ，即可由 得到 。解此方程需要 次计算，并且最小残差值等于 。 假定增加了两个已知数值 和 ，我们来讨论如何更新系统参数的估计，即使用已估计的参数向量 和简单的运算，得到 时刻的新估计 。为了减少过去数据数据对参数估计的影响，对数据 和 采取指数加权，即 时刻的数据矩阵和观测数据向量分别取作 (3.1.10)式中， 称为遗忘因子，且 。于是，可以写出式在 时刻的形式为 (3.1.11)乍一看，上式似乎没有什么特别吸引人之处

12、，其实不然。这是因为，如同下面的引理所述，式的极小化变量等价为下述式的极小化变量，而后者非常适合于递推更新。引理3.1.2r若 ， ，其中， 是正交矩阵， 是上三角矩阵，则式的极小化变量等同于下式的极小化变量： (3.1.12)证明见。如果将式的极小化变量记作 ，则以上讨论可总结为 的自适应递推估计算法如下。算法1（系统参数的自适应估计算法）步骤1 对矩阵 进行 分解，得 (3.1.13)式中， 是 正交矩阵， 为 上三角矩阵，且 是 零矩阵。步骤二 进行分块运算 (3.1.14)其中， 为 向量， 为 向量。步骤三 切结三角矩阵方程 得到 。3.2基于 变换的快速时变参数估计考察 矩阵 的

13、分解，即 (3.2.1)显然，只需要进行 次 变换即可。换言之，为了得到上述 分解，应该选择 为 个 变换矩阵之积，即 (3.2.2)式中 (3.2.3)是对矩阵 第 列向量 进行的 变换矩阵，其参数选择方法为 (3.2.4)其中 (3.2.5)并且 (3.2.6)递推的 分解算法如下：基于 分解的自适应参数估计算法一般由两个分开的过程组成：（1）递推更新 分解 中的上三角矩阵 ；（2）用回代法求解三角矩阵方程。由于直接的回代需要 次运算（ 为数据长度）。因此，即便 变换再快速，整个自适应算法也至少需要 次运算。文献将上述快速 分解算法和求解三角矩阵方程的回代法综合起来考虑，提出了只具有 复杂度的快速自适应算法。3.3基于 旋转的时变参数估计现在考虑另外一种递推方法，递推求解 的变化量 ，而不是直接递推求 本身。换句话说，令 (3.3.1)问题是如何更新 。假定正交矩阵 为已知，它满足 (3.3.2)由式，式和式易知， 是下式的极小化变量： (3.3.3)此式又可化简为 (3.3.4)式中， 。因此， 可以从三角矩阵方程 (3.3.5)解出，其中， 满足 (3.3.6)为了求出满足