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.

.

.

.

.

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.

.

.

.