昆明网站建设方案策划,百度竞价seo排名,长沙网站优化收费,网络建设和网站建设一、消元法介绍
消元法#xff08;elimination#xff09;是一个求解线性方程组的系统性方法。下面是使用消元法求解一个 2 2 2\times2 22 线性方程组的例子。消元之前#xff0c;两个方程都有 x x x 和 y y y#xff0c;消元后#xff0c;第一个未知数 x x x 将从第…一、消元法介绍
消元法elimination是一个求解线性方程组的系统性方法。下面是使用消元法求解一个 2 × 2 2\times2 2×2 线性方程组的例子。消元之前两个方程都有 x x x 和 y y y消元后第一个未知数 x x x 将从第二个方程消失 新的方程 8 y 8 8y8 8y8 能够直接得到 y 1 y1 y1再将 y 1 y1 y1 回代到第一个方程 x − 2 y 1 x-2y1 x−2y1求得 x 3 x3 x3则解就是 ( x , y ) ( 3 , 1 ) (x,y)(3,1) (x,y)(3,1)。 消元法的目的是得到一个上三角形系统。非零系数 1 , − 2 , 8 1,-2,8 1,−2,8 形成一个三角形这个系统从底部向上求解。首先得到 y 1 y1 y1然后求得 x 3 x3 x3。这个过程称之为回代。经过消元法得到的三角形回代可以在任意大小行和列的上三角形上使用。 重点 原始方程组有着相同的解 x 3 , y 1 x3,y1 x3,y1。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-2y1 x−2y1 得到 3 x − 6 y 3 3x-6y3 3x−6y3从方程 3 x 2 y 11 3x2y11 3x2y11 减去上面的方程右侧得到 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 l3 l3 呢第一个方程包含 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-8y4 4x−8y4同样的直线但是第一个主元变成 4 4 4。现在乘数就变成了 l 3 / 4 l3/4 l3/4。把需要消去的系数 3 3 3 除以主元 4 4 4 就可以得到乘数 最终仍然是个三角形系统通过最后一个方程得到 y 1 y1 y1。回代后得到 4 x − 8 4 4x-84 4x−84解得 x 3 x3 x3。这里虽然改变了数字但是直线是不变的解也就不会变。 主元 经过消元后的行的第一个非零数 乘数 需要消去的元 / 主元 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-2y1\\3x-6y11\end{matrix}\kern 15pt消元后\kern 15pt\begin{matrix}x-2y1\\\kern 18pt0y8\end{matrix} x−2y13x−6y11消元后x−2y10y8 0 y 8 0y8 0y8 无解。正常情况下是右侧的 8 8 8 除以第二个主元但是这里没有第二个主元零不允许是主元。从 Figure 2.6 中的行图像和列图像可以看出失效的原因。如果系统无解那么消元过程中就会出现类似 0 y 8 0y8 0y8 这样形式的方程。 行图像中可以发现这是两条平行线平行线是没有交点的若方程组有解那么这个解必定会同时落在两条直线上。这两条直线没有交点所以方程组无解。 列图像中可以看出两个列向量 ( 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-2y1\\3x-6y3\kern 4pt\end{matrix}\kern 15pt消元后\kern 15pt\begin{matrix}x-2y1\\\kern 19pt0y0\end{matrix}\kern 10pt仍然仅有一个主元 x−2y13x−6y3消元后x−2y10y0仍然仅有一个主元所有的 y y y 都满足方程 0 y 0 0y0 0y0实际上只有一个方程 x − 2 y 1 x-2y1 x−2y1。未知数 y y y 是自由的当 y y y 选定后通过 x 2 y 1 x2y1 x2y1 也就可以确定 x x x。 Figure 2.7 是该方程组的行图像和列图像。 此时的行图像两条平行线变成了同一条直线直线上的每一点都同时满足两个方程。 列图像中 b ( 1 , 3 ) \boldsymbol b(1,3) b(1,3) 与列 1 1 1 相同。所以列的线性组合可以是 x 1 , y 0 x1,y0 x1,y0也可以是 x 0 , y − 1 / 2 x0,y-1/2 x0,y−1/2。对于每一行的解 ( x , y ) (x,y) (x,y) 同样也是列的解。 关于消元法 失效 n \kern 10ptn n 个方程无法得到 n n n 个主元 消元法得到方程 0 ≠ 0 0\neq0 00无解或 0 0 00 00无限多解 得到 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}0x2y4\\3x-2y5\end{matrix}\kern 10pt两个方程交换\kern 15pt\begin{matrix}3x-2y5\\\kern 24pt2y4\end{matrix} 重新排列0x2y43x−2y5两个方程交换3x−2y52y4新的系统已经是三角形了。这个例子可以直接进行回代最后一个方程得到 y 2 y2 y2回代到第一个方程可以得到 x 3 x3 x3。本例行图像是正常的两条相交直线列图像也是正常的列向量不在同一方向。主元 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}2x4y-2z2\\4x9y-3z8\\-2x-3y7z10\end{matrix}\kern 25pt(2.2.1) 2x4y−2z24x9y−3z8−2x−3y7z10(2.2.1)第一个主元是 2 2 2左上角这个主元下方是要消去的 4 4 4第一个乘数就是 4 / 2 2 4/22 4/22。第一个方程乘 l 21 2 l_{21}2 l212 后用第二个方程减去上面的结果即可将 4 x 4x 4x 消去 步骤1 从方程 2 中减去 2 乘方程 1得 y z 4 yz4 yz4 我们也需要使用第一个主元消去第三个方程中的 − 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 y5z12 y5z12。 新的方程只包含了两个未知数 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}1y1z4\kern 6pt\\1y5z12\end{matrix} x已经被消去1y1z41y5z12我们已经得到一个 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/11 l321/11得到 4 z 8 4z8 4z8。 原始的 A x b A\boldsymbol x\boldsymbol b Axb 转换成了上三角形 U x c U\boldsymbol x\boldsymbol c Uxc 至此消元的目的达成从 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 Uxc 的形式可以使用回代来解方程组了 ( 4 z 8 得 z 2 ) ( y z 4 得 y 2 ) ( 2 x 4 y − 2 z 2 得 x − 1 ) (4z8\,得\,z2)\kern 10pt(yz4\,得\,y2)\kern 10pt(2x4y-2z2\,得\,x-1) (4z8得z2)(yz4得y2)(2x4y−2z2得x−1)方程组的解是 ( x , y , z ) ( − 1 , 2 , 2 ) (x,y,z)(-1,2,2) (x,y,z)(−1,2,2)。行图像中三个方程形成三个平面这三个平面都会经过解。原始的平面都是倾斜的经过消元后最后一个平面 4 z 8 4z8 4z8 是水平的。 列图像显示列向量的线性组合 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 Uxc 与 A x b A\boldsymbol x\boldsymbol b Axb 有相同的列向量组合 ( − 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}xxxx\\0xxx\\00xx\\00xx\end{bmatrix}最终目标\kern 8pt\begin{bmatrix}xxxx\\0xxx\\00xx\\000x\end{bmatrix}\kern 10pt(2.1.4) 列2之后有 x000xx00xxxxxxxx 最终目标 x000xx00xxx0xxxx (2.1.4)前向消元法的结果是一个上三角形系统如果 n n n 个主元均存在非零数字则矩阵是非奇异的。
五、主要内容总结
线性系统 A x b A\boldsymbol x\boldsymbol b Axb 成功消元后变成上三角形 U x c U\boldsymbol x\boldsymbol c Uxc。从方程 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 Uxc 使用回代的方法求解。从底到上当消元法完全失效时 A x b A\boldsymbol x\boldsymbol b Axb 无解或有无限多解。
六、例题
【例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}110\\121\\012\end{bmatrix}\rightarrow\begin{bmatrix}110\\011\\012\end{bmatrix}\rightarrow\begin{bmatrix}110\\011\\011\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 l310需要行 3 3 3 减去 0 0 0 乘行 1 1 1 如果将角落的单元 a 33 2 a_{33}2 a332 改成 a 33 1 a_{33}1 a331为什么会使得消元法失败 解 第一主元是 1 1 1第二主元也是 1 1 1乘数 l 21 1 / 1 1 l_{21}1/11 l211/11。 若将矩阵 A A A 的 ( 2 , 2 ) (2,2) (2,2) 位置的单元改成 1 1 1那么就必须要交换行 2 2 2 和行 3 3 3。 因为 a 31 0 a_{31}0 a310所以 l 31 0 / 1 0 l_{31}0/10 l310/10。某一行的开始是 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 Axb 有且仅有一个确切的解 解 矩阵的对角线就是主元的位置。 当这些主元全都不是 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}xyz7\\xy-z5\\x-yz3\end{matrix}\kern 15pt失败\kern 10pt\begin{matrix}xyz7\\xy-z5\\-x-yz3\kern 6pt\end{matrix} 成功xyz7xy−z5x−yz3失败xyz7xy−z5−x−yz3解 对于系统 1方程 2 和方程 3 分别减去方程 1乘数 l 21 1 , l 31 1 l_{21}1,l_{31}1 l211,l311由于 ( 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}xyz7\\\kern 16pt0y-2z-2\\\kern 10pt-2y0z-4\end{matrix}\kern 15pt交换行后\kern 10pt\begin{matrix}xyz7\\\kern 9pt-2y0z-4\\\kern 33pt-2z-2\end{matrix} 成功xyz70y−2z−2−2y0z−4交换行后xyz7−2y0z−4−2z−2回代后可得 z 1 , y 2 , x 4 z1,y2,x4 z1,y2,x4。主元是 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}xyz7\\\kern16pt0y-2z-2\\\kern 16pt0y2z10\end{matrix}\kern 15pt\begin{matrix}列\,2\,\pmb{没有主元}(它就是列\,1)\\进一步消元得到\,0z8\kern 12pt\\三个平面\pmb{不相交}于一点\kern 11pt\end{matrix} 失败xyz70y−2z−20y2z10列2没有主元(它就是列1)进一步消元得到0z8三个平面不相交于一点平面 1 与平面 2 相交于一条直线平面 2 与 平面 3 平行该方程组无解。 如果将第三个方程中的 3 3 3 改成 − 5 -5 −5则消元法会得到 0 0 00 00有无限多个解。三个平面相交于一条直线。此时第三个平面和第二个平面重合。
