QR分解

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

類別及定义
方陣
任何方块矩阵A都可以分解為
: A = QR
其中Q是正交矩阵（意味着QTQ = I）而R是上三角矩阵。如果A是非奇异的，且限定R的对角线元素为正，则这个因数分解是唯一的。

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

長方形矩陣
更一般地，我們可以將m×n的A矩陣，其中，分解成m×m酉矩阵Q和m×n三角矩陣R的乘積。由於m×n上三角矩陣的底部(m−n)行完全由零組成，因此對R或R和Q進行分解通常很有用：
:
A = QR = Q \begin{bmatrix} R_1 \\ 0 \end{bmatrix}
= \begin{bmatrix} Q_1 & Q_2 \end{bmatrix} \begin{bmatrix} R_1 \\ 0 \end{bmatrix}
= Q_1 R_1,

其中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变换将一个向量关于某个平面或者超平面进行反射。我们可以利用这个操作对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}\|
，并且在接下来矩阵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_1A = \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{bmatrix}
I_{k-1} & 0\\
0 & Q_k'\end{bmatrix}

将这个迭代过程进行t次之后（t = \min(m-1, n)）,将有
: R = Q_t \cdots Q_2Q_1A
其中R为一个上三角矩阵。因此，令
: Q = Q_1^T Q_2^T \cdots Q_t^T,
则A = QR为矩阵A的一个QR分解。

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

例子
现在要用Householder变换求解矩阵A的 QR 分解。
:A =
\begin{bmatrix} 0 & 3 & 1 \\
0 & 4 & -2 \\
2 & 1 & 1 \\
\end{bmatrix}

因为\alpha_1 = [ 0,\ 0,\ 2 ]^T , 令a_1 = ||\alpha_1||_2 = 2，则
: \omega_1 = \frac{\alpha_1 - a_1e_1}
= \frac{\boldsymbol{\beta}}{\sqrt{\langle \boldsymbol{\beta},\boldsymbol{\beta} \rangle }}

那么\{ \boldsymbol{\eta}_1,\ldots, \boldsymbol{\eta}_{k}, \boldsymbol{\eta}_{k+1} \}就是\boldsymbol{V}^k在\boldsymbol{v}上扩展的子空间\mathrm{span}\{\boldsymbol{v},\boldsymbol{\eta}_1,...,\boldsymbol{\eta}_k\}的标准正交基。

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

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

|-
|| ||\boldsymbol{\beta}_2
= \boldsymbol{v}_2-\langle \boldsymbol{v}_2, \boldsymbol{\eta}_1 \rangle \boldsymbol{\eta}_1,
|| ||\boldsymbol{\eta}_2 = {\boldsymbol{\beta}_2 \over \|\boldsymbol{\beta}_2\|}
|-
|| ||\boldsymbol{\beta}_3
= \boldsymbol{v}_3 -
\langle \boldsymbol{v}_3, \boldsymbol{\eta}_1 \rangle \boldsymbol{\eta}_1 -
\langle \boldsymbol{v}_3, \boldsymbol{\eta}_2 \rangle \boldsymbol{\eta}_2 ,

|| ||\boldsymbol{\eta}_3 = {\boldsymbol{\beta}_3 \over \|\boldsymbol{\beta}_3\|}
|-
|| ||align="center"|\vdots
|| ||align="center"|\vdots
|-
|| ||\boldsymbol{\beta}_n = \boldsymbol{v}_n-\sum_{i=1}^{n-1}\langle \boldsymbol{v}_n, \boldsymbol{\eta}_i \rangle \boldsymbol{\eta}_i,
|| ||\boldsymbol{\eta}_n = {\boldsymbol{\beta}_n\over\|\boldsymbol{\beta}_n\|}
|}

这样就得到\mathrm{span}\{ \boldsymbol{v}_1, \ldots , \boldsymbol{v}_n \}上的一组正交基\{ \boldsymbol{\beta}_1, \ldots , \boldsymbol{\beta}_n \}，以及相应的标准正交基\{ \boldsymbol{\eta}_1, \ldots , \boldsymbol{\eta}_n \}。
例子
现在要用格拉姆-施密特变换求解矩阵A的 QR 分解。
:A =
\begin{bmatrix} 1 & 2 & 4 \\
0 & 0 & 5 \\
0 & 3 & 6 \\
\end{bmatrix}

令， a = [1 , 0 , 0]
:q_1 = \frac{a} =
\begin{bmatrix} 1 \\
0 \\
0 \\
\end{bmatrix}

:\hat{q_2} = b - (b * q_1)q_1 =
\begin{bmatrix} 2 \\
0 \\
3 \\
\end{bmatrix} - 2
\begin{bmatrix} 1 \\
0 \\
0 \\
\end{bmatrix} =
\begin{bmatrix} 0 \\
0 \\
3 \\
\end{bmatrix}

:q_2 = \frac{\hat{q_2}} =
\begin{bmatrix} 0 \\
0 \\
1 \\
\end{bmatrix}

:\hat{q_3} = c - (c q_1)q_1 - (c q_2)q_2 =
\begin{bmatrix} 4 \\
5 \\
6 \\
\end{bmatrix} - 4
\begin{bmatrix} 1 \\
0 \\
0 \\
\end{bmatrix} - 6
\begin{bmatrix} 0 \\
0 \\
1 \\
\end{bmatrix}
=
\begin{bmatrix} 0 \\
5 \\
0 \\
\end{bmatrix}

:q_3 = \frac{\hat{q_3}} =
\begin{bmatrix} 0 \\
1 \\
0 \\
\end{bmatrix}

那么可知，
: Q =
\begin{bmatrix} 1 & 0 & 0 \\
0 & 0 & 1 \\
0 & 1 & 0 \\
\end{bmatrix}

由 A = QR，可知，
: R =
\begin{bmatrix} 1 & 2 & 4 \\
0 & 3 & 6 \\
0 & 0 & 5 \\
\end{bmatrix}

Matlab
MATLAB以qr函数来执行QR分解法，其语法为
: [Q,R]=qr(A)

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

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

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

如果m \leq n, 那么A^{T} =QR,这里Q^{T} = Q^{-1})。

R 的形式是 R = \begin{bmatrix} R_1 \\ 0 \end{bmatrix}，R_1是R上不为0的部分。
那么对于
:
x = Q \begin{bmatrix}
\left(R_1^\textsf{T}\right)^{-1}b \\
0
\end{bmatrix}

如果 m > n, 那么A =QR,这里Q^{T} = Q^{-1})。本质是最小化||A\hat{x} - b||
:\hat{x} = R_1^{-1} \left(Q_1^\textsf{T} b\right)

參考文獻
外部連結
*
*