s2Gauss EliminationsloluteAx =blGaussordereliminationidea:Thegoal of forward elimination is to-transform the coefficientmatrix into anupper triangular matrixTwo steps:1.Forward Elimination2.Back SubstitutionAx= bForthis system oflinearequations:if det(A) O The elementary row transformation of the augmented matrix:a(1)6()ainaacbCrecorded?A=(A,b)(A(I)=........上页am)q()g(1)6(1)下页n2nnn返圆
上页 下页 返回 slolute Ax b = 1、Gauss order elimination idea: The goal of forward elimination is to transform the coefficient matrix into an upper triangular matrix 。 = §2 Gauss Elimination For this system of linear equations: Ax = b The elementary row transformation of the augmented matrix: 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 recorded = i f det(A) 0 Two steps: 1. Forward Elimination 2. Back Substitution
if a 0Elimination:(1)aliiDefinning line multiplier:i=2,3,..,nmi1row(i) - row(1) × m1, thus :a(2 = a" - mnal)i,j=2,3,..,nb(2) = b(1) - m,b(1)i= 2,3,..,nall爱..aL0福(A(1),b(1)) →(A(2),b(2)) =....·bSalq(2)0上页?nn下页返回
上页 下页 返回 = (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 0 (1) if a11 Definning line multiplier: i n a a m i i 2,3, , (1) 1 1 (1) 1 1 = = ( ) (1) , : 1 row i row m thus − i (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 Elimination:
if all) =O because det(A)±0Thus : there are more than one element that isnot O in the first colum of Aif al) + O,thus : exchange the first row's positon of(A(), b()with the ith row's position,then :e lim ination.aa(1)6(1))ain(2)(2)(2)bs0a22a2nand.··det(0)+0(2)6(2)(2)0aCn21nnso,after k -lth step,(A), b())will as follows :上页下页返圆
上页 下页 返回 0 ( 1 ) if a11 = because det(A) 0 not in the first colum of A Thus there are more than one element that is 0: ' , : lim . 0, : ' ( , ) 1 (1) (1) (1) 11 with the i t h row s position then e ination if ai thus exchange the first row s positon of A b (2) (2) (2) 2 (2) 2 (2) 2 (2) 2 2 ( 1 ) 1 ( 1 ) 1 ( 1 ) 1 2 ( 1 ) 1 1 00 n n n n nn a a b a a b a a a b and det( • ) 0 , 1 ,( , ) : (1) (1) so after k − t h step A b will as follows
allaa)aa)·(A(1),b(1)) →(A(k),b(k))(k)(k)Rqaknkk(k)(k)6(k)Definning line multiplier:Oanknnnai=k+l,...,nmik(k)aikdet() +0ith row - k thxmik,thus :(k+1)(k)(k)i,j=k+1,...,na-mikaij11i=k+1,..,n= b(*) - mxb(l)上页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 det(•) 0 Definning line multiplier: i k n a a m k kk k i k i k 1, , ( ) ( ) = = + ith row k th m ,thus: − i 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
Afterk =n -1 steps,(A,b()will as follows :q.(1+a12Oin11aa(A(1),b(1)) →(A(n),b(n)) :·b(n)q(n)nnnbecause : det(A) ± 0we can know: al ± Oi=1,2,.,nso,the upper triangular equationsA(n)x = b(n) has the unique soiution上页The solution of Ax = b is :下页返回
上页 下页 返回 = ( ) ( ) (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 1 ,( , ) : (1) (1) Afterk = n− steps A b will as follows ( , ) (n) (n) A b because : det(A) 0 we can know a i n i i i : 0 1,2, , ( ) = The solution of Ax = b is ： so the uppertriangular equationsA x b has the unique soiution (n) (n) , =