.
In this segment, we're going to talk about why we do LU
decomposition.|What is the advantage of doing LU decomposition method?
.
and you'll be able to see that why we want to do LU
decomposition, because it might seem to be, in the beginning, that, hey, we are spending
more time doing LU decomposition method than other methods.|So for example, when you have
A times X equal to C given to you.|So if you are doing,
let's suppose, Naive Gauss elimination.
So in this case, what you will be doing is you'll be doing
forward elimination, there will be
two steps which you'll be conducting in order to do Naive Gaussian method, you can do . . . you will do forward elimination
and then you will do back substitution.|So that's where
the computation time will be spent in order to solve this set of equations by Naive Gaussian method,
you will do forward elimination steps and you will do back substitution steps.|Now, if you are doing LU
decomposition method,
then what is the time spent?|The first one, you will do
forward elimination steps to find L times
U, and that's something which we will be talking about in a different segment,
that you'll be, in order to do LU decomposition, you have to first decompose your
A matrix into L times U, and for that you'll be doing the same kind of steps which you are
doing for the forward elimination steps for Naive Gaussian method.|And then you have
to solve L times Z equal to C, and that's forward
substitution.
And then third one is that you have
U times X equal to Z, so once you have
found out what Z, is you're going to put it in here, in U X equal to Z equation,
and you're going to do back substitution.
So what you are finding out here is that in Naive Gaussian method you are using forward
elimination and back substitution, in LU decomposition method you are using the forward elimination steps to
find the decomposition of the coefficient matrix into L times U, then you have to do the
forward substitution, and then you have to do the back substitution.|So it seems that this is more work . . .
not seems, but it is more work to do this than to do the Naive Gaussian method, because
you have an extra step of this forward substitution, which you are seeing there.
So the question arises that why is then LU decomposition method even used if
first you're going to use the forward elimination steps to find the decomposition itself,
then you have to do forward substitution, and then you have to do back substitution?|So let's go ahead and see that what the
reason for that is.|The reason for that is that because
if you have multiple
right-hand sides, and
coefficient matrix
is not changing,
then your L times U,
your LU decomposition method, may
be better in terms of computational effort which you're . . . or the computational
time it's going to take, so if you have multiple right-hand sides.|A good example of that can be, let's suppose if you're
trying to find the inverse of A.
Let's suppose you're trying to find inverse of A.|In order to find the inverse of A,
you will have to solve n such sets of equations.|You will have to solve . . . you will have to solve
n sets of equations
with n different right-hand sides.
.
So if you are trying to find the inverse of A, you will have to solve n sets of equations with n
different right-hand sides.|So that means that only the right-hand side will be changing when you are trying to find the
inverse of A, and you will have n different right-hand sides, your coefficient matrix is not going to change.
So how does that make LU decomposition method a better method to use than
using Gauss elimination?|So let's go ahead and see how that works out.
.