求解线性最小二乘问题的经典算法——正规方程法
字数 2848 2025-12-19 19:08:49

好的，我注意到在您提供的冗长列表中，关于求解线性最小二乘问题的经典算法——正规方程法并未出现过。这是一个极其重要且基础的方法。下面我将为您详细讲解。

基于正规方程法求解线性最小二乘问题

1. 问题描述

首先，我们需要明确什么是“线性最小二乘问题”。在科学计算和数据分析中，我们经常会遇到一个实际问题：我们有一组观测数据，希望通过一个线性模型（由一组基函数的线性组合构成）来拟合或逼近这些数据。通常，模型的参数个数（比如 n）远小于观测数据的个数（比如 m），这导致由模型和数据构成的线性方程组是“超定的”，即方程数量多于未知数数量，通常没有精确解。

数学描述如下：
给定一个矩阵 A ∈ ℝ^(m×n) (m ≥ n) 和一个向量 b ∈ ℝ^m，我们希望找到一个向量 x ∈ ℝ^n，使得线性模型 A x 在某种度量下最接近观测数据 b。最常用的度量是欧几里得范数（2-范数）的平方。因此，问题转化为求解：
minimize || **b** - **A x** ||₂²，对所有的 x ∈ ℝ^n。
这里，||·||₂ 表示向量的2-范数（即长度）。这个优化问题就称为线性最小二乘问题。

2. 解题思路与推导——为什么是“正规方程”？

我们的目标是最小化残差向量 r = b - A x 的范数平方。这本质上是一个无约束的凸优化问题。我们可以通过微积分来找到极值点。

目标函数：f(**x**) = || **b** - **A x** ||₂² = (**b** - **A x**)^T (**b** - **A x**)。
将其展开：
f(**x**) = **b**^T **b** - 2**x**^T **A**^T **b** + **x**^T **A**^T **A** **x**。

为了求最小值，我们对 x 求梯度（即对每个分量求偏导数，然后组合成向量），并令其等于零向量：
∇f(**x**) = -2 **A**^T **b** + 2 **A**^T **A** **x** = 0。

化简这个方程，我们得到：
**A**^T **A** **x** = **A**^T **b**。

这个关键的方程组就叫做正规方程。它是一个关于 x 的线性方程组，系数矩阵是 N = A^T A ∈ ℝ^(n×n)，这是一个对称的半正定矩阵。如果矩阵 A 是满列秩的（即其列向量线性无关，rank(A) = n），那么 A^T A 就是对称正定矩阵，是可逆的。此时，正规方程有唯一解，也就是原最小二乘问题的最优解：
**x*** = (**A**^T **A**)^(-1) **A**^T **b**。

矩阵 (**A**^T **A**)^(-1) **A**^T 也被称为矩阵 A 的 Moore-Penrose伪逆 的一种计算方法（当 A 满列秩时）。

3. 算法步骤详解

基于正规方程求解线性最小二乘问题 min ||Ax - b||₂² 的完整算法步骤如下：

前提条件：假设矩阵 A ∈ ℝ^(m×n) 是满列秩的 (m ≥ n)。

步骤 1：形成正规方程系数矩阵和右端项

  • 计算 C = A^T A。这是一个 n×n 的矩阵。计算它需要大约 m * n² 次浮点运算（如果利用对称性可以减半，但复杂度仍是 O(m n²)）。
  • 同时计算向量 d = A^T b。这是一个 n 维向量，计算需要约 2 m n 次运算。
    现在，我们得到了一个新的、规模更小的线性方程组：**C x = d**。

步骤 2：求解对称正定线性方程组
由于 C 是对称正定的，我们可以使用稳定且高效的Cholesky分解来求解。

  • Cholesky分解：将 C 分解为一个下三角矩阵 L 和其转置的乘积，即 **C = L L**^T，其中 L 的对角线元素为正。
    • 从第一行开始，逐列计算。对于 j = 1, 2, ..., n：
      L_{j,j} = sqrt(C_{j,j} - Σ_{k=1}^{j-1} L_{j,k}²)
      L_{i,j} = (C_{i,j} - Σ_{k=1}^{j-1} L_{i,k} L_{j,k}) / L_{j,j}， 对于 i = j+1, ..., n。
  • 前向替代：解下三角方程组 **L y = d**，得到中间向量 y。
  • 后向替代：解上三角方程组 **L**^T **x = y**，最终得到最小二乘解 x*。

步骤 3：（可选）计算残差或拟合优度
如果需要，可以计算残差向量的范数平方：||r||₂² = ||b||₂² - 2 **x***^T **d** + **x***^T **C x***。由于 **C x* = d**，可以简化为 ||r||₂² = **b**^T **b** - **d**^T **x***。这可以用来评估拟合效果。

4. 算法的特点与注意事项

  1. 优点：

    • 概念简单直观：直接源于微积分求极值，易于理解。
    • 实现直接：只需要基础的矩阵乘法和一个线性方程组求解器（Cholesky分解）。
    • 当 n 相对较小时非常高效：因为它将问题从 m×n 简化为 n×n。在很多工程问题（如曲线拟合）中，n（模型参数）很小，而 m（数据点）很大，此法很合适。

  2. 缺点与风险：

    • 条件数平方问题：正规方程系数矩阵 C = A^T A 的条件数是原矩阵 A 的条件数的平方，即 cond(C) ≈ [cond(A)]²。如果 A 本身是病态的（即列近似线性相关，导致 cond(A) 很大），那么 C 的条件数会变得极其巨大。在浮点运算中，这会导致求解正规方程时数值不稳定，解可能因舍入误差而严重失真。
    • 对秩亏问题失效：如果 A 不是满列秩，则 A^T A 是奇异的，Cholesky分解会失败，正规方程有无限多解。
    • 计算复杂度：形成 A^T A 需要 O(m n²) 运算，当 n 很大时（例如上万个参数），这可能比一些迭代法（如LSQR）或基于QR分解的方法开销更大。

5. 总结

正规方程法是将最小二乘优化问题转化为一个对称正定线性方程组求解的经典方法。其核心是计算并求解正规方程 A^T A x = A^T b。在矩阵 A 列满秩且良态的情况下，通过Cholesky分解求解是一种简单有效的方法。然而，必须警惕其潜在的数值不稳定性，对于病态问题或大规模问题，通常更推荐使用基于 QR分解 或 奇异值分解（SVD） 的数值稳定性更好的算法。正规方程法作为理解最小二乘原理的基石和某些场景下的实用工具，其地位非常重要。

好的，我注意到在您提供的冗长列表中，关于 求解线性最小二乘问题的经典算法——正规方程法 并未出现过。这是一个极其重要且基础的方法。下面我将为您详细讲解。 基于正规方程法求解线性最小二乘问题 1. 问题描述 首先，我们需要明确什么是“线性最小二乘问题”。在科学计算和数据分析中，我们经常会遇到一个实际问题：我们有一组观测数据，希望通过一个线性模型（由一组基函数的线性组合构成）来拟合或逼近这些数据。通常，模型的参数个数（比如 n ）远小于观测数据的个数（比如 m ），这导致由模型和数据构成的线性方程组是“超定的”，即方程数量多于未知数数量，通常没有精确解。 数学描述如下： 给定一个矩阵 A ∈ ℝ^(m×n) (m ≥ n) 和一个向量 b ∈ ℝ^m，我们希望找到一个向量 x ∈ ℝ^n，使得线性模型 A x 在某种度量下最接近观测数据 b 。最常用的度量是欧几里得范数（2-范数）的平方。因此，问题转化为求解： minimize || **b** - **A x** ||₂² ，对所有的 x ∈ ℝ^n。 这里， ||·||₂ 表示向量的2-范数（即长度）。这个优化问题就称为 线性最小二乘问题 。 2. 解题思路与推导——为什么是“正规方程”？ 我们的目标是最小化残差向量 r = b - A x 的范数平方。这本质上是一个无约束的凸优化问题。我们可以通过微积分来找到极值点。 目标函数： f(**x**) = || **b** - **A x** ||₂² = (**b** - **A x**)^T (**b** - **A x**) 。 将其展开： f(**x**) = **b**^T **b** - 2**x**^T **A**^T **b** + **x**^T **A**^T **A** **x** 。 为了求最小值，我们对 x 求梯度（即对每个分量求偏导数，然后组合成向量），并令其等于零向量： ∇f(**x**) = -2 **A**^T **b** + 2 **A**^T **A** **x** = 0 。 化简这个方程，我们得到： **A**^T **A** **x** = **A**^T **b** 。 这个关键的方程组就叫做 正规方程 。它是一个关于 x 的线性方程组，系数矩阵是 N = A ^T A ∈ ℝ^(n×n)，这是一个对称的半正定矩阵。如果矩阵 A 是 满列秩 的（即其列向量线性无关， rank(A) = n ），那么 A ^T A 就是对称正定矩阵，是可逆的。此时，正规方程有唯一解，也就是原最小二乘问题的最优解： **x*** = (**A**^T **A**)^(-1) **A**^T **b** 。 矩阵 (**A**^T **A**)^(-1) **A**^T 也被称为矩阵 A 的 Moore-Penrose伪逆 的一种计算方法（当 A 满列秩时）。 3. 算法步骤详解 基于正规方程求解线性最小二乘问题 min ||Ax - b||₂² 的完整算法步骤如下： 前提条件 ：假设矩阵 A ∈ ℝ^(m×n) 是满列秩的 (m ≥ n)。 步骤 1：形成正规方程系数矩阵和右端项 计算 C = A ^T A 。这是一个 n×n 的矩阵。计算它需要大约 m * n² 次浮点运算（如果利用对称性可以减半，但复杂度仍是 O(m n²)）。 同时计算向量 d = A ^T b 。这是一个 n 维向量，计算需要约 2 m n 次运算。 现在，我们得到了一个新的、规模更小的线性方程组： **C x = d** 。 步骤 2：求解对称正定线性方程组 由于 C 是对称正定的，我们可以使用稳定且高效的 Cholesky分解 来求解。 Cholesky分解 ：将 C 分解为一个下三角矩阵 L 和其转置的乘积，即 **C = L L**^T ，其中 L 的对角线元素为正。 从第一行开始，逐列计算。对于 j = 1, 2, ..., n： L_{j,j} = sqrt(C_{j,j} - Σ_{k=1}^{j-1} L_{j,k}²) L_{i,j} = (C_{i,j} - Σ_{k=1}^{j-1} L_{i,k} L_{j,k}) / L_{j,j} ， 对于 i = j+1, ..., n。 前向替代 ：解下三角方程组 **L y = d** ，得到中间向量 y 。 后向替代 ：解上三角方程组 **L**^T **x = y** ，最终得到最小二乘解 x * 。 步骤 3：（可选）计算残差或拟合优度 如果需要，可以计算残差向量的范数平方： ||r||₂² = ||b||₂² - 2 **x***^T **d** + **x***^T **C x*** 。由于 **C x* = d** ，可以简化为 ||r||₂² = **b**^T **b** - **d**^T **x*** 。这可以用来评估拟合效果。 4. 算法的特点与注意事项 优点 ： 概念简单直观 ：直接源于微积分求极值，易于理解。 实现直接 ：只需要基础的矩阵乘法和一个线性方程组求解器（Cholesky分解）。 当 n 相对较小时非常高效 ：因为它将问题从 m×n 简化为 n×n。在很多工程问题（如曲线拟合）中，n（模型参数）很小，而 m（数据点）很大，此法很合适。 缺点与风险 ： 条件数平方问题 ：正规方程系数矩阵 C = A^T A 的条件数是原矩阵 A 的条件数的平方，即 cond(C) ≈ [cond(A)]² 。如果 A 本身是病态的（即列近似线性相关，导致 cond(A) 很大），那么 C 的条件数会变得 极其巨大 。在浮点运算中，这会导致求解正规方程时 数值不稳定 ，解可能因舍入误差而严重失真。 对秩亏问题失效 ：如果 A 不是满列秩，则 A^T A 是奇异的，Cholesky分解会失败，正规方程有无限多解。 计算复杂度 ：形成 A^T A 需要 O(m n²) 运算，当 n 很大时（例如上万个参数），这可能比一些迭代法（如LSQR）或基于QR分解的方法开销更大。 5. 总结 正规方程法是将最小二乘优化问题转化为一个对称正定线性方程组求解的经典方法。其核心是 计算并求解正规方程 A^T A x = A^T b 。在矩阵 A 列满秩且良态的情况下，通过Cholesky分解求解是一种简单有效的方法。然而，必须警惕其潜在的 数值不稳定性 ，对于病态问题或大规模问题，通常更推荐使用基于 QR分解 或 奇异值分解（SVD） 的数值稳定性更好的算法。正规方程法作为理解最小二乘原理的基石和某些场景下的实用工具，其地位非常重要。