Gaussian Elimination

1 Gaussian EliminationCarl Friedrich Gauss (1777-1855)German mathematician and scientist,contributed to number theory, statistics, algebra, analysis, differential geometry, geophysics, electrostatics,astronomy, optics24/45 Gaussian Elimination Method: This is aGEM of amethodto solve a system of linear that a system ofmlinear equations innunknownsx1,..,xnis of the forma11x1+a12x2+..+a1nxn=b1a21x1+a22x2+. .+a2nxn= ..am1x1+am2x2+..+amnxn=bmwhereaij(1 i m, 1 j n) andbi(1 i m)are known observation: Operations of three types onthese equations do not alter the solutions :1. Interchanging two Multiplying all the terms of an equation by a Adding to one equation a multiple of Elimination Method: This is aGEM of amethodto solve a system of linear that a system ofmlinear equations innunknownsx1.

2 ,xnis of the forma11x1+a12x2+..+a1nxn=b1a21x1+a22x2+. .+a2nxn= ..am1x1+am2x2+..+amnxn=bmwhereaij(1 i m, 1 j n) andbi(1 i m)are known observation: Operations of three types onthese equations do not alter the solutions :1. Interchanging two Multiplying all the terms of an equation by a Adding to one equation a multiple of Elimination Method: This is aGEM of amethodto solve a system of linear that a system ofmlinear equations innunknownsx1,..,xnis of the forma11x1+a12x2+..+a1nxn=b1a21x1+a22x2+. .+a2nxn= ..am1x1+am2x2+..+amnxn=bmwhereaij(1 i m, 1 j n) andbi(1 i m)are known observation: Operations of three types onthese equations do not alter the solutions :1.

3 Interchanging two Multiplying all the terms of an equation by a Adding to one equation a multiple of Elimination Method: This is aGEM of amethodto solve a system of linear that a system ofmlinear equations innunknownsx1,..,xnis of the forma11x1+a12x2+..+a1nxn=b1a21x1+a22x2+. .+a2nxn= ..am1x1+am2x2+..+amnxn=bmwhereaij(1 i m, 1 j n) andbi(1 i m)are known observation: Operations of three types onthese equations do not alter the solutions :1. Interchanging two Multiplying all the terms of an equation by a Adding to one equation a multiple of Elimination Method: This is aGEM of amethodto solve a system of linear that a system ofmlinear equations innunknownsx1.

4 ,xnis of the forma11x1+a12x2+..+a1nxn=b1a21x1+a22x2+. .+a2nxn= ..am1x1+am2x2+..+amnxn=bmwhereaij(1 i m, 1 j n) andbi(1 i m)are known observation: Operations of three types onthese equations do not alter the solutions :1. Interchanging two Multiplying all the terms of an equation by a Adding to one equation a multiple of Elimination Method: This is aGEM of amethodto solve a system of linear that a system ofmlinear equations innunknownsx1,..,xnis of the forma11x1+a12x2+..+a1nxn=b1a21x1+a22x2+. .+a2nxn= ..am1x1+am2x2+..+amnxn=bmwhereaij(1 i m, 1 j n) andbi(1 i m)are known observation: Operations of three types onthese equations do not alter the solutions :1.

5 Interchanging two Multiplying all the terms of an equation by a Adding to one equation a multiple of above system of linear equations can be writtenin matrix form as follows. = ( )or in short asAx=b, whereA= ,x= ,b= .Them nmatrixA= (aij)is called thecoefficientmatrixof the system. By asolutionof( )we meanany choice ofx1,x2,..,xnwhich satisfies all theequations in the eachbi=0, then the system is said to it is called aninhomogeneous above system of linear equations can be writtenin matrix form as follows. = ( )or in short asAx=b, whereA= ,x= ,b= .Them nmatrixA= (aij)is called thecoefficientmatrixof the system. By asolutionof( )we meanany choice ofx1,x2.

6 ,xnwhich satisfies all theequations in the eachbi=0, then the system is said to it is called aninhomogeneous above system of linear equations can be writtenin matrix form as follows. = ( )or in short asAx=b, whereA= ,x= ,b= .Them nmatrixA= (aij)is called thecoefficientmatrixof the system. By asolutionof( )we meanany choice ofx1,x2,..,xnwhich satisfies all theequations in the eachbi=0, then the system is said to it is called aninhomogeneous the known data in the system( )is captured in them (n+1)matrix(A|b) := .This is called theaugmented matrixfor the the above three operations on the equations inthe linear system correspond to the followingoperations on the rows of the augmented matrix:(i) interchanging two rows,(ii) multiply a row by a nonzero scalar,(iii) adding a multiple of one row to are calledelementary row Elimination Method consists of reducingthe augmented matrix to a simpler matrix from whichsolutions can be easily found.

7 This reduction is bymeans of elementary row the known data in the system( )is captured in them (n+1)matrix(A|b) := .This is called theaugmented matrixfor the the above three operations on the equations inthe linear system correspond to the followingoperations on the rows of the augmented matrix:(i) interchanging two rows,(ii) multiply a row by a nonzero scalar,(iii) adding a multiple of one row to are calledelementary row Elimination Method consists of reducingthe augmented matrix to a simpler matrix from whichsolutions can be easily found. This reduction is bymeans of elementary row the known data in the system( )is captured in them (n+1)matrix(A|b) :=.

8 This is called theaugmented matrixfor the the above three operations on the equations inthe linear system correspond to the followingoperations on the rows of the augmented matrix:(i) interchanging two rows,(ii) multiply a row by a nonzero scalar,(iii) adding a multiple of one row to are calledelementary row Elimination Method consists of reducingthe augmented matrix to a simpler matrix from whichsolutions can be easily found. This reduction is bymeans of elementary row 1(A system with a unique solution):x 2y+z=52x 5y+4z= 3x 4y+6z= augmented matrix for this system is the 3 4matrix 1 2 12 5 41 4 6 5 310 The elementary row operations mentioned above willbe performed on the rows of this augmented matrix,28/45 Example 1(A system with a unique solution):x 2y+z=52x 5y+4z= 3x 4y+6z= augmented matrix for this system is the 3 4matrix 1 2 12 5 41 4 6 5 310 The elementary row operations mentioned above willbe performed on the rows of this augmented matrix,28/45 First we add -2 times the first row to the second row.

9 Thenwe subtract the first row from the third , 1 2 10 1 20 2 5 5 135 The circled entry is the first nonzero entry in the firstrow and all the entries below this are 0. Such acircled entry is called a pivot. This next step is called sweeping a column. Here we repeat the process forthe smaller matrix:viz.( 1 2 2 5 135) (-1201 1331)Put back the rows and columns that has been cut outearlier:29/45 First we add -2 times the first row to the second row. Thenwe subtract the first row from the third , 1 2 10 1 20 2 5 5 135 The circled entry is the first nonzero entry in the firstrow and all the entries below this are 0. Such acircled entry is called a pivot.

10 This next step is called sweeping a column. Here we repeat the process forthe smaller matrix:viz.( 1 2 2 5 135) (-1201 1331)Put back the rows and columns that has been cut outearlier:29/45 First we add -2 times the first row to the second row. Thenwe subtract the first row from the third , 1 2 10 1 20 2 5 5 135 The circled entry is the first nonzero entry in the firstrow and all the entries below this are 0. Such acircled entry is called a pivot. This next step is called sweeping a column. Here we repeat the process forthe smaller matrix:viz.( 1 2 2 5 135) (-1201 1331)Put back the rows and columns that has been cut outearlier:29/45 First we add -2 times the first row to the second row.