2-1高斯( Gauss)消去法 消元过程 对线性方程组Ax=b如果det(4)≠0 对其增广矩阵施行行初等变换: 4=(4)=(4)0)2
2-1高斯（Gauss）消去法 一、消元过程 A = (A,b) = (1) (1) (1) 2 (1) 1 (1) 2 (1) 2 (1) 2 2 (1) 2 1 (1) 1 (1) 1 (1) 1 2 (1) 1 1 n n n n n n n a a a b a a a b a a a b ( , ) (1) (1) A b 记 = 对线性方程组 Ax = b 对其增广矩阵施行行初等变换: 如果det(A) 0
假定a(1)≠0 定义行乘数 1 11 第i行-第1行×m1,则 2) J (1) 0 2) (4①),b()一(4(2,b2) 22 0 2 (2)n1(2) n2 nn
0 (1) 假定 a11 定义行乘数 i n a a m i i 2,3, , (1) 1 1 (1) 1 1 = = = (2) (2) (2) 2 (2) 2 (2) 2 (2) 2 2 (1) 1 (1) 1 (1) 1 2 (1) 1 1 0 0 n n n n n n a a b a a b a a a b ( , ) (2) (2) A b 第i行−第1行mi1 ,则 (1) 1 1 (2) (1) aij = aij −mi a j (1) 1 1 (2) (1) bi = bi − mi b i, j = 2,3, ,n i = 2,3, ,n ( , ) (1) (1) A b
如果 0由于det(4)≠0 则A的第一列中至少有一个元素不为零 如a≠0,则将(,b)的第一行与第 交换后消元 11 12 (1( 1n2 0 n (2) (2)p(2) 2 因此第k-1步后(4①),b()将化为
0 (1) 如果 a11 = 由于 det(A) 0 则 A的第一列中至少有一个元素不为零 交换后消元 如 ai ( 1 1 1 ) 0,则将(A (1) ,b (1) )的第一行与第i 1 行 (2) (2) (2) 2 (2) 2 (2) 2 (2) 2 2 (1) 1 (1) 1 (1) 1 2 (1) 1 1 0 0 n n n n n n a a b a a b a a a b 且 因此,第k − 1步后,(A (1) ,b (1) )将化为
(4①),b() 2) 2)1(2) 22 2n (k) (4,b) (k) (k) nk nn ik i=k+1,… 第i行-第行×m,则 k k+1 (k+1) b =k+1
= ( ) ( ) ( ) ( ) ( ) ( ) (2) 2 (2) 2 (2) 2 2 (1) 1 (1) 1 (1) 1 2 (1) 1 1 k n k n n k n k k k k kn k kk n n a a b a a b a a b a a a b ( , ) (k ) (k ) A b ( , ) (1) (1) A b i k n a a m k kk k i k i k 1, , ( ) ( ) = = + 第i行−第k行mi k ,则 ( 1) ( ) (k ) ik kj k ij k aij = a −m a + ( 1) ( ) (k ) i k k k i k bi = b − m b + i, j = k + 1, , n i = k + 1, ,n
当经过k=n-1步后(A,b0)将化为 2 (4①),b()→(4m,b0) 2 2n 由于de(4)≠0 可知a≠0 因此,上三角形方程组A)x=b()有唯一解
( , ) (n) (n) A b = ( ) ( ) (2) 2 (2) 2 (2) 2 2 (1) 1 (1) 1 (1) 1 2 (1) 1 1 n n n n n n n a b a a b a a a b ( , ) (1) (1) A b 当经过k = n −1步后,(A (1) ,b (1) )将化为 由于 det(A) 0 a i n i i i 0 1,2, , 可知 ( ) = 因此,上三角形方程组 A (n) x = b (n) 有唯一解
二、回代过程 由于a≠0i=1,2,…,n b、n 所以 a.x j=i+1 1 因此得到线性方程组Ax=b的解
二、回代过程 ( ) ( ) n nn n n n a b x = i = n −1,n − 2, ,2,1 ( ) 1 ( ) ( ) i i i n j i j i i j i i i a b a x x = + − = a i n i i i 0 1,2, , 由于 ( ) = 因此得到线性方程组 Ax = b的解 所以
高斯消去法的计算量 作第步消元时乘法次数:(m-k)(mn-k+1)次 除法次数:(n-k)次 作第k步消元乘除法运算总次数为 (n-k)(n-k+2)次 完成全部n-1步消元需作乘除法运算总次数为 ∑(n-k)(n-k+2) k=1
三、高斯消去法的计算量 作第k步消元时 乘法次数： (n − k)(n − k + 1)次 除法次数： (n − k)次 作第k步消元乘除法运算总次数为 (n − k)(n − k + 2)次 完成全部n − 1步消元需作乘除法运算总次数为 − = − − + 1 1 ( )( 2) n k n k n k
全部回代过程需作乘除法的总次数为 2 ∑(n-+1) 22 于是 Gauss消去法的乘除法运算总的次数为 2 12 MD n +O(n2) 3 33 3 当n很大时MD n 3 3
于是Gauss消去法的乘除法运算总的次数为 MD 3 3 2 3 n n n = + − ( ) 3 2 3 O n n = + 当n很大时 3 3 2 3 n n n MD = + − 3 3 n 全部回代过程需作乘除法的总次数为 = − + n i n i 1 ( 1) 2 2 2 n n = +
四、高斯消去算法 输入: 方程组的阶数m;增广矩阵[A4b的元素an1≤i≤n1≤j≤n+1 输出 方程组的觚x1,ⅹ2…,x或方法失败的信息 步骤 S1对k=1,2,,n-1做S11~S12 s11若ak=0.,则输出方法失败的信息;停机 S12 对i=k+1 置 ik kk 2 对j=k+1,n+1
四、高斯消去算法 输入： 输出 步骤 方程组的阶数n；增广矩阵A,b的元素ai j ,1 i n,1 j n +1 方程组的解x1 ,x2 , ,xn或方法失败的信息 S1 对 k=1,2,…,n-1 做 S11~S12 S11 若 = 0,则输出方法失败的信息；停机. akk S12 . 1,..., 1 / ; 1,..., ij ij ik kj ik ik kk a a a a j k n a a a i k n = − = + + = = + 置 对 置 对
S2若a,=0,则输出方法失败的信息;停机 S3置xn=an+1 对i=n-1,n-2 i,n+1 置 J=1 s4输出(x1,x2灬,xn)停机
S2 若 = 0,则输出方法失败的信息；停机. an n S3 i i n j i i n i j j in n n n n a a a x xi n n x a a − == − − = = + ++ 1 , 1 , 1 1, 2,..., 1 / ; 置对置 S4 ( , ,..., ); . 输出 x1 x2 xn 停机