LU Decomposition Method: Basis


Uploaded by numericalmethodsguy on 04.03.2009

Transcript:
.
.
In this segment, we're going to talk about LU decomposition method
of solving simultaneous linear equations, and try to
figure out what the basis of LU decomposition method is to solve . . . to solve
simultaneous linear equations.|So let's look at just the basis of it.
So when you are given a set of equations, you might be given, let's suppose, n equations, n unknowns,
so you'll have the coefficient matrix, A, which will be an n-by-n matrix,
and then you have your solution vector, or your unknown vector as they may call it, equal
to C, which is the right-hand side vector.|So what
we want to do is, we are given the coefficient matrix, A, we are given the right-hand side vector,
C, and we want to find out what the solution vector, X, is.|So let's
see what the LU decomposition method is based on.|It's based on that if you
can write
A is equal to L times U.|So if you are able to take the coefficient matrix and
write it as a lower triangular matrix multiplied by an upper triangular matrix, so this is a lower triangular
matrix,
and this is an upper triangular matrix.
So if you are able to write down A
is equal to L times U, then how can we use this . . .
this equation, or this breaking down of A
into L times U into solving a set of equations, and how does it help us?
So if I have A is equal to L times U, I can substitute my . . . instead of A, I'll put L times U into
my . . . into my set of equations and see what I get.|So what that means is that instead of
A I'm putting L times U times X
is equal to C.|So A has been decomposed into a lower triangular matrix multiplied
by an upper triangular matrix, X is still the unknown vector, the solution vector, and C is the right-hand
side.|Now I can take L inverse of both sides, if L inverse
exists.|So I can multiply it by L inverse
on both sides, if L inverse exists, and that's what I'm going to get.|Now, I know
that L inverse times L is nothing but the identity matrix.|So I'll get identity matrix
times the upper triangular matrix times the solution vector is equal to the
inverse of the lower triangular matrix times the right-hand side vector, C.
Now, identity matrix multiplied to any other matrix, if, again, the multiplication is possible, will be the
matrix itself, so it's U times X is equal to L inverse times
C.|So is what I have been able to get it broken down into, and I'm going to say, hey, let this
be equal to Z.|Let this be equal to Z, and you can very well see that what
Z will be, since U is n-by-n, X is n-by-1, L inverse will be
n-by-n, C is n-by-1, Z will be also an n-by-1 matrix, it'll be
n rows and one column, that's what Z will be.|Again, keep in mind that
Z is not known to us, so I'm going to put in parentheses here, say, say that
U times X is equal to L inverse times C, which we got from here, but
equal to the single column vector here, which is just
simply Z.|So let's say that it is equal to Z.|How does that help me?
Because now I can say, hey, L inverse times C is equal to Z,
and I can multiply now both sides by L . . .
L matrix, and I'll get L times Z,
and since L times L inverse is the identity matrix,
that's the definition of an inverse of a matrix, and then since identity matrix times C will
be the C itself will be equal to L
times Z.|So that's what I'm going to get from here, the C
will be equal to L times Z, and then I also have that U times X
is equal to Z from here, right?|So basically what I have is two
sets of equations.|U times X is equal to Z, and then I have
L times Z is equal to C.|So you can see that you can solve this L times Z first
equal to C, because you know the L, because you know what the decomposition is taking place
for A.|So you know L, you know C, which is your right-hand side, you
can find Z.|So once you have found Z, you can plug it back in here, and since you know your
upper triangular matrix, you can find out what the value of X is.|So that's what the LU decomposition
method is based on.|So let me write this down here.|So basically what you will be doing is that you'll
solving L times Z equal to C first, which is the first
set of equations which you're going to solve, and then once you have found Z,
you'll have U times X is equal to Z.|So L is known,
C is known, you'll be able to find Z, so once Z is known, Z is known, U is known,
you'll be able to find out what X is, so that'll be the second set of equations which you'll be solving.
Now what is the advantage of doing it this way?|It is because of the fact that when you have an L, let's suppose you have a
3-by-3 matrix, let's suppose L is a 3-by-3 matrix, so our L is going to look like this . . .
your L is going to look like this, it'll have nonzero numbers here, and
then there will be 0 numbers right here.|So that's your Z is going to be here
and your right-hand side, C, is going to be here.|So you can very well see that in order to find z1, z2,
z3, you can solve the first equation right here, because there's only one unknown in the
equation, because these two are 0s, and then you can find out the next
entry of z, so let me just change the Z to, just for clarification
purposes, z1, z2, z3, and then c1, c2, and c3.
So you can see that what is happening is that if you look at the first equation, the
only unknown is z1, because 0 will get multiplied by z2 and 0 will get multiplied by z3,
so you will get z1 from the first equation.|So from the first equation, you can definitely get
z1, because it is just one equation, one unknown.|Now if you look at the second equation,
it is this term multiplied by z1, this term multiplied by z2,
plus 0 times z3, so you have two unknowns, you have z1 and z2 unknowns, but z1
you just found out, so you can find out z2 from there.|Same thing here,
here you have this multiplied by z1, this multiplied by z2, this multiplied by z3
equal to c3, so you might think there are three unknowns, but there is only one unknown, because
you just found z1 and z2 from the previous relationships, so you will get z3 from there.
So you can very well see that the reason why we do LU decomposition method is because we can solve this equation . . .
this set of equations by solving one equation, one unknown at a time, by something
which is called forward substitution,
because you are doing the substitution forwards.|And same thing, once your z1, z2, and z3
are found, you can look at this, if this is the U matrix, which is x1,
x2, x3, let's suppose, for a 3-by-3 example,
and I'll put my z1, z2, and z3 values, which I just obtained from
solving the first set of equations there, and then I'll have for the upper
triangular matrix is going to look like this so far as its population is concerned, and there will be 0s right here,
and now here I can do back substitution, because I can solve this equation, and I'll
be able to find out what x3 is.|Now, when I take this equation here,
I know that there are two unknowns in there, x2 and x2, but I just found out x3, so it is
basically trying to solve only one equation at a time.|Same thing here, with the forward substitution
here, I'll have x1, x2, x3 in the equation, but since x2 and x3
were just found out by the back substitution, I will have the value of x1
from the first equation.|So, again, this part also is about solving
one equation, one unknown at a time, and that's called back substitution.
So this forward substitution
and back substitution is what's going to help us to be able to do the . . . do the
LU decomposition method, solve L times Z equal to C first,
and then solve U times X equal to Z, and that's the basis of the LU decomposition method.
And that's the end of this segment.
.
.
.