第k步:设a≠0,计算因子l=-a)/a)(=k+1…,m 将增广矩阵的第i行+l×第k行,得到: lk 1k+1 In 0 (k) (k) (k) kk k.k+1 0 0 (k+1) (k+1) k+1) k+1 b (k+1) (k+1) n.k+1 n (k+1) (k) +. a 其中 (k+1) k b(k)+ b (k) ikk
0 ( ) k 第k步：设 a kk ，计算因子 ( ) ( ) / ( 1, ..., ) k k ik ik kk l a a i k n 将增广矩阵的第 i 行 + lik 第k行，得到： ( 1 ) ( ) ( ) ( 1 ) ( ) ( ) ( , 1, ..., ) k k k ij ij ik k j k k k i i ik k a a l a b b l b i j k n 其中 (1) (1) (1) (1) (1) 11 1 1, 1 1 1 1 ( ) ( ) ( ) ( ) , 1 ( 1) ( 1) ( 1) 1, 1 1, 1 1 ( 1) ( 1) ( ) , 1 0 0 0 0 0 k k n k k k k kk k k kn k k k k k k k k n k k k k k n k nn n n a a a a x b a a a x b a a x b a a x b
共进行n-1步,得到 ,(1) (1) (1) (1) 12 In (2) n (n 回代过程:x =ba o - x 丿=+1 定理:若A的所有顺序主子式均不为0,则高斯消 去法能顺序进行消元,得到唯一解
( ) ( ) / n nn n n n x b a ( 1, ..., 1) ( ) 1 ( ) ( ) i n a b a x x i ii n j i j i ij i i i 定理：若A的所有顺序主子式 均不为0，则高斯消 去法能顺序进行消元，得到唯一解。 回代过程： 共进行 n 1步，得到 ( ) ( 2 ) 2 (1 ) 1 2 1 ( ) ( 2 ) 2 ( 2 ) 22 (1 ) 1 (1 ) 12 (1 ) 11 . . . . . . . . . ... ... ... n n n n nn n n b b b x x x a a a a a a
运算量( Amount of Computation) (1)用克莱姆( Cramer)法则求解n阶线性方程组 Ol=1.2 每个行列式由n!项相加,而每项包含了n个因子 相乘,乘法运算次数为(n-1)n!次.蕌 仅考虑乘(除)法运算,计算解向量包括计算 n+1个行列式和n次除法运算,乘(除)法运算次 数N=(n+1)(n-1)n!+n 当n=8时,N=200,0000
Ø 运算量 （Amount of Computation） （1）用克莱姆（Cramer）法则求解n阶线性方程组 每个行列式由n!项相加，而每项包含了n个因子 相乘，乘法运算次数为(n-1)n !次. , 1, 2 , ..., i i D x i n D 仅考虑乘(除)法运算,计算解向量包括计算 n+1个行列式和n次除法运算,乘(除)法运算次 数N=(n+1)(n-1)n!+n. 当n=8时,N＝200，0000
(2)高斯消去法: 第1个消去步,计算11(i=2,3,…,n),有n-1次 除法运算.使a1;①变为a1;(2)以及使b;①变为b1(2) 有n(n-1)次乘法运算 第k个消去步,有n-k次除法运算、(n-k+1)(n-k)次 乘法运算 乘法运算总次数为: ∑k(k-1)=( k=1 除法运算总次数为:(n-1)+.+1n(n-1)/2
（2） 高斯消去法: 第1个消去步， 计算li1(i=2,3，…，n)， 有n-1次 除法运算. 使aij (1)变为 aij (2) 以及使bi (1)变为bi (2) 有n(n-1)次乘法运算. 第k个消去步，有n-k次除法运算、(n-k+1)(n-k)次 乘法运算. 乘法运算总次数为： 除法运算总次数为: (n-1)+…+1=n(n-1)/2 3 1 1 ( 1 3 n k k k ) ( n n)
回代过程的计算 除法运算次数为n次.乘法运算的总次数为 n+(n-1)+…+1=n(n-1)2次 > Gauss消去法 除法运算次数为:n(n-1)/2+n=n(n+1)/2, 乘法运算次数为:蕌 n(n-1)(n+1)/3+n(n-1)/2=n(n-1)(2n+5)/6, (n=30,为9890) 通常也说Gaus消去法的运算次数与n3同阶,记为0(n3)
回代过程的计算 除法运算次数为n次. 乘法运算的总次数为 n+(n-1)+…+1=n(n-1)/2次 Ø Gauss消去法 除法运算次数为:n(n-1)/2+n=n(n+1)/2， 乘法运算次数为: n(n-1)(n+1)/3+n(n-1)/2=n(n-1)(2n+5)/6， 通常也说Gauss消去法的运算次数与n 3同阶，记为O(n 3) (n 30,为9890)