QR分解

QR 分解（QR factorization）把矩阵的列改写为一组互相垂直的单位方向，再记录原列由这些方向组成的系数。设实矩阵 $A$ 有 $m$ 行、 $n$ 列， $m \geq n$ 且各列线性无关。它的薄 QR 分解是 $A = Q R, Q^{𝖳} Q = I_{n},$ 其中 $Q$ 是 $m \times n$ 矩阵， $R$ 是对角元非零的 $n \times n$ 上三角矩阵。 $Q$ 的列给出方向， $R$ 说明原来的每一列沿这些方向走了多远。若约定 $R$ 的对角元为正，满列秩情形下这组薄分解唯一。

两列向量的分解

取 $a_{1} = (2, 1)^{𝖳}$ 、 $a_{2} = (1, 2)^{𝖳}$ 。第一列长度为 $\sqrt{5}$ ，沿它的单位方向为 $q_{1} = (2, 1)^{𝖳} / \sqrt{5}$ 。第二列在这个方向上的系数是 $r_{12} = q_{1}^{𝖳} a_{2} = \frac{2 \cdot 1 + 1 \cdot 2}{\sqrt{5}} = \frac{4}{\sqrt{5}} .$ 减去这一部分，得到与 $q_{1}$ 垂直的余量： $w_{2} = a_{2} - r_{12} q_{1} = (1, 2)^{𝖳} - \frac{4}{5} (2, 1)^{𝖳},$ 所以 $w_{2} = (- 3 / 5, 6 / 5)^{𝖳}$ 。核对 $a_{1}^{𝖳} w_{2} = - 6 / 5 + 6 / 5 = 0$ 。余量的长度为 $3 / \sqrt{5}$ ，所以 $q_{2} = w_{2} / ‖ w_{2} ‖ = (- 1, 2)^{𝖳} / \sqrt{5}$ 。

图中第二列 $a_{2}$ 被拆成沿第一列的投影 $p = (8 / 5, 4 / 5)$ 与垂直余量 $w_{2} = (- 3 / 5, 6 / 5)$ 。两段相接到 $a_{2}$ 的端点；直角对应上面的点积为零。

从原点画出第一列二一和第二列一二，第二列分解成投影八分之五四分之五与垂直余量负五分之三六分之五 — 第二列等于沿第一列的投影加上垂直余量；QR 将两条原方向换成互相垂直的单位方向。

把两条单位方向放入 $Q$ ，把长度和投影系数放入 $R$ ，便得 $A = (\begin{matrix} 2 & 1 \\ 1 & 2 \end{matrix}), Q = \frac{1}{\sqrt{5}} (\begin{matrix} 2 & - 1 \\ 1 & 2 \end{matrix}) .$ $R = \frac{1}{\sqrt{5}} (\begin{matrix} 5 & 4 \\ 0 & 3 \end{matrix}) .$ 直接相乘有 $Q R = \frac{1}{5} (\begin{matrix} 10 & 8 - 3 \\ 5 & 4 + 6 \end{matrix}) = A$ ；而 $Q^{𝖳} Q = I_{2}$ 。这里并未改变矩阵表示的变换，只是把输入列的组合换成便于计算的正交坐标。

从逐列投影得到一般公式

设 $A = [a_{1} \dots a_{n}]$ 。按列执行Gram-Schmidt正交化：对第 $j$ 列，先计算它沿此前单位方向的系数 $r_{i j} = q_{i}^{𝖳} a_{j}$ （ $i < j$ ），再令 $w_{j} = a_{j} - \sum_{i < j} r_{i j} q_{i},$ 再令 $r_{j j} = ‖ w_{j} ‖$ 、 $q_{j} = w_{j} / r_{j j}$ 。对任意 $k < j$ ，因为已得的 $q_{i}$ 两两正交， $q_{k}^{𝖳} w_{j} = q_{k}^{𝖳} a_{j} - \sum_{i < j} r_{i j} q_{k}^{𝖳} q_{i} = r_{k j} - r_{k j} = 0.$ 每个新 $q_{j}$ 因而与旧方向正交。原列又满足 $a_{j} = \sum_{i < j} r_{i j} q_{i} + r_{j j} q_{j}$ ；把所有列并排，就是 $A = Q R$ 。第 $j$ 列只用到前 $j$ 个方向，因此 $R$ 的主对角线以下全为零。

满列秩保证每个 $w_{j} \neq 0$ ：若它为零，第 $j$ 列已经由前几列张成，与列线性无关矛盾。这同时解释了 $r_{j j} > 0$ 和 $R$ 可逆的来源。若列相关，某一步会遇到零余量；这时仍可做带秩信息的 QR 计算，但不能沿用此处“ $R$ 可逆”的求解步骤。

用 QR 求一条最小二乘直线

设三个自变量为 $t = 0, 1, 2$ ，观测为 $b = (1, 2, 2)^{𝖳}$ 。用 $c + d t$ 拟合时，设计矩阵为 $A = (\begin{matrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{matrix}), x = (\begin{matrix} c \\ d \end{matrix}) .$ 每一行都对应一个时刻的预测，故 $A x = (c, c + d, c + 2 d)^{𝖳}$ 。第一列是常数方向，第二列是时间方向。把时间列在常数方向上的部分减掉，相当于把 $(0, 1, 2)$ 中心化成 $(- 1, 0, 1)$ 。由此得到 $Q = (\begin{matrix} 1 / \sqrt{3} & - 1 / \sqrt{2} \\ 1 / \sqrt{3} & 0 \\ 1 / \sqrt{3} & 1 / \sqrt{2} \end{matrix}),$ $R = (\begin{matrix} \sqrt{3} & \sqrt{3} \\ 0 & \sqrt{2} \end{matrix}) .$ 两列 $Q$ 的点积为零、长度为一。用观测分别与它们做内积，有 $Q^{𝖳} b = (5 / \sqrt{3}, 1 / \sqrt{2})^{𝖳}$ 。求解 $R x = Q^{𝖳} b$ ，先从第二行得 $\sqrt{2} d = 1 / \sqrt{2}$ ，再从第一行得 $\sqrt{3} (c + d) = 5 / \sqrt{3}$ 。得 $d = 1 / 2$ 、 $c = 7 / 6$ 。拟合值是 $(7 / 6, 5 / 3, 13 / 6)$ ，残差为 $b - A x = (- 1 / 6, 1 / 3, - 1 / 6)$ ，残差平方和为 $1 / 6$ 。残差与常数列及时间列的点积均为零，和最小二乘法的正交条件一致。

这里的三角方程不只是凑出同一个答案。记 $p = Q Q^{𝖳} b$ 为观测在列空间上的正交投影，则 $b - p$ 与该空间垂直。对任意参数 $x$ ，先把残差拆开： $b - A x = (b - p) + Q (Q^{𝖳} b - R x) .$ 两项正交，且 $Q$ 保持向量长度，因此 $‖ b - A x ‖^{2} = ‖ b - p ‖^{2} + ‖ Q^{𝖳} b - R x ‖^{2} .$ 第二项非负，且 $R$ 可逆，故令 $R x = Q^{𝖳} b$ 恰好给出唯一的最小二乘参数。这个等式也解释了残差为何仍可能不为零： $b - p$ 不在模型允许的预测方向内。

精确计算与浮点计算的边界

在精确算术中，满列秩矩阵的正规方程 $A^{𝖳} A x = A^{𝖳} b$ 与 QR 方程给出同一个解。浮点计算时，直接形成 $A^{𝖳} A$ 会把二范数条件数平方；两列几乎相关时可能失去有效数字。上面的逐列投影适合手算和解释结构，实际程序常用 Householder 反射求 QR，以更好地保持正交性。数值实现方法与推导中选用的手算法需要区分。

练习可把观测改为 $(1, 2, 3)$ 而保持三个时间不变。此时 $Q^{𝖳} b = (6 / \sqrt{3}, 2 / \sqrt{2})^{𝖳}$ ，三角方程给出 $d = 1, c = 1$ ；三点恰落在 $1 + t$ 上，残差为零。原例的非零残差来自数据不共线，而不是 QR 分解不精确。

参考资料与知识联系

Boyd 与 Vandenberghe，《Introduction to Applied Linear Algebra》：正交化、薄 QR 与最小二乘。
Driscoll 与 Braun，《Fundamentals of Numerical Computation》：QR 分解及Householder 计算：分解、求解与浮点稳定性。
先修：正交投影、Gram-Schmidt正交化；后续：最小二乘法、条件数、伪逆。