第五章：高斯消元法

---

定理 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), (ii)$ 的每个解都是 $(i'), (ii')$ 的解，反之亦然。

另一方面，乘以零可能会改变解。 例如，$(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)

如本例所示，在变量 $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_i \vc{v}_i = \vc{u}$ 中减去方程 $\sum_{i=1}^q k^\prime_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$，所以解是相同的。