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) )b(b)xa(a...)xa(a)xa(akjNkNjN2k2j21k1j1+=++++++ (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 . 1Similarly, 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) row #k : : aN1x1 + … + aNNxN = bN (1.2.1-5) 2The 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 Ax = b , so we write the system as NNN2N1kN k2k1jN j2j11N1211a ... a a: :a ...a a: :a ...a a: :a ... a a=Nkj1Nkj1b:b:b:bx:x:x:x (1.2.1-6) After a row operation, we have the equivalent system A’x = b ’ +++NNN2N1kNjNk2j2k1 j1jN j2j11N1211a ... a a: :)a(ca ... )a(ca )a (ca: :a ...a aa ... a a+=Nkjj1Nkj1b : )b(cb: b : b x:x:x:x (1.2.1-7) 3Since 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, b ) = (1.2.1-8) 44443444421Matrix 1)(N x Nb a ... a:b a ... a:b a ... a:b a ... aN NN N1k kN k1j jNj111N11+ After our elementary row operation, the system is written as (A’, b ’) = (1.2.1-9) 4444444434444444421Matrix 1)(N x Nb a ... a:b(cb a(ca ... a(ca:b a ... a:b a ... aN NN N1)kj )kNjN )k1j1j jNj111N11++++ 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 Ax = b based opon a sequence of these row operations. 4We now present the standard approach to solving Ax = b , the Method of Gaussian Elimination. First, we start with the original augmented matrix (A, b ) of the system, (A, b ) = (1.2.1-10) N NNN3N2 N1k kN3332 k1j jN2322j111N131211b a ... a a a : : : : : : b a ... a a a : : : : : : b a ... a a a: : : : : : b a ... a a a 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 112121aaλ = (1.2.1-11) We now perform a row operation where we replace the 2nd row by the equation -λ(a2111x1 + a12x2 + … + a1NxN = b1) + (a21x1 + a22x2 + … + a2NxN = b2) )bλ(b)xaλ(a...)xaλ(a)xaλ(a1212N1N212N21221221112121−=−++−+− (1.2.1-12) We see that the coefficient multiplying x1 in this equation is )aλ(a112121− = a21 - 0aaaaa2121111121=−= (1.2.1-13) 5If 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)) = (1.2.1-14) −−−−NNNN3N2N133N33323112121N212N13212312212211N131211b a ... a a a: : : : : : b a ... a a a)bλ(b )aλ(a ... )aλ(a )aλ(a 0b a ... a a a 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 + x2 + x3 = 4 2x1 + x2 + 3x3 = 7 3x1 + x2 + 6x3 = 2 (1.2.1-15) The original augmented matrix for this system is (A, b ) = (1.2.1-16) 2 6 1 37 3 1 24 1 1 1 6Since a11 ≠0, we can define 112121aaλ = = 212= (1.2.1-17) We now perform the row operation (1.2.1-10) (1.2.1-14) to obtain (A(2,1), b (2,1)) = −−−−2 6 1 3 (2)(4)7 (2)(1)3 (2)(1)1 (2)(1)24 1 1 1 = (1.2.1-18) −−2 6 1 31 1 1 04 1 1 1 We now wish to continue this process to place a zero in the (3,1) position of the augmented matrix. If (1.2.1-19) 1212(2,1)21j212j(2,1)2jbλbb ,aλaa −=−= We write the augmented matrix following the first row operation as (A(2,1), b (2,1)) = (1.2.1-20) NNNN3N2N133N333231(2,1)2(2,1)2N(2,1)23(2,1)2211N131211b a ... a a
View Full Document
Unlocking...