消元法 ■上三角方程组 41X1+412X2+.+4nXn=b 4222+.+2nn=b2 →X= j=i+1 -,i=n,n-1,1 ui unnxn =bn 时间复杂度：O(n2) 下三角方程组 1 =b 12X1+122X2 =b2 b- =: →X= -,i=1,2,.,n mx+In2x2++lmxn=bn 时间复杂度：O(n2) 7
消元法 上三角方程组 时间复杂度： 下三角方程组 时间复杂度： 7 11 1 12 2 1 1 22 2 2 2 1 , , 1, ,1 n n n i ij j n n j i i ii nn n n ux ux ux b b ux ux ux b x i nn u ux b = + + ++ = − + + = ⇒= = − = = ∑ 2 O n( ) 1 11 1 1 21 1 22 2 2 1 11 2 2 , 1,2, , i i ij j j i ii n n nn n n l x b b lx lx lx b x in l lx lx lx b − = = − + = ⇒= = = + ++ = ∑ 2 O n( )
消元法 ■ 初等变换： ●交换矩阵的两行 ●某一行乘以一个非零数 ·某一个乘以一个非零数，加到另一行 ■ Gauss随元法：先将矩阵化为上/下三角矩阵，再回代 求解 a12 13 n b 412 b 0 b52 d21 a22 a2n [初等变接) 0 0 6g an an2 . 0 0 0 b 8
消元法 初等变换： 交换矩阵的两行 某一行乘以一个非零数 某一个乘以一个非零数，加到另一行 Gauss消元法：先将矩阵化为上/下三角矩阵，再回代 求解 8 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 ( ) ( ) (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 n n n nn n n n a b a a b a a a b a a a a b 初等变换
消元法 第一步：第1行x01+第i行，i=2,3,n a 412 . b a 412 b a21 a22 a2n b2 0 a品 . a b) 初等变换 : . an2 . b 0 a . a 运算量：(n-1)*(1+n) 9
消元法 第一步：第 行 第 行， 运算量： 9 1 11 i a a − 1 × + i i n = 2,3, , 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 n − + 1*1 ) ( )
消元法 (2) 第二步：第2行×二+第i行，i=3,4,n a a12 a13 b b 11 品 a 0 b2) a品 a 0 初等变换〉 0 0 a bs 0 a品 . 0 0 a a b 运算量：（n-2)*(1+n-1)=(n-2)n 10
消元法 第二步：第 行 第 行， 运算量： 10 (2) 2 (2) 22 i a a − 2 × + i i n = 3,4, , (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 n nn -2 * 1 -1 -2 ) ( + =) ( )
消元法 ■类似的做下去，第k步： 第k行×需+第ī行，1=k+,.,n (K) 运算量： (nk*Hmk+1)=(n k)(n k 2) ◆ n-1步运算之后 411 a13 ain b 0 品 . a b 0 0 d . 0 0 0 总运算量： 2=③n-k+2)+(m+/2=” +n2- =0(n3) 3 3 11
消元法 类似的做下去，第 步： 第 行 第 行， 运算量： 步运算之后 总运算量： 11 k k ( ) ( )k ikk kk aa− × + i ik n = +1, , ( ) *(1 1) ( )( 2) nk nk nknk －＋－＋－－＋ = 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 n n n nnnnn 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 On −=∑ − −+ + + = + − =