. In the preceding Step,
we have extended the elimination process to calculate the inverse A of the coefficient matrix A and assumed that it exists.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 and assumed that 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. It yields efficient computer algorithms for handling practical problems.
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 all elements below the leading diagonal are zero. The product of L1 and U1 is
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 as follows:
Stage l:
Write Ax = LUx = b.
Stage 2:
Set y = Ux, so that Ax = Ly = b. Use forward substitution with Ly = b to find y1, y2, . . , yn in that order, i.e., assume that 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 with Ux = y to find xn, . . . , x1 in that order.
Later on we shall outline a general method for finding LU decompositions of square matrices. The following example demonstrates this method, involving the matrix A = L1U1 above. If we wish to solve Ax = b for a number of different vectors b, then this method is more efficient than Gauss elimination. Once we have found an LU decomposition of A, we need only forward and backward substitute to solve the system for any b.
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 yields:
Thus, the solution of Ax = b is:
which you may check, using the original equations. We turn now to the problem of finding an LU decomposition of a given square matrix A.
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 (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 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 into 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 to clarify this procedure. 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 LU equals the coefficient matrix of the original system:
.
Another technique which 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´n case, n extra conditions are required.) One common choice is to require all the diagonal elements of L to be 1; the resulting method is known as Doolittle's method. Another choice is make the diagonal elements in U to be 1; this is Crout's method. Since Doolittle's method will give the same in this direct LU decomposition for A, given above, we shall use Crout's method to illustrate 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.
where
