QR分解

QR分解法是三種将矩阵分解的方式之一。這種方式,把矩阵分解成一个正交矩阵与一个上三角矩阵的积。QR分解经常用来解线性最小二乘法问题。QR分解也是特定特征值算法QR算法的基础。

线性代数

向量 · 向量空间  · 行列式  · 矩阵

定义编辑

实数矩阵AQR分解是把A分解为

 

这里的Q正交矩阵(意味着QTQ = I)而R是上三角矩阵。类似的,我们可以定义A的QL, RQ和LQ分解。

更一般的说,我们可以因数分解复数 × 矩阵(有着mn)为 ×  幺正矩阵(在QQ = I的意义上)和 × 上三角矩阵的乘积。

如果A非奇异的,且限定R 的对角线元素为正,则这个因数分解是唯一的。

QR分解的求法编辑

QR分解的实际计算有很多方法,例如Givens旋转Householder变换,以及Gram-Schmidt正交化等等。每一种方法都有其优点和不足。

使用Householder变换编辑

Householder变换编辑

Householder变换将一个向量关于某个平面或者超平面进行反射。我们可以利用这个操作对 的矩阵 进行QR分解。

矩阵 可以被用于对一个向量以一种特定的方式进行反射变换,使得它除了一个维度以外的其他所有分量都化为0。

 为矩阵 的任一m维实列向量,且有 (其中 为标量)。若该算法是通过浮点数实现的,则 应当取和 的第 维相反的符号(其中 是要保留不为0的项),这样做可以避免精度缺失。对于复数的情况,令

 

Stoer & Bulirsch 2002,p.225),并且在接下来矩阵 的构造中要将矩阵转置替换为共轭转置。

接下来,设 为单位向量 ,||·||为欧几里的范数  单位矩阵,令

 
 
 

或者,若 为复矩阵,则

 ,其中 
式中  共轭转置(亦称埃尔米特共轭埃尔米特转置)。

 为一个 的Householder矩阵,它满足

 

利用Householder矩阵,可以将一个 的矩阵 变换为上三角矩阵。 首先,我们将A左乘通过选取矩阵的第一行得到行向量 的Householder矩阵 。这样,我们得到的矩阵 的第一列将全部为0(第一行除外):

 

这个过程对于矩阵 (即 排除第一行和第一列之后剩下的方阵)还可以继续做下去,从而得到另一个Householder矩阵 。注意到 其实比 要小,因为它是在 而非 的基础上得到的。因此,我们需要在 的左上角补上1,或者,更一般地来说:

 

将这个迭代过程进行 次之后( ),将有

 

其中R为一个上三角矩阵。因此,令

 

 为矩阵 的一个QR分解。

相比与Gram-Schmidt正交化,使用Householder变换具有更好的数值稳定性

例子编辑

现在要用Householder变换求解矩阵   分解。

 

因为 , 令 ,则

 

则有

 

从而,

 

 , 则 。令

 
 

记,

 

则,

 

那么

 

使用吉文斯旋转编辑

吉文斯旋转编辑

吉文斯旋转表示为如下形式的矩阵

 

这里的 c = cos(θ) 和 s = sin(θ) 出现在第 i 行和第 j 行与第 i 列和第 j 列的交叉点上。就是说,吉文斯旋转矩阵的所有非零元定义如下::

 

乘积 G(i, j, θ)x 表示向量 x 在 (i,j)平面中的逆时针旋转 θ 弧度。

吉文斯旋转作用于QR分解编辑

对于一个向量

 

如果,  ,   ,   , 那么,就存在旋转矩阵G,使  底部转成0。

 

每一次的旋转,吉文斯旋转都可以将一个元素化成0,直到将原始矩阵转成一个上三角矩阵,则完成分解。

 
 

例子编辑

 
 
 
 
 

对于: 子矩阵 : 

 
 
 
 
 
 
 

使用格拉姆-施密特正交化方法编辑

基本思想编辑

 
图1   上投影,构造 上的正交基 

格拉姆-施密特正交化的基本想法,是利用投影原理在已有正交基的基础上构造一个新的正交基。

   上的 维子空间,其标准正交基为 ,且 不在 上。由投影原理知, 与其在 上的投影 之差

 


是正交于子空间 的,亦即 正交于 的正交基 。因此只要将 单位化,即

 

那么 就是  上扩展的子空间 的标准正交基。

根据上述分析,对于向量组 张成的空间  ( ),只要从其中一个向量(不妨设为 )所张成的一维子空间 开始(注意到 就是 的正交基),重复上述扩展构造正交基的过程,就能够得到  的一组正交基。这就是格拉姆-施密特正交化

格拉姆-施密特正交化算法编辑

首先需要确定已有基底向量的顺序,不妨设为 。Gram-Schmidt正交化的过程如下:

   
   
   
   
   

这样就得到 上的一组正交基 ,以及相应的标准正交基 

例子编辑

现在要用格拉姆-施密特变换求解矩阵   分解。

 

令,  

 
 
 
 
 

那么可知,

 

 ,可知,

 

Matlab编辑

MATLAB以qr函数来执行QR分解法,其语法为

[Q,R]=qr(A)
其中Q代表正规正交矩阵,
而R代表上三角形矩阵。

此外,原矩阵A不必为正方矩阵; 如果矩阵A大小为 ,则矩阵Q大小为 ,矩阵R大小为 

用途编辑

解线性方程组编辑

对于直接求解线性方程组的逆,用QR分解的方法求解会更具有数据的稳定性。 对于求解一个线性系统 , 这里 的维度是 

如果 , 那么 ,这里 )。

  的形式是    上不为0的部分。 那么对于

 

如果 , 那么 ,这里 )。本质是最小化 

 

外部連結编辑

[1][2]

  1. ^ MIT. QR Decomposition. Youtube. 
  2. ^ Poujh. QR Decomposition Givens旋转. Youtube.