LU decomposition, or Doolittle decomposition is the process of decomposing a matrix into a product of an upper-triangular matrix U and a lower triangular matrix L. LU decomposition is LUP decomposition, where P is the identity matrix. In this article, it is represented by the variable T.
Table of contents |
2 Solving 3 Applications 4 Related articles |
Factorization
The basic line of thought to get this upper and lower triangular matrix is as follows.
Using gaussian elimination on a matrix A we actually apply a number of elementary matrix transformations to obtain an upper triangular matrix U and then use back substitution to quickly solve the problem.
Suppose T is the product of all elementary transformations and applying it to A, this gives us:
- TAx=Tb, with TA=U, upper triangular,
- resulting in Ux=Tb.
- Ux=T1 T2 ... Tn b, with T1-1 T2-1 ... Tn-1 = L
- ⇒ LUx=b.
Solving
Once the upper and lower triangular matrices are known, solving this equation becomes very efficient as it can be split up into:- Lz=b using forward substitution
- Ux=x using backward substition, both solvable in O(n2) time.
Applications
The matrices L and U can be used to calculate the matrix inverse. Computer implementations that invert matrices often use this approach.
Related articles