高斯若尔当消元法

2.1 引言

2.1.1 线性方程组求解的演变

早在四千年前，巴比伦数学家就已经开始处理线性方程组。¹ 他们能够求解简单的二元方程组，例如 $x + y = 12$ ， $x - y = 2$ 。中国数学家在其《九章算术》中，将这一方法推广到三元方程组，并涉及以中国剩余定理形式出现的相关数论背景。方程组求解问题也出现在分析学中，例如在约束条件下求函数最大值时。由莱布尼茨开创的行列式方法，经加布里埃尔·克莱姆发展，得到了方程组或方程的显式求解公式。现代求解方程组的方法采用一种清晰的消元过程。这一过程速度极快，由卡尔·弗里德里希·高斯将其形式化。这正是我们至今仍在使用的办法。它还能有效地计算行列式。

2.1.2 高斯消元法

消元法当然在高斯之前很久就已使用。我们很早就将其作为普通的消元法来学习。例如，解出一个变量，然后代入其余方程，得到一个未知数更少的方程组。高斯所做的，是写下了一个形式化的消元过程。这大约是在 1809 年。他称普通的消元法为“eliminationem vulgarem”。这一过程并非凭空而来。对相当应用性的问题的研究必定导致了它的产生。例如，高斯在 1801 年，根据当年夏天公布的 $24$ 次测量数据，在几周内就预测出了小行星谷神星的轨道。据报道，高斯花了超过 $100$ 个小时来确定轨道的 $5$ 个参数。像这样的练习无疑激励了高斯后来写下更形式化的程序，用以解决线性问题或更一般的数据拟合问题。“高斯消元法”这一名称首先由乔治·福赛思使用，而艾伦·图灵则以我们今天教授的方式描述了它。我们将在这里形式化地看到，该过程是以一种唯一的方式确定的。²

2.2 讲座

2.2.1 线性变换与方程

如果一个 $n \times m$ 矩阵 $A$ 乘以一个向量 $x \in ℝ^{m}$ ，我们得到 $ℝ^{n}$ 中的一个新向量 $A x$ 。过程 $x \to A x$ 定义了一个从 $ℝ^{m}$ 到 $ℝ^{n}$ 的线性映射。给定 $b \in ℝ^{n}$ ，可以要求找到满足线性方程组 $A x = b$ 的 $x$ 。从历史上看，这条通往线性代数的门径，远在矩阵为人所知之前就已有人走过：其根源可追溯至数千年前的巴比伦和中国。³

2.2.2 增广矩阵与行化简

求解该系统的最佳方法是行化简增广矩阵 $B = [A ∣ b] .$ 这是一个 $n \times (m + 1)$ 矩阵，因为现在有 $m + 1$ 列。高斯-若尔当消元算法从一个矩阵 $B$ 产生一个行简化矩阵 $rref (B)$ 。该算法允许做三件事：从一行减去另一行、缩放一行以及交换两行。如果我们考察方程组，所有这些操作都保持解空间不变。我们的目标是产生主元 1 “ $1$ ”，即矩阵中某行第一个非零项为 $1$ 的项。目标是得到一个处于行简化阶梯形的矩阵。这意味着：

每个非零行都有一个主元 1，
每个包含主元 $1$ 的列，除该主元外没有其他非零项。第三个条件是
在具有主元 1 的行之上的每一行，其主元 1 都位于更左侧。

2.2.3 行简化阶梯形的唯一性

我们将在课堂和作业中练习这个过程。这里有一个定理

定理 1. 每个矩阵 $A$ 都有唯一的行简化阶梯形。

证明。 ⁴我们使用关于矩阵列数 $m$ 的归纳法。归纳假设是 $m = 1$ 的情形，即只有一列。根据条件 B)，要么没有非零项，要么有 $1$ 个非零项。如果没有，我们得到零列。如果非零，根据条件 C)，它必须位于顶部。我们得到行简化阶梯形。现在，假设所有 $n \times m$ 矩阵都有唯一的行简化阶梯形。取一个 $n \times (m + 1)$ 矩阵 $[A ∣ b]$ 。如果删除最后一列 $b$ ，它仍保持行简化阶梯形（见引理）。删除最后一列然后行化简，与先行化简再删除最后一列是相同的。因此，行化简后 $A$ 的列是唯一确定的。现在注意，对于 $[A ∣ b]$ 中末尾没有主元 1 的行，所有项都为零，因此末尾项也一致。假设我们有两个行化简结果和，其中是 $A$ 的行化简结果。在的最后一列出现主元 “ $1$ ” 当且仅当 $A$ 中对应的行为零。因此，在末尾也有该主元 “ $1$ ”。现在假设最后一列没有主元 1，且。那么我们有 $x$ ，它是方程的解。由于行化简时方程的解保持不变，也有。因此。 ◻

2.2.4 证明构造中矩阵分块的引理

一个单独的引理可以将证明分解：

如果 $[A ∣ b]$ 是行简化的，那么 $A$ 是行简化的。

证明。 我们必须检查定义行简化阶梯形的三个条件。 ◻

2.2.5

如果 $A$ 是行简化阶梯形，那么任何子矩阵都是行简化阶梯形，这个说法并不正确。你能找到一个例子吗？

2.3 示例

例 1. 为了行化简，我们使用三个步骤并在右侧记录。为节省空间，我们有时只报告完成两个步骤后的结果。我们圈出主元 $1$ 。注意，我们没有立即通过缩放第一行来得到主元 $1$ 。尽可能避免分数是个好主意。

例 2. 完成下面的数独问题，这是一个需要填充矩阵的游戏。规则是：在四个 $2 \times 2$ 子方格中、四行中以及四列中，数字 $1$ 到 $4$ 都必须出现，因此总和为 $10$ 。 $[\begin{matrix} 2 & 1 & x & 3 \\ 3 & y & z & 1 \\ 4 & 3 & a & 2 \\ b & c & d & e \end{matrix}]$ 对于行，我们有方程对于列，有对于四个方格，有我们可以通过写出相应的增广矩阵然后进行行化简来求解该系统。解为 $[\begin{array}{cccc} 2 & 1 & 4 & 3 \\ 3 & 4 & 2 & 1 \\ 4 & 3 & 1 & 2 \\ 1 & 2 & 3 & 4 \end{array}] .$

2.4 图解

方程组

是一个层析成像问题。这类问题出现在磁共振成像中。其前身是 X 射线计算机断层扫描（CT），艾伦·麦克劳德·科马克因此于 1979 年获得诺贝尔奖（科马克于 1956-1957 年在哈佛大学休假，期间萌生了这一想法）。科马克直到 1998 年都住在马萨诸塞州温彻斯特。他原本是物理学家。他的工作对医学产生了巨大影响。

**图 2.** MRI 扫描仪可以测量沿线的组织密度平均值。MRI（磁共振成像）是一种避免患者受到辐射暴露的放射成像技术。求解方程组可以计算出实际密度，从而实现“透视身体内部”的魔法。

我们构建增广矩阵 $[A ∣ b]$ 并进行行化简。首先从第 $4$ 行减去前三行之和，然后改变第 $4$ 列的符号：

现在我们可以读出解。我们看到 $v$ 和 $w$ 可以自由选择。它们是自由变量。我们设 $v = r$ 和 $w = s$ 。然后只需解出变量：

**图 3.** 这是一个具有 $F = 540$ 个面的多面体。在作业中，你将仅凭这一知识计算出顶点数 $V$ 和边数 $E$ 。成立的方程是 $V - E + F = 2$ 和 $3 F = 2 E$ 。

练习

练习 1. 对于一个具有 $v$ 个顶点、 $e$ 条边和 $f$ 个三角形面的多面体，欧拉证明了他的著名公式 $V - E + F = 2$ 。另一个关系式 $3 F = 2 E$ 称为德恩-索末菲关系，因为每个面与 $3$ 条边相接，每条边与 $2$ 个面相接。假设三角形面数 $F$ 为 $F = 540$ 。将未知量 $V, E, F$ 的方程组写成矩阵形式 $A x = b$ ，然后使用高斯消元法求解。

练习 2. 行化简矩阵 $A = [\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 4 & 0 \\ 1 & 2 & 3 & 0 & 0 \end{matrix}]$ 。

练习 3. 在《九章算术》中，出现了以下方程组通过写出增广矩阵并进行行化简来求解它。

练习 4.

下列哪些矩阵是行简化阶梯形？
两个 $n \times m$ 简化行阶梯形矩阵，如果它们包含相同数量的主元 $1$ 且位置相同，则称为同类型。例如， $[\begin{matrix} 1 & 2 & 0 \\ 0 & 0 & 1 \end{matrix}]$ 和 $[\begin{matrix} 1 & 3 & 0 \\ 0 & 0 & 1 \end{matrix}]$ 是同类型的。简化行阶梯形的 $2 \times 2$ 矩阵有多少种类型？

练习 5. 给定 $A = [\begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{matrix}]$ 。比较 $rref (A^{T})$ 与 $(rref (A))^{T}$ 。行简化矩阵的转置是行简化矩阵吗？

我向阿贾克核实过，他也暗示法斯托斯可能泄露了高斯-若尔当消元法。最新漫威电影的开场场景显示永恒族于公元前5000年抵达这里。↩︎
J.F. Grcar，《高斯消元法的数学家们》，《美国数学会通告》，58卷，2011年。↩︎
更多信息，请查看2018年Math 22a课程网站上的展览。↩︎
该证明广为人知：例如，Thomas Yuster，《数学杂志》，1984年。↩︎

目录