Module for Cholesky, Doolittle and Crout Factorization

Check out the new Numerical Analysis Projects page.

The modern way to solve a linear system  AX = B is to first find the A = LU factorization. Then construct the solution to the linear system  AX = B  by performing the two steps:
1. Solve the lower-triangular system    LY = B  for  Y.
2. Solve the upper-triangular system    UX = Y  for  X.

This will require three subroutines to accomplish: Doolittle,  ForeSub  and  BackSub.
First we will experiment with the Doolittle method for finding L and U.
The Doolittle factorization uses 1's on the diagonal of  L.

The Doolittle Factorization.
Derivation.

Mathematica Subroutine (Doolittle).

The forward elimination subroutine:

Mathematica Subroutine (Forward Elimination).

The back substitution subroutine:

Mathematica Subroutine (Back Substitution).

The Cholesky Decomposition.

    If A is real, symmetric and positive definite matrix, then Cholesky decomposition is

                  

where U an upper triangular matrix.  

Remark.  Observe that is a lower triangular matrix, so that  A = LU.

    The following Cholesky subroutine can be used when the matrix  A  is real, symmetric and positive definite.
Observe that the loop starting with  For[j=k,j<=n,j++,  is not necessary and that  U  is computed by forming the transpose of  L.

The Cholesky factorization subroutine:

Mathematica Subroutine (Cholesky factorization).

Example 1.  Find the  A = LU factorization for the matrix    using the Doolittle method.  
Solution 1.

For curiosity, the reader might be interested in other methods of computing  L  and  U.

The Crout Factorization.
Derivation and Example.
 

The PreCholesky Factorization.
Derivation and Example.

Example 2.  Solve the linear system  LUX = B  where  L, U  and  B  are given below by
    ,  ,  and  .  
Use the forward substitution and back substitution subroutines to construct X.  
Solution 2.

Example 3.  Solve the linear system  AX = B  by finding the  A = LU  factorization with the Doolittle method, where:
        ,  and  .  
Then solve the lower-triangular system  LY = B  for  Y,  then solve the upper-triangular system  UX = Y  for  X.
Use the forward substitution and back substitution subroutines.  
Solution 3.

Example 4.  Find the  A = LU factorization for the matrix    using the Cholesky subroutine.
Remark. The matrix  A  must be real, symmetric and positive definite.  
Solution 4.

Old Lab Project (Doolittle's Method  Doolittle's Method).  Internet hyperlinks to an old lab project.  

Research Experience for Undergraduates

Cholesky, Doolittle and Crout Factorizations  Cholesky, Doolittle and Crout Factorizations    
Internet hyperlinks to web sites and a bibliography of articles.  

Downloads (Cholesky, Doolittle, Crout Factorizations Cholesky, Doolittle, Crout Factorizations).  
Download this Mathematica notebook.  

(c) John H. Mathews 2003