这是我关于线性代数中两种重要方程组——超定方程组和欠定方程组——的解法学习总结。这两种情况在理论和实际应用（如数据拟合、信号处理）中都非常常见。

1. 超定方程组 (Overdetermined System)

当线性方程组 $Ax=b$ 中，方程的数量大于未知数的数量时，我们称之为超定方程组。

• 矩阵形式：$A$ 是一个 “瘦高” 型的 $m \times n$ 矩阵，其中 $m > n$。
• 解的性质：通常情况下，由于约束（方程）过多，系统没有精确解。向量 $b$ 不在矩阵 $A$ 的列空间中。
• 求解目标：我们不再寻求精确解，而是寻找一个最优近似解 $\hat{x}$，使得误差向量 $Ax-b$ 的长度（L2范数）最小。这就是著名的最小二乘法 (Least Squares Method)。
  $$ \min_{\hat{x}} \|A\hat{x} - b\|_2^2 $$
• 核心方法：该问题的解可以通过正规方程 (Normal Equation) 导出。当矩阵 $A$ 列满秩（即列向量线性无关）时，正规方程为：
  $$ A^T A \hat{x} = A^T b $$
• 最终解：通过求解正规方程，我们得到最优解 $\hat{x}$。这个解可以用左伪逆 (Left Pseudoinverse) $A^\dag$ 表示。
  $$ \hat{x} = (A^T A)^{-1} A^T b = A^\dag b $$

附：最优解的证明方法

超定方程的最优解（最小二乘解）可以通过多种方式证明，这里介绍两种核心方法。

a) 微积分推导 (Derivation via Calculus)

这种方法将问题视为一个求函数最小值的优化问题。目标函数是误差的平方 $f(x) = |Ax-b|^2$。当函数的梯度为零时，我们能找到极值点。

1. 定义目标函数：
   $$ f(x) = \|Ax - b\|^2 = \sum_{i=1}^{m} \left( \sum_{j=1}^{n} A_{ij}x_j - b_i \right)^2 $$
2. 计算梯度：我们对 $f(x)$ 求关于向量 $x$ 的梯度 $\nabla f(x)$。这是一个标准的矩阵求导结果。
   $$ \nabla f(x) = 2A^T(Ax-b) $$
3. 令梯度为零：最小值点 $\hat{x}$ 必须满足梯度为零的条件。
   $$ \nabla f(\hat{x}) = 2A^T(A\hat{x} - b) = 0 $$
4. 求解：整理上式，我们便得到了正规方程，进而求得最优解。
   $$ A^T A \hat{x} = A^T b \\ \implies \hat{x} = (A^T A)^{-1} A^T b $$

b) 直接验证 (Direct Verification)

这种方法更为直接，它首先给出解的形式，然后证明对于任何其他的向量，其误差都更大。

1. 定义最优解 $\hat{x}$ 满足 $A^T(A\hat{x}-b)=0$。
2. 展开误差：对于任意一个n维向量 $x$，我们分析其误差平方 $|Ax-b|^2$。通过引入 $\hat{x}$，我们进行如下代数变形：
   $$ \begin{aligned} \|Ax - b\|^2 &= \|(Ax - A\hat{x}) + (A\hat{x} - b)\|^2 \\ &= \|A(x - \hat{x})\|^2 + \|A\hat{x} - b\|^2 + 2(A(x - \hat{x}))^T (A\hat{x} - b) \\ &= \|A(x - \hat{x})\|^2 + \|A\hat{x} - b\|^2 + 2(x - \hat{x})^T \underbrace{A^T (A\hat{x} - b)}_{=0} \\ &= \|A(x - \hat{x})\|^2 + \|A\hat{x} - b\|^2 \end{aligned} $$
3. 得出结论：我们得到了一个类似勾股定理的优美形式。因为范数的平方 $|A(x - \hat{x})|^2$ 永远大于等于零，所以：
   $$ \|Ax - b\|^2 \ge \|A\hat{x} - b\|^2 $$
   这就证明了 $\hat{x}$ 确实是最小二乘解。等号仅在 $|A(x - \hat{x})|^2=0$ 时成立。因为 $A$ 的列向量线性无关，这只有在 $x=\hat{x}$ 时才会发生。

2. 欠定方程组 (Underdetermined System)

当线性方程组 $Ax=b$ 中，未知数的数量大于方程的数量时，我们称之为欠定方程组。

• 矩阵形式：$A$ 是一个 “矮胖” 型的 $m \times n$ 矩阵，其中 $m < n$。
• 解的性质：通常情况下，由于约束（方程）过少，如果系统有解，则它有无穷多个解。
• 求解目标：在无穷多的解中，我们需要一个标准来挑选出“最好”的一个。通常，我们选择那个自身长度（L2范数）最小的解，这被称为最小范数解 (Minimum Norm Solution)。
  $$ \min_{\hat{x}} \|\hat{x}\|_2^2 \quad \text{subject to} \quad A\hat{x}=b $$
• 核心方法：当矩阵 $A$ 行满秩（即行向量线性无关）时，我们可以保证 $AA^T$ 可逆，从而找到唯一的最小范数解。
• 最终解：最小范数解可以用右伪逆 (Right Pseudoinverse) $A^\dag$ 表示。
  $$ \hat{x} = A^T (AA^T)^{-1} b = A^\dag b $$

附：最优解的证明方法

欠定方程的最小范数解可以通过拉格朗日乘数法 (Method of Lagrange Multipliers) 优雅地推导出来。

1. 构造拉格朗日函数：我们将目标函数 $f(x) = x^Tx$ 和约束条件 $Ax-b=0$ 结合起来，构造拉格朗日函数 $L(x, \lambda)$，其中 $\lambda$ 是一个 $m \times 1$ 的拉格朗日乘数向量。
   $$ L(x, \lambda) = x^T x - \lambda^T(Ax - b) $$
2. 梯度置零：为了找到极值点，我们将 $L(x, \lambda)$ 分别对 $x$ 和 $\lambda$ 求偏导，并令其为零。
3. 对 $x$ 求导：
   $$ \nabla_x L(x, \lambda) = 2x - A^T \lambda = 0 \implies x = \frac{1}{2}A^T \lambda $$
   这个重要的结果表明，最小范数解 $\hat{x}$ 必须是 $A^T$ 的列向量的线性组合，即 $\hat{x}$ 必须位于 $A$ 的行空间中。为简化表示，令新变量 $z = \frac{1}{2}\lambda$，则 $\hat{x} = A^T z$。
4. 对 $\lambda$ 求导：这会自然地得到原始的约束条件。
   $$ \nabla_\lambda L(x, \lambda) = -(Ax - b) = 0 \implies Ax = b $$
5. 联立求解：我们将第3步得到的结果 $\hat{x} = A^T z$ 代入第4步的约束条件中。
   $$ A(A^T z) = b \implies (AA^T)z = b $$
   因为我们假设 $A$ 是行满秩的，所以 $m \times m$ 矩阵 $AA^T$ 是可逆的。因此，我们可以解出 $z$：
   $$ z = (AA^T)^{-1}b $$
6. 得到最终解：最后，将 $z$ 代回到 $\hat{x} = A^T z$ 的表达式中，就得到了最小范数解 $\hat{x}$ 的最终形式。
   $$ \hat{x} = A^T z = A^T(AA^T)^{-1}b $$

3. 总结与对比

伪逆 $A^\dag$ 为我们提供了一个统一的框架来理解这些“最优解”。它总能根据问题的性质，赋予我们一个有意义的、唯一的答案。