QR分解

(重定向自QR分解法

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

线性代数
向量 · 向量空间 · 基底  · 行列式  · 矩阵

类别及定义

编辑

方阵

编辑

任何方块矩阵A都可以分解为

 

其中Q正交矩阵(意味着QTQ = I)而R是上三角矩阵。如果A非奇异的,且限定R的对角线元素为正,则这个因数分解是唯一的。

更一般的说,我们可以因数分解复数 × 矩阵(有着mn)为 × 幺正矩阵(在QQ = I 的意义上,不需要是方阵)和 × 上三角矩阵的乘积。对m<n的情况,在Q × 方阵,而R则是 × 矩阵。

长方形矩阵

编辑

更一般地,我们可以将m×nA矩阵,其中mn,分解成m×m酉矩阵Qm×n三角矩阵R的乘积。由于m×n上三角矩阵的底部(mn)行完全由零组成,因此对RRQ进行分解通常很有用:

 

其中R1n×n上三角矩阵,0是(mnn零矩阵,Q1m×nQ2m×(mn),且Q1Q2都是有正交列。

已隐藏部分未翻译内容,欢迎参与翻译

Golub & Van Loan (1996,§5.2) call Q1R1 the thin QR factorization of A; Trefethen and Bau call this the reduced QR factorization.[1] If A is of full rank n and we require that the diagonal elements of R1 are positive then R1 and Q1 are unique, but in general Q2 is not. R1 is then equal to the upper triangular factor of the Cholesky decomposition of A* A (= ATA if A is real).

QL、RQ 和 LQ 分解

编辑

类似的,我们可以定义A的QL,RQ和LQ分解。其中L是下三角矩阵。

QR分解的求法

编辑

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

使用Householder变换

编辑

Householder变换

编辑

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

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

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

 

(Stoer & Bulirsch 2002,第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代表上三角形矩阵。

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

用途

编辑

解线性方程组

编辑

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

如果 , 那么 ,这里 )。

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

 

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

 

参考文献

编辑

外部链接

编辑