The A = LU Factorizations. 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.

 Derivation of the Doolittle Factorization.

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

Derivation and example of the Crout Factorization.

Derivation and example of the PreCholesky Factorization.

The forward elimination subroutine:

The back substitution subroutine:

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:

Exercise 1.  Find the  A = LU factorization for the following matrix using the Doolittle method.

Solution.

Exercise 2.  Solve the linear system  LUX = B  where  L, U  and  B  are given below.

Use the forward substitution and back substitution subroutines to construct X.

Solution.

First, solve the lower-triangular system    LY = B  for  Y.

Verify that  LY = B.

Second, solve the upper-triangular system    UX = Y  for  X.

Verify that  UX = Y.  

Therefore X is the solution to  LUX = B.
And we can verify that it is the solution.

Exercise 3.  Solve the linear system  AX = B  by finding the  A = LU  factorization with the Doolittle method.

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.

First, solve the lower-triangular system    LY = B  for  Y.

Verify that  LY = B.

Second, solve the upper-triangular system    UX = Y  for  X.

Verify that  UX = Y.  

Therefore X is the solution to  LUX = B. and hence AX = B
And we can verify that it is the solution.

Exercise 4.  Find the  A = LU factorization for the following matrix using the Cholesky subroutine.

Remark. The matrix A must be real, symmetric and positive definite.

Solution.

(c) John H. Mathews