2.2 消元法的概念

本文主要是介绍2.2 消元法的概念，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、消元法介绍

消元法（elimination）是一个求解线性方程组的系统性方法。下面是使用消元法求解一个 $2\times2$ 线性方程组的例子。消元之前，两个方程都有 $x$ 和 $y$ ，消元后，第一个未知数 $x$ 将从第二个方程消失：
在这里插入图片描述
新的方程 $8 y = 8$ 能够直接得到 $y = 1$ ，再将 $y = 1$ 回代到第一个方程 $x - 2 y = 1$ ，求得 $x = 3$ ，则解就是 $(x, y) = (3, 1)$ 。
消元法的目的是得到一个上三角形系统。非零系数 $1, - 2, 8$ 形成一个三角形，这个系统从底部向上求解。首先得到 $y = 1$ ，然后求得 $x = 3$ 。这个过程称之为回代。经过消元法得到的三角形，回代可以在任意大小（行和列）的上三角形上使用。
重点： 原始方程组有着相同的解 $x = 3, y = 1$ 。Figure 2.5 中对这两个系统都使用了一对直线来表示，它们均相交于点 $(3, 1)$ 。即经过消元后，它们会交于相同的点，每一步的方程都有相同的解。
在这里插入图片描述
如何从第一对直线得到第二对直线呢？将第一个方程乘 $3$ ，然后用第二个方程减去第一个方程。目的是消去未知数 $x$ ：

消去 $x$ ：从方程 $2$ 减去方程 $1$ 的倍数

$3$ 乘 $x - 2 y = 1$ 得到 $3 x - 6 y = 3$ ，从方程 $3 x + 2 y = 11$ 减去上面的方程，右侧得到 $8$ ，重点是左侧 $3 x$ 与 $3 x$ 相消得到 $2 y - (- 6 y) = 8 y$ ，消去了 $x$ ，系统变成了三角形。
如何得到乘数 $l = 3$ 呢？第一个方程包含 $1 x$ ，所以第一个主元是 $1$ （ $x$ 的系数），第二个方程包含 $3 x$ ，所以乘数是 $3$ 。 $3 x - 3 x$ 就可以得到零和三角形。
如果将第一个方程变为 $4 x - 8 y = 4$ （同样的直线，但是第一个主元变成 $4$ ）。现在乘数就变成了 $l = 3/4$ 。把需要消去的系数 $3$ 除以主元 $4$ 就可以得到乘数：

在这里插入图片描述
最终仍然是个三角形系统，通过最后一个方程得到 $y = 1$ 。回代后得到 $4 x - 8 = 4$ ，解得 $x = 3$ 。这里虽然改变了数字，但是直线是不变的，解也就不会变。

$\pmb{主元} = 经过消元后的行的第一个非零数\kern 15pt\\ \pmb{乘数} = （需要消去的元）/（主元）= 3/4$

新的第二个方程是从第二主元开始的，主元是 $8$ 。如果要解 $n$ 个方程，那么需要 $n$ 个主元，完成消元后，这些主元都会在三角形的对角线上。

二、消元法失效

正常情况下消元法可以找到解，但是也有失效的情况。有时会遇到除以 $0$ 的情况，这种情况下可能需要调整顺序，也可能消元法完全失效。
一般有如下三种例题的情况：例 1 是无解的情况，例 2 是有无穷解，例 3 可以通过交换方程的顺序来解决。
【例1】无解而完全失效。消元过后可以清楚的看到： $\begin{matrix}x-2y=1\\3x-6y=11\end{matrix}\kern 15pt消元后\kern 15pt\begin{matrix}x-2y=1\\\kern 18pt0y=8\end{matrix}$ $0 y = 8$ 无解。正常情况下是右侧的 $8$ 除以第二个主元，但是这里没有第二个主元（零不允许是主元）。从 Figure 2.6 中的行图像和列图像可以看出失效的原因。如果系统无解，那么消元过程中就会出现类似 $0 y = 8$ 这样形式的方程。

在这里插入图片描述
行图像中可以发现这是两条平行线，平行线是没有交点的，若方程组有解，那么这个解必定会同时落在两条直线上。这两条直线没有交点，所以方程组无解。
列图像中可以看出两个列向量 $(1, 3)$ 和 $(- 2, - 6)$ 位于同一个方向（同向或反向），所有列的线性组合都在同一直线上，但是右侧的列 $(1, 11)$ 不在这条直线上。不存在正确列的线性组合可以得到右侧的向量，因此方程组无解。
若将右侧改为 $(1, 3)$ ，那么会因为一整条直线都是解而失效。例 2 是由无穷多个解。
【例2】无限多解而失效。将 $\boldsymbol b$ 从 $(1, 11)$ 改成 $(1, 3)$ 。 $\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仍然仅有一个主元$ 所有的 $y$ 都满足方程 $0 y = 0$ ，实际上只有一个方程 $x - 2 y = 1$ 。未知数 $y$ 是自由的，当 $y$ 选定后，通过 $x = 2 y + 1$ 也就可以确定 $x$ 。
Figure 2.7 是该方程组的行图像和列图像。

在这里插入图片描述

此时的行图像，两条平行线变成了同一条直线，直线上的每一点都同时满足两个方程。
列图像中， $\boldsymbol b=(1,3)$ 与列 $1$ 相同。所以列的线性组合可以是 $x = 1, y = 0$ ，也可以是 $x = 0, y = - 1/2$ 。对于每一行的解 $(x, y)$ 同样也是列的解。
关于消元法：

失效 $\kern 10ptn$ 个方程无法得到 $n$ 个主元
消元法得到方程 $0\neq0$ （无解），或 $0 = 0$ （无限多解）
得到 $n$ 个主元表示成功，但是可能需要交换这 $n$ 个方程的顺序。

第三种消元法失效的情况下可以通过交换方程的顺序来解决。假设第一个主元的位置是 $0$ ，而 $0$ 不能作为主元。当第一个方程没有 $x$ 项时，我们可以将它与下面的方程交换：
【例3】暂时失效（主元出现 $0$ ）。交换行可以得到两个主元： $重新排列\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}$ 新的系统已经是三角形了。这个例子可以直接进行回代，最后一个方程得到 $y = 2$ ，回代到第一个方程可以得到 $x = 3$ 。本例行图像是正常的（两条相交直线），列图像也是正常的（列向量不在同一方向）。主元 $3$ 和 $2$ 也是正常的。但是需要进行一次行交换。
例 1 和例 2 是奇异的 —— 没有第二个主元。例 3 是非奇异的 —— 每个主元都存在，仅有一个解。奇异方程无解或有无限多解，非奇异方程仅有一个解。主元因为要做除数，所以不能是零。

三、三个方程三个未知数

为了更深入的理解高斯消元法， $2 \times 2$ 的系统是不够的，下面将以 $3 \times 3$ 的系统为例。现在的系数矩阵都是方形的 —— 行数与列数相等。 $\begin{matrix}2x+4y-2z=2\\4x+9y-3z=8\\-2x-3y+7z=10\end{matrix}\kern 25pt(2.2.1)$ 第一个主元是 $2$ （左上角），这个主元下方是要消去的 $4$ ，第一个乘数就是 $4/2 = 2$ 。第一个方程乘 $l_{21}=2$ 后，用第二个方程减去上面的结果，即可将 $4 x$ 消去：
步骤1： 从方程 2 中减去 2 乘方程 1，得： $y + z = 4$
我们也需要使用第一个主元消去第三个方程中的 $- 2 x$ 。最快的方法是将方程 3 与方程 1 相加，但是为了更系统的实现消元，我们仍然使用相同的方法，使用先乘后减的方法。乘数 $l_{31}=-2/2=-1$ ，将其与第一个方程相乘后，在从第三个方程减去上述结果：
步骤2： 方程 3 减去 $- 1$ 乘方程 1，得： $y + 5 z = 12$ 。
新的方程只包含了两个未知数 $y$ 和 $z$ ，第二个主元是 $1$ ： $x\,已经被消去\kern 10pt\begin{matrix}1y+1z=4\kern 6pt\\1y+5z=12\end{matrix}$ 我们已经得到一个 $2 \times 2$ 的系统，最后一步消去 $y$ 得到 $1 \times 1$ 的系统：
步骤3： 新的方程 3 减去 $1$ 乘新的方程 2，乘数是 $l_{32}=1/1=1$ ，得到 $4 z = 8$ 。
原始的 $A\boldsymbol x=\boldsymbol b$ 转换成了上三角形 $U\boldsymbol x=\boldsymbol c$ ：

在这里插入图片描述
至此消元的目的达成，从 $A$ 到 $U$ 完成了前向消元。注意 $U$ 的对角线就是主元 $2, 1, 4$ 。原始系统中主元 $1$ 和 $4$ 被隐藏了，通过消元法可以找到它们。 $U\boldsymbol x=\boldsymbol c$ 的形式可以使用回代来解方程组了： $(4z=8\,得\,z=2)\kern 10pt(y+z=4\,得\,y=2)\kern 10pt(2x+4y-2z=2\,得\,x=-1)$ 方程组的解是 $(x, y, z) = (- 1, 2, 2)$ 。行图像中三个方程形成三个平面，这三个平面都会经过解。原始的平面都是倾斜的，经过消元后最后一个平面 $4 z = 8$ 是水平的。
列图像显示列向量的线性组合 $A\boldsymbol x$ 产生右侧的向量 $\boldsymbol b$ ，组合系数 $(x, y, z) = (- 1, 2, 2)$ ： $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)$ 三角形 $U\boldsymbol x=\boldsymbol c$ 与 $A\boldsymbol x=\boldsymbol b$ 有相同的列向量组合 $(- 1, 2, 2)$ 产生右侧向量。

四、从 A 到 U 的消元法

对于 $4 \times 4$ 或者 $n\times n$ 的问题，消元法的步骤都是一样的。当高斯消元法成功时，系数矩阵将一列接一列的从 $A$ 变成 $U$ 。
列1. $\,\,$ 利用第一个方程将第一个主元下的都变成 0.
列2. $\,\,$ 利用新得到的第二个方程将第二个主元下的都变成 0.
列 3 到列 n. $\,\,$ 重复上述步骤，找到 $n$ 个主元和上三角矩阵 $U$ .
$列\,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)$ 前向消元法的结果是一个上三角形系统，如果 $n$ 个主元均存在（非零数字），则矩阵是非奇异的。

五、主要内容总结

线性系统 $A\boldsymbol x=\boldsymbol b$ 成功消元后变成上三角形 $U\boldsymbol x=\boldsymbol c$ 。
从方程 $i$ 减去 $l_{ij}$ 乘方程 $j$ 使得单元 $(i, j)$ 为 $0$ 。
乘数 $l_{ij}=\displaystyle\frac{行\,i\,要消去的单元}{行 \,j\,的主元}$ ，主元不为 $0$ 。
当主元的位置为 $0$ 时，如果下面有非零单元，交换行。
上三角 $U\boldsymbol x=\boldsymbol c$ 使用回代的方法求解。（从底到上）
当消元法完全失效时， $A\boldsymbol x=\boldsymbol b$ 无解或有无限多解。

六、例题

【例4】对矩阵 $A$ 进行消元法，第一主元和第二主元是什么？第一步的乘数 $l_{21}$ 是什么（行 2 减去 $l_{21}$ 乘行 1）？ $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$ 的 $(2, 2)$ 位置上数字变为多少会使得行 $2$ 和行 $3$ 必须交换？
为什么左下角的乘数 $l_{31}=0$ ，需要行 $3$ 减去 $0$ 乘行 $1$ ？
如果将角落的单元 $a_{33}=2$ 改成 $a_{33}=1$ ，为什么会使得消元法失败？
解：第一主元是 $1$ ，第二主元也是 $1$ ，乘数 $l_{21}=1/1=1$ 。
若将矩阵 $A$ 的 $(2, 2)$ 位置的单元改成 $1$ ，那么就必须要交换行 $2$ 和行 $3$ 。
因为 $a_{31}=0$ ，所以 $l_{31}=0/1=0$ 。某一行的开始是 $0$ 则不需要消元。矩阵 $A$ 是一个带状矩阵，中心带之外的都为 $0$ 。
如果原始角落的单元 $a_{33}$ 改成 $1$ ，消元法就会产生 $0$ 。没有第三个主元，消元法失败。

【例5】假设 $A$ 是一个三角形矩阵（上三角或下三角），主元会在什么位置？对于任意的 $\boldsymbol b$ ，什么情况下 $A\boldsymbol x=\boldsymbol b$ 有且仅有一个确切的解？
解：矩阵的对角线就是主元的位置。
当这些主元全都不是 $0$ 时，消元法执行成功可以。若 $A$ 是上三角，使用回代；若 $A$ 是下三角，使用前向代入。

【例6】使用消元法得到上三角形矩阵 $U$ 。通过回代求解，或者解释为什么无法执行？主元（不为 $0$ ）是什么？必要时可以交换方程的顺序。下面两个系统的唯一区别是最后一个方程的 $- x$ 。 $成功\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}$ 解：对于系统 1，方程 2 和方程 3 分别减去方程 1（乘数 $l_{21}=1,l_{31}=1$ ），由于 $(2, 2)$ 的位置会变成 0，所以交换方程 2 和 3 的顺序： $成功\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}$ 回代后可得 $z = 1, y = 2, x = 4$ 。主元是 $1, - 2, - 2$ 。
对于系统 2，执行消元后： $失败\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}$ 平面 1 与平面 2 相交于一条直线，平面 2 与平面 3 平行，该方程组无解。
如果将第三个方程中的 $3$ 改成 $- 5$ ，则消元法会得到 $0 = 0$ ，有无限多个解。三个平面相交于一条直线。此时第三个平面和第二个平面重合。