math lessons - LU decomposition

where P is a permutation matrix (as is P^-1), L is a lower triangular matrix, and U is an upper triangular matrix. Sometimes the permutation matrix can be chosen to be the identity matrix. In this case the decomposition becomes $A = L U .$

Notes

If the matrix A is positive definite we can construct the even simpler Cholesky decomposition

A = L L *

with L a lower triangular matrix with positive diagonal entries, and L^* the conjugate transpose of L.

Main idea

The LU decomposition is basically a modified form of Gaussian elimination. We transform the matrix A into an upper triangular matrix U by eliminating the entries below the main diagonal. The elimination is done column by column starting from the left, by multiplying A to the left with atomic lower triangular matrices.

Algorithms

There are two different algorithms to construct a LU-decomposition. The Doolittle decomposition constructs a unit lower triangular matrix and an upper triangular matrix, whereas the Crout algorithm constructs a lower triangular matrix and an unit upper triangular matrix.

Doolittle algorithm

Given an NxN matrix

A = (a n, n)

we define

A (0) : = A

and then we iterate n = 1,...,N-1 as follows.

We eliminate the matrix elements below the main diagonal in the n-th column of A^(n-1) by adding to i-th row of this matrix the n-th row multiplied by

$l_{i,n} := -\frac{a_{i,n}^{(n-1)}}{a_{n,n}^{(n-1)}}$

for $i = n+1,\ldots,N$ . This can be done by multiplying A^(n-1) to the left with the lower triangular matrix

$L_n = \begin{pmatrix} 1 & & & & & 0 \\ & \ddots & & & & \\ & & 1 & & & \\ & & l_{n+1,n} & \ddots & & \\ & & \vdots & & \ddots & \\ 0 & & l_{N,n} & & & 1 \\ \end{pmatrix}.$

We set

A (n) : = L n A (n - 1) .

After N-1 steps, we eliminated all the matrix elements below the main diagonal, so we obtain an upper triangular matrix A^(N-1). We find the decomposition

$A = L_{1}^{-1} L_{1} A^{(0)} = L_{1}^{-1} A^{(1)} = L_{1}^{-1} L_{2}^{-1} L_{2} A^{(1)} = L_{1}^{-1}L_{2}^{-1} A^{(2)} =\ldots = L_{1}^{-1} \ldots L_{N-1}^{-1} A^{(N-1)}.$

Denote the upper triangular matrix A^(N-1) by U, and $L=L_{1}^{-1} \ldots L_{N-1}^{-1}$ . Because the inverse of a lower triangular matrix L_n is again a lower triangular matrix, and the multiplication of two lower triangular matrices is again a lower triangular matrix, it follows that L is a lower triangular matrix. We obtain $A = L U$ .

It is clear that in order for this algorithm to work, one needs to have $a_{n,n}^{(n-1)}\not=0$ at each step (see the definition of $l i, n$ ). If this assumption fails at some point, one needs to interchange n-th row with another row below it before continuing. This is why the LU decomposition in general looks like $P - 1 A = L U$ .

Crout algorithm

Main article Crout matrix decomposition

Applications

Solving linear equations

Given a matrix equation

A x = L U x = b

we want to solve the matrix A for a given b. Triangular matrices (upper and lower) can be solved directly using forward and backward substitution without using the slow Gaussian elimination process. So when we have to solve a matrix equation multiple times for different b it is faster to do a LU-decomposition of the matrix once and then solve the triangular matrices for the different b than to use Gaussian elimination each time.

Inverse matrix

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

Mathematics Encyclopedia and Lessons

Lessons

Popular
Subjects

References

LU decomposition

Definition

Notes

Main idea