STEP 15

SYSTEMS OF LINEAR EQUATIONS 5*

Use of LU decomposition*

We have shown in STEP 11 how to solve a linear system Ax = b by Gauss elimination, applied to the augmented matrix . In the preceding Step, we have extended the elimination process to calculate the inverse A of the coefficient matrix A, assuming it exists.

Another general approach to solving Ax = b is known as the method of LU decomposition, which provides new insights into matrix algebra and has many theoretical and practical uses. Efficient computer algorithms for handling practical problems can be developed from it.

The symbols L and U denote lower triangular matrix and upper triangular matrices, respectively. Examples of lower triangular matrices are

Note that in such a matrix all elements above the leading diagonal are zero. Examples of upper triangular matrices are:

where now all elements below the leading diagonal are zero. The product of L1 and U1 is

  1. Procedure

    Suppose we have to solve a linear system Ax = b, and that we can express the coefficient matrix A in the form of the socalled LU decomposition A = LU.

    Then we may solve the linear system by the following procedure:

    Stage l: Write Ax = LUx = b.

    Stage 2: Set y = Ux, so that Ax = Ly = b. Use forward substitution on Ly = b to find y1, y2, . . , yn in that order, i.e., suppose the augmented matrix for the system Ly = b is:

    Then forward substitution yields y1 = b1/l11, and, subsequently,

    Note that the value of yi depends on the values y1, y2, . . , yi-1, which have already been calculated.

    Stage 3: Finally, use back-substitution on Ux = y to find xn, . . . , x1x in that order.

    Later on we shall outline a general method for finding LU decompositions of square matrices. The following example shows this method in action, involving the matrix A = L1U1 above. If we wish to solve Ax = b for a number of different bs, then this method is more efficient than Gauss elimination. Once we have found an LU decomposition of A, we need only do forward and backward substitutions to solve the system for any b.

  2. Example

    We shall solve the system

    Stage l: An LU decomposition of the system is

    Stage 2: Set y = U1x and then solve the system L1y = b, i.e.,

    Using forward substitution, we obtain:

    Stage 3: Solve

    Back-substitution now yields:

    Thus the solution of Ax = b is:

    which may be checked, using the original equations. We turn now to the problem of finding an LU decomposition of a given square matrix A.

  3. Realizing an LU decomposition

    For an LU decomposition of a given n x n matrix A, we seek a lower triangular matrix L and an upper triangular matrix U (both of order n x n) such that A = LU. The matrix U may be taken to be the upper triangular matrix resulting from Gauss elimination without partial pivoting (cf. Sections 3 and 5 of STEP 11), and the matrix L may be taken to be the lower triangular matrix which has diagonal elements 1 and which, for k < I, has as the (i, k) element the multiplier mik. This multiplier is calculated at the k-th stage of Gauss elimination and is required to transform the current value of aik to 0. In the notation of Step 11, these multipliers were given by mik = aik/akk, I = k+l, k+2,.. ,n.

    An example will help clarify this. From Step 11, we recall that Gauss elimination, applied to the system

    yielded the upper triangular matrix:

    Also, we saw that in the first stage we calculated the multipliers rn21 = a2l/a11 = 1 / 1= 1 and m3l = a3l/a11 = 2/ 1 = 2, while in the second stage we calculated the multiplier m32 = a32/a22 = -3/1 = -3. Thus

    It is readily verified that LUequals the coefficient matrix of the original system:

    . Another technique that may be used to find an LU decomposition of an n x n matrix is by direct decomposition. In order to illustrate this process, let it be rquired to find an LU decomposition for the 3 x 3 coefficient matrix of the system above. Then the required L and U are of the form

    Note that the total number of unknowns in L and U is 12, whereas there are only 9 elements in the 3 x 3 coefficient matrix A. To ensure that L and U are unique, we need to impose 12 - 9 = 3 extra conditions on the elements of these two triangular matrices. (In the general n x n case, n extra conditions are required.) One common choice is to require all the diagonal elements of L to have the value 1; the resulting method is known as Doolittle's method. Another choice is to require all the diagonal elements of U to be 1; this is Crout's method. Since Doolittle's method will result in the same LU decomposition for A, given above, we shall use Crout's method to illustrate this direct decomposition procedure.

    We then require that

    Multiplication of L and U yields:

    It is clear that this construction by Crout's method yields triangular matrices L and U for which A = LU.

    Checkpoint

    1. What constitutes an LU decomposition of a matrix A?
    2. How is a decomposition A = LU used to solve a linear system Ax = b?
    3. How may an LU decomposition be obtained by Gauss elimination?

    EXERCISES

    1. Find an LU decomposition of the matrix

      where

    2. Solve each of the following systems (Exercises 1 and 3 of STEP 11) by first finding an LU decomposition of the coefficient matrix and then using forward and backward substitutions.