LU-factorization

In linear algebra, a LU decomposition, or LUP 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.

Definition

Let A be a invertible_matrix over a positive definite then we can construct the even simpler Cholesky decomposition

<math>\mathbf{A} = \mathbf{L} \mathbf{L}^{*}<math>

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 from 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

<math>

\mathbf{A}= (a_{n,n}) <math>

We define

<math> \mathbf{A}^{(0)} := \mathbf{A}<math>

then we iterate n = 1,...,N

We eliminate the the matrix elements below the main diagonal in the n-th column by multiplying A with the the following lower triangular matrix from the left

<math>

\mathbf{L}_n = \begin{pmatrix}

\end{pmatrix} <math>

with

<math>l_{i,n} := -\frac{a_{i,n}^{(n)}}{a_{n,n}^{(n)}} \mbox{ , } i = n+1,\ldots,N<math>

We set

<math> \mathbf{A}^{(n)} := \mathbf{L}_n \mathbf{A}^{(n-1)}<math>

After N steps this yields the decomposition

<math>

\begin{matrix} \mathbf{A} = \mathbf{L}_{1}^{-1} \mathbf{L}_{1} \mathbf{A}^{(0)} = \mathbf{L}_{1}^{-1} \mathbf{A}^{(1)} = \mathbf{L}_{1}^{-1} \mathbf{L}_{2}^{-1} \mathbf{L}_{2} \mathbf{A}^{(1)} = \mathbf{L}_{1}^{-1}\mathbf{L}_{2}^{-1} \mathbf{A}^{(2)} = \mathbf{L}_{1}^{-1} \ldots \mathbf{L}_{N}^{-1} \mathbf{A}^{(N)} \end{matrix} <math>

As we eliminated all lower rows the matrix A^(N) has the form of an upper triangular matrix. 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. So we can write our decomposition in the short form

<math>

\mathbf{A} = \mathbf{L}_{1}^{-1} \ldots \mathbf{L}_{N}^{-1}\mathbf{A}^{(N)} = \mathbf{L} \mathbf{U} <math>

Crout algorithm

See main article Crout matrix decomposition

Applications

Solving linear equations

Given a matrix equation

<math>\mathbf{A} \mathbf{x} = \mathbf{L} \mathbf{U} \mathbf{x} = \mathbf{b}<math>

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.

Related articles

• Gaussian elimination
• Cholesky decomposition
• Crout decomposition