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正交化等等。每一种方法都有其优点和不足。

Gram-Schmidt正交化[编辑]

参见Gram-Schmidt正交化

使用Householder变换[编辑]

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

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

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

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

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

或者,若为复矩阵,则

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

为一个的Householder矩阵,它满足

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

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

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

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

为矩阵的一个QR分解。

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

Matlab[编辑]

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

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

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