Watch these five (5) videos in order. The total video time is 26 min. Be sure to test your knowledge with the knowledge checks after each video.
Description: This video introduces the general format for a system of linear equations and discusses the matrix notation.
Hello, this is video SOE|VL|01 and is an introduction to solving systems of equations.
Let's first look at an introduction to systems of equations. An example of system of equations is two equations and two unknowns, which is 2x – 5y = 1 and x + 3y= 6. In engineering, there could be actually numerous equations with a unique solution. For example, this set of three equations here, 10x1 + 4x2 + 10x3= 47, -5x1 – 7x2 + 3x3 = -10, and -10x1 – 8x2 + 9x3 = 1. It could be a small set of equations, or it can be large set of up to thousands of x, for example, computational fluid dynamics. What's most important to know is that the number of equations must equal to the number of unknowns.
Here is look at generalized equations. We have n equations that have multiple unknowns in it. And we have the coefficients starting with the letter a that are tied to the unknowns, x. And on the right-hand side of the equations, we have our constant values b. And so in the first equation, a11x1 means that the constant a11 is for equation 1, variable 1, and so forth. General equations can be placed into a matrix form. That is [A] times [X] is equal to [B]. [A] is equal to all the coefficients of your variables, a11, a21, etc., down to ann. For this notation, the a11 means a row 1, column 1, a21would be row 2, column 1, ann would be a row n and column n. Similarly, x would be all the unknowns that you're looking for, x1, x2, etc., down to xn. And b's are the constants that are not changing, b1, b2 down to bn. Systems of equations can be both linear or non-linear. Take for example, these sets of three equations. It may appear that these sets of equations are non-linear because it has terms such as e^x2 and sinx3. However, what you'll notice is that each of the variables x1, x2, and x3, could be expressed independently. And all we need to do here is actually rename variables. So, we can say z2 = e^x2 and z3 = sinx3. Then we can plug those back into the equations and we get more of a linear term, which is 3x1 + 2z2 +0z3 = pi, 2x1 + 0z2 + 4z3 = 4.4, 0x1 +9z2 + 5z3 = 3. And this can be taken easily and put into a matrix form as follows. Taking all the coefficients and the unknowns and equal equating it to the constants.
These two equations, however, 3x1 +x12x2 = 1, and x22 -17x1x2 = 0, are a set of non-linear equations as x1 and x2cannot be separated independently. So, to make it a set of non-linear equations, there needs to be just at least one equation that is non-linear. And then the whole system becomes a system of non-linear equations. The majority of the videos following, focus on solving systems of linear equations, except for the last set of Newton-Raphson method shown at the end.
This concludes the video. This project could not have been completed without the support of eCampus Ontario and the University of Ottawa.
Description: This video discusses using the Naïve Gauss Elimination method to solve a linear system of equations.
Hello, this is video SOE|VL|02 and is the theory of Naïve Gauss Elimination for solving systems of equations.
Let's first discuss the general theory. Naïve Gauss Elimination is complete by two steps, the first is forward elimination. In this step and unknowns are systematically removed from equations by subtracting scaled values of equations from each other. This is done until an upper triangular matrix is formed in and last equation only has one unknown. This can be seen in the reduced matrix below right where zeros are in the lower triangular matrix. And the last equation has a33’’ = b3’’. The second step is backward substitution. With the last equation having only one unknown, it can be easily solved for and then you continue solving it for each variable until you solve for x1. Forward elimination is the process of making that upper triangular matrix. Take for example, this matrix here of A and B. What we'll do is we'll apply some row manipulation to be able to remove it and get the upper triangular matrix shown on the right. We can do this first by finding R2a, which will be equal to R2 –(a21/a11)R1. And what that will do is it was make it so that the first column, second row, that value will go to 0. We can do something very similar with R3a, which will be equal to R3 – (a31/a11)R1. In this case here, the R's represent the rows.
Let's look at a quick example here. We're going to start with the first column. What we want to do this first column is in rows 2 and 3, we want them to become 0 by using Row 1. We can do that by taking 6 which this case here is at a11and also known as the pivot point and converting that into a 3 and also converting it into a 5. We do that with R2a =R2- (3/6)R1. And that will be for Row 2 and Row 3 would be R3a = R3 - (5/6)R1. If we do it properly, what will happen is we will have zeros in that first column for rows 2and 3 and R1 stays the same. Now that we've done that, we're going to move in one column. And so our pivot is now in Column 2. And what we want to do here is we want to make row 3 in that second column becomes 0. Instead of using Row 1, we'll use the Row 2 pivot point here as a22. We need to convert -3/2 to become -7/6. We do the same thing as before. We have R3b = R3a –((-7/6)/(-3/2))R2a. If we do that, this is the matrix that will be formed. And you'll notice it's become a tridiagonal matrix, triangular matrix. And this gives us the answer that we're looking for.
We can move on to the next step. The next step is the backward substitution. There are some general formulas that you can use. The first one is defined for xn and xn = bn after certain number of elimination steps divided by ann after certain number of elimination steps. Once you have that value, you can move forward and find the other values by using that x. You'll notice in this equation here, xi is equal to bi - summation aijxj all divided by aii. You'll notice that j is present and the summation series will grow the more xi’s that you have for the next value. When i = n-1, you'll only have one x that you'll be able to use. Let's look at the example from before. What you can do is take this matrix and convert it back into equations. And you'll see that the bottom one is easiest to solve to start with. So we can go and we can go backwards and solve for x3, then x2 and then x1 to get our final answer.
So Naïve Gauss Gauss Elimination is actually considered naïve for a few reasons. One is that when you're normalizing and converting it, if there's a 0 and you divide by 0, then the whole system will fail. Also, as you are genuinely changing the values through elimination, you can get significant round-off error depending on how large the system is. If you have an ill-conditioned or singular systems, in this case here where the similar equations are very, very similar, Naïve Gauss Elimination could fail as well.
Let's see another example of an elimination. Here we have three equations and three unknowns. The first column we can reduce the values in rows 2 and 3 to 0 with the following equations. The problem is at the same time. If you look what happens in the second column, second row, we get a 0. If we're using this as our pivot point, it won't work as we try to do our equation, R3b = R3a – 23/3 divided by 0. It will crash and we will not succeed and therefore will have to modify Gauss Elimination to be able to handle for these situations.
You may be familiar with the Gauss-Jordan elimination method for solving systems of equations. Take for example this matrix here we can do elimination and scaling so that the A matrix becomes identity matrix and the B matrix are the final answers. This differs from the Gauss elimination method, where we will only do the upper triangular matrix and then use back substitution to solve for the x-values needed. Now it may seem that the Gauss-Jordan Elimination is a better method. However, it actually takes more computational steps to complete and therefore longer and so Gauss Elimination is more effective.
This concludes the video. This project could not have been completed without the support of eCampus Ontario and the University of Ottawa.
Description: This video implements the theory of Naïve Gauss Elimination in a practice problem in a step-by-step approach.
Hello, this is video, SOE|VL|03 and is a step-by-step example of using Naïve Gauss elimination to solve a system of equations.
First, let's look at the problem. Solve the following sets of equation using Naive Gauss elimination. There are four equations and four unknowns, x1, x2, x3, and x4. The equations are as follows: The first equation is -2x1 - 5x2 +7x3 + 4x4 =6.02. The second equation is 6x1 + x2 - x3 + x4 = 26.49. The third equation is -5x2 +2x3 - x4 = -23.08. The final equation is 8x1 + x3 + 6x4 = 46.51. We can now take these equations and combine them into a matrix form as shown below in the bottom left. What we can do to make a little bit simpler as we can do an extended matrix where the a and B matrices are combined together in a 4x5 matrix. We now need to start forming the upper triangular matrix. What we'll do is we'll start with the first column, -2, 6, 0, 8. We want to do here is make 6 equal to 0 and 8 equal to 0. Since 0 is always 0, we don't have to do this. We'll do that with Row 1. We have R2a = R2 - (6/-2)R1, R4a = R4 – (8/-2)R1. What you're doing when you do these row multiplications is you're actually taking those factors and multiplying the row through, through each term. So for example, in the first column, second row we have 6 – (6/-2)(-2). Then we can go second row, third column and we have 1-(6/-2)(-5),and so forth. This way when we've done it all we should have zeros in that first column underneath -2 for all other rows.
Now that we've finished the first column of the matrix, we can move to the second column of -14, -5, and -20. Starting at Row number 2, we'll use Row number 2 as our pivot point to reduce the values in that column for Row 3 and Row 4, we can do Row 3 as R3b = R3 – (-5/-14)R2a. We can do R4b = R4a - (-20/-14)R2a. If you've done this correctly, we should now have 0s in Column 2, Rows 3 and 4 Now that we've reduced the equations in columns 1 and 2. We can move on to Column 3 and use Row 3 as our pivot point to reduce Row 4. The equation becomes R4c = R4b - (0.4286/3.4286)R3b. If done correctly, you should get an upper triangular matrix.
In this case here, we will be able to use back substitution to continue the problem with our upper triangular matrix, we can now use back substitution to solve this problem. The matrix here can actually be turned into a set of equations as shown below. With this, the best equation to start with is the last one. We can get x4 = 3.698/2.9583. Now that we have x4, we can find x3 because x3 = (-38.99+5.6427x4)/-5.1427. Now that we have x3 and x4, we can find x2, where x2 = (44.55 – 13x4 - 20x3)/-14. Now that we've got those three, we can finally find x1. In this case here, x1 will equal (6.02 - 4x4 - 7x3 + 5x2)/-2. So, we can solve these and we can get our final answer. Now the answers have been flipped so that x1 is in the first row of this, we get x1 = 4.1, x2 = 6.85, x3 = 6.21, and x4 = 1.25. That's the end of the problem.
This concludes the video. This project could not have be completed without the support of eCampusOntario and the University of Ottawa.
Description: This video discusses improvements to Naïve Gauss Elimination by adding partial pivoting and scaling to reduce rounding error and improve solutions of ill-conditions systems. These improvements give the Gauss Elimination method.
Hello, this is video SOE|VL|04 and is the theory of Gauss elimination for solving systems of equations.
Let's first talk about the theory of Gauss Elimination. Gauss Elimination is an improvement to Naïve Gauss Elimination. Recall that in Naïve Gauss elimination as rows were reduced, there's a chance that one of the pivot points would be 0. In this case, Row 2, Column 2 would become 0. This would make this solution unsolvable. Gauss Elimination improves on Naïve Gauss Elimination by systematically choosing which row should be used as the pivot. In this case, Row 2a and Row 3a should be swapped. And if you do this, a solution can be found.
We need to make a decision which row is the best row to be the pivot point. For the first iteration, we always use the first column. But in this case shown here, we have values with 6, 3, 1 and we're not sure which ones to start with. One way at looking at this as maybe taking the largest value of these to be your pivot point. And this will help actually reduce the round off error. However, in some cases, the magnitude of the coefficients might be much, much different. And we can't just simply take the largest value. For example, here in the first column we have 1390, 0.566, and 48 as our values. The question is, what would be the best row to be the row that we want to use as our pivot point. Let's take for example the matrix previously shown with the coefficients of the A matrix where it is orders of magnitude different. If we choose Column 1, we will use the values of 1390, 0.566, and 48 to determine which row should become Row 1. We do this with a scaling technique to determine if the value in the blue column is the largest relative value to the values of its row. We do this for each row and we choose the largest value to be become Row 1 . Here is a simple equation that you can use for si, the scaling factor for Row i, that is equal to the absolute value of aip, which would be the value of a in Row i, Column p divided by the maximum value in that row. You'll notice that each value should be the absolute value. We will always take it as absolute because we're looking for magnitudes. The denominator of this, it represents the value in the rows. Let's look at the example. We'll start with the first row. The first row we have 1390 and we could divide it by the largest value, which is 1499. If we do this, we get a value of 0.927. The second row largest value is 0.556. And that's the value that we're doing as well. So 0.556 divided by 0.556 is equal to 1. In the third row, we have 48 and we divide that by 52, the largest value in that row to get a value of 0.923. In this case, the second row should become our first row as it had a scaling factor of one.
We have now moved the second row to become a first row, starting with a value of 0.566, which will act as a pivot point to be able to reduce the values in the first column below it to 0. After we do the elimination step, we should have zeros and rows 2 and 3. And we can move to Column 2, starting at Row 2. To continue on, we will not change Row 1 anymore. Now that we moved to Column 2, we're going to look at the remaining values in the rows and determine which value is the largest through scaling. If we do the scaling technique here in the second row, we have 440.54 divided by the largest value, which is 440.54, which gives us a value of 1. And in the third row we have a value of 0.551 divided by 6.03, which gives us a value of 0.09. So in this case, we do not move the second row. And we can continue with Gauss elimination to form our upper triangular matrix. And then we have our upper triangular matrix. We can move forward with doing backwards substitution as before to solve for x values.
Let's look at the algorithm for Gauss Elimination.
This concludes the video. This project could not have been completed without the support of eCampusOntario and the University of Ottawa.
Description: This video implements the Gauss Elimination method to solve a problem in a step-by-step procedure.
Hello, this is video SOE|VL|05 and is a step-by-step example of using Gauss elimination for solving systems of equations.
First, let's look at the problem. Solve the following matrix using Gauss Elimination. We have a 4x4 matrix, so 4 unknowns and 4 equations. The first step is to take the matrix and look at the first column to be a pivot column, we needed to determine which value is the best to become the first row. We can do this by scaling. If we look at Row 1, we can do 4 divided by the maximum value in that row, which is 8, 4/8. The next row, we have 1 divided by 9, then 2 divided by 8, and then 5 divided by 8 for the last row. Hence, if you look at these values, the last row has the highest value of 0.625 and should be moved to become the first row. The order of the other rows do not really matter because we will be doing scaling on each iteration. Now that we've moved our best row, it becomes Row 1. We can start eliminating through Column 1. So, 5 here in Row 1 will be our pivot point to reduce all other values below it to 0. We can do this with R2a = R2 – (4/5)R1, R3a = R3 - (2/5)R1 , and R4a = R4 – (1/5)R1. When we do this, we should get the following matrix where we have 5 in the first column and zeros below. Now that the first column is complete, we won't move the first row and we'll move down to our second pivot column, Column 2. We have three equations now and we need to determine which one is the best one to become Row 2. If we do a scaling technique will actually notice that both Rows 2 and 3 get a value of 1. We can choose either, since we already have Row 2 in that spot, we won't move it. We will take Row 2 and keep it where it is in the second row. We will now move the pivot column to be the second column. And we're going to use Row 2 and particularly the pivot point of 5.6 to be able to reduce the values below it to 0, we will have R3b = R3a - (6.8/5.6)R2a, and R4b = R4a - (5.4/5.6)R2a. If done correctly the values in the second column below the second row should be 0. We will now move to the third column. In this case here we have two equations left, but we needed to determine which one is the best one to become our third row. If we do the scaling technique that's been using, you'll notice that the fourth row has a scaled value of 1, and so it should become the third row that we're using. We've swapped rows 3 and 4 here. We are now doing the elimination steps on the third column using the third row, particularly the pivot 9.5357 to reduce the value in row four to 0. We do this with R4c = R4b - (0.7857/9.5357)R3b. If you do this, then we will have an upper triangular matrix that we can use and we can move forward to backward substitution.
Now that we have the upper triangular matrix, we can use back substitution to determine the values of x1 to x4. We'll start with the last equation, that is x4 = 16.382/5.4607. Now that we have x4, we can find x3, x3 = (93.321 - 5.6786x4)/9.5357. Now that we have x3 and x4, we can find x2, which is (31.4 + 3.4x4 + 1.8x3)/5.6. Now that we have values of x2 to x4, we can finally find the last value of x1, which in this case, x1 = (137 - 8x4 - 6x3 - 3x2 - 5x1)/5. And with this, we can find our final matrix and we've swapped the values so that we get x1 = 7, x2 = 10, x3 = 8, and x4 = 3. That is, the end of this problem has been solved. You can take it and turn the values to the original matrix and you'll notice that we will get the correct answers.
This concludes the video. This project could not have been completed without the support of eCampusOntario and the University of Ottawa.