8.13 LU-Factorization

INTRODUCTION

Just as positive integers and polynomials can be factored, so too a matrix can sometimes be factored into other matrices. For example, in the last section we saw that if an n × n matrix A is diagonalizable, then there exists a nonsingular matrix P and a diagonal matrix D such that P−1AP = D. When the last equation is written as A = PDP−1 we say that A has been factored or decomposed into three matrices. There are many ways of factoring an n × n matrix A, but in this section we are interested in a special type of factorization that involves triangular matrices.

The notion of a triangular matrix was introduced in Section 8.1. See page 379.

LU-Factorization

Recall, a triangular matrix is a square matrix that is either a lower triangular matrix whose entries above the main diagonal are all zero or an upper triangular matrix whose entries below the main diagonal are all zero:

(1)

Lower and upper triangular matrices are very important in a variety of computational applications, but in this section we will confine our attention to their use in solving linear systems AX = B. We will denote a lower triangle matrix by the letter L and an upper triangular matrix by U. This leads to the following definition.

DEFINITION 8.13.1 LU-Factorization

Let A be an n × n matrix. If A can be written as a product A = LU where L and U are lower triangular and upper triangular matrices, respectively, then we say that A = LU is an LU-factorization of A.

An LU-factorization of a matrix A is also called an LU-decomposition of the matrix A.

EXAMPLE 1 An LU-Factorization

Suppose Then for the lower triangular matrix and the upper triangular matrix it is easily verified by matrix multiplication that an LU-factorization of A is

(2) ≡

Finding an LU-Factorization

Of course, the obvious question is: How do we find an LU-factorization for a given matrix A? For the sake of discussion let’s assume that A is a 3 × 3 matrix, although the procedures discussed in this section are applicable to square matrices of any order. We want to find two 3 × 3 matrices L and U such that A = LU or

(3)

By carrying out the indicated multiplication on the right-hand side of (3) and equating its entries to the corresponding known entries aij on the left-hand side we obtain a system of 9 equations in 12 variables, the variables being the lij and uij. Recall, such a system is underdetermined and, if consistent, would have many solutions. This leads us immediately to the conclusion that the matrices L and U in an LU-factorization are not uniquely determined. In other words:

  • An n × n matrix A can have several different LU-factorizations.

The factorization depends on the method used.

See page 393 at the end of Section 8.2.

Doolittle’s Method

In order to determine unique matrices L and U we need to impose three conditions on the variables lij and uij in (3). The method that we examine in the examples that follow is called Doolittle’s method after the American mathematician Myrick H. Doolittle (1830–1913). In this method the main diagonal entries lii of L in (3) are chosen to be all 1s. The next example illustrates a method for obtaining the remaining nine variables.

EXAMPLE 2 Example 1 Revisited

Use Doolittle’s method to find an LU-factorization of

SOLUTION

The matrix A is the one considered in Example 1. We are going to show how the factorization given in (2) can be found. Using (3) with lii = 1, i = 1, 2, 3 in the lower triangular matrix L we write

(4)

Then by the definition of equality of matrices we must have

(5)

At first glance (5) may look a bit formidable to solve, but it is not. Indeed, (5) is not so much a system of equations as it is a sequence of nine linear equations in one variable. The trick in solving (5) is to read each equation beginning with the first row moving left to right and use previously found values to determine the one variable in each equation. The variable determined by each equation is indicated in red in (5). Using the values u11 = 1, u12 = 1, u13 = 1 from the first row in the three equations in the second row yield, in turn, l21 = 3, u22 = −2, u23 = −1. Note that we also had to use l21 = 3 to find u22, and so on. The three equations in the third row then give l31 = 1, l32 = 1, u33 = 1. Substituting these values in the appropriate triangular matrices in (4) gives LU-factorization,

≡

An Algorithm

Doolittle’s method is very popular in that it is easily programmed in computer algebra systems such as Mathematica or MATLAB. In lieu of the brute force technique illustrated in Example 2, we can carry out Doolittle’s method using one of the elementary row operations that we used in Gaussian elimination to create an upper triangular matrix U out of the matrix A. In particular, we use the notion of row addition, that is, adding a nonzero multiple of one row of a matrix A to another row. Recall from Section 8.2, the notation cRi + Rj denotes the multiplication of the entries in the ith row of a matrix A by a nonzero constant c and adding them to the corresponding entries in the jth row. We state the following two-step algorithm without a formal proof. We assume that A has an LU-factorization.

  1. Create an upper triangular matrix U using row addition to zero out the entries below the main diagonal of A. For a 3 × 3 matrix, this looks like

    (6)

  2. Keep a record of the negatives of the multipliers of the rows used in step (i) by entering these numbers in an appropriate-sized identity matrix I. If we perform the addition cRi + Rj, then enter −c in the jth row and ith column of I. For example, if we perform 5R1 + R2 on A in (6) to zero out the entry in the second row and first column, we then replace the 0 in the second row and first column of the 3 × 3 identity I by the number −5:

    When finished with the reduction of A to U, the matrix created by recording the negatives of all the multipliers of the rows we used is a lower triangular matrix L because these numbers are placed in I in exactly the same position as the 0 s in the matrix U (below the diagonal).

EXAMPLE 3 Adding Multiples of Rows to Rows

Find an LU-factorization of

SOLUTION

We need only perform one row-addition operation on A to obtain the desired upper triangular matrix U. We simultaneously create L using the 2 × 2 identity I:

(7)

From (7) we see that

An LU-factorization of A is given by

≡

EXAMPLE 4 Adding Multiples of Rows to Rows

Find an LU-factorization of

SOLUTION

In this case the reduction of A to U requires three row-addition operations. We record the negatives of the multiples of the rows in the 3 × 3 identity I:

(8)

Inspection of (8) yields

Thus an LU-factorization of A is

≡

Solving Linear Systems

Suppose AX = B is a linear system of n equations in n variables. If an n × n coefficient matrix A in the system has an LU-factorization A = LU then AX = B is the same as (LU)X = B, or L(UX) = B. This last system can be solved efficiently in two steps:

  1. First, let Y = UX so that L(UX) = B becomes LY = B Solve for Y by forward-substitution.
  2. Then solve UX = Y for X using back-substitution.

The next example illustrates the method.

EXAMPLE 5 Example 1 Revisited

Solve the system

SOLUTION

In terms of the matrix notation AX = B, the linear system is the same as

(9)

where the coefficient matrix A in (9) is the matrix in Example 1. Using the LU-factorization of A given in (2) of Example 1, (9) can be written

(10)

If we let in (10), where Y is the column matrix

, (11)

then (10) is the same as

(12)

We now use forward-substitution in the second form of the system in (12). That is, we substitute obtained from the first equation into the second equation of (12). This immediately gives Then substituting both these values into the third equation of (12) yields Since the column matrix Y is now determined, we now solve that is

(13)

We solve the second form of the system in (13) by back-substitution, that is, we substitute x3 = 3 from the third equation into the second equation to obtain x2 = −2. Substituting these two values into the first equation of (13) yields x1 = −1 Hence the solution of the original system is x1 = −1, x2 = −2, x3 = 3. ≡

Relationship to Determinants

If an n × n matrix A has an LU-factorization A = LU, then det A is easy to evaluate using the determinant property det A = det L · det U.

See Theorem 8.5.6 on page 408.

EXAMPLE 6 Determinant of a Factored Matrix

Evaluate the determinant of the matrix A in Example 4.

SOLUTION

From Example 4 an LU-factorization A = LU is

so that

. (14)

Now here is the beauty of this technique. Going back to Theorem 8.5.8 we know that the determinant of a triangular matrix is the product of its main diagonal entries. So with no additional work we have immediately that (14) is

≡

REMARKS

(i) Not every n × n matrix A has an LU-factorization. For example, the 2 × 2 matrix has no LU-factorization. Try the method in Example 2 and see what happens. In general, if interchanges of rows are required in the method illustrated in Examples 3 and 4 in order to obtain U, then we say that an LU-factorization does not exist.

(ii) When solving a linear system AX = B by Gaussian elimination, the steps of that method must be repeated if the coefficient matrix A is the same but the column vector B is changed. The method for solving systems of linear equations illustrated in Example 5 is especially useful if a system AX = B has to be solved for different vectors Bi, = 1, 2, ..., n, since the matrices L and U remain the same in each system and so can be retained in a computer program. See Problems 31–34 in Exercises 8.13.

(iii) If a matrix A already has a 0 below its main diagonal such as

,

then we do not have to zero out the entry in the third row and first column by a row addition. So in the matrix in which we are recording the negatives of the multipliers we simply retain the 0 in the third row and first column.

(iv) Had we chosen the main diagonal entries of U in (3) to be all 1s, then an LU-factorization of a matrix A looks like

(15)

This is called Crout’s method because it was devised by the American mathematician Preston D. Crout (1907–1984). Like the Doolittle method, Crout’s method also gives a unique LU-factorization of A. See Problems 41 and 42 in Exercises 8.13.

(v) Cholesky’s method discovered by the French military officer and mathematician André-Louis Cholesky (1875–1918) is a way of finding an LU-factorization of a symmetric matrix, that is, a matrix A for which A = AT. The form of the factorization for a 3 × 3 symmetric matrix is A = LU = LLT:

(16)

See Problems 43 and 44 in Exercises 8.13.

8.13 Exercises Answers to selected odd-numbered problems begin on page ANS-21.

In Problems 1–10, use the procedure illustrated in Example 2 to find the LU-factorization of the given matrix.

In Problems 11–20, use the procedure illustrated in Examples 3 and 4 to find the LU-factorization of the given matrix.

In Problems 21–30, proceed as in Example 5 and use the corresponding LU-factorization from Problems 1–10 to solve the given linear system of equations.

In Problems 31–34, use the given LU-factorization

to solve the linear system for the given column matrix

In Problems 35–40, proceed as in Example 6 and use an LU-factorization to evaluate the determinant of the indicated matrix A.

  1. A is the matrix in Problem 15
  2. A is the matrix in Problem 16
  3. A is the matrix in Problem 17
  4. A is the matrix in Problem 18
  5. A is the matrix in Problem 19
  6. A is the matrix in Problem 20

In Problems 41 and 42, use Crout’s method discussed in (iv) of the Remarks to obtain an LU-factorization of the indicated matrix A.

  1. A is the matrix in Problem 15
  2. A is the matrix in Problem 16

In Problems 43 and 44, use Cholesky’s method discussed in (v) of the Remarks to obtain an LU-factorization of the indicated symmetric matrix A.

  1. A is the matrix in Problem 17
  2. A is the matrix in Problem 18