高斯消元法解线性方程组

贡献者： addis

预备知识　线性方程组的解集

　　¹线性方程组（有 $x_{1} \dots x_{n}$ 这 $n$ 个未知量，所以也叫 $n$ 元一次方程组）

\begin{matrix} (1) & {\begin{aligned} a_{1, 1} x_{1} + a_{1, 2} x_{2} + \dots + a_{1, n} x_{n} & = & y_{1} \\ a_{2, 1} x_{1} + a_{2, 2} x_{2} + \dots + a_{2, n} x_{n} & = & y_{2} \\ \dots \dots \dots \\ a_{m, 1} x_{1} + a_{m, 2} x_{2} + \dots + a_{m, n} x_{n} & = & y_{m} \end{aligned} \end{matrix}

可以写成矩阵和列矢量相乘的形式

\begin{matrix} (2) & A x = y, \end{matrix}

其中

A

是维度

m \times n

的矩阵，称为系数矩阵。

\begin{matrix} (3) & A = (\begin{matrix} a_{1, 1} & a_{1, 2} & \dots & a_{1, n} \\ a_{2, 1} & a_{2, 2} & \dots & a_{2, n} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{m, 1} & a_{m, 2} & \dots & a_{m, n} \end{matrix}), \end{matrix}

x

是

n

维列矢量

(x_{1}, x_{2}, \dots, x_{m}, \dots, x_{n})^{T}

。

y

是

m

维列矢量

(y_{1}, y_{2}, \dots, y_{m})^{T}

，称为常数列。

A

和

y

通常看做已知的，而

x

看做未知的，即方程组待求的解。下面我们介绍一种解线性方程组的简单的方法，高斯消元法（Gauss elimination）。 先来看一个简单的例子。

例 1　

　　我们先回顾一下初中阶段如何解线性方程组，例如

\begin{matrix} (4) & {\begin{aligned} 2 x + 3 y = 21 \\ 5 x - 2 y = 5 \end{aligned} \end{matrix}

一种方法是将第一条等式两边除以 2 再移项得到

\begin{matrix} (5) & x = - \frac{3}{2} y + \frac{21}{2} . \end{matrix}

再代入第二个条式消去

x

得

\begin{matrix} (6) & - \frac{19}{2} y + \frac{105}{2} = 5 . \end{matrix}

解得

y = 5

，再代入第一条等式得

x = 3

。

　　另一种更方便的解法是，将第一条等式（两边）乘以 $- 5 / 2$ ，加到第二条上消去 $x$ 得

\begin{matrix} (7) & - \frac{19}{2} y = - \frac{95}{2} . \end{matrix}

解得

y = 5

，再代入第一条等式得

x = 3

。为什么可以这么做？简单来说是因为如果两条等式都成立，将它们两边相加得到的新的等式同样成立。下面我们来详细讲解第二种方法。

　　为了书写简单，我们可以用所谓的增广矩阵（augmented matrix）来表示矩阵和常数列，即把式 4 记为

\begin{matrix} (8) & (\begin{array}{ccc} 2 & 3 & 21 \\ 5 & - 2 & 5 \end{array}) \end{matrix}

同样把第一行乘以

- 5 / 2

，加到第二行上得

\begin{matrix} (9) & (\begin{array}{ccc} 2 & 3 & 21 \\ 0 & - 19 / 2 & - 95 / 2 \end{array}) \end{matrix}

　　如果这个方程有多个未知数，且方程的数量和未知数相同（系数矩阵为方阵），理想情况下我们可以用第一行消去所有 $i > 1$ 行的第一个系数，再用第二行消去所有 $i > 2$ 行的第 2 个系数，以此类推，最后得到一个三角形系数矩阵。三角形系数矩阵的最后一行只有最后一个变量的系数不为零，我们求出这个变量后，再代入倒数第二行（只有两个未知量）求出另一个未知量，最后就可以得到所有未知量的值。这个过程叫做反向迭代（backward substitution）。

　　注意这只是一种理想的情况，如果在处理第 $i$ 行的时候发现 $a_{i, i} = 0$ ，则该方法无法进行下去。为此我们需要稍微复杂一些的方法，也就是高斯消元法的一般步骤。

1. 一般步骤

　　我们将式 1 形式的方程组用增广矩阵表示为

\begin{matrix} (10) & B = (A, y) = (\begin{array}{ccccc} a_{1, 1} & a_{1, 2} & \dots & a_{1, n} & y_{1} \\ a_{2, 1} & a_{2, 2} & \dots & a_{2, n} & y_{2} \\ ⋮ & ⋮ & ⋱ & ⋮ & ⋮ \\ a_{m, 1} & a_{m, 2} & \dots & a_{m, n} & y_{m} \end{array}) \end{matrix}

　　定义以下三种矩阵（或增广矩阵）变换为初等行变换。初等行变换不改变方程组的解²。

对调矩阵中的第 $i$ 行与第 $j$ 行，记作 $r_{i} \leftrightarrow r_{j}$
将矩阵第 $i$ 行的所有元素乘以一个非零数 $k$ ，记作 $r_{i} \times k$
把矩阵第 $i$ 行的所有元素乘以数 $k$ 后加到第 $j$ 行上，下文简记为 $r_{j} + r_{i} \times k$

　　任何非零矩阵（或增广矩阵）经过有限次初等行变换后总可以使系数矩阵 $A$ 转化为梯形矩阵（echelon form）。我们把梯形矩阵定义为满足该条件的矩阵：第 $i$ 行的第一个非零系数³ $a_{i, q (i)}$ 的列标 $q (i)$ 总是大于第 $i - 1$ 行的第一个非零元 $a_{i - 1, q (i - 1)}$ 的列标 $q (i - 1)$ 。与例 1 不同的是，当系数矩阵经过行变换化为梯形矩阵后，最后若干行有可能都为零，最后一个非零行也未必只有一个非零元。

　　高斯消元法的一般步骤如下：

先处理第 $i = 1$ 行，如果 $a_{1, 1} = 0$ 但某 $i^{'} > 1$ 的行有 $a_{i^{'}, 1} \neq 0$ ，就先进行行变换⁴ $r_{i} \leftrightarrow r_{i^{'}}$ 。如果第一列全为 0，我们就无视第 1 列，从第 2 列重新开始，以此类推。记此时第 1 行第一个非零元的列标为 $q (1)$ 。接下来做若干次行变换 $r_{i^{'}} + r_{1} \times k$ 使所有第 $i^{'} > 1$ 行的 $a_{i^{'}, q (1)}$ 都为 0。
依次处理第 $i = 2 \dots m - 1$ 行⁵。要处理第 $i$ 行，先令 $q (i) = q (i - 1) + 1$ ，如果此时矩阵元 $a_{i, q (i)} = 0$ ，但某 $i^{'} > i$ 的行有 $a_{i^{'}, q (i)} \neq 0$ ，就先进行行变换 $r_{i} \leftrightarrow r_{i^{'}}$ 。若不存在这样的 $i^{'}$ ，我们就改令 $q (i) = q (i - 1) + 2$ 并重新开始该步骤，以此类推。接下来做若干次行变换 $r_{i^{'}} + r_{i} \times k$ 使所有第 $i^{'} > i$ 行的 $a_{i^{'}, q (i)}$ 都为 0。

　　完成后，系数矩阵就会变为梯形矩阵。

例 2　解线性方程组

\begin{matrix} (11) & {\begin{aligned} x_{1} & + & x_{2} & - & x_{3} & + & x_{4} & = & 3 \\ 2 x_{1} & + & 2 x_{2} & - & 2 x_{3} & + & x_{4} & = & 7 \\ x_{1} & + & x_{2} & + & 2 x_{4} & = & 3 \\ 2 x_{1} & + & 2 x_{2} & - & x_{3} & + & 5 x_{4} & = & 4 \end{aligned} \end{matrix}

解：

　　将该方程组写成增广矩阵形式

\begin{matrix} (12) & B = (\begin{array}{ccccc} 1 & 1 & - 1 & 1 & 3 \\ 2 & 2 & - 2 & 1 & 7 \\ 1 & 1 & 0 & 2 & 3 \\ 2 & 2 & - 1 & 5 & 4 \end{array}) \end{matrix}

对第一列

\begin{matrix} (13) & \begin{aligned} r_{2} - 2 & r_{1} \\ r_{3} - 1 & r_{1} \\ r_{4} - 2 & r_{1} \end{aligned} ⟹ B = (\begin{array}{ccccc} 1 & 1 & - 1 & 1 & 3 \\ 0 & 0 & 0 & - 1 & 1 \\ 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 3 & - 2 \end{array}) \end{matrix}

　　发现此时，矩阵第二列自第二行以下全为零，所以需要依次向下一列寻找不为零的元素。继续消元

\begin{matrix} (14) & \begin{aligned} r_{2} \leftrightarrow r_{4} \\ r_{3} - 1 r_{2} \\ r_{4} - 0 r_{2} \end{aligned} ⟹ B = (\begin{array}{ccccc} 1 & 1 & - 1 & 1 & 3 \\ 0 & 0 & 1 & 3 & - 2 \\ 0 & 0 & 0 & - 2 & 2 \\ 0 & 0 & 0 & - 1 & 1 \end{array}) \end{matrix}

\begin{matrix} (15) & r_{4} - 0.5 r_{3} ⟹ B = (\begin{array}{ccccc} 1 & 1 & - 1 & 1 & 3 \\ 0 & 0 & 1 & 3 & - 2 \\ 0 & 0 & 0 & - 2 & 2 \\ 0 & 0 & 0 & 0 & 0 \end{array}) \end{matrix}

我们按照上面的方法用第 3 行求

x_{4}

，代入第 2 行求得

x_{3}

。然而当我们想用第 1 行求

x_{1}

的时候却出发现我们还没求出

x_{2}

。解决办法是，我们令

x_{2} = c

且假设

c

可以取任意值，再把

x_{1}

用

c

表示。方程的解可以表示为

\begin{matrix} (16) & {\begin{aligned} x_{1} & = 5 - c \\ x_{2} & = c \\ x_{3} & = 1 \\ x_{4} & = - 1 \end{aligned} \end{matrix}

或者写成列矢量的形式

\begin{matrix} (17) & x = c (\begin{matrix} - 1 \\ 1 \\ 0 \\ 0 \end{matrix}) + (\begin{matrix} 5 \\ 0 \\ 1 \\ - 1 \end{matrix}) . \end{matrix}

将该式代入方程组，可以验证

c

取任意值时方程组都成立。

　　如果多个 $x_{i}$ 的值都未知，我们就分别假设它们等于不同的任意常数 $c_{i}$ 即可。

2. 解的数量

　　根据以上步骤，当系数矩阵变为梯形矩阵后，可以用以下步骤判断解的数量：

若存在系数 $a_{i, j}$ 全为零的行 $i$ ，但是对应的常数 $y_{i}$ 却不为零，则方程组无解。
若存在 $d$ 个系数 $a_{i, j}$ 全为零的行 $i$ ，且对应的所有 $y_{i}$ 也都为零，则方程有无穷个解，且需要 $d$ 个任意常数来表示所有可能的解。
若不存在系数 $a_{i, j}$ 全为零的行，则系数矩阵可以化为三角矩阵，使对角线上的元素全不为零。此时方程有唯一解。

3. 解的结构

　　按照高斯消元法的一般步骤，如果方程有解，我们总可以将解表示为一些常矢量的线性组合加上一个常矢量。

\begin{matrix} (18) & x = \sum_{i = 1}^{d} c_{i} x_{i} + x_{0} . \end{matrix}

其中

c_{i}

是

d

个任意常数（当方程有唯一解时

d = 0

），无论这些常数取什么值，

x

都是方程的解。另一方面，给出方程的任意一个解，总能找到一些常数

c_{i}

与之对应。式 18 叫做方程的通解（general solution），通解中的任意一个就做方程的特解（special solution）。

　　将式 18 代入方程组，使用矩阵乘法分配律（式 17 ）得到

\begin{matrix} (19) & A \sum_{i = 1}^{d} c_{i} x_{i} + A x_{0} = y, \end{matrix}

由于

x_{0}

是方程的一个特解，有

A x_{0} = y

。所以

\begin{matrix} (20) & A \sum_{i = 1}^{d} c_{i} x_{i} = 0 . \end{matrix}

线性方程组

A x = y

中，如果

y = 0

（粗体的

0

表示零矢量，即每个元都是

0

），则方程组被称为是齐次（homogeneous）的。上式说明

\sum_{i} c_{i} x_{i}

就是齐次方程组

A x = 0

的通解。

　　综上所述，对于任意有解的非齐次（inhomogeneous）方程组 $A x = y$ ，我们可以将通解（式 18 ）从形式上理解为齐次方程组 $A x = 0$ 的通解与非齐次方程组的任一特解相加。

1. ^ 参考 Wikipedia 相关页面。
2. ^ 这点我们留到以后证明
3. ^ 为了书写简单，我们将每次变换后的系数矩阵元仍然用 $a_{i, j}$ 来表示，虽然它的值可能已经发生变化。若需要区分，可以将第 $n$ 次变换后的矩阵元用 $a_{i, j}^{(n)}$ 表示。
4. ^ 如果 $a_{1, 1} \neq 0$ 则不需要
5. ^ 如果在处理 $i = m - 1$ 之前就得到了梯形矩阵，则可提前终止。

高斯消元法解线性方程组

例 1

1. 一般步骤

例 2 解线性方程组

2. 解的数量

3. 解的结构

例 1　

例 2　解线性方程组