QR Decomposition
1. 定理
定理 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 矩阵：
并注意到 \(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\) 是上三角的，且
这完成了证明。 \(\blacksquare\)
定理 1.2 Thin QR Decomposition
如果 \(A\in\mathbb{R}^{m\times n}\) 具有完全列秩，那么存在唯一的 QR 分解
其中 \(Q\in\mathbb{R}^{m\times m}\) 具有正交列，\(R\in\mathbb{R}^{m\times n}\) 是上三角的，且对角线元素为正。