Encyclopedia > LU decomposition

  Article Content

LU decomposition

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.

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.

The gaussian elimination algorithm uses only the third form of the three elementary matrix transformations to make TA upper triangular. Using the properties of these elementary transformations, we calculate the inverse of T which shows us it is a lower triangular matrix L which can be added to the left and right side of the previous equation resulting in:

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
and
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.

See also



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Quioque, New York

... female householder with no husband present, and 42.6% are non-families. 36.3% of all households are made up of individuals and 17.6% have someone living alone who is 65 ...

 
 
 
This page was created in 22 ms