AI 数学课程 · 第 23 课,共 180

高斯消元保持解集不变

从首个主元为零的方程组中恢复模型参数,然后在 NumPy 中实现安全的行运算并检查残差。

分享这篇文章

一个用于恢复参数的方程组可能包含正确的信息,却以一个令人不便的零开头。如果第一个主元为零,安全的做法不是凭空创造新方程或除以零,而是重写同一组约束,直到它的结构显现出来。

这正是高斯消元的作用:使用可逆的初等行运算简化线性方程组,同时严格保持完全相同的解集。学完本课后,你将能够应用三种合法的行运算,解决一个小型参数恢复问题,在 NumPy 中实现这些运算,并诊断零主元、冗余行、矛盾和浮点残差。

**学习成果:**在不改变解的情况下应用初等行运算。

第 13 课:无解、唯一解还是多解按照解集对线性方程组进行了分类。第 18 课:矩阵组织线性规则介绍了紧凑存储系数的方法。官方 Mathematics for Machine Learning 配套网站 将下一步放在当前书籍 PDF的第 2.3 节。来源解释了初等变换和增广矩阵;本文中的数字、参数场景、代码、可视化和练习题均为原创。

目标是得到更简单的方程组,而不是换一个问题

考虑一个有 mm 个线性方程和 nn 个未知数的方程组。我们可以写成

Aθ=b,A\boldsymbol{\theta}=\boldsymbol{b},

其中 A∈Rm×nA\in\mathbb{R}^{m\times n} 是系数矩阵,θ∈Rn\boldsymbol{\theta}\in\mathbb{R}^{n} 包含未知参数,b∈Rm\boldsymbol{b}\in\mathbb{R}^{m} 包含观测到的等式右端。矩阵方程的每一行代表一个标量方程:

ai1θ1+ai2θ2+⋯+ainθn=bi.a_{i1}\theta_1+a_{i2}\theta_2+\cdots+a_{in}\theta_n=b_i.

高斯消元改变这些行的外观,使主元和未知数更容易读取,但不能改变哪些参数向量能让所有方程成立。不变量是集合

S={θ∈Rn:Aθ=b}.\mathcal{S}=\left\{\boldsymbol{\theta}\in\mathbb{R}^{n}: A\boldsymbol{\theta}=\boldsymbol{b}\right\}.

把右端附在系数行上后,矩阵记号更有用:

[a11a12⋯a1nb1a21a22⋯a2nb2⋮⋮⋮⋮am1am2⋯amnbm].\left[\begin{array}{ccc|c} a_{11}&a_{12}&\cdots&a_{1n}&b_1\\ a_{21}&a_{22}&\cdots&a_{2n}&b_2\\ \vdots&\vdots&&\vdots&\vdots\\ a_{m1}&a_{m2}&\cdots&a_{mn}&b_m \end{array}\right].

这就是增广矩阵。竖线提醒我们,最后一列不是另一个未知系数,而是方程的输出;每当某一行发生变化时,它必须和该行一起移动。

三种可逆操作保持解集不变

令 RiR_i 表示增广矩阵中的一整行。初等行运算恰好有三种:

合法操作记号可逆的原因
交换两行Ri↔RjR_i\leftrightarrow R_j再交换一次即可。
用非零标量乘一行Ri←λRiR_i\leftarrow\lambda R_i,λ≠0\lambda\ne0乘以 1/λ1/\lambda。
把一行的倍数加到另一行Ri←Ri+λRjR_i\leftarrow R_i+\lambda R_j,i≠ji\ne j从 RiR_i 中减去 λRj\lambda R_j。

第三种操作通常称为行替换。它包括把一个方程加到另一个方程上、从一个方程中减去另一个方程,以及用精心选择的倍数消去某个系数。

非零条件很重要。把 RiR_i 变成 0Ri0R_i 会抹去一个约束;不存在能恢复它的逆操作。完整行规则同样重要:如果只乘系数而不乘对应的右端项,就会创建一个新方程。

为什么增广矩阵携带完整方程

假设某一行表示

θ1+2θ2=5.\theta_1+2\theta_2=5.

它的增广行是 [1    2∣5][1\;\;2\mid5]。将方程乘以 33 意味着

3(θ1+2θ2)=3(5)⟺3θ1+6θ2=15,3(\theta_1+2\theta_2)=3(5) \quad\Longleftrightarrow\quad 3\theta_1+6\theta_2=15,

因此合法的矩阵操作是

[1    2∣5]⟶[3    6∣15].[1\;\;2\mid5]\longrightarrow[3\;\;6\mid15].

而 [3    6∣5][3\;\;6\mid5] 表示的是 3θ1+6θ2=53\theta_1+6\theta_2=5,这是一个不同的约束。高斯消元并不允许我们独立编辑左侧和右侧;它是对完整方程的受控重写。

同样的原则也解释了行替换。如果

Ri:aiTθ=bi,Rj:ajTθ=bj,\begin{aligned} R_i &: \boldsymbol{a}_i^{\mathsf T}\boldsymbol{\theta}=b_i,\\ R_j &: \boldsymbol{a}_j^{\mathsf T}\boldsymbol{\theta}=b_j, \end{aligned}

那么用 Ri+λRjR_i+\lambda R_j 替换 RiR_i 就意味着

(ai+λaj)Tθ=bi+λbj.(\boldsymbol{a}_i+\lambda\boldsymbol{a}_j)^{\mathsf T} \boldsymbol{\theta} =b_i+\lambda b_j.

每个系数和右端都接受相同的组合。新行更容易使用,但仍然编码着原来两行已经包含的信息。

例题:恢复三个评分参数

想象一个由三个测量信号构成的玩具线性评分:

  • f1f_1:检索匹配特征;
  • f2f_2:验证特征;
  • f3f_3:工具确认特征。

评分规则为

s=θ1f1+θ2f2+θ3f3.s=\theta_1f_1+\theta_2f_2+\theta_3f_3.

下面的计数和分数刻意选得很小。它们是用于教学的参数识别问题,并不是在声称生产排序系统应当使用这些特征或权重。

观测f1f_1f2f_2f3f_3观测分数 ss
A0215
B1114
C24515

三行变成

0θ1+2θ2+θ3=5,θ1+θ2+θ3=4,2θ1+4θ2+5θ3=15.\begin{aligned} 0\theta_1+2\theta_2+\theta_3&=5,\\ \theta_1+\theta_2+\theta_3&=4,\\ 2\theta_1+4\theta_2+5\theta_3&=15. \end{aligned}

写成矩阵形式:

[0215111424515].\left[\begin{array}{ccc|c} 0&2&1&5\\ 1&1&1&4\\ 2&4&5&15 \end{array}\right].

第一个元素是零,所以第一行不能被缩放成第一个主元。这是记账问题,不是方程组无解的证据。我们可以换入一个非零行。这个静态优先的可视化记录每个状态,包括操作标签和完整的增广矩阵:

三参数恢复示例中的每一次行运算。

三参数恢复示例中的每一次行运算

完整静态记录

所有状态都保留在可选控件下方。操作会改变完整的一行,因此每个状态都表示一个等价方程组。

  1. 步骤 0开始:原始增广矩阵
    原始增广矩阵
     θ₁θ₂θ₃b
    R10215
    R21114
    R324515
  2. 步骤 1R₁ ↔ R₃
    步骤后的矩阵 1
     θ₁θ₂θ₃b
    R124515
    R21114
    R30215
  3. 步骤 2R₁ ← ½R₁
    步骤后的矩阵 2
     θ₁θ₂θ₃b
    R1125/215/2
    R21114
    R30215
  4. 步骤 3R₂ ← R₂ − R₁
    步骤后的矩阵 3
     θ₁θ₂θ₃b
    R1125/215/2
    R20-1-3/2-7/2
    R30215
  5. 步骤 4R₂ ↔ R₃
    步骤后的矩阵 4
     θ₁θ₂θ₃b
    R1125/215/2
    R20215
    R30-1-3/2-7/2
  6. 步骤 5R₂ ← ½R₂
    步骤后的矩阵 5
     θ₁θ₂θ₃b
    R1125/215/2
    R2011/25/2
    R30-1-3/2-7/2
  7. 步骤 6R₁ ← R₁ − 2R₂
    步骤后的矩阵 6
     θ₁θ₂θ₃b
    R1103/25/2
    R2011/25/2
    R30-1-3/2-7/2
  8. 步骤 7R₃ ← R₃ + R₂
    步骤后的矩阵 7
     θ₁θ₂θ₃b
    R1103/25/2
    R2011/25/2
    R300-1-1
  9. 步骤 8R₃ ← −R₃
    步骤后的矩阵 8
     θ₁θ₂θ₃b
    R1103/25/2
    R2011/25/2
    R30011
  10. 步骤 9R₁ ← R₁ − 3/2R₃
    步骤后的矩阵 9
     θ₁θ₂θ₃b
    R11001
    R2011/25/2
    R30011
  11. 步骤 10R₂ ← R₂ − 1/2R₃
    步骤后的矩阵 10
     θ₁θ₂θ₃b
    R11001
    R20102
    R30011

一次查看一个合法变换

聚焦此面板,然后使用按钮或左右方向键在各个状态之间移动。

步骤 0 / 10

操作开始:原始增广矩阵

当前增广矩阵
 θ₁θ₂θ₃b
R10215
R21114
R324515

第一列的第一个元素为零,因此缩放该行是不合法的。下面的非零行可以提供第一个主元。

行标签、操作文本以及 b 前的竖线在不依赖颜色的情况下传达含义。如果 JavaScript 不可用,静态序列仍然可用。

下面按代数顺序进行同样的计算。在前两列中使用部分主元选取:当当前列有多个非零候选时,选择绝对值最大的候选。可视化保留分数,以便每一步都能手工核对。

恢复出的参数通过直接代入检查:

[021111245][121]=[0+4+11+2+12+8+5]=[5415]=b.\begin{aligned} \begin{bmatrix} 0&2&1\\ 1&1&1\\ 2&4&5 \end{bmatrix} \begin{bmatrix}1\\2\\1\end{bmatrix} &= \begin{bmatrix} 0+4+1\\ 1+2+1\\ 2+8+5 \end{bmatrix}\\ &= \begin{bmatrix}5\\4\\15\end{bmatrix} =\boldsymbol{b}. \end{aligned}

这个解并不是因为某个行运算猜出了新参数。每一步都改变了同三个约束的表示方式。最终的单位矩阵块让答案很容易读取。

NumPy 实现与数学过程相对应

下面的实现明确写出了三种合法操作。它作用于一个有限的实值二维增广数组的副本。最后一列被视为右端,atol 是把浮点数视为零的阈值。该实现执行 Gauss–Jordan 消元,因此会同时清除每个主元上方和下方的项。

import numpy as np


def swap_rows(matrix, first, second):
    result = np.array(matrix, dtype=float, copy=True)
    result[[first, second], :] = result[[second, first], :]
    return result


def scale_row(matrix, row, factor):
    if factor == 0:
        raise ValueError("row scaling needs a nonzero factor")
    result = np.array(matrix, dtype=float, copy=True)
    result[row, :] *= factor
    return result


def replace_row(matrix, target, source, factor):
    if target == source:
        raise ValueError("target and source rows must be different")
    result = np.array(matrix, dtype=float, copy=True)
    result[target, :] += factor * result[source, :]
    return result


def gauss_jordan(augmented, atol=1e-12):
    work = np.array(augmented, dtype=float, copy=True)
    if work.ndim != 2 or work.shape[1] < 2:
        raise ValueError("expected a 2D augmented matrix")
    if not np.all(np.isfinite(work)):
        raise ValueError("all entries must be finite")

    row_count, column_count = work.shape
    variable_count = column_count - 1
    pivot_row = 0

    for pivot_column in range(variable_count):
        if pivot_row == row_count:
            break

        candidates = np.abs(work[pivot_row:, pivot_column])
        pivot_offset = int(np.argmax(candidates))
        if candidates[pivot_offset] <= atol:
            continue

        pivot = pivot_row + pivot_offset
        if pivot != pivot_row:
            work = swap_rows(work, pivot_row, pivot)

        pivot_value = work[pivot_row, pivot_column]
        work = scale_row(work, pivot_row, 1.0 / pivot_value)

        for row in range(row_count):
            if row == pivot_row:
                continue
            coefficient = work[row, pivot_column]
            if abs(coefficient) > atol:
                work = replace_row(
                    work, row, pivot_row, -coefficient
                )

        pivot_row += 1

    work[np.abs(work) <= atol] = 0.0
    return work


A = np.array(
    [
        [0.0, 2.0, 1.0],
        [1.0, 1.0, 1.0],
        [2.0, 4.0, 5.0],
    ]
)
b = np.array([5.0, 4.0, 15.0])
augmented = np.column_stack((A, b))

rref = gauss_jordan(augmented)
theta = rref[:, -1]  # valid here because the coefficient block is full rank
residual = A @ theta - b

assert np.allclose(residual, 0.0, rtol=1e-12, atol=1e-12)
assert np.allclose(
    theta,
    np.linalg.solve(A, b),
    rtol=1e-12,
    atol=1e-12,
)

print(theta)
print(np.linalg.norm(residual, ord=np.inf))

经验证的输出是

[1. 2. 1.]
0.0

最后一个断言把手工构建的消元结果与numpy.linalg.solve进行比较;当前 NumPy 文档将其定义为用于方阵满秩系统,并说明对于奇异或非方形系数矩阵会抛出 LinAlgError。这个比较是交叉检查,并不是隐藏行运算的理由:本课的重点是让保持等价的机制可以被检查。

残差

r=Aθ^−b\boldsymbol{r}=A\widehat{\boldsymbol{\theta}}-\boldsymbol{b}

衡量计算得到的参数满足所给方程的程度。代码使用的无穷范数是残差坐标绝对值中的最大值。在精确算术中,本例得到零向量;在浮点算术中,正确结果也可能产生量级为机器舍入误差的数值。

边界情况揭示主元的含义

零主元是算法的分支点,而不是结论。如果当前主元位置为零,但同一列更下方出现非零项,就交换行。如果下方每一项都是零,就移到下一列;该列可能只是没有提供新的独立信息。

消元后,检查系数全部为零的行。有两种不同结果:

  1. 右端为零的全零行 [0    0    0∣0][0\;\;0\;\;0\mid0] 是冗余的,不增加约束。如果某个变量也没有主元,方程组可能有无穷多个解。
  2. 右端非零的全零行,例如 [0    0    0∣1][0\;\;0\;\;0\mid1],表示 0=10=1。方程组不一致,没有解。

例如,下面两行

[123246]→R2←R2−2R1[123000]\left[\begin{array}{cc|c} 1&2&3\\ 2&4&6 \end{array}\right] \xrightarrow{R_2\leftarrow R_2-2R_1} \left[\begin{array}{cc|c} 1&2&3\\ 0&0&0 \end{array}\right]

表示同一条直线两次。只改变第二个右端会得到不同结果:

[123247]→R2←R2−2R1[123001],\left[\begin{array}{cc|c} 1&2&3\\ 2&4&7 \end{array}\right] \xrightarrow{R_2\leftarrow R_2-2R_1} \left[\begin{array}{cc|c} 1&2&3\\ 0&0&1 \end{array}\right],

这就是矛盾。两个例子中的系数行看起来都相关;是否一致取决于右端。消元必须带着这一项移动,这样算法才能区分冗余和矛盾。

最短的误解测试是问:当左侧乘以 22 时,θ1+θ2=3\theta_1+\theta_2=3 会变成什么?合法结果是 2θ1+2θ2=62\theta_1+2\theta_2=6,而不是 2θ1+2θ2=32\theta_1+2\theta_2=3。行运算能保持解集,是因为完整方程被可逆地变换了。

这对 AI 流程为何重要

这个玩具评分展示了直接用途:当方程能够确定一个参数向量时,多次观测可以恢复未知权重。在真实流程中,矩阵可能描述校准权重、小型物理模型、约束系统,或更大模型的诊断切片。消元有助于回答三个实际问题:

  • 观测是否为每个参数提供了一个主元?
  • 一个看似重复的观测是否只是冗余?
  • 测得的目标是否与假设的线性规则矛盾?

该方法也标出了精确问题的边界。带噪观测往往会让方程组不一致,而超定数据集可能不存在能精确满足每一行的向量。在这种情况下,强行消除矛盾就会改变问题。最小二乘法提出的是另一个问题——寻找总误差较小的向量——这属于下一步的数值线性代数决策,而不是精确的行等价结论。同样,numpy.linalg.solve 要求系数矩阵是方阵且满秩;奇异或非方形问题需要根据实际目标选择方法。

下一课会给出消元所揭示的阶梯结构名称:主元、基本变量、自由变量以及通解的形状。要带到下一课的不变量很简单:每个合法行运算改变的是方程组的视角,而不是答案的集合。

检查你的理解

Question 1

为什么一行乘以零不是初等行运算,而乘以 5 却是合法的?

Show the step-by-step solution

从行方程 g(θ)=0g(\boldsymbol{\theta})=0 开始。乘以 55 得到 5g(θ)=05g(\boldsymbol{\theta})=0。由于 5≠05\ne0,把原方程乘以 1/51/5 就能恢复它。解集不变。

乘以零会对每个 θ\boldsymbol{\theta} 都得到 0=00=0。原来的约束消失了,而且没有任何乘法可以恢复它。因此该操作不可逆,并可能扩大解集。

Question 2

对增广矩阵 [[1, 2 | 7], [0, 1 | 3]] 应用 R₁ ← R₁ − 2R₂。新的第一行是什么?

Show the step-by-step solution

使用完整的第二行,包括它的右端项:

R1=[1    2∣7],R2=[0    1∣3].R_1=[1\;\;2\mid7], \qquad R_2=[0\;\;1\mid3].

将第二行乘以 22:

2R2=[0    2∣6].2R_2=[0\;\;2\mid6].

逐项相减:

R1−2R2=[1−0    2−2∣7−6]=[1    0∣1].R_1-2R_2 =[1-0\;\;2-2\mid7-6] =[1\;\;0\mid1].

新的第一行是 [1    0∣1][1\;\;0\mid1]。省略右端的相减会得到不同的方程。

Question 3

使用行交换后再消元,求解 0x + y = 2 和 x + y = 3。

Show the step-by-step solution

写出增广矩阵:

[012113113].\left[\begin{array}{cc|c} 0&1&2\\ 1&1&3 1&1&3 \end{array}\right].

第一个主元位置为零,所以交换两行:

[113012].\left[\begin{array}{cc|c} 1&1&3\\ 0&1&2 \end{array}\right].

消去第二个主元上方的项:

R1←R1−R2⟹[101012].R_1\leftarrow R_1-R_2 \quad\Longrightarrow\quad \left[\begin{array}{cc|c} 1&0&1\\ 0&1&2 \end{array}\right].

读取单位矩阵块可得 x=1x=1、y=2y=2。代回可检查两个原方程:0(1)+2=20(1)+2=2 且 1+2=31+2=3。

Question 4

全零行 [0, 0 | 0] 和 [0, 0 | 4] 各表示什么?

Show the step-by-step solution

行 [0    0∣0][0\;\;0\mid0] 表示 0=00=0。它是冗余的,不限制变量。如果另一个变量没有主元,这种自由度可以产生无穷多个解。

行 [0    0∣4][0\;\;0\mid4] 表示不可能成立的 0=40=4。一行矛盾就会使整个方程组无解,即使其他行看起来一致。

区别完全在右端。消元必须带着这一项移动,这样算法才能区分冗余和矛盾。

Question 5

某位开发者把 [1, 1 | 3] 变成 [2, 2 | 3],并说这只是行缩放。这个说法正确吗?

Show the step-by-step solution

乘以 22 的行缩放必须作用于每一项:

2[1    1∣3]=[2    2∣6].2[1\;\;1\mid3]=[2\;\;2\mid6].

所声称的行 [2    2∣3][2\;\;2\mid3] 表示 2θ1+2θ2=32\theta_1+2\theta_2=3。将该方程除以 22 得到 θ1+θ2=3/2\theta_1+\theta_2=3/2,而不是原来的 θ1+θ2=3\theta_1+\theta_2=3。说法错误,因为右端被独立改变了。

Question 6

为什么 NumPy 实现判断主元或残差是否为零时要使用容差?

Show the step-by-step solution

在精确算术中,零是精确值。浮点运算会近似存储许多分数,因此数学上的零结果可能显示为 10−1610^{-16} 这样很小的数。把每一个非零位模式都当作真实主元,可能会产生没有意义的行运算。

因此,实现用 atol 比较绝对值,也用相对和绝对容差检查残差。容差必须符合数据的尺度:对接近 11 的值合理的阈值,可能对接近 10−910^{-9} 的测量过大,也可能对非常大的值过小。小残差说明拟合良好,但不能证明病态系统中的参数估计稳定。

Question 7

一个恢复系统有三个未知参数,但消元结束时只有两个主元和一行全零行。在选择数值方法前应得出什么结论?

Show the step-by-step solution

两个主元约束了两个独立的参数方向。全零行没有增加新信息,因此至少有一个参数方向是自由的,除非另一行显示出矛盾。

如果没有形如 [0    0    0∣c][0\;\;0\;\;0\mid c] 且 c≠0c\ne0 的行,那么方程组一致并有无穷多个解。在这个模型下,数据无法确定唯一的参数向量。向缺失主元任意填数是建模选择,而不是消元的结果;下一步应报告自由参数或收集一个独立观测。

资料来源

  1. Mathematics for Machine Learning companion website
  2. Mathematics for Machine Learning book PDF
  3. NumPy documentation: numpy.linalg.solve
  4. NumPy documentation: numpy.allclose
  5. NumPy documentation: numpy.finfo
  6. NumPy documentation: numpy.linalg.norm
  7. NumPy documentation: numpy.linalg.cond