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, and the matrix L may be taken to be the lower triangular matrix which has diagonal elements 1 and which, for k <>, has as the (i, k) element the multiplier m_ik. This multiplier is calculated at the k-th stage of Gauss elimination and is required to transform the current value of a_ik to 0. In the notation of Step 11, these multipliers were given by m_ik = a_ik/a_kk, 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 rn₂₁ = a_2l/a₁₁ = 1 / 1= 1 and m_3l = a_3l/a₁₁ = 2/ 1 = 2, while in the second stage we calculated the multiplier m₃₂ = a₃₂/a₂₂ = -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?