专题进阶 · 数值算法推荐总顺序 · 第 112 / 148 课

用行变换消去未知数,解释部分选主元、回代与残差检查。

先学会这些,再进入本课 矩阵乘法
还有 1 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 数值算法

高斯消元Gaussian Elimination

用行变换把线性系统化为三角形,选主元有助于数值稳定。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

用行变换消去未知数,解释部分选主元、回代与残差检查。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

解方程组 2x+y=5、4x+3y=11,如何把多未知数系统化成从后往前可解的形式?

02一步步得到方法

矩阵行就是一条线性方程

A 的每行记录各未知数系数,b 记录右端值。交换方程顺序、给一行减去另一行的倍数,都不改变解集。消元选择主元后,将其下方同列系数消为零,逐列得到上三角系统 Ux=c。

回代从最后一行开始,因为那时只剩一个未知数;求出 x_j 后,将它的贡献从前一行右端减掉,再除以对应对角系数。

为什么要交换主元行

若当前主元为零,直接除法无法进行;即使极小也可能放大舍入误差。部分选主元在当前列剩余行中选择绝对值最大的元素交换上来,让消元乘子绝对值不超过 1。

选主元改善稳定性,但不能治愈病态问题。A 轻微变化就使解剧烈变化时,残差很小也不一定意味着解的相对误差小;应结合条件数与原问题尺度判断。

消元是在做等价的行变换

用主元行的适当倍数消去下方同一列,只改变方程的表达方式,不改变精确算术下的解集。完成后形成上三角系统,从最后一个未知量向前回代。

数值上不能只关注主元是否恰为0。非常小的主元会造成大倍数与误差放大,部分主元选取通常选择本列绝对值较大的候选并同步交换右端;病态问题仍可能对输入误差敏感。

03把一个小例子完全算清楚

增广矩阵 [[2,1,5],[4,3,11]]。

步骤计算与状态为什么这样做
选主元换行[[4,3,11],[2,1,5]]当前列选绝对值 4
第二行减 0.5 倍第一行[0,−0.5,−0.5]消去 x
回代y=1,x=(11−3)/4=2再代回原方程验证

窄屏可左右滑动表格,阅读完整计算与理由。

解为 [2,1],原方程残差为零(本例可精确表示)。

04为什么这个方法成立

  1. 每次交换和倍数相减是可逆行变换,保持解集。
  2. 非奇异方阵在适当主元下形成非零对角的上三角矩阵。
  3. 回代逐个唯一确定未知量,因此得到原系统解。

05把推导翻译成代码

Python · 可独立运行的教学实现

def solve_linear(a,b):
    n = len(b)
    assert len(a)==n and all(len(row)==n for row in a)
    m = [list(map(float,row))+[float(value)] for row,value in zip(a,b)]
    for k in range(n):
        pivot = max(range(k,n),key=lambda i:abs(m[i][k]))
        if abs(m[pivot][k]) < 1e-12:
            raise ArithmeticError("singular or small pivot")
        m[k],m[pivot] = m[pivot],m[k]
        for i in range(k+1,n):
            factor = m[i][k]/m[k][k]
            for j in range(k,n+1):
                m[i][j] -= factor*m[k][j]
    x = [0.0]*n
    for i in range(n-1,-1,-1):
        x[i] = (m[i][n]-sum(m[i][j]*x[j] for j in range(i+1,n)))/m[i][i]
    return x

逐个理解关键决定

range(k,n+1)
增广矩阵右端列也必须一起做行变换。
range(n-1,-1,-1)
上三角系统从后往前解,保证右侧未知量已有值。

06时间、空间与实现范围

稠密 n×n 消元 O(n³),回代 O(n²),本复制实现空间 O(n²)。

小主元阈值 1e−12 是教学尺度下的保护,不是通用秩判据;生产计算宜用成熟数值库和尺度相关判定。

07改变条件,检查哪里会出错

只变换 A 不变换 b

等式右端没有同步变化,会得到另一个方程组。

有解就一定能无选主元消元

A=[[0,1],[1,0]] 可逆,但首主元为零,必须交换。

交换矩阵行却忘记交换右端

方程系数与常数必须成对移动,否则就变成另一个线性系统。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

A=[[0,1],[1,0]],b=[2,3] 解是什么?

需要一点提示

先交换方程。

查看解析与答案

[3,2]。

练习 2 · 边界与辨析

两行完全相同但右端不同意味着什么?

需要一点提示

消元后出现 0=非零。

查看解析与答案

系统不相容,无解;本方阵唯一解接口会以小主元失败,不提供完整解分类。

练习 3 · 变式与迁移

得到 x 后最基本的数值检查?

需要一点提示

代回原始系统。

查看解析与答案

计算残差 r=b−Ax,并按 A、x、b 的尺度归一化;残差小仍需考虑条件数。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Driscoll 与 Braun · Fundamentals of Numerical Computation

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。