.
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.|So if you . . . if you look at Naive Gaussian method,
so let's look at Naive Gauss elimination method.
Let's go ahead and see that how much time Naive Gaussian method would take if I was going to
find the inverse of an A matrix, inverse of an n-by-n A matrix.|So in that
case I'll have forward elimination, okay?|Forward elimination takes . . .
the amount of time forward elimination takes is
approximately equal to C times n cubed
divided by 3.
She amount of time forward elimination takes, in order to . . . the computational time is C times
n cubed divided by 3, approximately equal to, where C is simply the time
to conduct a
FLOP, okay?|Multiply/divide FLOP . . .
multiply/divide FLOP.|What do I mean by that?
C is the amount of time which it conducts . . . which it takes to conduct a multiplication/
division floating point operation, so it is proportional to n cubed by 3.
So if n is the number of equations . . . n is the . . .
n-by-n is the order of the A matrix, then the amount of time which it's going to take to do forward elimination
in the Naive Gaussian method will be proportional to C n cubed divided by 3.|There are certain assumptions
which are involved in this is that we are assuming that multiply and divide
floating point operations are taking the same amount of time, which is not actually true.
We also . . . we're not also . . . we're also neglecting how much . . . how many floating
point operations we have to do of addition and subtraction, although they take a little bit less time.
So having . . . having taken these assumptions, that's why I put the word
approximately here, because this is not exactly the number of floating point operations you are
doing in Gaussian . . . in the forward elimination part of the Gauss elimination method.
This is only the multiply/divide floating point operations you are doing, also you are then assuming that
multiply and divide takes the same amount of time, and you're also neglecting the addition and subtraction,
but this is not a bad assumption to make here that how much time forward elimination takes.
In a similar spirit, back substitution . . . back substitution
takes approximately C n squared divided by 2
amount of time.|So if somebody was going to say that, hey, for
doing one sets of . . . one set of equations, it will take C times n cubed by 3, for
back substitution it takes C n squared divided by 2 amount of time, where C is the time
it takes to conduct a single multiply/divide floating point operation, then I can see that
the total time it's going to take, so total time
it is going to take to find the inverse of A matrix will be
C n cubed divided by 3, plus C n squared divided by 2.
So this is going to be the amount of time it's going to take to do a single forward elimination and
back substitution, so I'll have n times that.|n times C n cubed divided by 3,
plus C n squared by 2 will be the amount of time it's going to take for me to do the
n . . . to find out the inverse of A, because I have to do these
forward substitution and back substitution n times.|Now what about LU decomposition
method?|So let's do it on a separate place here.|In the LU decomposition method,
what's going to happen is that the amount of time I have to do forward
elimination, so forward elimination is going to take the same amount of time as
it takes for Naive Gaussian method, because I'm using the same steps of
forward elimination to do the LU decomposition, so it'll be C n cubed divided by 3.
Then also, of course, I have to do forward substitution,
and that's going to take approximately C n squared by 2,
because forward substitution will be same as back substitution, we just talked about that back
substitution take C n squared by 2 time, so then back substitution
will take approximately C n squared by 2 time also.
So you can see that LU decomposition is going to take more time,
because we have forward elimination steps, forward substitution steps, and back substitution steps, if we were just doing this
once, because the total time will be C n cubed divided by 3, plus
C n squared by 2, plus C n squared by 2, because this is the times,
which is this part here, is the additional which you have to take in terms of . . .
in LU decomposition method.|But the thing is that what you are not seeing
is that this . . . this is the time which it's going to take to do the LU decomposition method . . .
or the LU decomposition of the A matrix, so this has to be done only
once, however this part here will have to be done n times, because I'll have to do
the forward substitution and back substitution n times, because the LU decomposition
only has to be done once.|So if I . . . this is the total time it's going to take to do
LU decomposition.|So this one becomes C n cubed divided by 3,
plus C n cubed, and that becomes
4 C n cubed divided by 3.
So you can already see that the . . . if I
try to write down what is the time taken by Gaussian elimination, so if I look at
Gaussian elimination time, and then divided by the . . .
divided by the LU decomposition time.
What is that equal to?|The Gauss elimination time is n times
C n cubed divided by 3, plus C n squared divided by 2,
and the LU decomposition times is 4 n cubed . . .
4 C n cubed divided by 3.|And this is
approximately equal to, if n is large, then this quantity here becomes small as compared to this quantity
here, so I can always write this as approximately equal to c n cubed divided by 3, so I'm going to neglect
this term here, and divided by 4 C n cubed divided by 3.
So what I'm going to get is this and this cancels, C and C cancels, and that's n divided
by 4.|So what it is basically telling you that the amount of time Gauss elimination is going to take
to find the inverse of a matrix will be n by 4 times what LU
decomposition is going to take in order to be able to do the finding the inverse of a matrix.
So you can very well see if n is equal to . . . if n is equal to 1000, let's suppose,
your Gauss elimination . . . your Gauss elimination time
divided by the LU decomposition time is going to be
250, because n divided by 4, 1000 divided by 4 is
250.|So Gauss elimination will take 250 times more what
LU decomposition will take to do . . . find the inverse of a matrix.|So this is the reason why
LU decomposition is favored over Gauss elimination when you have multiple right-hand sides,
as will be the case when you are trying to find the inverse of a matrix.|And that's the
end of this segment.
.