Gauss Elimination and Back-Substitution

hello and welcome to MATLAB programming for numerical computations we are in week number four in this week we are covering linear equations well in lecture 4.2 we are going to cover one of the most popular method for solving linear equations which is known as Gauss elimination in today's lecture we are going to use what is known as the knife Gauss elimination technique okay so let us take an example in order to show how we are going to solve this problem this example is from the computational techniques video course module three part two the link for which is given over here okay so these are three equations in three unknowns the three unknowns are X 1 X 2 and X 3 together they form a vector which is a column vector containing three rows okay we will write this equation as ax equal to B where a matrix is going to be nothing but 1 1 1 2 1 3 3 4 minus 2 and our B vector is going to be 4 7 9 in the previous lecture we have seen that we can use MATLAB powerful linear algebra suite in order to find the solution X either using inverse of a multiplied by B or the backslash command or what we are going to do today is to use the Gauss elimination technique in order to solve this linear equation ok and let's say edit gauss Olymp the one that we are going to create in order to solve the problem using Gauss elimination let's go on and look at the problem our a is 1 1 1 2 1 3 let's write that down a is 1 1 1 2 1 2 1 3 and 3 4 minus 2 1 3 3 4 minus 2 our B matrix is nothing but let's go back and see four seven nine B is for semicolon seven semicolon nine okay let's save this run this we get a and B and our X is going to be nothing but a backslash B and that's our X which is one to one so that's the solution to our problem using matlab's backslash command okay what we want to do is to solve this problem using Gauss elimination so the first step and Gauss elimination is to create an Augmented matrix so let's go ahead and do that let's make the comments first solve a X equal to be naive Gauss elimination and Augmented matrix will be equal to a comma B and we'll end this with a semicolon okay let's go back okay now at each step a I I is the pivot element so first we will have a 1 1 as the pivot element then we will have a 2 2 as the pivot element and finally a 3 3 as a pivot element we don't have to do anything with a 3 3 mainly because a 3 3 8 or rather column row number 3 is the last row so let's actually do this a 1 1 as favorite element okay so we will have a set of computations with that we'll have a set of computations with a 2 comma 2 as pivot element and with a 3 comma 3 as pivot element in let us say Gauss elimination notice that when I've used two percentage signs this has formed a section in this particular goal okay we'll just put enter over here okay now we are ready to let's do the next steps so what's the step with AII as the pivot element so let's say a 1 1 as the pivot element we want to create zeros in the pivot column which means in column number one so column one over here is basically 2 1 3 so what we are going to do is we are going to subtract 2 times Row one from call a row number two so we need to use row operations you wrote to the new Row two is going to be Row two the old root 2 minus alpha times Row 1 where alpha is a 2 1 divided by a 1 1 a 2 1 which is 2 divided by a 1 1 which is 1 so that is going to give alpha as equal to 2 and Row 2 minus 2 times Row 1 is going to be our first step so let's do that in MATLAB saying alpha equal to a 2 comma 1 that is the second row first column divided by a 1 comma 1 ok let's go back and see that's exactly what we had alpha IJ is going to be equal to a ji / AI I so a 2 1 divided by a 1 1 and then a 3 1 divided by a 1 1 okay so that is going to be our alpha our road to equal to Rho 2 minus alpha times Row 1 okay this is not a correct way so how do we get the rope how are we going to get the row and that we are going to get the row of the a B matrix and the way we are going to do that let's actually copy/paste this and yeah so we have this a B matrix so how are we going to get row number two row number two of a B is nothing but rows 2 comma colon the entire row row number 2 will be extracted by this command this is what we get so this is going to be Row 2 what is Row 1 Row 1 is a b1 comma colon okay so what is alpha multiplied by Row 1 alpha multiplied by Row 1 is going to be nothing but 2 multiplied by a B 1 comma colon and when we do that that's exactly what we get so this is 2 multiplied by Row 1 what we want to do is Row 2 minus 2 multiplied by Row 1 and assign it to Row 2 so a B 2 comma colon is going to be equal to a B 2 comma colon which means Row 2 equal to Rho 2 minus alpha multiplied by Row 1 and Row 1 was a b1 comma colon right this is Row 1 which is exactly what I have written over here alpha value is 2 this is exactly what was written over here Row 2 is a b2 comma colon which is exactly what I have written over here and that expression is being assigned to a b2 comma colon so let me cut this go back over here and paste this so this is going to be nothing but Rho 2 minus alpha times Rho 1 okay and that's good with us next what we want to do is we want to repeat that with Row 3 as we have seen over here we use the pivot element to create zeroes in the entire pivot column entire column 1 we are going to use Row 1 in order to create 0 over here as well as 0 over here okay so we need to now repeat that for row number 2 and the way we are going to do that is nothing but alpha now is going to be a 3 comma 2 divided by a sorry 3 comma 1 divided by a 1 comma 1 note that only the row numbers change row number has changed from two to three and we change from two to three over here and minus alpha multiplied by a row number 1 so it's Row 3 equal to Row 3 minus alpha times Row 1 so that is all the computation required with a 1 1 as the pivot element and we are done over here so that's the first step now we need to repeat that for column number 2 so what now after at the end of this what we are going to get is we are going to get 1 1 1 this guy is going to be 0 this guy is going to be a modified number and so on and so forth this is again going to be 0 and these we are going to have some numbers let's do this let's save this just run it and see what value of a B we are getting and if we are getting any errors ok cool so we do not have any errors let's clear the screen and type a B ok so what we have done at the end of the first step is with the a1 1 as the pivot element we have obtained 0 in that pivot column in column number 1 in row 2 3 and so on we have obtained zeros over here ok so that is the first step now the second step is going to be to convert this as 0 using our - sorry a 2 2 as the pivot element we are going to use row operations with a 2 2 as the pivot element and let's go back to MATLAB and let us do that in this case now alpha is going to be something divided by a 2 comma 2 what's that something going to be that's going to be row number 3 right what we want to do what we want to do over here is we want to use Row 2 in order to get this guy equal to 0 so alpha is going to be this guy divided by this guy so this is a 3 of my 2 divided by a 2 comma 2 so this is a 3 sorry 3 comma 2 okay again keeping up with the equations that we had seen our minute before so that's the value of alpha over here and our value of a B 3 comma colon is going to be nothing but a B 3 comma colon minus alpha multiplied by a B now this time it's 2 comma colon why they cause our equation with a to 2 as the pivot element was our 3 minus alpha times R 2 okay so our 3 is this guy equal to R 3 minus alpha times R 2 and that is what we get over here so let's save this and run this and see what we get with our matrix Amy okay boots that is something wrong and let's go back and check what exactly did we do wrong okay alpha is going to be equal to a I am sorry this is a problem I should be using a B over here and not a okay it's a shift we are everything I need to change right and alpha over here also has to be Amy because we are working with the Augmented matrix okay because this is on the lower triangular form we don't really need to do anything with the pivot element a 3 3 so oops yeah let me go over here and delete this part with pivot element and this is the end of our Gauss elimination we are done with Gauss elimination over here why did we take just two steps because we had a three by three matrix okay next step is going to be back substitution okay now yes with respect to back substitution what we do is we have our last equation as if we go back to MATLAB and check this our last equation is minus 4 X 3 equal to minus 4 so X 3 is just going to be this guy divided by this guy ok so our X 3 is going to be equal to 1 okay then we go on to the second last equation second last equation is minus 1 X 2 plus 1 multiplied by X 3 equal to minus 1 we take this on to the right hand side and divide by a to 2 and that is going to be our solution for X 2 and then we use X 2 and X 3 in order to find X 1 that's the procedure that we are going to use so let's do that so we are going to do X so X initial is our solution okay so our X 3 is going to be nothing but a B and sorry maybe 3 comma n which is the last n basically means the last column and third row so a B 3 comma n divided by a B 3 comma 3 that's the value of x 3 right again what we get with respect to X 3 is a B 3 comma 3 is the denominator and a B 3 comma N is the numerator a B 3 comma end is the numerator and a B 3 comma 3 is the denominator that is our X 3 or X 2 is going to be nothing but a b2 comma end right a B Row 2 and last column so a b2 comma n minus a B 2 comma 3 x x3 okay that is going to be the numerator so we will put the numerator and brackets okay divided by T 2 comma 2 that is going to be our X 2 and our X 1 it is going to be let's just copy this and we'll have to change from 2 to 1 everywhere and everything else remains the same so 1 comma end minus a B 2 comma 3 multiplied by X 3 will change to a B 1 comma 3 multiplied by X 3 and we will to this we're gonna add a B 1 comma 2 multiplied by X 2 1 comma 2 multiplied by X 2 ok so let's see what we have done what we have done over here is the first guy X 1 is going to be a B 1 comma n minus a B 1 comma 3 multiplied by X 3 minus a B 1 comma 2 multiplied by X 2 and that's really what we have learned over here in our MATLAB okay and that will give us the solution once I change the denominator also keep in mind that I have an inner bracket over here and then router bracket over here okay save this we run this and we check whether the solutions are met or not our value of x is 1 - 1 which was the same as a backslash so our Gauss elimination is working to the way we desired to work okay now let's spend some time in order to make this better what you want be mean by this is that MATLAB has a very powerful linear algebra set of tools and we don't really need to write this in the way we have written it right now what we need to do is we need to put it in a loop okay so first of all let's look at this equation okay let me copy this the numerator that was in the bracket and paste it over here we just put some spaces so that it becomes a little bit easy for us check ok so we have a b1 comma end - bunch of things ok let's keep a b1 command on its own we don't have to worry about that part let's look at the thing that was there in the brackets that was a B 1 comma 3 multiplied by X 3 plus a B 1 comma 2 multiply by x2 so if I were to write a B 1 comma 2 2 3 what I'm going to get is the two guys so a B 1 comma 2 and a B 1 comma 3 okay if I write x 2 : 3 I'm going to get now a vector which is a column vector and if I multiply these two what I am going to get is a B 1 comma 2 multiplied by X 2 plus a B 1 comma 3 multiplied by X 3 which is exactly what we had over here okay so let me just multiply this guy with this guy okay and that is going to be B 1 comma 2 2 3 multiplied by X 2 2 3 and we want to check whether the result is same as the sky that is whether the result is equal to 3 or not so let me press ENTER and we actually find yes that's absolutely what we get so let me go over here and I'm going to change thing in the bracket to what we had written in the command prompt in the command from what we had written is this copy it and paste it over here okay and that is going to be our value of x 1 okay now if that is value of x 1 this is you if you see it's 1 plus 2 2 3 okay so we will just write it as sorry 1 plus 1 okay ah 2 n and we will go up and we will write n equal to 3 we have three equations so why we write it over here we will actually take this and put it right at the top okay so 1 plus 1 2 n + 1 plus 1 2 n K divided by a B 1 comma 1 likewise what we are going to do is a be 2 comma 2 plus 1 2 n multiplied by a be 2 plus 1/2 okay why we are writing it in this way because now we have this X going from 3 to 3 and that is good enough for us ok let's put this in a loop for I equal to 2 by point two in step of minus 1 to 1 and n right and this is going to be I okay I have replacing two with eyes over here okay everywhere there where there is two and replacing it with lye okay same thing I'm going to do over here but everywhere there is one I am going to replace that with diet okay now you compare these two what we will see is that these two expressions are exactly the same that's how we write that leaves results in a loop okay as a matter of fact if we were to do this for X 3 what we are going to get is a B 3 comma and minus a B 3 comma 3 plus 1 4 2 3 & 4 to 3 is null so 4 2 3 is going to be nothing so it's going to be just a B - nothing divided by a B 3 comma 3 so I will delete this and I will change this to you and loss LM ok and we see our X is exactly the same as we got earlier with that we come to the end of lecture 4.2 and I will see you in the next lecture thanks and bye

Channel: MATLAB Programming for Numerical Computation

Views: 57,591

Rating: 4.9175258 out of 5

Keywords: Lec, Gauss, Elimination, and, BackSubstitution

Id: JY99xfMgwnk

Length: 21min 38sec (1298 seconds)

Published: Mon Feb 01 2016