Tricki
a repository of mathematical know-how

LU factorization

Quick description

The LU factorization is perhaps the most common method for solving linear systems of equations. It is equivalent to Gaussian elimination, but preserves information so that new systems with the same matrix can be solved efficiently. This factorization has the form

 A = LU

where L is lower triangular (that is, \ell_{ij}=0 if j>i), and U is upper triangular (that is u_{ij}=0 if i>j).

Usually it is used in a modified form PA=LU where P is a permutation matrix (that is, all entries are zero or one, and only one entry in each row and in each column is non-zero).

Prerequisites

Linear algebra.

Example 1

To compute the LU factorization use recursion, which is essentially the algorithmic version of induction.

The 1\times 1 case is easy: [a_{11}]=[1]\,[a_{11}].

If

 A = \left[\begin{array}{cc} A_1&b\\ c^T&d \end{array}\right]

then we can recursively compute the LU factorization of A_1=L_1 U_1. Then an LU factorization of A can be given by

 A = \left[\begin{array}{cc} L_1 & \\ m^T&1\end{array}\right] \left[\begin{array}{cc} U_1 & v\\ &w\end{array}\right]

where L_1 v = b, m^T U_1 =c^T, and m^T v+w = d, which can all be solved provided A_1 is non-singular.

General discussion

This method can be modified to give a constructive proof of the existence of the LU factorization provided every principal (north-west) square submatrix of A is non-singular. This recursive construction creates an L matrix with 1's on the diagonal. It can be easily modified to create a U matrix with 1's on the diagonal.

A different recursive construction can be given where we use the decomposition

 A = \left[\begin{array}{cc} \alpha&\beta^T\\ \gamma&A_1 \end{array}\right].

This gives equivalent computations, but done in a different order.

Comments

Title

Could this article perhaps have a more informative title? If you don't already know what LU factorization is, then the title gives you no clue where this tool might be helpful!