QR分解

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

定义

实数矩阵A的QR分解是把A分解为

$A=QR,\,$

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

更一般的说，我们可以因数分解复数$m$×$n$矩阵（有着m ≥ n）为$m$×$n$ 酉矩阵（在Q^∗Q = I的意义上）和$n$×$n$上三角矩阵的乘积。

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

QR分解的求法

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

Gram-Schmidt正交化

参见Gram-Schmidt正交化

使用Householder变换

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

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

令$\mathbf {x}$为矩阵$A$的任一m维实列向量，且有$\|\mathbf {x} \|=|\alpha |$（其中$\alpha$为标量）。若该算法是通过浮点数实现的，则$\alpha$应当取和$\mathbf {x}$的第$k$维相反的符号（其中$x_{k}$是要保留不为0的项），这样做可以避免精度缺失。对于复数的情况，令

$\alpha =-\mathrm {e} ^{\mathrm {i} \arg x_{k}}\|\mathbf {x} \|$

(Stoer & Bulirsch 2002，第225頁)，并且在接下来矩阵$Q$的构造中要将矩阵转置替换为共轭转置。

接下来，设$\mathbf {e} _{1}$为单位向量$(1,0,\cdots ,0)^{T}$，||·||为欧几里的范数，$I$为$m\times m$单位矩阵，令

$\mathbf {u} =\mathbf {x} -\alpha \mathbf {e} _{1},$

$\mathbf {v} ={\mathbf {u} \over \|\mathbf {u} \|},$

$Q=I-2\mathbf {v} \mathbf {v} ^{T}.$

或者，若$A$为复矩阵，则

$Q=I-(1+w)\mathbf {v} \mathbf {v} ^{H}$，其中$w=\mathbf {x} ^{H}\mathbf {v} \mathbf {/} \mathbf {v} ^{H}\mathbf {x}$

式中$\mathbf {x} ^{H}$是$x$的共轭转置（亦称埃尔米特共轭或埃尔米特转置）。

则$Q$为一个$m\times m$的Householder矩阵，它满足

$Q\mathbf {x} =(\alpha ,0,\cdots ,0)^{T}.\,$

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

$Q_{1}A={\begin{bmatrix}\alpha _{1}&\star &\dots &\star \\0&&&\\\vdots &&A'&\\0&&&\end{bmatrix}}$

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

$Q_{k}={\begin{pmatrix}I_{k-1}&0\\0&Q_{k}'\end{pmatrix}}.$

将这个迭代过程进行$t$次之后（$t=\min(m-1,n)$）,将有

$R=Q_{t}\cdots Q_{2}Q_{1}A$

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

$Q=Q_{1}^{T}Q_{2}^{T}\cdots Q_{t}^{T},$

则$A=QR$为矩阵$A$的一个QR分解。

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

Matlab

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

[Q,R]=qr(A)

其中Q代表正规正交矩阵，

而R代表上三角形矩阵。

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