第一节Gauss消元法 一、引言 二、Gauss 消元法的基本思想 三、 主元消元法 四、 Gauss消元法的矩阵形式 五、小结
第一节 Gauss 消元法 四、 Gauss 消元法的矩阵形式 三、 主元消元法 二、 Gauss 消元法的基本思想 一、引言 五、小结
一、引言 在自然科学和工程技术问题中，涉及到许多数值计算 问题，最终都要归结为解线性代数方程组AX=b。其中 A∈R",bR”,A是可逆的。本章和下一章分别讨论解方程 组的直接方法和迭代方法。所谓直接方法就是通过有限次 的精确运算能得到真解的一类数值方法。从本质上讲，直 接方法的原理是找到一个可逆矩阵M,使得MA是一个上 三角阵，这个过程称为“消元”过程。消元之后再进行 “回代”，即球解Mb 。 实际计算过程中，不必明显 地计算出短阵，而只须把M和计算出来。这类直接 方法中最基本和最简单的就是 消元法，本章首先论 消元法和矩阵分解法，以及Gass消元法在各种情况下的 变形，并分析其误差
在自然科学和工程技术问题中，涉及到许多数值计算 问题，最终都要归结为解线性代数方程组 。其中 是可逆的。本章和下一章分别讨论解方程 组的直接方法和迭代方法。所谓直接方法就是通过有限次 的精确运算能得到真解的一类数值方法。从本质上讲，直 接方法的原理是找到一个可逆矩阵 ，使得 是一个上 三角阵，这个过程称为“消元”过程。消元之后再进行 “回代” ，即求解 。实际计算过程中，不必明显 地计算出矩阵 ,而只须把 和 计算出来。这类直接 方法中最基本和最简单的就是 消元法，本章首先讨论 消元法和矩阵分解法，以及 消元法在各种情况下的 变形，并分析其误差。 , , n n n A R b R A AX b = M MA MAX Mb = M Mb GaussGauss MA Gauss 一、引言
二、 Gauss消元法的基本思想 考虑n阶线性代数方程组： ax+a2x2+.+anx=b azx a2x2++aznxn =bz anx1+an2X2+…+amXn=b 用矩阵和向量的记号表示，则有 AX=b (1.2) 其中A=(a,)m为可逆矩阵，X=(xx2,…,xn了，b=(0,b,,b,) 消元法分消元和迭代两个过程，消元过程是将(1.1)化成 为如下形式的上三角方程组：
用矩阵和向量的记号表示，则有 ( ) 其中 A a = ij n n 为可逆矩阵， 1, 2 1 2 ( , , ) , ( , , , ) . T T X x x x b b b b = = n n 消元法分消元和迭代两个过程，消元过程是将(1.1)化成 为如下形式的上三角方程组： 二、 Gauss 消元法的基本思想 考虑 n 阶线性代数方程组： ( ) 11 1 12 2 1 1 21 1 22 2 2 2 1 1 2 2 1.1 n n n n n n nn n n a x a x a x b a x a x a x b a x a x a x b + + + = + + + = + + + = AX b = (1.2)
a+aax=b a22x32+…+a2x=b2 (1.3 .... 迭代过程是从(1.3)最后一个方程直接解出xn,x。=b,01am 然后依公式 a,k=n-1,…3,2,1 (1.4 依次求出xn1,x-2,…x2,x,称为回代求解。消元过程的实 质是对增广矩阵(A,b)作一系列初等行变换，最后把A化为上 三角矩阵4”，得(4”，b)，因为对(Ab)每做一次初等行变 换，相当于对方程式组(1.1)进行一次同解变换，所以与，b) 相应的上三角形方程组(1.3)是(1.1)的同解方程组
( ) (1) (1) (1) (1) 11 1 12 2 1 1 (2) (2) (2) 22 2 2 2 ( ) ( ) 1.3 n n n n n n nn n n a x a x a x b a x a x b a x b + + + = + + = = 迭代过程是从(1.3)最后一个方程直接解出 ( ) ( ) , / , n n n n n nn x x b a = 然后依公式 ( ) ( ) ( ) ( ) 1 , 1, 3,2,1 1.4 n k k k k k kj j kk j k x b a x a k n = + = − = − 1 2 2 1 , , , n n x x x x − − A 依次求出 ，称为回代求解。消元过程的实 质是对增广矩阵 作一系列初等行变换，最后把 化为上 三角矩阵 ，得 ，因为对 每做一次初等行变 换，相当于对方程式组(1.1)进行一次同解变换，所以与 相应的上三角形方程组（1.3）是（1.1）的同解方程组。 ( , ) A b ( ) n A ( ) ( ) ( , ) n n A b ( , ) A b ( ) ( ) ( , ) n n A b
设方程组(1.1)的增广矩阵(A,b)=(4”,b),不妨设 a1≠0，并令m1=a1a州0=2,3，…，n),第一步消元是用m1 乘第一行然后加到第(=2,3，，m行上去，从而把第一列 主对角元以下的元素全化为0，得 aag…a b) (1.5) …a…a2b9 第二步，假设a8≠0，令m2=a21a(i=3,4,,m),于是 用上述方法又可把(1.5)化为
第二步，假设 (2) a22 0, 令 (2) (2) 2 2 22 / ( 3, 4, , ), m a a i n i i = = 于是 用上述方法又可把(1.5)化为 设方程组（1.1）的增广矩阵 (1) (1) ( , ) ( , ), A b A b = 不妨设 a11 0, 并令 (1) (1) 1 1 11 / ( 2,3, , ), m a a i n i i = = 第一步消元是用 mi1 主对角元以下的元素全化为0，得 乘第一行然后加到第 i i n ( 2,3, , ) = 行上去，从而把第一列 (1.5) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1 1 1 1 11 12 1 1 2 2 2 2 2 22 2 2 2 2 2 , n n n n nm n a a a b a a b A b a a b =
a a唱 a喝 (A,b)= a8 a鼎 (1.6) a 第三步，假设a4g≠0，再用a消去a,…a,如此继 续，共n-1步即可把方程组1.1)化为形如(1.3)的上 三角方程组： AX =b(m) (1.7) 其中A”和bm分别为方程组(1.3)的系数矩阵和右端 向量
(1) (1) (1) (1) (1) 11 12 13 1 1 (2) (2) (2) (2) 22 23 2 2 (3) (3) (3) (3) (3) 33 3 3 (3) (3) (3) 3 ( , ) n n n n nn n a a a a b a a a b A b a a b a a b = (1.6) 第三步，假设 再用 消去 如此继 续，共 步即可把方程组(1.1)化为形如（1.3）的上 三角方程组： (3) a33 0, (3) 33 a (3) (3) 43 3 , , , a an n −1 ( ) ( ) n n A X b = (1.7) 其中 和 分别为方程组(1.3)的系数矩阵和右端 向量。 ( ) n A ( ) n b
这样就完成了消元过程，最后利用公式1.4)回代” 求解。 由以上分析可以看出，消元过程的第K步共含除 法运算n-k次，乘法运算(n-k)(n-k+)次，所以消元 过程共含乘除法次数为 而回代过程的乘除法运算次数为
这样就完成了消元过程，最后利用公式(1.4)“回代” 求解。 由以上分析可以看出，消元过程的第 步共含除 法运算 次，乘法运算 次，所以消元 过程共含乘除法次数为 k n k − (n k n k − − + )( 1) 1 1 3 2 1 1 5 ( ) ( )( 1) 3 2 6 n n k k n n n n k n k n k − − = = − + − − + = + − 而回代过程的乘除法运算次数为
n-k+) n"n k=1 22 所以Gauss消元法总的乘除法次数为 +n2-n、n3 n 3 33 如果我们用Gramer法则计算(1.1)的解，要计算n+1 个n阶行列式并作n次除法。而计算每个行列式，若用 子式展开的方法，则有n!次乘法，所以用Gramer法则 大约需要(n+1)次乘除法运算。例如，当n=10时约需 4×10?次运算，而用Gauss消元法只需30次乘法运算
2 1 ( 1) 2 2 n k n n n k = − + = − 3 3 2 3 3 3 n n n + − n 所以 Gauss 消元法总的乘除法次数为 n =10 如果我们用 法则计算(1.1)的解，要计算 个 阶行列式并作 次除法。 而计算每个行列式，若用 子式展开的方法，则有 次乘法，所以用 法则 大约需要 次乘除法运算。例如，当 时约需 次运算，而用 消元法只需 次乘法运算。 n! (n +1 !) 7 4 10 Gramer n +1 n Gramer Gauss n 430
例1方程组 [0.0003x+3.0000x2=2.0001 1.0000x1+1.0000x2=1.0000 (2) 的精确解为=-子在m消元法计算中取5位有效 2 数字。 解：方程 (①×(-1)10.0003+方程(2)得： 0.0003x+3.0000x2=2.0001 9999.0x2=6666.0 x=0.6667,代入方程(1)得x=0,由此得到的解完全失真， 如果交换两个方程的顺序，得到等价方程组 1.0000x+1.0000x2=1.0000 0.0003x1+3.0000x2=2.0001
1 2 1 2 0.0003 3.0000 2.0001 (1) 1.0000 1.0000 1.0000 (2) x x x x + = + = 例1 方程组 解： 方程 (1) ( 1)/ 0.0003 − + 方程(2)得： 1 2 2 0.0003 3.0000 2.0001 9999.0 6666.0 x x x + = = = x2 0.6667, 代入方程(1)得 x1 = 0, 由此得到的解完全失真， 如果交换两个方程的顺序，得到等价方程组 1 2 1 2 1.0000 1.0000 1.0000 0.0003 3.0000 2.0001 x x x x + = + = 的精确解为： 1 2 1 2 , , 3 3 x x = = 在 Gauss 消元法计算中取 5 位有效 数字
经Gauss 消元后有 1.0000x1+1.0000x2=1.0000 2.9997x2=1.9998 .x2=0.6667,x1=0.3333 由此可以看到，在有些情况下，调换方程组的次序对 方程组的解是有影响的，在消元法中抑制舍入误差的增长 是十分重要的
经 Gauss 消元后有 1 2 2 1.0000 1.0000 1.0000 2.9997 1.9998 x x x + = = = = x x 2 1 0.6667, 0.3333 由此可以看到，在有些情况下，调换方程组的次序对 方程组的解是有影响的，在消元法中抑制舍入误差的增长 是十分重要的