Basis of LU Decomposition Method of Solving Simultaneous Linear Equations

In this segment we'll talk about the LU decomposition method the basis of it. So, to talk about the basis of the LU decomposition method we need to recall what we are trying to do in the first place. So, what we are trying to do is we are solving a set of equations. So, let's suppose n equations n unknowns, and then we know that this is the coefficient matrix, and this is called the unknown vector. Many times, called the solution vector. I like to call the unknown vector because we don't know it yet. And of course, there's a solution vector once we know what the solution is, and this is called the right-hand side vector. So, we want to be able to find out what this unknown vector is, that's the bottom line. What LU decomposition basis is that hey one can write the coefficient matrix, the square matrix, which is the coefficient matrix here, as in the form of [L] times [U], where [L] is the, what we call as the lower triangular matrix, and [U] is called the upper triangular. And people might say that, hey, can we always write a in LU form? It's a little bit not a difficult question to answer, but we cannot do it clearly. One of the things which I can tell you is that if [A] has an inverse or what we call as a non-singular matrix then you can surely write it in some form which looks like, where this [P] is a perturbation matrix and this [P] could be the identity matrix, and then it'll be just in this form, but sometimes you might have to use the perturbation matrix to be able to reduce the coefficient matrix into an LU form. So, we're not going to get into this discussion at this time, because it makes a little bit more complicated, so we're going to stick with this that hey you have an [A] matrix and you're able to decompose into [L] times [U]. So, how does that help us to find the solution towards the set of equations? Let's go and talk about that.

So, as you can see that we are given [A][X] is equal to [C], and then we're also saying that hey somehow, we know what the LU decomposition of the matrix [A] is, and that's what it is. So, what I’m going to do is we're going to substitute this into here. I’m going to say [L] times [U] times [X] is equal to [C]. And now what I’m going to do is I’m going to multiply both sides by [L] inverse. That's what I’m going to do. And the reason why I’m allowed to do so is because we already said that hey [A] is a non-singular matrix, and that's the only thing for which we are talking about the LU decomposition method. So, if [A] is non-singular, then [L] and [U] also have to be non-singular, it can be proven. So, that's what gives us the capability of multiplying both sides by [L] inverse. But what is [L] inverse times [L]? it is just [I]. And what is [I] times [U]? It is just [U], as per the definition of identity matrix. So, we get this. Now what I’m going to do is say I’m going to say, hey, let [U] times [X] be equal to [Z] say. So, we're not saying that it's equal to some known quantity [Z] we're saying hey it'll be some vector [Z] because it's an n-by-n matrix, this is an n by 1, matrix and it's an n by 1 matrix. So, if that is the case if [U] [X] is equal to [Z], then what we have is that [L] inverse times [C] will be equal to [Z] also. And I can multiply both sides by [L] now, and let's see what do we get from doing that. [L] times [L] inverse is the identity matrix, identity matrix times [C] matrix is just the [C] matrix, and you get [L] times [Z]. And what I’m going to do is I’m going to just write it down here: we get [L] times [Z] equal to [C]. So, what you're finding out here is that you're getting two sets of equations. Two sets, not two equations, two sets of equations where you have this, and this. So, you can very well see that what the basis of the LU decomposition method is that, hey, let's go and solve this first because we know what the [C] is, we know what the right hand side vector is, we know what [L] is because we've said that hey we know what the LU decomposition of the a matrix is we can find our z's and once we have calculated [Z] we can plug it back in here and since we know what the [U] matrix is because we already said that hey we know the LU decomposition of the a matrix we can find the value of [X]. So, it's a two-step process: you have to first solve [L] times [Z] equal to [C] and then you have to solve [U] [X] equal to [Z]. So, let's go and summarize this.

So, in summary we are trying to solve [A][X] equal to [C]. We already know what the LU decomposition of [A] is, and we end up with the two sets of equations we say [L][Z] is equal to [C], and then we say [U] [X] is equal to [Z]. So, this is because of the first set of equations this was the second set of equations. So, what you're finding out is that you have a lower triangular matrix multiplied by unknown vector [Z] will give and [C] is the right-hand side vector, will allow you to find [Z] once your [Z] has been found you have [U] as an upper triangular matrix and you can find the value of [X]. So, let's go and see that how does it work for, let's suppose, a three-by-three matrix. Not for example, just to give an idea that hey how it makes it easy so if I had a three-by-three matrix, so I have [L] times [Z] equal to [C] which I have to solve first, so the lower triangular matrix is a three-by-three so I’m just taking an example here of a three-by-three equation, three equations three unknowns. And I’ll have a [Z] one here [Z] two here [Z] three here and the right-hand side also will have three elements in it, like this one. You can very well see that when I look at this set of equations, in the first equation I only find out that hey z1 is the only unknown because 0 will get multiplied by z2 and 0 will get multiplied by z3. So, I’ll have from the first equation I can find z1 now if I look at the second equation what's going to happen is that it will get multiplied uh z1 will get multiplied by a non-zero quantity, z2 will get multiplied by non-zero quantity, and z3 will get multiplied by zero right here. But I already found z1. So, since I already found out z1, it's only one equation one unknown, where I can run z2. Same thing let's do for the last one. For the last one, non-zero numbers are getting multiplied to z1 z2 and z3, but we already know z1 and z2, so that means that we're going to solve only one equation and one unknown to find z3. So, you're finding out we would be very similar to what we talked about the back substitution method in our gauss elimination. So, the only reason, the only difference is that this is forward substitution, and that is the first step of LU decomposition method. Let's go and see that hey what happens when we have the second set of equations which is [U][X] equal to [Z].

So, let's look at the second set of equations which is [U] [X] equal to [Z], and we just found out [Z] from the forward substitution so we want to be able to find out what [X] is. Let's take an example of three equations three unknowns and see how that works out. So, we'll have non-zero elements here in the upper triangular matrix, possibly. But surely zero elements right here in those locations. And then we have three elements in the unknown vector, and then just we have found out what the [Z] vector is so we'll know these three numbers on the right side. But if you start from the back you start from the last equation you find out that, hey, this last equation has only one non-zero element here multiplied to x3, so that will give me x3 directly. Now if I look at the second last equation, although this is getting multiplied to x2 and this is getting multiplied to x3, which are non-zero elements, but I just found out x3, so I can find out where x2 is. Same thing here; x1 x2 and x3 are getting multiplied to non-zero quantities, but I already know what x2 and x3 are, so that allows me to solve in one equation one known at a time, just like the previous ones, and I find x1. And this is nothing but back substitution which is exactly the same algorithm which you use for Gaussian elimination whether it was a naive Gaussian method or whether it was Gaussian emission with partial plating. So, that is the basis of the LU decomposition method, how it works so far as solving a set of simultaneous linear equations is concerned. And that is the end of this segment.