Watch these four (4) videos in order. The total video time is 27 min. Be sure to test your knowledge with the knowledge checks after each video.
Description: This video discusses how to decompose a matrix into upper and lower matrices, and then solve problem using forward and back substitution. These three steps give Crout Decomposition.
Hello, this is video SOE|VL|06 and it is the theory of Crout decomposition for solving systems of equations.
Let's first talk about the general theory of Crout Decomposition. The standard system of equations that we have is usually [A][X]=[B]. What we've used in the past is Gauss Elimination to solve this, However, sometimes there are different B matrices that needs to be solved for the same [A] matrix. If you do this, Gauss Elimination is not very efficient. There are other methods called LU decomposition that are actually great for solving systems with multiple [B] matrices. What we do here is first decompose [A] into two different matrices, [L] for lower and [U] for upper matrices. Once this step is decomposed, what we'll do is the next step, which is forward substitution. Forward substitution, we'll use this lower matrix [L] and the [B] matrix to find an intermediate matrix [D]. With [D] and [U], we can use it to solve for [X] doing backwards substitution, which is the third step. The nice part here is once this has been decomposed, all you need to do is forward substitution, then back substitution for each new value of [B]. This becomes much more efficient than Gauss Elimination for these sets of problems.
Just as a reminder, we have [A] matrix which is equal to all the coefficients a11, a12, etc., all the way down to ann. The [L] matrix is a lower matrix. What this represents is the lower triangular matrix, that is, all values on the diagonal and below are filled with some numbers. And all values above the diagonal are all 0. That's the lower triangular matrix. The upper triangular matrix is [U], and it follows as this, all values above the diagonal. It has values of u12, u1n, etc. All values below are 0 and on the diagonal are equal to 1. This type of method is a Crout Decomposition method. What you can do is if you do not want to store both by themselves, sometimes we can combine them together in an [A’] matrix where the L values and U values do not overlap and you can combine them together. And if you were to program, this would be stored together as well.
The question is, how do you decompose the matrix? There are series of equations that you can use to decompose it for Crout Decomposition. We'll go through them now. The first step is you start with your [A] matrix. Step 1a is that li1 = ai1. Once you've had those values, we will move onto 1b. 1b is u1j = a1j/l11. This is the first step for all the interior points. Later, we're going to be using a different formula. So for 2a we'll use lij = aij - the summation from k = 1 to j - 1 of likukj. This is part of the decomposition step. And what you'll notice here is there's actually a subtraction. So what you're doing here is actually an elimination method, just like Gauss Elimination. After 2a tou have 2b, which is ujk = ajk– summation from i = 1 to j -1 of ljiuik all divided by ljj. This is the next step for the upper part of the matrix. Then you'll go back and use the same formula for 3a that we used for 2a. And then continue on for 3b for 2b all the way until you get to the last corner of the matrix at ann. And for the last n value, what we’ll use is lnn = ann – summation from k =1 to n -1 of lnkukn. Now this may look like a lot, but as you go through an example, you'll notice that it is relatively straightforward and a nice pattern is formed, which we'll do in a later video.
Once we have that, what we can do is do the foward substitution using the relationship that [L][D] = [B]. You'll notice if we took the [L] matrix for, let's say a 4x4 matrix, you'll notice that you can get to relationships quite easily from equations here. And what you can get as d1 = b1/l11 and so forth all the way down to d4. So this would be forward substitution. Once we have this intermediate matrix [D], We can now solve for [X] using [U] matrix. So [U][X] = [B]. And what you'll notice here, if we're using upper matrix, it'll be very similar to what was done before. We can solve for the values. So for example, x4 = d4, x3 = d3 -u34x4, etc., until you get your final value.
Let's now look at the algorithm.
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 theory of Crout Decomposition in a practice problem in a step-by-step approach.
Hello, this is video SOE|VL|07 and it is a step-by-step example of Crout Decomposition for solving systems of equations.
Let's now look at the problem. Solve the following systems of equation using Crout Decomposition. What you'll notice is that we have two sets of systems of equations, but both of them share the same [A] matrix. The only thing that's different is the [B] matrices with different values. This is a prime example of when to use Crout Decomposition. So just as a recap, we have the [A] matrix which is equal to on the first row, 5, 4, 4, 8, row 2 is 7, 8, 6, 8, and 6, 10,8,9 is the third row. And the fourth row is 3, -3, 7, 9. We have one [B] matrix, which we'll call [B1], which is negative -26.5, -13.5, -17, and -65. And our other [B] matrix, [B2] we’ll call it is -20, -ten, -30, and -40. Recall that we're going to do a lower triangular matrix called [L], where there's L values on the lower triangle including the diagonal and zeros above. We're going to do an upper triangular matrix which is one on the diagonal with U values of the upper triangular and 0 on the lower triangular matrix. For this example, we're going to use [A’], which will be a combination of [L] and [U] just to store the values and see what happens with them. This is not a real matrix, this is justvery good for a technique to solve these problems.
So for this example, we will not be using any partial pivoting and row swapping just so that we can focus on the LU decomposition part. The first step is we're going to use equation 1a which is li1= ai1. What we'll do here is we're going to solve for that first column. First column is 5, 7, 6, 3. Essentially, the [L] matrix values are the same. So the values of [L] matrix expressed here in [A’] matrix get replaced in there. The next equation is 1b, that is u1j = a1j /l11. We will do this, starting at column j = 2 in the first row as well. To do this, we're going to use the L value that we have, which it turns out to be five as well and as we do this, we can calculate those three values, which ends up being 4/5, 4/5, and 8/5. Now that we've done the first row and first column will move in a little bit with equation 2a. That is, lij = aij - summation of k = 1 to j - 1 of likukj. What does this mean when we actually put the values in? We're going to look for l22 first. If you plug the values in, we get l22 = a22 – l21u12. And if you look at an [A’] matrix here, you'll see what values were using surrounded by the l22 value. We can do the same thing for the next one, which is l23 = a23 – l21u12, and l24= a24 – l41u12. Once we have those, we've decomposed the next column in the matrix, and we'll continue on. Now that we've done that, we'll move on to equation 2b. In this case, equation to be is ujk = ajk - summation of i = 1 to j - 1 of ljiuik all divided by ljj. This will be starting at u23. And that will equal to (a23-l21u13)/l22. You'll notice in the [A’] matrix here, what values are being used to solve for u23. We can do the same thing for u24 which is equal to (a24-l21u14)/l22. We do that. Now we've solved up to the second row in [A’] prime matrix. That will continue as before, we're going to do 3a, which is the same equation as 2a. We will start looking for l33 at the beginning. What you'll notice is that since j = 3, we're actually going to have summation terms that will be used here. So l33 = a33 -l31u13 - l32u23. If you look at the [A’] matrix, we're looking for the value of l33 and it is related to the values to the left of it in the matrix and above it. We could do the same thing for l43 which will equal to a43 – l41u13 – l42u23. Finally, we have the [A’] prime matrix for those values that we've solved for the first three columns. Let's continue to using equation 3B, which is the same as 2b. What we're going to do here is find the value of u34. And again, just like in 3a, we have extra terms here. u34 = (a34 - l31u14 - l32u24)/l33. You'll notice we're looking for the value of u34 and it's related to all the values to the left of it in the [A’] matrix and everything above it, in the [A’] matrix and that gives us the value. We only have one last value to find. For the last value will use equation 4, which will be the corner here, which is lnn = ann - summation of k = 1 to n - 1 of lnkukn Since we're at 4, we'll have actually three terms here. So l44 = a44 - l41u14 - l42u24 - l43u34. Just as before, if you look at the value of we're looking for in [A’], l44 is related to all the values to its left and above it. We will find the last value and we've decomposed the matrix.
Can now take that [A’] matrix and split them appropriately between the [L] and [U] matrices. And if you'd like, you can test to ensure that [L][U] = [A]. Through the matrix multiplication, you should get the same answer coming out if you've done so, you've done the decomposition correctly.
Now we'll use forward substitution that is [L][D]=[B]. What we're looking for here is matrix [D] an intermediate matrix that we'll use. So we’ll bring up our L matrix and our [B1] matrix. And what you’ll notice here, we can convert these into equations. And now that we've converted them into equations will be able to solve them. We can also look at the other [B] matrix that we had, which was matrix [B2]. And we can find its equations as well. And what you'll notice is that the left-hand side with all the terms 5d1, etc., are equal in both cases. And the only thing that changes is the right-hand side of these equations, which is exactly what we need to do to solve. Here are the equations and we can take the left-hand side and find our [D1] matrix and [D1] matrix is equal to -5.3, 9.8333, -15.57, -5. And then we can apply the same technique again to find your [D2] matrix, which is -4, 7.5, -19.286, -6.6136. Now these matrices are intermediate, they are not the answers.
We're going to use our upper triangular matrix now to solve this. So now that we have our intermediate [D] matrices, we can now use the relationship of [U][X] = [D]. So we can solve for our x values that we're looking for. So as a reminder, [U] is upper triangular matrix and we have our values of [D1]. And if you look here that the best equation to use is the fourth equation. And we could do backwards substitution to find out that x4 = 5 and have the rest of the equations based off of the other x-values. We can do the same thing for [D2]. And just like before, the left-hand side of the equation, in both of these sets are equal and all that changes is the right-hand side. Let's solve the equations. Let's go for the first one. When we solve the values, our estimate of [X1] is 1.5, 3.5, -2, -5. And for the second set, we have of matrix [X2], we have 8.5259, -1.0956, -1.3347, and -6.6136. These are the final answers. You can put them back into the original equations and they should all work.
This concludes the video. This project could not have been completed without the support of eCampusOntario and the University of Ottawa.
Description: This video discusses how to use a special case of decomposition to solve for tridiagonal matrices called the Thomas Algorithm. This method can only be used for tridiagonal matrices.
Hello. This is video SOE|VL|08 and it is the theory of Thomas Algorithm for solving tridiagonal matrices.
Let's look at the general theory behind Thomas Algorithm. The Thomas Algorithm is a special algorithm, it is actually a special case of LU decomposition, but it only applies to matrices that have values only on the diagonal and the upper and lower diagonal, everything else must be 0. This actually is quite common in many engineering problems and therefore very useful for an engineer. We have a certain notation for this. We have the lower diagonal which is labeled as E, going from e2 because it starts at Row 2, to en. We have the upper diagonal, which is the letter G, Starting at g1going to gn-1. We have the main diagonal, which is F going from f1 to fn. And we have what was the b-values which we're calling R in this case.
Just like LU decomposition, we will start by decomposing the matrix. We go with k = 2 to n. We've got two equations that we'll use. First we'll use ek = ek/fk-1. Then we will have fk = fk-ekgk-1. What's important to note here is you actually update the values as you go through. For example, if you had e2, that'll be updated in the first equation and that e2 is what can be used to calculate f2, the second equation here. A good way to organize this is using matrices. So we'll have the [E] matrix, the [G] matrix, and the [F] matrix. And what you'll notice is since the [E] matrix has one less value than the diagonal, we have shifted it down since there is no value of e at e1. And same thing for the [G] matrix. This goes from g1 to g4, and there's no values, in this case at the end at g5 and we put a blank there. We can populate this using our diagonals from our equations. So the [E] matrix can be populated, our [G] matrix can be populated, and our [F] matrix. If we did that, it would look something as follows. So [E] is equal to blank, 2, 2, 7, 8, [G] is equal to 4, 1, 2, 8, blank, and [F] is equal to 1, 6, 9, 9, 1. When we're done this and we do the formulations we can actually change them as we go so it'll look something like this. One thing you'll notice is that [G] does not change and in the [F] matrix, the value at 1, it does not change as well, f1, but everything else will change as you go through.
The next step is forward substitution. Again, we'll go from k = 2 to n and the formula here is rk = rk – ekrk-1. Just like before, we will continually update our values. So for example, calculated r2 and r2 will be used when we calculate r3. It'll be the updated value. We can get our values and we can place them into a matrix again. In this case here, this is essentially equal to the [B] matrix that we've seen before. And so if we have the [R] matrix, it'll just look as such, 21, 37, 39 ,47, 17. And if we apply the formula above, what we'll get is our prime in this case, as I've been calling it, the first value of r1 stays the same as 21, but the rest will change.
The final step for decomposition is the backward substitution. The first step is we'll find the last value in this case, xn = rn/fn. And then for all other values of k = n-1 to 1., we'll use the following formula, xk = (rk-gk*xk+1)/fk. What you'll notice here is we'll be using values as we continue on. So for example, if we're looking for x2, what we'll need to know is x3. If we’re looking for x3, we'd need to know x4 and so forth. And this is the back substitution that we normally use. In this case here, just as a preview. The first equation here, xn is just the last value. And the other equation will give us the rest of them.
Let's discuss the algorithm.
This concludes the video. This project cannot have been completed without the support of eCampusOntario and the University of Ottawa.
Description: This video implements the theory of Thomas Algorithm in a practice problem in a step-by-step approach.
Hello, this is video SOE|VL|09 and is a step-by-step example of Thomas algorithm for solving tridiagonal matrices.
First, let's look at the problem. Solve the following matrix using Thomas algorithm. This is a tridiagonal matrix as our only values on the diagonal and the upper and lower diagonals as well. And the rest are zeros. And we have seven equations and seven unknowns. So it looks quite large, but with this algorithm, it could be go quite quickly.
Step one is to convert the tridiagonal matrix into separate matrices, so we have the [E] matrix, we have the [G] matrix. Note that those each have one less, so we've padded it to be the same size as the [F] and [R] matrices with the blank spaces, we have [F] matrix, we have the [R] matrix. Step one is to decompose. We do this by going from k = 2 to n with two equations, ek = ek/fk-1, and fk = fk – ekgk-1. Let's start and you'll notice a pattern form. As we do this, we'll do ek first, which will be 2 divided by 4. What we'll do here is we're going to replace that value immediately with the answer which is 0.5. Next we'll do fk = fk-ekgk-1. We will replace that immediately with a value which will be equal to 1. Then we move down and we'll use the new values as we go through this. So, we'll have e3 here, which will be still equal to three as it is crossed out. Then we'll do f3, four becomes -2. Then we have e4, which becomes -0.5. We keep working our way through until we are at the bottom. Now what you'll notice as well is that as we're using [G], we're not changing it as we go through and [G] never changes. It's only the [E], [F] and [R] matrices that we'll use. Will do the last step here, which is e7 and f7 we've done here is replace the matrix with the new values that will using. And this is the decomposition step.
The second step is using forward substitution. And we can do this from k = 2 to n using the following formula, rk = rk- ekrk-1. For the first equation, what we end up getting is r2 = r2 - e2r1. And just as before, we will continue updating as we go through, the second 32 becomes 16. We move down to the r3, r3 becomes -5. Then we convert for r4 from 49 to 41.5, 38 becomes 23.565, 22 becomes 85.764, and 15 becomes 0.493. This is the step for forward substitution.
Now we'll do the final step, which is backward substitution to find our values of x. And we'll do this first with xn = rn/fn. This case here we'll find x7 first and x7 will equal to one. Afterwards, we're going to use from k = n-1 to 1. The formula xk = rk – gkxk+1, so the value we just found, all divided by fk. If we do this, we can find that x6 = 7, x5 = 6, x4 = 1, x3 = 5, x2 = 6, and finally, x1 = 5. So we've just found our answers to our problem and we are done Thomas Algorithm.
This concludes the video. This project could not have been completed without the support of eCampusOntario and the University of Ottawa.