Basic Idea of the Method

The Gauss Elimination Method has the disadvantage that all right-hand sides (i.e. all the vectors of interest for a given problem) must be known in advance for the elimination step to proceed. The LU Decomposition Method outlined here has the property that the matrix modification (or decomposition) step can be performed independent of the right hand side vector. This feature is quite useful in practice - therefore, the LU Decomposition Method is usually the Direct Scheme of choice in most applications.

To develop the basic method, let's break the coefficient matrix into a product of two matrices,

where is a lower triangular matrix and is an upper triangular matrix.

Now, the original system of equations,

becomes

This expression can be broken into two problems,

The rationale behind this approach is that the two systems given in eqn. (6.5) are both easy to solve; one by forward substitution and the other by back substitution. In particular, because is a lower diagonal matrix, the expression, , can be solved with a simple forward substitution step. Similarly, since has upper triangular form, can be evaluated with a simple back substitution algorithm.

Thus the key to this method is the ability to find two matrices, , that satisfy eqn. (6.2). Doing this is referred to as the Decomposition Step and there are a variety of algorithms available. Three specific approaches are as follows:

Doolittle Decomposition:

Because of the specific structure of the matrices, a systematic set of formulae for the components of results.

Crout Decomposition:

The evaluation of the components of is done in a similar fashion as above.

Cholesky Factorization:

For symmetric, positive definite matrices, where

then,

and a simple set of expressions for the elements of can be obtained (as above).

Other factorizations of this type are also possible (see a good numerical methods text). Once the elements of are available (usually stored in a single NxN matrix), the solution step for the unknown vector, , is a simple process [as outlined above in eqn. (6.5)]. Matlab's standard equation solver (using the backslash notation, x = A\b), uses several variants of the basic LU Decomposition method depending on the form of the original coefficient matrix (see the Matlab help files for details).