Gaussian elimination | Lecture 10 | Matrix Algebra for Engineers

so in this video we're going to do what is really the main algorithm of matrix algebra the algorithm that computers spend an awful lot of time working on and that's the algorithm for solving a system of linear equations because we're doing it by hand we're considering these small baby systems so this is three equations and three unknowns but on a computer you would be doing thousands of equations and thousands of unknowns and then you need a very efficient algorithm in order to do it quickly so that algorithm is called Gaussian elimination so I want to kind of step you through the algorithm in the video today so there are no matrices when we write down a system of equations but I think you've seen a little bit of this already but you know the main reason for matrices is to represent linear systems of equations so how do we do that so the first equation is the first row of the matrix so you take the coefficients minus 3 to minus 1 and then multiplies the unknown vehicle X 1 X 2 X 3 so this is why we define matrix multiplication the way that we did we have minus 3 X 1 plus 2 X 2 minus X 3 so that's equal to the right hand side which is minus 1 okay so the first equation is represented by the first row of the matrix and then the second equation becomes the second row 6 times X 1 minus 6 times X 2 plus 7 times X 3 equals minus 7 and the last equation becomes the third row 3 X 1 means 4 X 2 plus 4 X 3 equals minus 6 ok so the usefulness of matrices here we can represent this system by a matrix equation sometimes we just write this simply as a the matrix a times the vector X is equal to the right hand side B right ax equals B that's our equation okay so what is the Gaussian elimination algorithm I can tell you the first step and then explain to you the algorithm the first step is to form what's called the Augmented matrix Augmented matrix and that's our a matrix with the right-hand side be attached to the last column so that's the matrix minus 3 to minus 1 and then we attach minus 1 6 minus 6 7 and then we attach minus 7 and 3 minus 4 4 and we attach minus 6 so that's called the Augmented matrix ok now the idea is to do some operations on this matrix to make this system of linear equations easy to solve so what are we allowed to do so what are we allowed to do through the system of equations that doesn't change this solution we can change the order of the equations that's the same thing as changing the order of the rows of the matrix ok we can multiply any equation by a number by a constant that's the same as multiplying a row by a constant ok and then the last operation which is the most important operation is that we can multiply one of the equations by a constant and add it to another equation okay so for instance we can multiply the first both sides of the first equation by 2 and add it to the second equation so the left side to the left side the right side to the right side okay so that's what we're going to do we're going to take this matrix and then we're going to try to add rows by a constant and add it to rows underneath so that we will bring this matrix to upper triangular form at least the a part of this matrix we want to bring it to upper triangular if we do that the solution will be very easy okay so we have we start here this is called the pivot position so that's the pivot let me write it here that's the pivot okay and we have to eliminate all the numbers below the pivot so we want to get rid of the six right below the pivot to do that we can multiply the first row by two and add it to the second row and then the six will become 6 minus six which will give us a zero so let's do that so this matrix then goes into the first row minus 3 2 minus 1 minus 1 and then the second row we multiply the first row by 2 and add it to the second row so we get our 0 here right that's the point and then we have a 4 minus 6 is minus 2 and then we have minus 2 plus 7 is 5 and then we have minus 2 minus 7 is minus 9 okay so we got the number below the pivot is we got a 0 below the pivot and then the last row we also want to get a 0 below the pivot so we just add the first row to the last row will get us a 0 so we have 0 minus 3 plus 3 2 minus 4 is minus 2 minus 1 plus 4 is 3 and minus 1 minus 6 is minus 7 ok so we've used our pivot here our minus 3 to eliminate all the numbers below the pivot how we find the next pivot so the next pivot will be this number here because we're trying to get to upper triangular so we're trying to eliminate everything below this upper triangular matrix here so we need to eliminate this minus 2 down here so how do we do that we multiply the second row by minus 1 and add it to the third row so the first row stays the same that's the minus 3 2 minus 1 minus 1 the second row stays the same that's a 0 minus 2 5 minus 9 and then we multiply the second row by minus 1 and add it to the third row so we get 0 0 and then minus 5 plus 3 is minus 2 and then 9 minus 7 is 2 ok then we have our upper triangular matrix here right so let me sketch that out that's that's the upper triangular matrix so that's the goal of Gaussian elimination to do operations on this Augmented matrix to bring this a matrix to upper triangular form ok when we do that we have a system of equations now so we have each row represents one equation so let's write the equation so we have minus 3x 1 plus 2 X 2 minus X 3 equals minus 1 okay that's the same as our original equation the second equation the second equation now is minus 2 X 2 plus 5 X 3 equals minus 9 the third equation is minus 2 X 3 equals 2 ok so this is our upper triangular system the idea here is the solution of this system now is very fast compared to the solution of the original system so it's really you have to think computationally the idea here is that the computer can solve this very fast ok that means few operations to solve this system so you start at the bottom so the method of solution here is called back substitution ok because you start at the bottom substitution you start at the bottom and work your way forward so the bottom is X 3 equals minus 1 right and then the second equation we solve for X 2 so you can write it down immediately that X 2 you divide by minus 2 so minus 1/2 and you throw everything onto the right hand side so we have minus 5 X 3 minus 9 and then you substitute in the previous found solution so that's the beauty of back substitution is everything you need as you work your way up you already have so here we have X 3 equals minus 1 so we have plus 5 minus 9 is minus 4 divided by minus 2 - so the solution here is - okay finally the first equation we have X 1 and then we're dividing by -3 so minus 1 over 3 and then we're throwing everything to the right hand side let me do the order that we've solved so we have X 3 - 2 X 2 and then minus 1 at the end okay and then we plug in the numbers so X 3 is -1 X 2 is 2 so minus 1 minus 4 is minus 5 minus 1 is minus 6 minus 6 divided by minus 3 is 2 okay and that completes the solution we can write down the solution if we want so we have X 1 X 2 X 3 is equal 2 X 1 is 2 X 2 is 2 X 3 is minus 1 okay Gaussian elimination so you have a system of n equations and n unknowns supposed to be a unique solution you can write that system as ax equals B so here we say a will be an invertible matrix so the solution will be x equals a inverse b at least formally but it's much faster to actually solve using gaussian elimination you form an Augmented matrix so you take your a and you attach to it B as the last column then you do operations that are allowed with the goal of converting the Augmented matrix into an upper triangular matrix at least the a part of that matrix - upper triangular then when you end up with the upper triangular system of Asians it's very easy to solve you use back substitution you start with the last equation and work your way upwards and then you have all of the solutions as you keep going and then you find the solution okay a very very important algorithm for large-scale computation I'm Jeff jasanoff thanks for watching and I'll see you in the next video you

Channel: Jeffrey Chasnov

Views: 104,192

Rating: 4.8958097 out of 5

Keywords: gaussian elimination method, gauss elimination method, gauss elimination method matrices, gaussian elimination method matrices, how to do gaussian elimination, gauss jordan elimination, gauss elimination, system of linear equations, how to solve a system of linear equations, linear algebra, matrix algebra, gauss method, elimination matrices method, matrices elimination method, matrices gaussian elimination, gauss jordan elimination method

Id: RgnWMBpQPXk

Length: 13min 59sec (839 seconds)

Published: Mon Jul 09 2018