QR分解

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

 類別及定义 
方陣
任何方块矩阵A都可以分解為

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

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

長方形矩陣
更一般地，我們可以將m×n的A矩陣，其中，分解成m×m酉矩阵Q和m×n三角矩陣R的乘積。由於m×n上三角矩陣的底部(m−n)行完全由零組成，因此對R或R和Q進行分解通常很有用：  

其中R1是n×n上三角矩陣，0是零矩陣，Q1是m×n，Q2是，且Q1和Q2都是有正交列。

 call Q1R1 the thin QR factorization of A; Trefethen and Bau call this the reduced QR factorization. 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的项），这样做可以避免精度缺失。对于复数的情况，令

，并且在接下来矩阵的构造中要将矩阵转置替换为共轭转置。

接下来，设为单位向量，||·||为欧几里德范数，为单位矩阵，令
  ， 
  ， 
  。 

或者，若为复矩阵，则
 ，其中
 式中是的共轭转置（亦称埃尔米特共轭或埃尔米特转置）。

则为一个的Householder矩阵，它满足


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

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

将这个迭代过程进行次之后（）,将有

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

则为矩阵的一个QR分解。

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

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


因为, 令，则

则有

从而，

记, 则。令


记，

则， 

那么

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

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

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

吉文斯旋转作用于QR分解
对于一个向量

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

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



例子




对于:子矩阵 :



 使用格拉姆-施密特正交化方法 
 基本思想 


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

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

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

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

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

 格拉姆-施密特正交化算法 
首先需要确定已有基底向量的顺序，不妨设为。Gram-Schmidt正交化的过程如下：



这样就得到上的一组正交基，以及相应的标准正交基。
 例子 
现在要用格拉姆-施密特变换求解矩阵的 分解。

令， 

那么可知，

由，可知，

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


其中Q代表正规正交矩阵，
而R代表上三角形矩阵。

此外，原矩阵A不必为正方矩阵；
如果矩阵A大小为，则矩阵Q大小为，矩阵R大小为。

Category:矩阵分解

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

如果,  那么,这里)。

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

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

 參考文獻 

 外部連結