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 |
|
2 Main idea 3 Algorithm 4 Applications 5 Related articles |
Let A be an invertible matrix. Then A can be decomposed as
The LU decomposition is similar to Gaussian elimination. In gaussian elimination we are trying to solve the matrix equation
During the LU decomposition on the other hand b is not transformed and the matrix equation can be written as
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 TN ... T2 T1=T, then the upper triangular matrix is:
Thus we have the decomposition of the matrix A into the product of L and U:
The matrices L and U can be used to calculate the matrix inverse. Computer implementations that invert matrices often use this approach.
Definition
where P is a permutation matrix, L is a lower triangular matrix and U is an upper triangular matrix. Main idea
The elimination process yields an upper triangular matrix U and transforms the vector b into b›
As U is an upper triangualar matrix this equation is very easy to solve.
so we can reuse the decomposition if we want to solve the same equation for a different '\'b''.Algorithm
The inverse of the matrix T is :
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 Ti-1 are lower triangular (see elementary matrix transformations). Being a product of the Ti-1 also:
is lower triangular.Applications
Inverse Matrix
Related articles