You can navigate through this E-Book using the menu to the left. For E-Books that have a Chapter/Section organization each option in the menu to the left indicates a chapter and will open a menu showing the sections in that chapter. Alternatively, you can navigate to the next/previous section or chapter by clicking the links in the boxes at the very top and bottom of the material.
Also, depending upon the E-Book, it will be possible to download the complete E-Book, the chapter containing the current section and/or the current section. You can do this be clicking on the E-Book, Chapter, and/or the Section link provided below.
For those pages with mathematics on them you can, in most cases, enlarge the mathematics portion by clicking on the equation. Click the enlarged version to hide it.
In this section we’re going to discuss a method for factoring a square matrix A into a product of a lower triangular
matrix, L, and an upper triangular
matrix, U. Such a factorization can be used to solve
systems of equations as we’ll see in the next section when we revisit that
topic.
Let’s start the section out with a definition and a theorem.
|
Definition 1 If A is a square matrix and it can be
factored as  where L
is a lower triangular matrix and U
is an upper triangular matrix, then we say that A has an LU-Decomposition
of LU.
|
|
Theorem 1 If A is a square matrix and it can be
reduced to a row-echelon form, U,
without interchanging any rows then A
can be factored as where L
is a lower triangular matrix.
|
We’re not going to prove this theorem but let’s examine it
in some detail and we’ll find a way to determine a way of determining L.
Let’s start off by assuming that we’ve got a square matrix A and that we are able to reduce it
row-echelon form U without
interchanging any rows. We know that
each row operation that we used has a corresponding elementary matrix, so let’s
suppose that the elementary matrices corresponding to the row operations we
used are .
We know from Theorem
4 in a previous section that multiplying these to the left side of A in the same order we applied the row
operations will be the same as actually applying the operations. So, this means that we’ve got,
We also know that elementary matrices are invertible so
let’s multiply each side by the inverses, ,
in that order to get,
Now, it can be shown that provided we avoid interchanging
rows the elementary row operations that we needed to reduce A to U
will all have corresponding elementary matrices that are lower triangular
matrices. We also know from the previous
section that inverses of lower triangular matrices are lower triangular
matrices and products of lower triangular matrices are lower triangular
matrices. In other words, is a lower triangular matrix and so using this
we get the LU-Decomposition for A of .
Let’s take a look at an example of this.
|
Example 1 Determine
an LU-Decomposition for the following matrix.
Solution
So, first let’s go through the row operations to get this
into row-echelon form and remember that we aren’t allowed to do any
interchanging of rows. Also, we’ll do
this step by step so that we can keep track of the row operations that we
used since we’re going to need to write down the elementary matrices that are
associated with them eventually.
Okay so, we’ve got our hands on U.
Now we need to get L. This is going to take a little more
work. We’ll need the elementary
matrices for each of these, or more precisely their inverses. Recall
that we can get the elementary matrix for a particular row operation by
applying that operation to the appropriately sized identity matrix ( in this case). Also recall that the inverse matrix
can be found by applying the inverse operation to the identity matrix.
Here are the elementary matrices and their inverses for
each of the operations above.
Okay, we know can compute L.
Finally, we can verify that we’ve gotten an
LU-Decomposition with a quick computation.
So we did all the work correctly.
|
That was a lot of work to determine L. There is an easier way to
do it however. Let’s start off with a
general L with “*” in place of the
potentially non-zero terms.
Let’s start with the main diagonal and go back and look at
the operations that was required to get 1’s on the diagonal when we were
computing U. To get a 1 in the first row we had to
multiply that row by . We didn’t need to do anything to get a 1 in
the second row, but for the sake argument let’s say that we actually multiplied
that row by 1. Finally, we multiplied
the third row by to get a 1 in the main diagonal entry in that
row.
Next go back and look at the L that we had for this matrix.
The main diagonal entries are 3, 1, and -29. In other words, they are the reciprocal of
the numbers we used in computing U. This will always be the case. The main diagonal of L then using this idea is,
Now, let’s take a look at the two entries under the 3 in the
first column. Again go back to the
operations used to find U and take a
look at the operations we used to get zeroes in these two spots. To get a zero in the second row we added onto and to get a zero in the third row we added onto .
Again, go back to the L
we found and notice that these two entries are 2 and -4. Or, they are the negative of the multiple of
the first row that we added onto that particular row to get that entry to be
zero. Filling these in we now arrive at,
Finally, in determining U
we onto to get the entry in the third row and second
column to be zero and in the L we
found this entry is 9. Again, it’s the
negative of the multiple of the second row we used to make this entry
zero. This gives us the final entry in L.
This process we just went through will always work in
determining L for our LU-Decomposition
provided we follow the process above to find U.
In fact that is the one drawback to this process. We need to find U using exactly the same steps we used in this example. In other words, multiply/divide the first row
by an appropriate scalar to get a 1 in the first column then zero out the
entries below that one. Next,
multiply/divide the second row by an appropriate scalar to get a 1 in the main
diagonal entry of the second row and then zero out all the entries below
this. Continue in this fashion until
you’ve dealt with all the columns. This
will sometimes lead to some messy fractions.
Let’s take a look at another example and this time we’ll use
the procedure outlined above to find L
instead of dealing with all the elementary matrices.
|
Example 2 Determine
an LU-Decomposition for the following matrix.
Solution
So, we first need to reduce B to row-echelon form without using row interchanges. Also, if we’re going to use the process
outlined above to find L we’ll need
to do the reduction in the same manner as the first example. Here is that work.
So, U
is,
Now, let’s get L. Again, we’ll start with a general L and the main diagonal entries will
be the reciprocal of the scalars we needed to multiply each row by to get a
one in the main diagonal entry. This
gives,
Now, for the remaining entries, go back to the process and
look for the multiple that was needed to get a zero in that spot and this
entry will be the negative of that multiple.
This gives us our final L.
As a final check we can always do a quick multiplication
to verify that we do in fact get B
from this factorization.
So, it looks like we did all the work correctly.
|
We’ll leave this section by pointing out a couple of facts
about LU-Decompositions.
First, given a random square matrix, A, the only way we can guarantee that A will have an LU-Decomposition is if we can reduce it to
row-echelon form without interchanging any rows. If we do have to interchange rows then there
is a good chance that the matrix will NOT have an LU-Decomposition.
Second, notice that every time we’ve talked about an
LU-Decomposition of a matrix we’ve used the word “an” and not “the”
LU-Decomposition. This choice of words
is intentional. As the choice suggests
there is no single unique LU-Decomposition for A.
To see that LU-Decompositions are not unique go back to the
first example. In that example we
computed the following LU-Decomposition.
However, we’ve also got the following LU-Decomposition.
This is clearly an LU-Decomposition since the first matrix
is lower triangular and the second is upper triangular and you should verify
that upon multiplying they do in fact give the shown matrix.
If you would like to see a further example of an
LU-Decomposition worked out there is an example in the next section.