QR Decomposition

1. 定理

Theorem 1.1 QR Decomposition

如果 $A\in\mathbb{R}^{m\times n}$，则存在一个正交矩阵 $Q\in\mathbb{R}^{m\times m}$ 和一个上三角矩阵 $R\in\mathbb{R}^{m\times n}$ 使得 $A = QR$。

证明

对于 $n=1$，设 $Q$ 是相对于 $A \in \mathbb{R}^{m\times 1}$ 的 Householder 矩阵：

$$v = A \pm \|A\|_2e_1, Q = I - \frac{2vv^{\top}}{v^{\top}v}$$

并注意到 $Q^{\top} = Q$，那么 $R = Q^{\top}A$ 且 $R(2:m)=0$。

对于一般的 $n$，设 $A = [A_1|u]$ 其中 $u = A(:,n)$ 且 $A_1\in\mathbb{R}^{m\times(n-1)}$。

通过归纳，存在一个正交矩阵 $Q_1\in\mathbb{R}^{m\times m}$ 使得 $R_1 = Q_1^{\top}A_1$ 是上三角的，这意味着如果 $R_1 = \begin{bmatrix}R_{11}\\R_{12}\end{bmatrix}$ 其中 $R_{11}\in\mathbb{R}^{m\times m}$，那么 $R_{12}=0$。

设 $w = Q_1^{\top}u$，即 $u = Q_1 w$。

设 $u(n:m) = Q_2R_2$ 是 $u(n:m)$ 的 QR 分解。

如果 $Q := Q_1\begin{bmatrix}I_{n-1}& 0\\ 0& Q_2\end{bmatrix}$，$R := \begin{bmatrix}R_{11}& w(1:n-1)\\ R_{12}&R_2 \end{bmatrix}$，那么 $Q$ 是正交的，$R$ 是上三角的，且

$$\begin{aligned} QR &= Q_1 \begin{bmatrix}I_{n-1}& 0\\ 0& Q_2\end{bmatrix}\begin{bmatrix}R_{11}& w(1:n-1)\\ R_{12}&R_2 \end{bmatrix}\\ &= Q_1 \begin{bmatrix}R_{11}& w(1:n-1)\\ 0 & Q_2R_2=w(n:m) \end{bmatrix}\\ &= [A_1|u]= A, \end{aligned}$$

这完成了证明。 $\blacksquare$

Theorem 1.2 Thin QR Decomposition

如果 $A\in\mathbb{R}^{m\times n}$ 具有完全列秩，那么存在唯一的 QR 分解

$$A = Q_1 R_1$$

其中 $Q\in\mathbb{R}^{m\times m}$ 具有正交列，$R\in\mathbb{R}^{m\times n}$ 是上三角的，且对角线元素为正。

2. Computing QR Decomposition

2.1 Householder QR

2.2 Gram-Schmidt QR