LU decomposition

In linear algebra, a LU decomposition, or LUP decomposition or Doolittle decomposition is a matrix decomposition of a matrix into a lower triangular matrix L, an upper-triangular matrix U and a permutation matrix P. This decomposition is used in numerical analysis to solve a system of linear equations.

Table of contents

1 Definition

2 Algorithm 1

3 Algorithm 2

4 Applications

4.1 Inverse Matrix
4.2 Solving of matrix equations

5 Related articles

Definition

Let A be an invertible matrix. Then A can be decomposed as

P A = L U

where P is a permutation matrix, L is a lower triangular matrix and U is an upper triangular matrix.

Algorithm 1

By applying a series of elementary matrix transformations (i.e. multiplications of A on the left) we construct an upper triangular matrix U starting from A. This method is called the Gauss method. These elementary matrix transformations are all of the linear combinator transformation type (the third listed type in the entry "elementary matrix transformations").Suppose T is the product of N transformations T_N ... T₂ T₁=T, then the upper triangular matrix is:

TA = T_N ... T₂ T₁A =: U.

The inverse of the matrix T is :

T ^-1 = T₁^-1 T₂^-1 ... T_N^-1.

As the gaussian elimination algorithm uses only the third form of the three types of elementary matrix transformations to make A upper triangular, we can infer that all the T_i^-1 are lower triangular (see elementary matrix transformations). Being a product of the T_i^-1 also:

T ^-1 = T₁^-1 T₂^-1 ... T_N^-1 =:L

is lower triangular.

Thus we have the decomposition of the matrix A into the product of L and U:

LU = T ^-1TA = A.

Algorithm 2

Here is a direct method for decomposing an matrix into the product of a lower triangular matrix and an upper triangular matrix ,

For a matrix, this becomes:

This gives three types of equations

This gives $N 2$ equations for $N 2 + N$ unknowns (the decomposition is therefore not unique); the system can be solved using Crout's method.

Applications

Inverse Matrix

The matrices L and U can be used to calculate the matrix inverse. Computer implementations that invert matrices often use this approach.

Solving of matrix equations

Given a matrix equation and the LU decomposition of A

first solve for . This can be done by forward substitution

for i=2,...,N. Then solve for . This can be done by back substitution

for i=N-1,...,1

This algorithm for solving matrix equations takes O(n²) operations (excluding the LU decomposition) and is therefore much faster than using Gauss algorithm.