一、消元法介绍
消元法（elimination）是一个求解线性方程组的系统性方法。下面是使用消元法求解一个
2
×
2
2\times2
2×2 线性方程组的例子。消元之前，两个方程都有
x
x
x 和
y
y
y，消元后，第一个未知数
x
x
x 将从第二个方程消失：
新的方程
8
y
=
8
8y=8
8y=8 能够直接得到
y
=
1
y=1
y=1，再将
y
=
1
y=1
y=1 回代到第一个方程
x
−
2
y
=
1
x-2y=1
x−2y=1，求得
x
=
3
x=3
x=3，则解就是
(
x
,
y
)
=
(
3
,
1
)
(x,y)=(3,1)
(x,y)=(3,1)。
消元法的目的是得到一个上三角形系统。非零系数
1
,
−
2
,
8
1,-2,8
1,−2,8 形成一个三角形，这个系统从底部向上求解。首先得到
y
=
1
y=1
y=1，然后求得
x
=
3
x=3
x=3。这个过程称之为回代。经过消元法得到的三角形，回代可以在任意大小（行和列）的上三角形上使用。
重点： 原始方程组有着相同的解
x
=
3
,
y
=
1
x=3,y=1
x=3,y=1。Figure 2.5 中对这两个系统都使用了一对直线来表示，它们均相交于点
(
3
,
1
)
(3,1)
(3,1)。即经过消元后，它们会交于相同的点，每一步的方程都有相同的解。
如何从第一对直线得到第二对直线呢？将第一个方程乘
3
3
3，然后用第二个方程减去第一个方程。目的是消去未知数
x
x
x：
消去 x x x：从方程 2 2 2 减去方程 1 1 1 的倍数
3
3
3 乘
x
−
2
y
=
1
x-2y=1
x−2y=1 得到
3
x
−
6
y
=
3
3x-6y=3
3x−6y=3，从方程
3
x
+
2
y
=
11
3x+2y=11
3x+2y=11 减去上面的方程，右侧得到
8
8
8，重点是左侧
3
x
3x
3x 与
3
x
3x
3x 相消得到
2
y
−
(
−
6
y
)
=
8
y
2y-(-6y)=8y
2y−(−6y)=8y，消去了
x
x
x，系统变成了三角形。
如何得到乘数
l
=
3
l=3
l=3 呢？第一个方程包含
1
x
1x
1x，所以第一个主元是
1
1
1（
x
x
x 的系数），第二个方程包含
3
x
3x
3x，所以乘数是
3
3
3。
3
x
−
3
x
3x-3x
3x−3x 就可以得到零和三角形。
如果将第一个方程变为
4
x
−
8
y
=
4
4x-8y=4
4x−8y=4（同样的直线，但是第一个主元变成
4
4
4）。现在乘数就变成了
l
=
3
/
4
l=3/4
l=3/4。把需要消去的系数
3
3
3 除以主元
4
4
4 就可以得到乘数：
最终仍然是个三角形系统，通过最后一个方程得到
y
=
1
y=1
y=1。回代后得到
4
x
−
8
=
4
4x-8=4
4x−8=4，解得
x
=
3
x=3
x=3。这里虽然改变了数字，但是直线是不变的，解也就不会变。
主元 = 经过消元后的行的第一个非零数 乘数 = （需要消去的元） / （主元） = 3 / 4 \pmb{主元} = 经过消元后的行的第一个非零数\kern 15pt\\ \pmb{乘数} = （需要消去的元）/（主元）= 3/4 主元=经过消元后的行的第一个非零数乘数=（需要消去的元）/（主元）=3/4
新的第二个方程是从第二主元开始的，主元是 8 8 8。如果要解 n n n 个方程，那么需要 n n n 个主元，完成消元后，这些主元都会在三角形的对角线上。
二、消元法失效
正常情况下消元法可以找到解，但是也有失效的情况。有时会遇到除以
0
0
0 的情况，这种情况下可能需要调整顺序，也可能消元法完全失效。
一般有如下三种例题的情况：例 1 是无解的情况，例 2 是有无穷解，例 3 可以通过交换方程的顺序来解决。
【例1】无解而完全失效。消元过后可以清楚的看到：
x
−
2
y
=
1
3
x
−
6
y
=
11
消元后
x
−
2
y
=
1
0
y
=
8
\begin{matrix}x-2y=1\\3x-6y=11\end{matrix}\kern 15pt消元后\kern 15pt\begin{matrix}x-2y=1\\\kern 18pt0y=8\end{matrix}
x−2y=13x−6y=11消元后x−2y=10y=8
0
y
=
8
0y=8
0y=8 无解。正常情况下是右侧的
8
8
8 除以第二个主元，但是这里没有第二个主元（零不允许是主元）。从 Figure 2.6 中的行图像和列图像可以看出失效的原因。如果系统无解，那么消元过程中就会出现类似
0
y
=
8
0y=8
0y=8 这样形式的方程。
行图像中可以发现这是两条平行线，平行线是没有交点的，若方程组有解，那么这个解必定会同时落在两条直线上。这两条直线没有交点，所以方程组无解。
列图像中可以看出两个列向量
(
1
,
3
)
(1,3)
(1,3) 和
(
−
2
,
−
6
)
(-2,-6)
(−2,−6) 位于同一个方向（同向或反向），所有列的线性组合都在同一直线上，但是右侧的列
(
1
,
11
)
(1,11)
(1,11) 不在这条直线上。不存在正确列的线性组合可以得到右侧的向量，因此方程组无解。
若将右侧改为
(
1
,
3
)
(1,3)
(1,3)，那么会因为一整条直线都是解而失效。例 2 是由无穷多个解。
【例2】无限多解而失效。将
b
\boldsymbol b
b 从
(
1
,
11
)
(1,11)
(1,11) 改成
(
1
,
3
)
(1,3)
(1,3)。
x
−
2
y
=
1
3
x
−
6
y
=
3
消元后
x
−
2
y
=
1
0
y
=
0
仍然仅有一个主元
\begin{matrix}x-2y=1\\3x-6y=3\kern 4pt\end{matrix}\kern 15pt消元后\kern 15pt\begin{matrix}x-2y=1\\\kern 19pt0y=0\end{matrix}\kern 10pt仍然仅有一个主元
x−2y=13x−6y=3消元后x−2y=10y=0仍然仅有一个主元所有的
y
y
y 都满足方程
0
y
=
0
0y=0
0y=0，实际上只有一个方程
x
−
2
y
=
1
x-2y=1
x−2y=1。未知数
y
y
y 是自由的，当
y
y
y 选定后，通过
x
=
2
y
+
1
x=2y+1
x=2y+1 也就可以确定
x
x
x。
Figure 2.7 是该方程组的行图像和列图像。
此时的行图像，两条平行线变成了同一条直线，直线上的每一点都同时满足两个方程。
列图像中，
b
=
(
1
,
3
)
\boldsymbol b=(1,3)
b=(1,3) 与列
1
1
1 相同。所以列的线性组合可以是
x
=
1
,
y
=
0
x=1,y=0
x=1,y=0，也可以是
x
=
0
,
y
=
−
1
/
2
x=0,y=-1/2
x=0,y=−1/2。对于每一行的解
(
x
,
y
)
(x,y)
(x,y) 同样也是列的解。
关于消元法：
失效 n \kern 10ptn n 个方程无法得到 n n n 个主元
消元法得到方程 0 ≠ 0 0\neq0 0=0（无解），或 0 = 0 0=0 0=0（无限多解）
得到 n n n 个主元表示成功，但是可能需要交换这 n n n 个方程的顺序。
第三种消元法失效的情况下可以通过交换方程的顺序来解决。假设第一个主元的位置是
0
0
0，而
0
0
0 不能作为主元。当第一个方程没有
x
x
x 项时，我们可以将它与下面的方程交换：
【例3】暂时失效（主元出现
0
0
0）。交换行可以得到两个主元：
重新排列
0
x
+
2
y
=
4
3
x
−
2
y
=
5
两个方程交换
3
x
−
2
y
=
5
2
y
=
4
重新排列\kern 15pt\begin{matrix}0x+2y=4\\3x-2y=5\end{matrix}\kern 10pt两个方程交换\kern 15pt\begin{matrix}3x-2y=5\\\kern 24pt2y=4\end{matrix}
重新排列0x+2y=43x−2y=5两个方程交换3x−2y=52y=4新的系统已经是三角形了。这个例子可以直接进行回代，最后一个方程得到
y
=
2
y=2
y=2，回代到第一个方程可以得到
x
=
3
x=3
x=3。本例行图像是正常的（两条相交直线），列图像也是正常的（列向量不在同一方向）。主元
3
3
3 和
2
2
2 也是正常的。但是需要进行一次行交换。
例 1 和例 2 是奇异的 —— 没有第二个主元。例 3 是非奇异的 —— 每个主元都存在，仅有一个解。奇异方程无解或有无限多解，非奇异方程仅有一个解。主元因为要做除数，所以不能是零。
三、三个方程三个未知数
为了更深入的理解高斯消元法，
2
×
2
2×2
2×2 的系统是不够的，下面将以
3
×
3
3×3
3×3 的系统为例。现在的系数矩阵都是方形的 —— 行数与列数相等。
2
x
+
4
y
−
2
z
=
2
4
x
+
9
y
−
3
z
=
8
−
2
x
−
3
y
+
7
z
=
10
(
2.2.1
)
\begin{matrix}2x+4y-2z=2\\4x+9y-3z=8\\-2x-3y+7z=10\end{matrix}\kern 25pt(2.2.1)
2x+4y−2z=24x+9y−3z=8−2x−3y+7z=10(2.2.1)第一个主元是
2
2
2（左上角），这个主元下方是要消去的
4
4
4，第一个乘数就是
4
/
2
=
2
4/2=2
4/2=2。第一个方程乘
l
21
=
2
l_{21}=2
l21=2 后，用第二个方程减去上面的结果，即可将
4
x
4x
4x 消去：
步骤1： 从方程 2 中减去 2 乘方程 1，得：
y
+
z
=
4
y+z=4
y+z=4
我们也需要使用第一个主元消去第三个方程中的
−
2
x
-2x
−2x。最快的方法是将方程 3 与方程 1 相加，但是为了更系统的实现消元，我们仍然使用相同的方法，使用先乘后减的方法。乘数
l
31
=
−
2
/
2
=
−
1
l_{31}=-2/2=-1
l31=−2/2=−1，将其与第一个方程相乘后，在从第三个方程减去上述结果：
步骤2： 方程 3 减去
−
1
-1
−1 乘方程 1，得：
y
+
5
z
=
12
y+5z=12
y+5z=12。
新的方程只包含了两个未知数
y
y
y 和
z
z
z，第二个主元是
1
1
1：
x
已经被消去
1
y
+
1
z
=
4
1
y
+
5
z
=
12
x\,已经被消去\kern 10pt\begin{matrix}1y+1z=4\kern 6pt\\1y+5z=12\end{matrix}
x已经被消去1y+1z=41y+5z=12我们已经得到一个
2
×
2
2×2
2×2 的系统，最后一步消去
y
y
y 得到
1
×
1
1×1
1×1 的系统：
步骤3： 新的方程 3 减去
1
1
1 乘新的方程 2，乘数是
l
32
=
1
/
1
=
1
l_{32}=1/1=1
l32=1/1=1，得到
4
z
=
8
4z=8
4z=8。
原始的
A
x
=
b
A\boldsymbol x=\boldsymbol b
Ax=b 转换成了上三角形
U
x
=
c
U\boldsymbol x=\boldsymbol c
Ux=c：
至此消元的目的达成，从
A
A
A 到
U
U
U 完成了前向消元。注意
U
U
U 的对角线就是主元
2
,
1
,
4
2,1,4
2,1,4。原始系统中主元
1
1
1 和
4
4
4 被隐藏了，通过消元法可以找到它们。
U
x
=
c
U\boldsymbol x=\boldsymbol c
Ux=c 的形式可以使用回代来解方程组了：
(
4
z
=
8
得
z
=
2
)
(
y
+
z
=
4
得
y
=
2
)
(
2
x
+
4
y
−
2
z
=
2
得
x
=
−
1
)
(4z=8\,得\,z=2)\kern 10pt(y+z=4\,得\,y=2)\kern 10pt(2x+4y-2z=2\,得\,x=-1)
(4z=8得z=2)(y+z=4得y=2)(2x+4y−2z=2得x=−1)方程组的解是
(
x
,
y
,
z
)
=
(
−
1
,
2
,
2
)
(x,y,z)=(-1,2,2)
(x,y,z)=(−1,2,2)。行图像中三个方程形成三个平面，这三个平面都会经过解。原始的平面都是倾斜的，经过消元后最后一个平面
4
z
=
8
4z=8
4z=8 是水平的。
列图像显示列向量的线性组合
A
x
A\boldsymbol x
Ax 产生右侧的向量
b
\boldsymbol b
b，组合系数
(
x
,
y
,
z
)
=
(
−
1
,
2
,
2
)
(x,y,z)=(-1,2,2)
(x,y,z)=(−1,2,2)：
A
x
=
(
−
1
)
[
2
4
−
2
]
+
2
[
4
9
−
3
]
+
2
[
−
2
−
3
7
]
=
[
2
8
10
]
=
b
(
2.2.3
)
A\boldsymbol x=(-1)\begin{bmatrix}\kern 7pt2\\\kern 7pt4\\-2\end{bmatrix}+2\begin{bmatrix}\kern 7pt4\\\kern 7pt9\\-3\end{bmatrix}+2\begin{bmatrix}-2\\-3\\\kern 7pt7\end{bmatrix}=\begin{bmatrix}2\\8\\10\end{bmatrix}=\boldsymbol b\kern 10pt(2.2.3)
Ax=(−1)
24−2
+2
49−3
+2
−2−37
=
2810
=b(2.2.3)三角形
U
x
=
c
U\boldsymbol x=\boldsymbol c
Ux=c 与
A
x
=
b
A\boldsymbol x=\boldsymbol b
Ax=b 有相同的列向量组合
(
−
1
,
2
,
2
)
(-1,2,2)
(−1,2,2) 产生右侧向量。
四、从 A 到 U 的消元法
对于
4
×
4
4×4
4×4 或者
n
×
n
n\times n
n×n 的问题，消元法的步骤都是一样的。当高斯消元法成功时，系数矩阵将一列接一列的从
A
A
A 变成
U
U
U。
列1.
\,\,
利用第一个方程将第一个主元下的都变成 0.
列2.
\,\,
利用新得到的第二个方程将第二个主元下的都变成 0.
列 3 到列 n.
\,\,
重复上述步骤，找到
n
n
n 个主元和上三角矩阵
U
U
U.
列
2
之后有
[
x
x
x
x
0
x
x
x
0
0
x
x
0
0
x
x
]
，最终目标
[
x
x
x
x
0
x
x
x
0
0
x
x
0
0
0
x
]
(
2.1.4
)
列\,2\,之后有\kern 8pt\begin{bmatrix}x&x&x&x\\0&x&x&x\\0&0&x&x\\0&0&x&x\end{bmatrix}，最终目标\kern 8pt\begin{bmatrix}x&x&x&x\\0&x&x&x\\0&0&x&x\\0&0&0&x\end{bmatrix}\kern 10pt(2.1.4)
列2之后有
x000xx00xxxxxxxx
，最终目标
x000xx00xxx0xxxx
(2.1.4)前向消元法的结果是一个上三角形系统，如果
n
n
n 个主元均存在（非零数字），则矩阵是非奇异的。
五、主要内容总结
- 线性系统 A x = b A\boldsymbol x=\boldsymbol b Ax=b 成功消元后变成上三角形 U x = c U\boldsymbol x=\boldsymbol c Ux=c。
- 从方程 i i i 减去 l i j l_{ij} lij 乘方程 j j j 使得单元 ( i , j ) (i,j) (i,j) 为 0 0 0。
- 乘数 l i j = 行 i 要消去的单元 行 j 的主元 l_{ij}=\displaystyle\frac{行\,i\,要消去的单元}{行 \,j\,的主元} lij=行j的主元行i要消去的单元，主元不为 0 0 0。
- 当主元的位置为 0 0 0 时，如果下面有非零单元，交换行。
- 上三角 U x = c U\boldsymbol x=\boldsymbol c Ux=c 使用回代的方法求解。（从底到上）
- 当消元法完全失效时， A x = b A\boldsymbol x=\boldsymbol b Ax=b 无解或有无限多解。
六、例题
【例4】对矩阵
A
A
A 进行消元法，第一主元和第二主元是什么？第一步的乘数
l
21
l_{21}
l21 是什么（行 2 减去
l
21
l_{21}
l21 乘行 1）？
A
=
[
1
1
0
1
2
1
0
1
2
]
→
[
1
1
0
0
1
1
0
1
2
]
→
[
1
1
0
0
1
1
0
1
1
]
=
U
A=\begin{bmatrix}1&1&0\\1&2&1\\0&1&2\end{bmatrix}\rightarrow\begin{bmatrix}1&1&0\\0&1&1\\0&1&2\end{bmatrix}\rightarrow\begin{bmatrix}1&1&0\\0&1&1\\0&1&1\end{bmatrix}=U
A=
110121012
→
100111012
→
100111011
=U矩阵
A
A
A 的
(
2
,
2
)
(2,2)
(2,2) 位置上数字变为多少会使得行
2
2
2 和行
3
3
3 必须交换？
为什么左下角的乘数
l
31
=
0
l_{31}=0
l31=0，需要行
3
3
3 减去
0
0
0 乘行
1
1
1？
如果将角落的单元
a
33
=
2
a_{33}=2
a33=2 改成
a
33
=
1
a_{33}=1
a33=1，为什么会使得消元法失败？
解： 第一主元是
1
1
1，第二主元也是
1
1
1，乘数
l
21
=
1
/
1
=
1
l_{21}=1/1=1
l21=1/1=1。
若将矩阵
A
A
A 的
(
2
,
2
)
(2,2)
(2,2) 位置的单元改成
1
1
1，那么就必须要交换行
2
2
2 和行
3
3
3。
因为
a
31
=
0
a_{31}=0
a31=0，所以
l
31
=
0
/
1
=
0
l_{31}=0/1=0
l31=0/1=0。某一行的开始是
0
0
0 则不需要消元。矩阵
A
A
A 是一个带状矩阵，中心带之外的都为
0
0
0。
如果原始角落的单元
a
33
a_{33}
a33 改成
1
1
1，消元法就会产生
0
0
0。没有第三个主元，消元法失败。
【例5】假设
A
A
A 是一个三角形矩阵（上三角或下三角），主元会在什么位置？对于任意的
b
\boldsymbol b
b，什么情况下
A
x
=
b
A\boldsymbol x=\boldsymbol b
Ax=b 有且仅有一个确切的解？
解： 矩阵的对角线就是主元的位置。
当这些主元全都不是
0
0
0 时，消元法执行成功可以。若
A
A
A 是上三角，使用回代；若
A
A
A 是下三角，使用前向代入。
【例6】使用消元法得到上三角形矩阵
U
U
U。通过回代求解，或者解释为什么无法执行？主元（不为
0
0
0）是什么？必要时可以交换方程的顺序。下面两个系统的唯一区别是最后一个方程的
−
x
-x
−x。
成功
x
+
y
+
z
=
7
x
+
y
−
z
=
5
x
−
y
+
z
=
3
失败
x
+
y
+
z
=
7
x
+
y
−
z
=
5
−
x
−
y
+
z
=
3
成功\kern 10pt\begin{matrix}x+y+z=7\\x+y-z=5\\x-y+z=3\end{matrix}\kern 15pt失败\kern 10pt\begin{matrix}x+y+z=7\\x+y-z=5\\-x-y+z=3\kern 6pt\end{matrix}
成功x+y+z=7x+y−z=5x−y+z=3失败x+y+z=7x+y−z=5−x−y+z=3解： 对于系统 1，方程 2 和方程 3 分别减去方程 1（乘数
l
21
=
1
,
l
31
=
1
l_{21}=1,l_{31}=1
l21=1,l31=1），由于
(
2
,
2
)
(2,2)
(2,2) 的位置会变成 0，所以交换方程 2 和 3 的顺序：
成功
x
+
y
+
z
=
7
0
y
−
2
z
=
−
2
−
2
y
+
0
z
=
−
4
交换行后
x
+
y
+
z
=
7
−
2
y
+
0
z
=
−
4
−
2
z
=
−
2
成功\kern 10pt\begin{matrix}x+y+z=7\\\kern 16pt0y-2z=-2\\\kern 10pt-2y+0z=-4\end{matrix}\kern 15pt交换行后\kern 10pt\begin{matrix}x+y+z=7\\\kern 9pt-2y+0z=-4\\\kern 33pt-2z=-2\end{matrix}
成功x+y+z=70y−2z=−2−2y+0z=−4交换行后x+y+z=7−2y+0z=−4−2z=−2回代后可得
z
=
1
,
y
=
2
,
x
=
4
z=1,y=2,x=4
z=1,y=2,x=4。主元是
1
,
−
2
,
−
2
1,-2,-2
1,−2,−2。
对于系统 2，执行消元后：
失败
x
+
y
+
z
=
7
0
y
−
2
z
=
−
2
0
y
+
2
z
=
10
列
2
没有主元
(
它就是列
1
)
进一步消元得到
0
z
=
8
三个平面
不相交
于一点
失败\kern 10pt\begin{matrix}x+y+z=7\\\kern16pt0y-2z=-2\\\kern 16pt0y+2z=10\end{matrix}\kern 15pt\begin{matrix}列\,2\,\pmb{没有主元}(它就是列\,1)\\进一步消元得到\,0z=8\kern 12pt\\三个平面\pmb{不相交}于一点\kern 11pt\end{matrix}
失败x+y+z=70y−2z=−20y+2z=10列2没有主元(它就是列1)进一步消元得到0z=8三个平面不相交于一点平面 1 与平面 2 相交于一条直线，平面 2 与 平面 3 平行，该方程组无解。
如果将第三个方程中的
3
3
3 改成
−
5
-5
−5，则消元法会得到
0
=
0
0=0
0=0，有无限多个解。三个平面相交于一条直线。此时第三个平面和第二个平面重合。
