|
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 systems of linear equations.
Definition
Let A be an invertible matrix over a field. The matrix A can be decomposed as - P - 1A = LU
- A = LUP
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 = LU.
Notes If the matrix A is positive definite we can construct the even simpler Cholesky decomposition - A = LL *
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 = (an,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
for . This can be done by multiplying A(n-1) to the left with the lower triangular matrix -
We set - A(n): = LnA(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 -
Denote the upper triangular matrix A(N-1) by U, and . Because the inverse of a lower triangular matrix Ln 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 = LU.
It is clear that in order for this algorithm to work, one needs to have at each step (see the definition of li,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 - 1A = LU.
Crout algorithm Main article Crout matrix decomposition
Applications
Solving linear equations Given a matrix equation - Ax = LUx = 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.
Related articles
See also | 
Feeds |
Contact