第 5 章：高斯消元法

---

定理 5.2 中的第一条高斯消元法规则 允许交换两个方程的顺序。不难理解，简单地 重排方程顺序不会改变方程组的 解，即

\begin{equation} \begin{cases} \begin{array}{rrrl} a_{11} x & \bsfem \, + a_{12} y & \bsfem \, + a_{13} z & \bsfem \, = b_1 , \\ a_{21} x & \bsfem \, + a_{22} y & \bsfem \, + a_{23} z & \bsfem \, = b_2 , \end{array} \end{cases} \Leftrightarrow \begin{cases} \begin{array}{rrrl} a_{21} x & \bsfem \, + a_{22} y & \bsfem \, + a_{23} z & \bsfem \, = b_2 , \\ a_{11} x & \bsfem \, + a_{12} y & \bsfem \, + a_{13} z & \bsfem \, = b_1 . \end{array} \end{cases} \end{equation}

(5.49)

下一条规则允许我们将一个方程乘以一个不等于 $0$ 的常数。由代数可知，将方程两边 同时乘以非零常数不会改变该方程的解， 因而也不会影响方程组的解。

\begin{equation} \begin{cases} \begin{array}{rrrll} a_{11} x & \bsfem \, + a_{12} y & \bsfem \, + a_{13} z & \bsfem \, = b_1 , & \bsfem \, \, \, (i) \\ a_{21} x & \bsfem \, + a_{22} y & \bsfem \, + a_{23} z & \bsfem \, = b_2 , & \bsfem \, \, \, (ii) \end{array} \end{cases} \Leftrightarrow \begin{cases} \begin{array}{rrrll} ka_{11} x & \bsfem \, + ka_{12} y & \bsfem \, + ka_{13} z & \bsfem \, = kb_1 , & \bsfem \, \, \, (i') = k (i)\\ a_{21} x & \bsfem \, + a_{22} y & \bsfem \, + a_{23} z & \bsfem \, = b_2 . & \bsfem \, \, \, (ii') = (ii) \end{array} \end{cases} \end{equation}

(5.50)

注意，我们可以将 $(i')$ 除以 $k$ 来恢复原方程组。 因此 $(i), (i)$ 的每个解都是 $(i'), (i')$ 的解，反之亦然。

另一方面，乘以零会改变 解。例如，$(x,y) = (2, 3)$ 不满足 方程

\begin{equation} x + y = 1, \, \, \, (i) \end{equation}

(5.51)

但它满足方程

\begin{equation} 0\cdot (x + y) = 0 \cdot 1. \, \, \, \, (i') = 0 (i) \end{equation}

(5.52)

此处 $(i)$ 的每个解都是 $(i')$ 的解，但 $(i')$ 的解未必都是 $(i)$ 的解。 我们无法从 $(i')$ 恢复方程 $(i)$。

第三条规则允许我们将另一行的倍数加到 某一行上。假设解 $(x, y, z)$ 满足方程组

\begin{equation} \begin{cases} \begin{array}{rrrll} a_{11} x & \bsfem \, + a_{12} y & \bsfem \, + a_{13} z & \bsfem \, = b_1, & \bsfem \, \, \, (i)\\ a_{21} x & \bsfem \, + a_{22} y & \bsfem \, + a_{23} z & \bsfem \, = b_2, & \bsfem \, \, \, (ii)\\ a_{31} x & \bsfem \, + a_{32} y & \bsfem \, + a_{33} z & \bsfem \, = b_3. & \bsfem \, \, \, (iii)\\ \end{array} \end{cases} \end{equation}

(5.53)

将第一行的 $k$ 倍加到 第二行，得到

\begin{equation} \begin{cases} \begin{array}{rrrrll} a_{11} x & \bsfem \, + a_{12} y & \bsfem \, + a_{13} z & \bsfyra = & \bsfem b_1, & \bsfem \, \, \, (i')=(i) \\ (a_{21}+ka_{11}) x & \bsfem \, + (a_{22}+ka_{12}) y & \bsfem \, + (a_{23}+ka_{13}) z & \bsfyra = & \bsfem b_2 + k b_1, & \bsfem \, \, \, (ii') = (ii)+k(i)\\ a_{31} x & \bsfem \, + a_{32} y & \bsfem \, + a_{33} z & \bsfyra = & \bsfem b_3. & \bsfem \, \, \, (iii') = (iii) \\ \end{array} \end{cases} \end{equation}

(5.54)

由于这里只使用了标准代数规则（例如，在方程两边同时加上同一常数，这不会改变 方程本身）， 原 方程组 (5.53) 的解 $(x,y,z)$ 必然 也是上面 方程组 (5.54) 的解。 重要的是，我们可以将第一行 (i') 的 $-k$ 倍加到第二行 (ii')，从而从新方程组 (5.54) 恢复原方程组 (5.53)。 因此 方程组 (5.54) 的每个解 也必然是上面 方程组 (5.53) 的解。 因此我们已经证明两个方程组等价。

---

一个一般的 线性方程组形如

\begin{equation} \begin{cases} \begin{array}{rrrrrl} a_{11} x_1 + & \bs a_{12} x_2 + & \bs a_{13} x_3 + & \bs \ldots + & \bs a_{1M} x_M & \bs = b_1,\\ a_{21} x_1 + & \bs a_{22} x_2 + & \bs a_{23} x_3 + & \bs \ldots + & \bs a_{2M} x_M & \bs = b_2,\\ a_{31} x_1 + & \bs a_{32} x_2 + & \bs a_{33} x_3 + & \bs \ldots + & \bs a_{3M} x_M & \bs = b_3,\\ & & & & & \bsfem \vdots\\ a_{N1} x_1 + & \bs a_{N2} x_2 + & \bs a_{N3} x_3 + & \bs \ldots + & \bs a_{NM} x_M & \bs = b_N,\\ \end{array} \end{cases} \end{equation}

(5.55)

其中 $a_{kl}$ 和 $b_k$ 是已知常数，$x_k$ 是未知变量。我们首先处理第一个变量 $x_1$。有两种可能情况。要么所有系数 $a_{i1}$ 都为零。那么我们就无法再对这个变量做任何操作。在 例 5.5 中我们会更详细地描述这种情况。更典型的情况是至少有一个系数 $a_{i1}$ 非零。此时，利用 高斯消元法 的第一法则，总可以重新排列方程，化为如上且满足 $a_{11}\neq 0$ 的方程组。然后可以将 $-(a_{21}/a_{11})$ 倍的第一行加到第二行，将 $-(a_{31}/a_{11})$ 倍的第一行加到第三行，依此类推，从而除第一个方程外从所有方程中消去 $x_1$。将新的常数记为 $a'_{kl}$ 和 $b'_k$，得到

\begin{equation} \begin{cases} \begin{array}{rl} a_{11} x_1 + & \bs a_{12} x_2 + & \bs a_{13} x_3 + & \bs \ldots & \bsfem + a_{1M} x_M & \bs = b_1,\\ & \bs a'_{22} x_2 + & \bs a'_{13} x_3 + & \bs \ldots & \bsfem + a'_{2M} x_M & \bs = b'_2,\\ & \bs a'_{32} x_2 + & \bs a'_{33} x_3 + & \bs \ldots & \bsfem + a'_{3M} x_M & \bs = b'_3,\\ & & & & & \bsfem \vdots\\ & \bs a'_{N2} x_2 + & \bs a'_{N3} x_3 + & \bs \ldots & \bsfem + a'_{NM} x_M & \bs = b'_N.\\ \end{array} \end{cases} \end{equation}

(5.56)

经过这一步，$x_1$ 前的系数仅在第一个方程中非零，或者它们全部为零。

现在，同样的程序可应用于带撇常数构成的较小方程组，即 (5.56) 中所有不涉及 $x_1$ 的行。同样有两种情况。要么所有这些方程中，我们要消去的变量 $x_2$ 的系数都为零；要么至少有一个方程中变量 $x_2$ 的系数非零。经重新排序和消元后，要么所有方程中变量 $x_2$ 的系数都为零，要么恰有一个方程中变量 $x_2$ 的系数非零。

这一过程持续进行，直到不再含有未知变量的方程。 最后，可能剩下 $0 = 0$ 型的方程。这些方程可以直接删去。 有三种可能的结果。

第一种情况是若至少有一个 $0 = \hat{b}_{i} \neq 0$ 型的方程， 则方程组无解。一个例子见 方程组 (5.33)。 对于接下来的讨论，我们假设不属于这种情况。

第二种情况是所得方程组呈 三角形，即

\begin{equation} \begin{cases} \begin{array}{rl} \hat{a}_{11} x_1 + & \bs \hat{a}_{12} x_2 + & \bs \hat{a}_{13} x_3 + & \bs \ldots + & \bsfem \hat{a}_{1M} x_M & \bs = \hat{b}_1,\\ & \bs \hat{a}_{22} x_2 + & \bs \hat{a}_{13} x_3 + & \bs \ldots + & \bsfem \hat{a}_{2M} x_M & \bs = \hat{b}_2,\\ & & \bs \hat{a}_{33} x_3 + & \bs \ldots + & \bsfem \hat{a}_{3M} x_M & \bs = \hat{b}_3,\\ & & & & & \bsfem \vdots\\ & & & & \bsfem \hat{a}_{MM} x_M & \bs = \hat{b}_M,\\ \end{array} \end{cases} \end{equation}

(5.57)

其中 $\hat{a}_{kl}$ 和 $\hat{b}_k$ 是经过一整轮高斯消元法后的常数。此时，变量 $x_M$ 可以精确求出， 这一结果又可用于从倒数第二个方程求出 $x_{M-1}$，依此类推。因此方程组有唯一解。

第三种可能是消元后方程个数少于未知数个数，例如

\begin{equation} \begin{cases} \begin{array}{rl} \hat{a}_{11} x_1 + & \bs \hat{a}_{12} x_2 + & \bs \hat{a}_{13} x_3 + & \bs \hat{a}_{14} x_4 + & \bsfem \hat{a}_{15} x_M & \bs = \hat{b}_1,\\ & & \bs \hat{a}_{23} x_3 + & \bs \hat{a}_{24} x_4 + & \bsfem \hat{a}_{25} x_5 & \bs = \hat{b}_2,\\ & & & \bs \hat{a}_{34} x_4 + & \bsfem \hat{a}_{35} x_5 & \bs = \hat{b}_3.\\ \end{array} \end{cases} \end{equation}

(5.58)

如本例所示，有 $3$ 个方程在变量 $x_1$、$x_3$ 和 $x_4$ 前有非零首元系数，共涉及 $3$ 个变量。 事实上，其余两个变量，即 $x_2$ 和 $x_5$，没有任何约束。 于是可令 $x_2 = t_1$、$x_5 = t_2$，再求出其余变量。本例中

\begin{equation} x_4 = \frac{1}{\hat{a}_{34}}(\hat{b}_3 -\hat{a}_{35} t_{2}) . \\ \end{equation}

(5.59)

此后，其余变量（本例中为 $x_1$ 和 $x_3$）可以求出。由于解依赖于一组变量 $\{t_1, t_2\}$，而它们可取任意值， 我们有无穷多 解。

因此，方程组要么无解，要么有唯一解，要么有无穷多解。

---

由 线性无关 的定义 （定义 5.2） 可知，若向量组 线性相关，则方程

\begin{equation} k_1\vc{v}_1 + k_2\vc{v}_2 + \dots + k_n \vc{v}_n = \vc{0} \end{equation}

(5.72)

有解，其中至少有一个 $k_1, k_2, \dots k_n$ 不为 零。假设最后一个值 $k_n$ 就是这样一个非零 值。（我们总可以通过重新编号指标使之为真。） 于是可将第 $n$ 项移到另一边

\begin{equation} k_1\vc{v}_1 + k_2\vc{v}_2 + \dots + k_{n-1} \vc{v}_{n-1} = - k_n \vc{v}_n, \end{equation}

(5.73)

由于 $k_n$ 不为零，我们可以除以 $-k_n$ 并交换两边，得到

\begin{equation} \vc{v}_n = -\frac{k_1}{k_n}\vc{v}_1 - \dots - \frac{k_{n-1}}{k_n} \vc{v}_{n-1}. \end{equation}

(5.74)

可见，我们已将向量 $\vc{v}_n$ 写成了其余向量的 线性组合。

反向证明更简单。假设其中一个向量可表示为其余向量的 线性组合。重新编号后，设它为向量 $\vc{v}_n$。于是得到

\begin{equation} \vc{v}_n = a_1\vc{v}_1 + a_2\vc{v}_2 + \dots + a_{n-1} \vc{v}_{n-1}. \end{equation}

(5.75)

将 $\vc{v}_n$ 项移到另一边，得到

\begin{equation} 0 = a_1\vc{v}_1 + a_2\vc{v}_2 + \dots + a_{n-1} \vc{v}_{n-1} - 1\vc{v}_n, \end{equation}

(5.76)

再取 $k_1 = a_1, k_2 = a_2, \dots k_{n-1} = a_{n-1}, k_n = -1$，我们就得到该方程的一个解

\begin{equation} k_1\vc{v}_1 + k_2\vc{v}_2 + \dots + k_{n-1} \vc{v}_{n-1} - k_n\vc{v}_n = 0 \end{equation}

(5.77)

其中并非所有 $k_j$ 都为零，因为 $k_n$ 等于 $-1$。这意味着向量组 $\vc{v}_1, \vc{v}_2, \dots \vc{v}_n$ 是 线性相关 的。

---

前两条定理是双向的，因此我们用 $\Rightarrow$ 标记正向证明，用 $\Leftarrow$ 标记反向证明。

1 $\Rightarrow$：假设 $\vc{u}$ 和 $\vc{v}$ 线性无关。定理 5.4 给出 $\vc{u}$ 不能表示为 $\vc{v}$ 的 线性组合，即 $\vc{u} \neq \lambda \vc{v}$，同理 $\vc{v} \neq \lambda \vc{u}$。这意味着 $\vc{u}$ 和 $\vc{v}$ 不平行，于是由 定理 2.4 可知它们在 平面 中构成一个 基。

1 $\Leftarrow$：假设 $\vc{u}$ 和 $\vc{v}$ 在 平面 中构成一个 基。我们现在证明这意味着 $\vc{u}$ 和 $\vc{v}$ 线性无关。假设它们并非 线性无关，却仍构成一个 基，即表达式 $x_u \vc{u} + x_v \vc{v}$ 可以到达 平面 中的每一点。由于它们 线性相关，定理 5.4 指出我们可以写出 $\vc{u} = \lambda \vc{v}$ 或 $\vc{v} = \lambda\vc{u}$。进一步假设我们可以将 $\vc{u}$ 写为 $\vc{u} = \lambda \vc{v}$（这总可以通过交换 $\vc{u}$ 和 $\vc{v}$ 的标签来实现）。假设我们要用 $\vc{w} = x_u \vc{u} + x_v \vc{v}$ 在这个 基 下描述新向量 $\vc{w}$。这等于 $\vc{w} = x_u \lambda \vc{v} + x_v \vc{v} = (x_u \lambda + x_v) \vc{v} = \mu \vc{v}$，其中 $\mu$ 是等于 $(x_u \lambda + x_v)$ 的标量。这意味着只有与 $\vc{v}$ 平行的向量 $\vc{w}$ 才能用 $x_u \vc{u} + x_v \vc{v}$ 来描述，因此 $\vc{u}$、$\vc{v}$ 不能成为整个平面的 基。

2 $\Rightarrow$：定理 2.5 指出，若不存在同时平行于 $\vc{u}$、$\vc{v}$ 和 $\vc{w}$ 的 平面，则这三个向量在空间中构成一个 基。 假设存在一个与三个向量都平行的 平面 $\pi$。由于它与 $\vc{u}$ 和 $\vc{v}$ 平行，它可以写为

\begin{equation} \pi: \vc{p} + s\vc{u} + t\vc{v}, \end{equation}

(5.87)

其中 $\vc{p}$ 是 平面 上的一点，$s$ 和 $t$ 是标量。若 $\pi$ 平行于 $\vc{w}$，这意味着若 平面 中有一点 $\vc{q}$，则点 $\vc{q} + \vc{w}$ 也在该 平面 中。$\vc{q}$ 在该 平面 中意味着存在两个标量 $s_1$ 和 $t_1$，使得

\begin{equation} \vc{q} = \vc{p} + s_1\vc{u} + t_1\vc{v}, \end{equation}

(5.88)

而 $\vc{q} + \vc{w}$ 在该 平面 中意味着存在两个标量 $s_2$ 和 $t_2$，使得

\begin{equation} \vc{q} + \vc{w} = \vc{p} + s_2\vc{u} + t_2\vc{v}. \end{equation}

(5.89)

若我们将第一个方程从第二个方程中减去，得到

\begin{equation} \vc{w} = (s_2-s_1)\vc{u} + (t_2-t_1)\vc{v}. \end{equation}

(5.90)

因此 $\vc{w}$ 可表示为 $\vc{u}$ 和 $\vc{v}$ 的 线性组合，据 定理 5.4 这意味着这些向量并非 线性无关。因此，若 $\vc{u}$、$\vc{v}$ 和 $\vc{w}$ 线性无关，则不可能存在同时平行于这三个向量的 平面。于是，由 定理 2.5 可知，三个 线性无关 的向量 $\vc{u}$、$\vc{v}$、$\vc{w}$ 在空间中构成一个 基。

2 $\Leftarrow$：假设 $\vc{u}$、$\vc{v}$ 和 $\vc{w}$ 在空间中构成一个 基。我们现在证明这意味着 $\vc{u}$、$\vc{v}$ 和 $\vc{w}$ 线性无关。假设它们并非 线性无关，却仍构成一个 基，即表达式 $x_u \vc{u} + x_v \vc{v} + x_w \vc{w}$ 可以到达空间中的每一点。由于它们 线性相关，定理 5.4 指出我们至少可以将其中一个向量写为另两个向量的 线性组合。设其中一个为 $\vc{u}$（否则重新命名向量），我们现在可以将 $\vc{u}$ 写为 $\vc{u} = \lambda_v \vc{v} + \lambda_w \vc{w}$。现在我们要用 $\vc{q} = x_u \vc{u} + x_v \vc{v} + x_w \vc{w}$ 在这个 基 下描述 $\vc{q}$。代入 $\vc{u}$ 的 线性 表达式得 $\vc{q} = x_u (\lambda_v \vc{v} + \lambda_w \vc{w}) + x_v \vc{v} + x_w \vc{w} = (x_u \lambda + x_v) \vc{v} + (x_u \lambda_w + x_w) \vc{w} = \mu_v \vc{v} + \mu_w \vc{w}$，其中 $\mu_v$ 和 $\mu_w$ 是标量。这意味着只有与 $\vc{v}$ 和 $\vc{w}$ 所张成的 平面 平行的向量 $\vc{q}$ 才能用 $x_u \vc{u} + x_v \vc{v} + x_w \vc{w}$ 来描述，因此 $\vc{u}$、$\vc{v}, \vc{w}$ 不能成为整个三维空间的 基。 因此，它们 线性无关。

3：假设 $\vc{u}$、$\vc{v}$ 和 $\vc{w}$ 是 平面 中的向量。先考察 $\vc{u}$ 和 $\vc{v}$。若它们 线性相关，即平行，则整个向量组 $\vc{u}$、$\vc{v}$、$\vc{w}$ 也 线性相关，证明完毕。然而，若 $\vc{u}$ 和 $\vc{v}$ 线性无关，则据 (1) 它们在 平面 中构成一个 基。这意味着 $\vc{w}$ 可表示为 线性组合

4：第 4 条的证明与第 3 条相同。

\begin{equation} \vc{w} = \lambda_1 \vc{u} + \lambda_2 \vc{v} \end{equation}

(5.91)

对某个 $\lambda_1, \lambda_2$。这可以写为

\begin{equation} \lambda_1 \vc{u} + \lambda_2 \vc{v} + (-1)\vc{w} = 0 \end{equation}

(5.92)

据 定义 5.2，这意味着三个向量 线性相关，因为 $k_1 = \lambda_1$、$k_2 = \lambda_2$、$k_3 = -1$ 满足 式 (5.67)。

---

假设向量组 $\vc{u}_1, \vc{u}_2, \ldots, \vc{u}_q$ 是 $\R^n$ 的 基。则据 定义 2.10，对每个 $\vc{u}$，方程 $k_1\vc{v}_1 + k_2 \vc{v}_2 + \dots + k_q \vc{v}_q= \vc{u}$ 都有解，因此据 定义 5.3 这些向量张成 $\R^n$。 要证明这些向量 线性无关，我们注意到方程 $ \sum_{i=1}^q k_i \vc{v}_i = \vc{0}$ 有一个解 $k_1=0, k_2=0, \ldots, k_q=0$。据 基 的定义 （定义 2.10），该解是唯一的。这证明这些向量 线性无关。

为完成反向证明，我们假设向量组 $\vc{u}_1, \vc{u}_2, \ldots, \vc{u}_q$ 张成 $\R^n$ 且 线性无关。我们需要证明 $\sum_{i=1}^q k_i \vc{v}_i = \vc{u}$ 对每个 $\vc{u}$ 都恰有一个解。由于这些向量张成 $\R^n$，对每个 $\vc{u}$ 都至少有一个解。假设有两个解 $(k_1, k_2, \ldots, k_q)$ 和 $(k^\prime_1, k^\prime_2, \ldots, k^\prime_q)$。若我们将方程 $\sum_{i=1}^q k^\prime_i \vc{v}_i = \vc{u}$ 从 $\sum_{i=1}^q k_i \vc{v}_i = \vc{u}$ 中减去，得到 $\sum_{i=1}^q (k_i-k^\prime_i) \vc{v}_i = \vc{0}$。由于这些向量 线性无关（定义 5.2），我们有 $(k_i-k^\prime_i) = 0$，但这给出 $k_i=k^\prime_i$，因此两个解相同。