超定方程组

已知 m×nm \times n 的列满秩矩阵 A\boldsymbol{A}（m≥nm \ge n），未知 nn 维列向量 x\boldsymbol{x}，已知 mm 维列向量 y\boldsymbol{y}，有：

Ax=y\boldsymbol{Ax} = \boldsymbol{y}

当 m>nm > n 时，这是一个超定方程组（方程的数量大于未知数的数量，且这些方程之间经常存在一些小矛盾），通常不存在 x\boldsymbol{x} 的精确解。那么我们退一步，我们想要一个“很像解”的解。

正规方程

🤓👆诶，我们可以往等式两边的左边同乘一个 AT\boldsymbol{A}^{\mathrm{T}}（这一乘其实严格来说并不严谨，毕竟原来等号就很难成立，且矩阵乘法不满足消去律，这里实际上我们构造了一个新的方程），得到：

ATAx=ATy\boldsymbol{A}^{\mathrm{T}} \boldsymbol{Ax} = \boldsymbol{A}^{\mathrm{T}} \boldsymbol{y}

这个方程就叫正规方程。

这式子漂不漂亮？这式子太漂亮了！ATA\boldsymbol{A}^{\mathrm{T}} \boldsymbol{A} 是 nn 阶方阵（可以求逆！），x\boldsymbol{x} 和 ATy\boldsymbol{A}^{\mathrm{T}} \boldsymbol{y} 都是 nn 维列向量，那一切就舒服♡多了：

x=(ATA)−1ATy\boldsymbol{x} = \left( \boldsymbol{A}^{\mathrm{T}} \boldsymbol{A} \right)^{-1} \boldsymbol{A}^{\mathrm{T}} \boldsymbol{y}

这样，我们就可以得到一个很不错（实际上是最不错，这就是今天要证明的）的 x\boldsymbol{x} 的解。其中，(ATA)−1AT\left( \boldsymbol{A}^{\mathrm{T}} \boldsymbol{A} \right)^{-1} \boldsymbol{A}^{\mathrm{T}} 称为 A\boldsymbol{A} 的伪逆。（就像伪娘一样）

残差、最小二乘解

很多时候，精确解对于超定方程组是个奢求，即 Ax\boldsymbol{Ax} 和 y\boldsymbol{y} 总是有一些偏差的。对于一个解，我们定义它的残差向量 r\boldsymbol{r}：

r=y−Ax\boldsymbol{r} = \boldsymbol{y} - \boldsymbol{Ax}

显然，残差的范数（模）∥r∥\lVert \boldsymbol{r} \rVert 越小，这个解 x\boldsymbol{x} 就越好。当 ∥r∥\lVert \boldsymbol{r} \rVert 取到最小值时，x\boldsymbol{x} 就是我们最想要的最小二乘解（Ax\boldsymbol{Ax} 与 y\boldsymbol{y} 各位相差的平方和最小）。

证明：正规方程的解就是最小二乘解

因为我太菜了，导不出来 基于矩阵求导的证明一个字也看不懂，所以这里换个角度，用几何法来证。哎呀~ 几何法得了 MVP！

寻找最小二乘解，从几何角度看，就是在 A\boldsymbol{A} 的列空间 Col⁡(A)\operatorname{Col}(\boldsymbol{A})（由 A\boldsymbol{A} 各个列向量张成的空间）中寻找与 y\boldsymbol{y} 最接近的向量（即 y\boldsymbol{y} 在 Col⁡(A)\operatorname{Col}(\boldsymbol{A}) 中的正交投影）。那么，正如平面外一点到平面，垂线段最短，想要 y\boldsymbol{y} 与 Ax\boldsymbol{Ax} 的残差 r\boldsymbol{r} 最短，那 r\boldsymbol{r} 就必须与 Col⁡(A)\operatorname{Col}(\boldsymbol{A}) 正交。

与 Col⁡(A)\operatorname{Col}(\boldsymbol{A}) 正交，就是和它的每个基向量都正交（内积等于 0）。记 A=[c1c2⋯cn]\boldsymbol{A} = \begin{bmatrix} \boldsymbol{c}_{1} & \boldsymbol{c}_{2} & \cdots & \boldsymbol{c}_{n} \end{bmatrix}，那么：

{c1Tr=0c2Tr=0⋮cnTr=0\left\{ \begin{array}{c} \boldsymbol{c}_{1}^{\mathrm{T}} \boldsymbol{r} = 0 \\ \boldsymbol{c}_{2}^{\mathrm{T}} \boldsymbol{r} = 0 \\ \vdots \\ \boldsymbol{c}_{n}^{\mathrm{T}} \boldsymbol{r} = 0 \end{array} \right.

合起来就是：

ATr=0\boldsymbol{A}^{\mathrm{T}} \boldsymbol{r} = \boldsymbol{0}

将 r=y−Ax\boldsymbol{r} = \boldsymbol{y} - \boldsymbol{Ax} 代入：

AT(y−Ax)=0\boldsymbol{A}^{\mathrm{T}} ( \boldsymbol{y} - \boldsymbol{Ax} ) = \boldsymbol{0}

整理一下：

ATAx=ATy\boldsymbol{A}^{\mathrm{T}} \boldsymbol{Ax} = \boldsymbol{A}^{\mathrm{T}} \boldsymbol{y}

这，恰是正规方程！

所以，求解超定方程组时，通过构造正规方程得到的解就是最小二乘解。

Quod Erat Demonstrandum Miau~