第 28 章矩阵运算 (Matrix Operations)

核心结论

线性方程组求解：n 阶非奇异系统 \(Ax = b\) 用 LUP 分解（\(PA = LU\)）+ 前向 / 后向替换，时间 \(\Theta(n^3)\)（分解）+ \(\Theta(n^2)\)（替换）——比直接求逆 \(x = A^{-1}b\) 更稳定。
LUP 分解与置换：L 是单位下三角，U 是上三角，P 是置换矩阵（行置换保证数值稳定）；用部分主元（partial pivoting）选每列最大元素作为枢轴。
矩阵求逆的等价性（定理 28.1 / 28.2）：「矩阵乘法」与「矩阵求逆」在渐近复杂度上等价——若乘法时间 \(M(n)\)，则求逆时间 \(O(M(n))\)，反之亦然（技术条件下）。故 Strassen / Coppersmith-Winograd 加速直接惠及求逆。
对称正定矩阵 (SPD)：\(A = A^T\) 且对所有非零 \(x\) 有 \(x^T A x > 0\)；可无除零做 LU 分解；前主子矩阵与 Schur 补也是 SPD（引理 28.4 / 28.5）。
最小二乘拟合：超定系统 \(Ac = y\)（m > n）求最小化误差平方和 → 法方程 \(A^T A c = A^T y\)；解为 \(c = (A^T A)^{-1} A^T y\)，矩阵 \(A^+ = (A^T A)^{-1} A^T\) 称为伪逆。

本章主旨

本章聚焦「用矩阵分解解方程」——LUP 分解是数值线性代数的核心工具，类比于「整数分解之于数论」。三个主题环环相扣：(1) 用 LUP 分解高效解 \(Ax = b\)；(2) 求逆可归约为解 \(AX = I_n\)，与矩阵乘法等价；(3) SPD 矩阵是「最好的矩阵」——无除零、可分解、用于最小二乘。最小二乘是数据拟合、机器学习的基础设施。本章主要讨论数值方法的算法结构，数值稳定性仅简要提及（详细见 Golub & Van Loan）。

一、核心概念

本章围绕 6 个核心概念展开：从线性方程组求解出发，先介绍 LUP 分解与前向 / 后向替换，再讨论矩阵求逆与乘法的等价性，最后介绍 SPD 矩阵与最小二乘。

概念	定义 + 重要性	实现提示
线性方程组 \(Ax = b\)	n 个方程 n 个未知数；矩阵形式 \(A \in \mathbb{R}^{n \times n}\)，解唯一当且仅当 A 非奇异（行列式 ≠ 0）。	§28.1；欠定（m < n）有无穷解或无解；超定（m > n）通常无解。
LUP 分解	三矩阵分解 \(PA = LU\)；L 单位下三角，U 上三角，P 置换矩阵。	§28.1；分解时间 Θ(n³)；解方程时间 Θ(n²)；数值稳定（部分主元）。
前向 / 后向替换	前向替换：解下三角系统 \(Ly = Pb\)，时间 Θ(n²)；后向替换：解上三角系统 \(Ux = y\)，时间 Θ(n²)。	§28.1；合并后 LUP-SOLVE 总时间 Θ(n²)。
矩阵求逆等价性	定理 28.1：乘法不比求逆难；定理 28.2：求逆不比乘法难（SPD 假设 + regularity 条件）。	§28.2；意味着 Strassen / CW 等乘法加速直接惠及求逆。
对称正定矩阵 (SPD)	\(A = A^T\) 且对所有非零 x，\(x^T A x > 0\)；前主子矩阵与 Schur 补也是 SPD；LU 分解无除零（推论 28.6）。	§28.3；是数值线性代数中「最易处理」的矩阵类。
最小二乘拟合	超定系统 \(Ac = y\)（m > n）；法方程 \(A^T A c = A^T y\)；解 \(c = (A^T A)^{-1} A^T y\)；伪逆 \(A^+ = (A^T A)^{-1} A^T\)。	§28.3；用 SPD 性质保证解存在唯一；常用多项式拟合。

概念

定义 + 重要性

实现提示

线性方程组 \(Ax = b\)

n 个方程 n 个未知数；矩阵形式 \(A \in \mathbb{R}^{n \times n}\)，解唯一当且仅当 A 非奇异（行列式 ≠ 0）。

§28.1；欠定（m < n）有无穷解或无解；超定（m > n）通常无解。

LUP 分解

三矩阵分解 \(PA = LU\)；L 单位下三角，U 上三角，P 置换矩阵。

§28.1；分解时间 Θ(n³)；解方程时间 Θ(n²)；数值稳定（部分主元）。

前向 / 后向替换

前向替换：解下三角系统 \(Ly = Pb\)，时间 Θ(n²)；后向替换：解上三角系统 \(Ux = y\)，时间 Θ(n²)。

§28.1；合并后 LUP-SOLVE 总时间 Θ(n²)。

矩阵求逆等价性

定理 28.1：乘法不比求逆难；定理 28.2：求逆不比乘法难（SPD 假设 + regularity 条件）。

§28.2；意味着 Strassen / CW 等乘法加速直接惠及求逆。

对称正定矩阵 (SPD)

\(A = A^T\) 且对所有非零 x，\(x^T A x > 0\)；前主子矩阵与 Schur 补也是 SPD；LU 分解无除零（推论 28.6）。

§28.3；是数值线性代数中「最易处理」的矩阵类。

最小二乘拟合

超定系统 \(Ac = y\)（m > n）；法方程 \(A^T A c = A^T y\)；解 \(c = (A^T A)^{-1} A^T y\)；伪逆 \(A^+ = (A^T A)^{-1} A^T\)。

§28.3；用 SPD 性质保证解存在唯一；常用多项式拟合。

二、详细笔记

28.1 线性方程组与 LUP 分解

What：n 阶非奇异矩阵 \(A\) 分解为 \(PA = LU\)，其中 L 单位下三角、U 上三角、P 置换矩阵；解 \(Ax = b\) 等价于解两个三角系统。

Why：三角系统的求解是 Θ(n²)，远快于高斯消元的 Θ(n³)；LUP 分解的代价一次性付出，可重复用于多个右端向量。

How：

LUP 分解的存在性（定理 28.1，CLRS §28.1）：任何非奇异矩阵 A 都有 LUP 分解。

解方程流程：

求 \(A\) 的 LUP 分解：\(PA = LU\)。
解下三角系统 \(Ly = Pb\)（前向替换）：时间 Θ(n²)。
解上三角系统 \(Ux = y\)（后向替换）：时间 Θ(n²)。
总计：分解 Θ(n³) + 两次替换 Θ(n²) = Θ(n³)。

前向替换公式：

\[y_i = b_{\pi[i]} - \sum_{j=1}^{i-1} \ell_{ij} y_j, \quad i = 1, \ldots, n\]

后向替换公式：

\[x_i = \left(y_i - \sum_{j=i+1}^{n} u_{ij} x_j\right) / u_{ii}, \quad i = n, n-1, \ldots, 1\]

LUP-DECOMPOSITION 的关键是「部分主元」(partial pivoting)：每步选剩余行中最大元素作为枢轴，更新置换矩阵 P——保证数值稳定。

When：需要求解 \(Ax = b\) 且 A 非奇异；需要多次解（不同右端向量）；关心数值稳定性。

Example：CLRS §28.1 的 3×3 例子：\(A = \begin{pmatrix} 1 & 2 & 0 \\ 3 & 4 & 4 \\ 5 & 6 & 3 \end{pmatrix}\)，LUP 分解后解 \(Ax = (3,7,8)^T\) 得 \(x = (-1.4, 2.2, 0.6)^T\)。

28.2 计算 LUP 分解

What：基于「高斯消元 + 部分主元」递归 / 迭代地构造 L, U, P；时间 Θ(n³)。

Why：LUP 分解是后续求逆、特征值、最小二乘等高级算法的基础；理解其构造过程有助于诊断数值稳定性问题。

How：

LUP-DECOMPOSITION(A)：

if n = 1: return L=I, U=A, P=I
选 pivot：\(k = \arg\max_{i \geq 1} |a_{i1}|\)
交换 A 的第 1 行与第 k 行（更新 P）
算 \(\ell_{i1} = a_{i1} / a_{11}\) for \(i \geq 2\)
算 Schur 补：\(a'_{ij} = a_{ij} - \ell_{i1} a_{1j}\) for \(i,j \geq 2\)
递归 LUP-DECOMPOSITION(A')，合并 L, U, P

复杂度分析：

选 pivot：Θ(n)
算 \(\ell\) 与 Schur 补：Θ(n²)
递归：\(T(n) = T(n-1) + \Theta(n^2)\) = Θ(n³)

部分主元的必要性：避免除以接近 0 的数，防止舍入误差放大；CLRS 图 28.2 展示完整过程。

When：任何需要解线性方程组的场景；矩阵计算库（LAPACK、Eigen）的核心；矩阵分解算法的对比基准。

Example：CLRS 图 28.2 的 4×4 矩阵；经过 3 步消元得到 \(PA = LU\)；最后一轮不需要进一步操作（k = n）。

28.3 矩阵求逆与矩阵乘法的等价性

What：在渐近意义上，「矩阵求逆」与「矩阵乘法」等价——定理 28.1（乘法不比求逆难）+ 定理 28.2（求逆不比乘法难，SPD + regularity 假设）。

Why：Strassen（§4.2）的 Θ(n^2.81) 矩阵乘法加速直接惠及求逆；理论上不存在「比求逆更快的独立算法」。

How：

定理 28.1（乘法不难过求逆）：

\[M(n) = O(I(n)) \quad \text{构造 } 3n \times 3n \text{ 矩阵 } D \text{，其逆的右上 } n \times n \text{ 子块即 } AB\]

D 矩阵构造：

\[D = \begin{pmatrix} I_n & A & 0 \\ 0 & I_n & B \\ 0 & 0 & I_n \end{pmatrix}, \quad D^{-1} = \begin{pmatrix} I_n & -A & AB \\ 0 & I_n & -B \\ 0 & 0 & I_n \end{pmatrix}\]

定理 28.2（求逆不难过乘法，SPD 假设）：

递推关系 \(I(n) \leq 2 I(n/2) + 4 M(n/2) + O(n^2)\)，由 master 定理得 \(I(n) = O(M(n))\)。

对一般非奇异 A：用 \(A^{-1} = (A^T A)^{-1} A^T\) 归约为求 SPD 矩阵 \(A^T A\) 的逆（\(A^T A\) 是 SPD）。

When：理论上展示「乘法 = 求逆」；实践中很少显式求逆（数值不稳定），多用 LUP 分解。

Example：1000×1000 矩阵求逆用 Strassen 加速：Θ(1000^2.81) ≈ 6.3·10⁸，比朴素 Θ(10⁹) 快 ~2 倍。

28.4 对称正定矩阵 (SPD) 与 Schur 补

What：对称正定矩阵 \(A = A^T\) 且对所有非零 x，\(x^T A x > 0\)；具有「所有主子矩阵 SPD」「LU 分解无除零」等优良性质。

Why：SPD 是数值线性代数「最好处理」的矩阵类——很多算法（Cholesky 分解、共轭梯度、最小二乘）都假设 SPD；很多物理 / 统计问题自然产生 SPD 矩阵（如协方差矩阵、Hessian 矩阵）。

How：

核心性质：

引理 28.3：SPD ⟹ 非奇异。
引理 28.4：SPD 的所有前主子矩阵也是 SPD。
引理 28.5：SPD 的 Schur 补也是 SPD。
推论 28.6：SPD 的 LU 分解不会除以 0。

Schur 补定义（式 28.15）：

\[S = C - B A_k^{-1} B^T \quad (\text{相对于前 } k \times k \text{ 子矩阵 } A_k)\]

证明引理 28.5 的关键：「配方法」——把二次型 \(x^T A x\) 写成「完全平方 + 剩余」形式，证明剩余 = \(z^T S z\) > 0。

应用：Cholesky 分解 \(A = LL^T\)（L 下三角）只对 SPD 有效，且无须置换——比 LUP 更高效（节省约一半运算）。

When：协方差矩阵、Hessian 矩阵、距离平方矩阵、内核矩阵（kernel matrix）；任何「正定二次型」对应的应用。

Example：多元正态分布的协方差矩阵是 SPD；最小二乘的法方程矩阵 \(A^T A\) 是 SPD（若 A 列满秩）。

28.5 最小二乘拟合

What：超定系统 \(Ac = y\)（m > n）无精确解；求最小化误差平方和的解 → 法方程 \(A^T A c = A^T y\) → 解 \(c = (A^T A)^{-1} A^T y\)；矩阵 \(A^+ = (A^T A)^{-1} A^T\) 称为伪逆。

Why：数据拟合、回归分析、机器学习的核心；解决「含噪声观测下找最佳参数」问题。

How：

问题形式化：

数据点 \((x_1, y_1), \ldots, (x_m, y_m)\)，m > n。
拟合函数 \(F(x) = c_1 f_1(x) + c_2 f_2(x) + \cdots + c_n f_n(x)\)（多项式、指数等基函数）。
误差向量 \(\eta = Ac - y\)，最小化 \(\|\eta\|^2 = \sum_i \eta_i^2\)。

法方程推导（式 28.19）：

\[\frac{\partial \|\eta\|^2}{\partial c_k} = 0 \;\Longrightarrow\; A^T(Ac - y) = 0 \;\Longrightarrow\; A^T A c = A^T y\]

解：

\[c = (A^T A)^{-1} A^T y = A^+ y\]

伪逆性质：

当 A 是方阵且非奇异时，\(A^+ = A^{-1}\)（伪逆退化为逆）。
当 m > n 时，\(A^+\) 是「最小范数最小二乘解」。

数值实践：直接解法方程可能 ill-conditioned（条件数大）；更稳定的是 QR 分解或 SVD 求最小二乘——CLRS 4e 仅提及，更详细的见 Golub & Van Loan。

When：数据拟合、回归分析、曲线拟合、机器学习线性模型；任何「带噪声的线性参数估计」。

Example：CLRS 图 28.3 的 5 个数据点，拟合二次多项式 \(F(x) = 1.2 - 0.757x + 0.214x^2\)，最小化误差平方和。

28.6 实际考量与数值稳定性

What：本章算法在理想算术下正确，但在浮点运算下需关注数值稳定性——舍入误差可能放大。

Why：实际部署时，理论正确 ≠ 实际正确；理解稳定性是工程实践的前提。

How：

常见稳定性问题：

病态矩阵：\(A\) 接近奇异时，舍入误差导致解偏差巨大；用条件数 \(\kappa(A) = \|A\| \cdot \|A^{-1}\|\) 度量。
部分主元 vs 完全主元：部分主元（按列选最大）足够；完全主元（全局最大）开销大但更稳定。
浮点精度：双精度约 16 位有效数字，单精度约 7 位。

稳定性推荐：

解线性方程组：LUP 分解 + 部分主元（数值稳定）。
矩阵求逆：尽量避免；用 LUP 分解解 Ax = b 替代。
最小二乘：用 QR / SVD 替代法方程（避免平方条件数）。

实际库：LAPACK（Fortran，工业标准）、Eigen（C++ 模板）、NumPy / SciPy（Python）。

When：实际部署任何矩阵算法；评估算法选择的 trade-off；处理病态问题时。

Example：Hilbert 矩阵是经典病态矩阵——n=10 时条件数 ~10¹³，法方程直接求逆完全失败，需用高精度算法。

三、关键图表

核心公式对照表

公式编号

内容

式 28.1

线性方程组 \(\sum_j a_{ij} x_j = b_i\)

式 28.2

矩阵形式 \(Ax = b\)

式 28.3

解 \(x = A^{-1} b\)

式 28.4

LUP 分解 \(PA = LU\)

式 28.5

前向替换 \(Ly = Pb\)

式 28.6

后向替换 \(Ux = y\)

式 28.9

Schur 补 \(S = C - v w^T / a_{11}\)

式 28.10

求逆方程 \(AX = I_n\)

式 28.15

Schur 补一般定义 \(S = C - B A_k^{-1} B^T\)

式 28.19

法方程 \(A^T A c = A^T y\)

式 28.20

最小二乘解 \(c = (A^T A)^{-1} A^T y\)

定理 28.1

矩阵乘法不难过求逆

定理 28.2

矩阵求逆不难过乘法（SPD + regularity）

引理 28.3

SPD ⟹ 非奇异

引理 28.4

SPD 前主子矩阵也是 SPD

引理 28.5

SPD Schur 补也是 SPD

推论 28.6

SPD 的 LU 分解无除零

四、思维导图

mindmap
  root((第 28 章 矩阵运算))
    线性方程组
      Ax=b
      唯一性条件
      数值稳定性
    LUP分解
      PA=LU
      单位下三角L
      上三角U
      置换矩阵P
      部分主元
    前向/后向替换
      Ly=Pb
      Ux=y
      Θ(n²)每次
    矩阵求逆
      AX=I_n
      LUP-SOLVE
      Θ(n³)
    等价性定理
      乘法≈求逆
      Strassen加速
      SPD+regularity
    SPD矩阵
      A=A^T
      xᵀAx>0
      LU无除零
      Schur补
    最小二乘
      法方程
      AᵀAc=Aᵀy
      伪逆A⁺
      多项式拟合

五、重点与易错点

LUP 分解 vs 直接求逆：解 \(Ax=b\) 用 LUP 分解比 \(x=A^{-1}b\) 数值稳定得多——后者因矩阵求逆放大舍入误差，实践中几乎不用。
部分主元的必要性：避免除以接近 0 的枢轴导致误差放大；CLRS 28.2-3 脚注提到「不主元的高斯消元可能数值不稳定」。
L 是单位下三角：对角元素全为 1；U 是上三角，对角可能含 0 但非奇异 A 保证非零。
矩阵求逆等价性的限制：定理 28.2 需要「regularity 条件」（满足常见情形如 Θ(n^c lg^d n)）；对特殊矩阵（如稀疏矩阵）可能有更优算法。
Strassen 与求逆：Strassen 原始论文动机即「更快解线性方程组」；其结果自动给出更快的求逆。
SPD 的「最好」性质：非奇异、所有主子矩阵 SPD、所有特征值正、Cholesky 分解存在；很多数值算法都假设 SPD。
Schur 补的对称性：若 A 对称，则 \(S = C - B A_k^{-1} B^T\) 也对称（因 \((B A_k^{-1} B^T)^T = B A_k^{-T} B^T = B A_k^{-1} B^T\)，因 SPD 时 \(A_k^{-1}\) 对称）。
最小二乘的法方程条件数：\(\kappa(A^T A) = \kappa(A)^2\)——条件数平方化，更病态；推荐用 QR / SVD。
伪逆与逆：当 A 是方阵且非奇异时，\(A^+ = A^{-1}\)；伪逆是逆的自然推广。
多项式拟合的次数选择：n = m 时过拟合（拟合噪声）；n ≪ m 时欠拟合（拟合趋势）；用交叉验证或 AIC / BIC 准则。
与第 4 章分治的关联：Strassen 矩阵乘法是分治在矩阵运算中的胜利；分治 + 矩阵递归是现代 BLAS 的基础。
与第 26 章最大流的关联：最大流问题的内部实现常用「流矩阵 + 残量网络」表示，矩阵操作无处不在。
与第 29 章线性规划的关联：单纯形法（第 29 章）的基础操作是矩阵分解；LUP 分解是其底层工具。
数值稳定性的代价：完全主元（global pivoting）数值更稳定但开销大；部分主元是工程折中。
工程实践：解线性方程组首选 LAPACK dgesv；矩阵求逆用 dgetri 但慎用；最小二乘用 dgels（QR/SVD）。

第 28 章 矩阵运算 (Matrix Operations)

核心结论

一、核心概念

二、详细笔记

28.1 线性方程组与 LUP 分解

28.2 计算 LUP 分解

28.3 矩阵求逆与矩阵乘法的等价性

28.4 对称正定矩阵 (SPD) 与 Schur 补

28.5 最小二乘拟合

28.6 实际考量与数值稳定性

三、关键图表

四、思维导图

五、重点与易错点

第 28 章矩阵运算 (Matrix Operations)