QR分解

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

定义 
实数矩阵A的QR分解是把A分解为
 
这里的Q是正交矩阵（意味着QTQ = I）而R是上三角矩阵。类似的，我们可以定义A的QL, RQ和LQ分解。

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

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

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大小为。

矩阵分解

用途

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

如果,  那么,这里)。

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

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

外部連結