1 2 1 Reduction of A x b to triangular form by Gaussian Elimination We now with to develop an automatic procedure an algorith for obtaining a solution to the set of N linear algebraic equations a11x1 a12x2 a1nxn b1 a21x1 a22x2 a2nxn b2 an1x1 an2x2 annxn bn 1 2 1 1 Note that we can select any two rows say j and k and add the two equations to obtain another one that is equally valid aj1x1 aj2x2 ajNxN bN ak1x1 ak2x2 akNxN bk a j1 a k1 x 1 a j2 a k2 x 2 a jN a kN x N b j b k 1 2 1 2 If the equation for row j is satisfied and the equation obtained by summing rows j and k 1 2 1 2 is satisfied then it automatically follows that the equation of row k must be satisfied We are therefore free to replace in our system of equations the equation ak1x1 ak2x2 akNxN bk by aj1 ak1 x1 aj2 ak2 x2 ajN akN xN bj bk with no effect on the solution x 1 Similarly we can take any row say j multiply it by a non zero scalar c to obtain an equation caj1x1 caj2x2 cajNxN cbj 1 2 1 3 that we can substitute for the original without effecting the solution In general for the linear system a11x1 a12x2 a1NxN b1 aj1x1 aj2x2 ajNxN bj row j ak1x1 ak2x2 akNxN bk row k aN1x1 aN2x2 aNNxN bN We can choose any j 1 N k 1 N and any scalar c 0 to form the following linear system with exactly the same solution as 1 2 1 4 a11x1 a1NxN b1 aj1x1 ajNxN bj row j caj1 ak1 x1 cajN akN xN cbj bk aN1x1 aNNxN bN 1 2 1 5 2 row k The process of converting 1 2 1 4 into the equivalent system 1 2 1 5 is known as an elementary row operation We develop in this section an algorithm for solving a system of linear equations by performing a sequence of these elementary row operations until the system is of a form that is easy to solve We will wish to use matrix vector notation A x b so we write the system as a 11 a j1 a k1 a N1 a 1N a j2 a jN a k2 a kN a N2 a NN a 12 x 1 b1 x j b j x b k k x b N N 1 2 1 6 After a row operation we have the equivalent system A x b a 11 a j1 ca j1 a k1 a N1 a j2 a jN ca j2 a k2 ca jN a kN a N2 a NN a 12 a 1N 3 x 1 b1 x j b j x cb b k k j x N bN 1 2 1 7 Since we must change both A and b for every elementary row operation it is common to perform these operations on the augmented matrix A b a 11 a 1N b1 a j1 a jN b j A b a a kN b k k1 a a NN b N N1 14 44 424444 3 N x N 1 Matrix 1 2 1 8 After our elementary row operation the system is written as a 1N b1 a 11 a j1 a jN bj A b ca a ca a cb b k1 jN kN j k j1 a N1 a NN bN 1 44444444244444444 3 N x N 1 Matrix 1 2 1 9 By applying the elementary row operation to the augmented matrix we automatically change both the left and right hand sides of A x b as needed to ensure that the solution x does not change We will now build a systematic approach to solving A x b based opon a sequence of these row operations 4 We now present the standard approach to solving A x b the Method of Gaussian Elimination First we start with the original augmented matrix A b of the system a 11 a 12 a 13 a j1 a 22 a 23 A b a a 32 a 33 k1 a N1 a N2 a N3 a jN b j a kN b k a NN b N a 1N b1 1 2 1 10 As long as a11 0 in section 1 2 3 we show how we can ensure that this is the case for systems with a unique solution we can define the finite scalar a 21 21 1 2 1 11 a 11 We now perform a row operation where we replace the 2nd row by the equation 21 a11x1 a12x2 a1NxN b1 a21x1 a22x2 a2NxN b2 a 21 21a 11 x 1 a 22 21a 12 x 2 a 2N 21a 1N x N b 2 21 b1 1 2 1 12 We see that the coefficient multiplying x1 in this equation is a a 21 21a 11 a21 21 a 11 a 21 a 21 0 a 11 5 1 2 1 13 If we write the augmented matrix obtained from this row operation to place a zero in the 2 1 position row 2 column 1 as A 2 1 b 2 1 a 12 a 11 0 a 22 21a 12 a 31 a 32 a N1 a N2 a 13 a 23 21a 13 a 1N b 2 21 b1 1 2 1 14 b3 bN b1 a 2N 21a 1N a 33 a 3N a N3 a NN Again the important point is that the linear system A 2 1 x b has the same solution x as the original system A x b As we develop this method let us consider a particular system for example the set of equations x1 x 2 x 3 4 2x1 x2 3x3 7 3x1 x2 6x3 2 The original augmented matrix for this system is 1 1 1 4 A b 2 1 3 7 3 1 6 2 1 2 1 16 6 1 2 1 15 Since a11 0 we can define 21 a 21 2 2 a 11 1 We now perform the row operation 1 2 1 10 2 1 A b 1 2 2 1 3 1 2 1 1 0 3 1 1 1 1 1 6 1 2 1 14 to obtain 1 1 2 1 1 4 1 2 1 2 1 17 7 2 4 2 4 3 2 1 6 1 2 1 18 We now wish to continue this process to place a zero in the 3 1 position of the augmented matrix If a 2 1 a 2j 21a 1j b 2 1 b 2 21 b1 1 2 1 19 2j 2 We write the augmented matrix following the first row operation as A 2 1 b 2 1 a 12 a 11 a 2 1 22 0 a 31 a 32 a a N2 N1 a 13 a 2 1 23 a 1N 2 1 2N a a 33 a 3N a N3 7 a NN b1 b 2 1 …
View Full Document
Unlocking...