消元法 第一步：第1行x01+第i行，i=2,3,n an a12 n b ar d12 b 2) 21 a22 … 0 初等变换) 022 a …: an an2 0 a … a 运算量：(n-1)*(1+n) 6
¡ 第一步：第 行 第 行， 运算量： 6 1 11 i a a 1 i i 2,3,,n n n nn n n n a a a b a a a b a a a b 1 2 21 22 2 2 11 12 1 1 (2) (2) (2) 2 (2) 2 (2) 2 (2) 22 11 12 1 1 0 0 n nn n n n a a b a a b a a a b 初等变换 n 1 *1 n
消元法 第二步：第2行×+第1行，i=3.4n (2) b an 412 a13 a11 a 0 … a bg2 0 a品 a 6g2 初等变换 0 0 a bs ... .; 0 a a 0 0 … a b3) 运算量：(n-2)*(1+n-1)=(n-2)n 7
¡ 第二步：第 行 第 行， 运算量： 7 (2) 2 (2) 22 i a a 2 i i 3,4,,n (3) (3) (3) 3 (3) 3 (3) 3 (3) 33 (2) 2 (2) 2 (2) 23 (2) 22 11 12 13 1 1 0 0 0 0 0 n nn n n n n a a b a a b a a a b a a a a b (2) (2) (2) 2 (2) 2 (2) 2 (2) 22 11 12 1 1 0 0 n nn n n n a a b a a b a a a b 初等变换 n - 2 *1 n -1 n - 2 n
消元法 ■类似的做下去，第k步： 第行×验+第：行，i=十1，，” (k) ■ 运算量： (n-k)*(1+n-k+1)=(n-k)(n-k+2) ◆ n-1步运算之后 411 12 a13 b 0 a 2 0 0 0 0 0 B() 总运算量： n-kn-k+2）+(m+1)）n/2=T+i-1=07) n-1 k=1 3 3 8
¡ 类似的做下去，第 步： 第 行 第 行， ¡ 运算量： ¡ 步运算之后 ¡ 总运算量： 8 k k ( ) ( )kikkkk aa i i k 1,,n (n－k) *(1＋n－k＋1) (n－k)(n－k＋2) n 1 ( ) ( ) (3) 3 (3) 3 (3) 33 (2) 2 (2) 2 (2) 23 (2) 22 11 12 13 1 1 0 0 0 0 0 0 nn nnnnnn a b a a b a a a b a a a a b 1 3 2 3 1 ( )( 2) 1 / 2 ( ) 3 3 nk n n n k n k n n n O n
消元法 ■ Gauss消元算法 Algorithm 9 Gaussian Elimination Algorithm Input: n,(a,(b) 1:for k 1 to n-1 do 2:for i=k+1 to n do 3: 之←-aik/akk 4: ak←0： 6 for j=k+1 to n do 6: ai)←aij-2akj; end for 8: b:←b,-zbk 9: end for 10:end for 11:for i=n to 1 step-1 do 12::←(：-∑=i+1ax)/a 13:end for Output: (c) 9
¡ Gauss消元算法 9