Background

Definition (LU-Factorization).  The nonsingular matrix A has an LU-factorization if it can be expressed as the product of a lower-triangular matrix L and an upper triangular matrix U:  

          .  

When this is possible we say that A has an LU-decomposition.  It turns out that this factorization (when it exists) is not unique.  If L has 1's on it's diagonal, then it is called a Doolittle factorization.  If U has 1's on its diagonal, then it is called a Crout factorization.  When  , it is called a Cholesky decomposition.  In this module we will develop an algorithm that produces a Doolittle factorization.

Theorem (LU Factorization with NO pivoting).  If row interchanges are not needed to solve the linear system AX = B, then A has the LU factorization (illustrated with 4×4 matrices).  

        = .
        
Remark 1.  This is not a linear system.
Remark 2.  The easy solution uses row vectors and is a modification of limited Gauss Jordan elimination.
Remark 3.  A sufficient condition for the factorization to exist is that all principal minors of A are nonsingular.

Proof  LU Factorization  LU Factorization  

Mathematica Subroutine (Limited Gauss-Jordan Elimination).

Computer Programs  LU Factorization  LU Factorization  

Mathematica Subroutine (LandU).

Example 1. Given  .  Find matrices L and U so that LU = A.  
Solution 1.

Example 2. Given  .  Find matrices L and U so that LU = A.  
Solution 2.

Example 3. Given  .  Can A be factored  A = LU?    
Solution 3.

Theorem (A = LU;  Factorization with NO Pivoting).  Assume that A has a Doolittle, Crout or Cholesky factorization.  The solution X to the linear system  , is found in three steps:  

    1.  Construct the matrices  , if possible.  
    2.  Solve    for    using forward substitution.
    3.  Solve    for    using back substitution.

Proof  LU Factorization  LU Factorization  

    The above theorem assumes that there are no row interchanges.  We have seen in Example 3 an example of a nonsingular matrix A could not be directly factored as A = LU.  If row interchanges are permitted then a factorization of a "permuted matrix" will be obtained.  A permutation of the first n positive integers  .  is an arrangement    of these integers in a definite order.  For example,    is a permutation of the five integers  .  The standard base vectors    for    are used in the next definition.  

Definition (Permutation Matrix).  An n×n permutation matrix P is a matrix with precisely one entry whose value is "1" in each column and row, and all of whose other entries are "0."  The rows of  P  are a permutation of the rows of the identity matrix and  P  can be written as  

        .

The elements of    have the form  

          

Theorem.  Suppose that    is a permutation matrix.  The product  PA  is a new matrix whose rows consists of the rows of  A  rearranged in the new order  .  

For example, the permutation matrix    will interchange rows 1 and 2 and also interchange rows 3 and 4.  

Theorem.  If  A  is a nonsingular matrix, then there exists a permutation matrix  P  so that  PA  has an LU-factorization

        PA = LU.  

Theorem (PA = LU;  Factorization with Pivoting).  Given that A is nonsingular.  The solution X to the linear system  , is found in four steps:  

    1.  Construct the matrices  .  
    2.  Compute the column vector   .
    3.  Solve    for    using forward substitution.
    4.  Solve    for    using back substitution.

Proof  LU Factorization  LU Factorization  

Computer Programs  LU Factorization  LU Factorization  

Mathematica Subroutine (LUfactor).
Remark.  The matrix  A  is a global variable and elements are changed when the  LUfactor  subroutine is executed.  Hence, it is important to save a copy of  A  in the variable  A0.
Use one of the following two versions of the  LUfactor  subroutine and the  SolveLU  subroutine.  The first version of  LUfactor  uses parallel programming and "row operations" instead of loops.

This is the second version of  LUfactor  and it uses more loops and traditional programming.

Mathematica Subroutine (LUfactor).

Use the subroutine SolveLU which is similar to the forward substitution and back substitution subroutines.

Mathematica Subroutine (SolveLU).

Remark.  Everything has been carefully set up so that  L,  U, and  P  can all be studied.

Example 4.  Use  PA = LU  factorization with pivoting to solve the linear system  .  
Solution 4.

Example 5.  Use  PA = LU  factorization with pivoting to solve the linear system  .  
Solution 5.

Application to Polynomial Curve Fitting

Theorem (Least-Squares Polynomial Curve Fitting). Given the    data points  ,  the least squares polynomial of degree  m  of the form  

        

that fits the n data points is obtained by solving the following linear system


          

for the m+1 coefficients .  These equations are referred to as the "normal equations".

Proof  Least Squares Polynomials  Least Squares Polynomials  

Example 6.  Find the "least squares parabola" that for the four data points  .  
Solution 6.

Example 7.  Find the "least squares cubic" that for the four data points  .  
Solution 7.

Example 8.  Consider the linear system AC=B in Example 7, i.e.  .

Replace the element    with in matrix A and solve the new system AC=B.
Solution 8.

Old Lab Project (LU Factorization  LU Factorization).  Internet hyperlinks to an old lab project.  

Research Experience for Undergraduates

LU Factorization  LU Factorization  Internet hyperlinks to web sites and a bibliography of articles.  

Download this Mathematica Notebook PA=LU Factorization with Pivoting

Return to Numerical Methods - Numerical Analysis

(c) John H. Mathews 2004