TABLE OF CONTENTS It is possible to show that any square matrix A can be expressed as a product of a lower triangular matrix L and an upper triangular matrix U:
| (2.11) |  |
The process of computing L and U for a given A is known as LU decomposition or LU factorization. LU decomposition is not unique (the combinations of L and U for a prescribed A are endless), unless certain constraints are placed on L or U. These constraints distinguish one type of decomposition from another. Three commonly used decompositions are listed in Table 2.2.
| Name | Constraints |
|---|---|
| Doolittle s decomposition | L ii=1, i = 1, 2, , n |
| Crout s decomposition | U ii=1, i=1, 2, , n |
| Choleski s decomposition | L= U T |
After decomposing A, it is easy to solve the equations Ax= b, as pointed out in Art. 2.1. We first rewrite the equations as LUx= b. Upon using the notation Ux= y, the equations become
which can be solved for y by forward substitution. Then
will yield x by the back substitution process.
The advantage of LU decomposition over the Gauss elimination method is that once A is decomposed, we can solve Ax= b for as many constant vectors b as we please. The cost of each additional solution is relatively small, since the...
