Welcome to a lesson on solving
a system of linear equations using LU Decomposition.
If we consider the given system of equations
here on the left, we know we can write this
as a matrix equation where we have the coefficient matrix,
the variable matrix, and this product is
equal to the constant matrix here on the right.
We're going to abbreviate this as AX = B.
Now we can solve this system using LU Decomposition
if we let the coefficient matrix, or matrix A,
equal matrix LU,
where L is a lower triangular matrix
and U is an upper triangular matrix.
Then we can perform a substitution
in the equation AX = B,
so if we substitute LU for A,
we would have the equation LUX = B,
which we can solve for X.
If we let UX = Y,
we would solve the equation LY = B for Y
and then solve the equation UX = Y for X,
which will give us our final solution.
But the first step is to find the LU Decomposition
of the coefficient matrix.
So as an example, we're going to go ahead
and solve this system here using LU Decomposition.
So again, here's our matrix equation,
and here's our coefficient matrix,
which we're going to find the LU Decomposition for,
and we'll do this using the shortcut method
where we'll perform row operations on this matrix
to form the upper triangular matrix and at the same time,
by using the opposite of the multipliers,
we'll build the lower triangular matrix.
So for example, if we want to have a zero
in this position here,
we want to determine what multiple of another row
you would add to this row
to have this element be a zero.
So we're going to place row two with
1 times row one plus row two.
Let's go ahead and do that
and place our new matrix over here on the left.
So row one and row three will stay the same,
and then for row two, -1 times one plus one is zero.
1 times one plus -2 is -3.
1 times -1 plus three is positive four.
Now we use the multiplier of -1
to help us obtain a zero in row two column one,
which means the element in row two column one
of our lower triangular matrix
will be the opposite of our multiplier,
or the opposite of -1,
so this element here will be positive one.
Now let's obtain a zero in this position here,
or row three column one.
We can replace row three with -2
times row one plus row three
to obtain a zero here.
Again, notice the first two rows would stay the same.
It's going to have -2 times one plus two is zero.
2 times one plus three is positive one,
and -2 times -1 is positive two plus one, is positive three.
Our multiplier is -2.
To obtain a zero in row three column one,
which means row three column one
of our lower triangular matrix,
will be the opposite of -2,
which means this will be positive 2.
And if the last row operation,
we want a zero here,
we have to use row two to do that.
So if we replace, so if we replace row three
with one-third times row two plus row three,
this will give us a zero here.
First two rows stay the same.
This element will still be zero.
And then here, we'll have 1/3 times -3,
that's -1 plus one, that's zero.
And then for this last element,
we'll have 1/3 times four, that's 4/3
plus positive three, which happens to be 9/3.
So the last element here will be 13/3.
Our multiplier to obtain a zero
in row three column two,
which corresponds to this position here in L,
is going to be the opposite of positive 1/3,
which means this element here will be -1/3.
So now we have the LU Decomposition of matrix A.
Here is our upper triangular matrix,
and here is our lower triangular matrix.
So now, if we go back to our notes just for a moment,
we're going to solve the equation LY = B for Y
and then UX = Y for X.
So here's our equation LY = B.
Here's our lower triangular matrix,
which we built using the shortcut.
Here's the matrix Y,
and here's our matrix B.
So we write this back as equations.
We would have y sub one equals four.
y sub one plus y sub two equals -6.
Two times y sub one
minus 1/3 y sub two
plus y sub three equals seven.
So we can see y sub one is equal to four.
Well if y sub one is equal to four,
we have four plus y sub two equals -6,
so y sub two equals -10.
And then for y sub three,
we have a little bit of work to do.
We would have two times y sub one, which is eight
minus 1/3 times -10, that's plus 10/3
plus y sub three equals seven.
So now we have y sub three
equals seven minus eight, that's -1
minus 10/3 is going to be -13/3.
Now that we have the values of the elements in matrix Y,
our last step is to solve the equation UX = Y for X.
And here's that matrix equation.
Notice this is our upper triangular matrix, which we found.
Here is our matrix X,
and here is our matrix Y with the values that we just found.
So we write this is as equations.
We would have x sub one plus x sub two
minus x sub three equals four.
3x sub two plus 4x sub three equals -10,
and the last equation is 13/3 x sub three equals -13/3,
so hopefully, we can see that x sub three
is equal to -1.
So if x sub 3 is equal to -1,
the second equation would be
3x sub two minus four
equals -10, add four to both sides.
6, divide by -3,
we have x sub two equals two.
Now we're left to find x sub one.
Now we have x sub one
plus x sub two, or plus two,
minus x sub three, which is -1, equals four.
We have x sub one plus three equals four.
So x sub one equals one.
This would be the solution to the system of equations,
which we solved using LU Decomposition.
Okay, I hope you found this helpful.