线性代数 Cheat Sheet 6-5：最小二乘问题
当方程组 $A \boldsymbol x = \boldsymbol b$ 的解不存在，但又需要求解时，最好的方法是寻找一个使 $A \boldsymbol x$ 尽可能接近 $\boldsymbol b$ 的 $\boldsymbol x$。
考虑 $A \boldsymbol x$ 作为 $\boldsymbol b$ 的一个近似。$\boldsymbol b$ 和 $A \boldsymbol x$ 之间的距离越小，$\lVert \boldsymbol b – A \boldsymbol x\rVert$ 近似程度越好。一般地最小二乘问题就是找出使 $\lVert \boldsymbol b – A \boldsymbol x\rVert$ 尽量小的 $\boldsymbol x$。术语“最小二乘”来源于这样的事实，即 $\lVert \boldsymbol b – A \boldsymbol x\rVert$ 是平方和的平方根。
定义 如果 $m \times n$ 矩阵 $A$ 和向量 $\boldsymbol b$ 属于 $\mathbb{R}^n$，则 $A \boldsymbol x = \boldsymbol b$ 的最小二乘解是 $\mathbb{R}^n$ 中的 $\hat{\boldsymbol x}$，使得
\begin{equation}
\lVert \boldsymbol b – A \hat{\boldsymbol x}\rVert \leq \lVert \boldsymbol b – A \boldsymbol x\rVert
\end{equation}
对所有 $\boldsymbol x \in \mathbb{R}^n$ 成立。
最小二乘问题最重要的特征是无论怎么选取 $\boldsymbol x$，向量 $A \boldsymbol x$ 必然属于列空间 $\mathrm{Col}\; A$。因此我们寻求 $\mathrm{Col}\; A$，使得 $A \boldsymbol x$ 是 $\mathrm{Col}\; A$ 中最接近 $\boldsymbol b$ 的点。如果 $\boldsymbol b$ 恰好在 $\mathrm{Col}\; A$ 中，那么对于某个 $\boldsymbol x$，有 $\boldsymbol b$ 等于 $A \boldsymbol x$，且这样的 $\boldsymbol x$ 是一个“最小二乘解”。
Contents
1. 一般最小二乘问题的解
对上面给定的 $A$ 和 $\boldsymbol b$，应用前文 的最佳逼近定理于子空间 $\mathrm{Col}\; A$，取
\begin{equation}
\hat{\boldsymbol b} = \mathrm{Proj}_{\mathrm{Col}\; A} \boldsymbol b
\end{equation}
由于 $\hat{\boldsymbol b}$ 属于 $A$ 的列空间，故方程 $A \boldsymbol x = \hat{\boldsymbol b}$ 是相容的，且存在一个属于 $\mathbb{R}^n$ 的 $\hat{\boldsymbol x}$，使得
\begin{equation}
A \hat{\boldsymbol x} = \hat{\boldsymbol b} \tag{1}
\end{equation}
由于 $\hat{\boldsymbol b}$ 是 $\mathrm{Col}\; A$ 中最接近 $\boldsymbol b$ 的点，因此一个向量 $\hat{\boldsymbol x}$ 是 $A \boldsymbol x = \boldsymbol b$ 的一个最小二乘解的充分必要条件是 $\hat{\boldsymbol x}$ 满足 $(1)$。这个属于 $\mathbb{R}^n$ 的 $\hat{\boldsymbol x}$ 是一系列由 $A$ 的列构造的 $\hat{\boldsymbol b}$ 的权。
若 $\hat{\boldsymbol x}$ 满足 $A \hat{\boldsymbol x} = \hat{\boldsymbol b}$，则由前文的正交分解定理，投影 $\hat{\boldsymbol b}$ 具有性质 $\boldsymbol b – \hat{\boldsymbol b}$ 与 $\mathrm{Col}\; A$ 正交，即 $\boldsymbol b – A \hat{\boldsymbol x}$ 正交于 $A$ 的每一列。如果 $\boldsymbol a_j$ 是 $A$ 的任意列，那么 $\boldsymbol a_j \cdot (\boldsymbol b – A \hat{\boldsymbol x}) = 0$ 且 $\boldsymbol a_j^\mathsf{T} (\boldsymbol b – A \hat{\boldsymbol x}) = 0$。由于每一个 $a_j^\mathsf{T}$ 是 $A$ 的行，因此
\begin{equation}
A^\mathsf{T} (\boldsymbol b – A \hat{\boldsymbol x}) = \boldsymbol 0 \tag{2}
\end{equation}
故有
\begin{equation}
A^\mathsf{T} \boldsymbol b – A^\mathsf{T} A \hat{\boldsymbol x} = \boldsymbol 0 \\
A^\mathsf{T} A \hat{\boldsymbol x} = A^\mathsf{T} \boldsymbol b
\end{equation}
此计算表明 $A \boldsymbol x = \boldsymbol b$ 的每个最小二乘解满足方程
\begin{equation}
A^\mathsf{T} A \boldsymbol x = A^\mathsf{T} \boldsymbol b \tag{3}
\end{equation}
矩阵方程 $(3)$ 表示的线性方程组通常称为 $A \boldsymbol x = \boldsymbol b$ 的法方程。$(3)$ 的解通常用 $\hat{\boldsymbol x}$ 表示。
定理 13 方程 $A \boldsymbol x = \boldsymbol b$ 的最小二乘解集和法方程 $A^\mathsf{T} A \boldsymbol x = A^\mathsf{T} \boldsymbol b$ 的非空解集一致。
定理 14 设 $A$ 是 $m \times n$ 矩阵，下面的条件是逻辑等价的：
a. 对于 $\mathbb{R}^m$ 中的每个 $\boldsymbol b$，方程 $A \boldsymbol x = \boldsymbol b$ 有唯一最小二乘解。
b. $A$ 的列时线性无关的。
c. 矩阵 $A^\mathsf{T} A$ 是可逆的。
当这些条件成立时，最小二乘解 $\hat{\boldsymbol x}$ 有下面的表示：
\begin{equation}
\hat{\boldsymbol x} = (A^\mathsf{T} A)^{-1} A^\mathsf{T} \boldsymbol b \tag{4}
\end{equation}
当最小二乘解 $\hat{\boldsymbol x}$ 用于产生 $\boldsymbol b$ 的近似 $A \hat{\boldsymbol x}$ 时，从 $\boldsymbol b$ 到 $A \hat{\boldsymbol x}$ 的距离称为这个近似的最小二乘误差。
2. 最小二乘解的另一个计算
某些时候，最小二乘解问题的法方程可能是病态的，也就是 $A^\mathsf{T} A$ 的元素在计算中出现的小误差有时可导致 $\hat{\boldsymbol x}$ 中出现较大的误差。如果 $A$ 的列线性无关，则最小二乘解常常可通过 $A$ 的 QR 分解更可靠地求出。
定理 15 给定一个 $m \times n$ 矩阵 $A$，它具有线性无关的列，取 $A = QR$ 是 $A$ 类似定理 12 的 QR 分解，那么对每一个属于 $\mathbb{R}^m$ 的 $\boldsymbol b$，方程 $A \boldsymbol x = \boldsymbol b$ 有唯一的最小二乘解，其解为
\begin{equation}
\hat{\boldsymbol x} = R^{-1} Q^\mathsf{T} \boldsymbol b
\end{equation}
对于定理 15 中的 $\hat{\boldsymbol x}$，有 $A \hat{\boldsymbol x} = Q R \hat{\boldsymbol x} = Q R R^{-1} Q^\mathsf{T} \boldsymbol b = Q Q^\mathsf{T} \boldsymbol b$。由定理 12，$Q$ 的列形成 $\mathrm{Col}\; A$ 的标准正交基，因此由定理 10，$Q Q^\mathsf{T} \boldsymbol b$ 是 $\boldsymbol b$ 在 $\mathrm{Col}\; A$ 上的正交投影 $\hat{\boldsymbol b}$，那么 $A \hat{\boldsymbol x} = \hat{\boldsymbol b}$ 说明 $\hat{\boldsymbol x}$ 是 $A \boldsymbol x = \boldsymbol b$ 的最小二乘解。