一、消元法介绍
消元法(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,有无限多个解。三个平面相交于一条直线。此时第三个平面和第二个平面重合。
【例7】若矩阵
A
A
A 已知,则使用 MATLAB 得到新的第二行,该新行是从行 2 减去 3 乘行 1 。
解: MATLAB 程序
A = [1 2 3; 4 5 6; 7 8 9]; % 创建矩阵 A
A(2, :) - 3 * A(1, :) % 得到新的行 2,A(2,:)为取矩阵 A 的第 2 行
运行结果:
【例8】MATLAB 指令 [L,U] = lu(rand(3))。找出第一、第二、第三主元的平均大小。abs(U(1,1)) 大于 1/2 是因为 lu 会选取列 1 最大可能的主元。
解: MATLAB 程序
[L, U] = lu(rand(3)); % rand(3) 是随机 3×3 矩阵,其单元均为 0~1 之间的数。 lu() 函数是进行 LU 分解
abs(U(1, 1)) % 第一主元 abs()函数是 求绝对值
abs(U(2, 2)) % 第二主元
abs(U(3, 3)) % 第三主元
运行结果:文章来源:https://www.toymoban.com/news/detail-716992.html
文章来源地址https://www.toymoban.com/news/detail-716992.html
到了这里,关于2.2 消元法的概念的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!