LU Decomposition

A procedure for decomposing an N×N matrix A into a product of a lower triangular matrix L and an upper triangular matrix U,


LU decomposition is implemented in the Wolfram Language as LUDecomposition[m].

Written explicitly for a 3×3 matrix, the decomposition is

 [l_(11) 0 0; l_(21) l_(22) 0; l_(31) l_(32) l_(33)][u_(11) u_(12) u_(13); 0 u_(22) u_(23); 0 0 u_(33)]=[a_(11) a_(12) a_(13); a_(21) a_(22) a_(23); a_(31) a_(32) a_(33)]
 [l_(11)u_(11) l_(11)u_(12) l_(11)u_(13); l_(21)u_(11) l_(21)u_(12)+l_(22)u_(22) l_(21)u_(13)+l_(22)u_(23); l_(31)u_(11) l_(31)u_(12)+l_(32)u_(22) l_(31)u_(13)+l_(32)u_(23)+l_(33)u_(33)]=[a_(11) a_(12) a_(13); a_(21) a_(22) a_(23); a_(31) a_(32) a_(33)].

This gives three types of equations

 i<j    l_(i1)u_(1j)+l_(i2)u_(2j)+...+l_(ii)u_(ij)=a_(ij)
 i=j    l_(i1)u_(1j)+l_(i2)u_(2j)+...+l_(ii)u_(jj)=a_(ij)
 i>j    l_(i1)u_(1j)+l_(i2)u_(2j)+...+l_(ij)u_(jj)=a_(ij).

This gives N^2 equations for N^2+N unknowns (the decomposition is not unique), and can be solved using Crout's method. To solve the matrix equation


first solve Ly=b for y. This can be done by forward substitution


for i=2, ..., N. Then solve Ux=y for x. This can be done by back substitution


for i=N-1, ..., 1.

See also

Gaussian Elimination, Lower Triangular Matrix, Matrix Decomposition, Cholesky Decomposition, QR Decomposition, Triangular Matrix, Upper Triangular Matrix

Explore with Wolfram|Alpha


Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. "LU Decomposition and Its Applications." §2.3 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 34-42, 1992.

Referenced on Wolfram|Alpha

LU Decomposition

Cite this as:

Weisstein, Eric W. "LU Decomposition." From MathWorld--A Wolfram Web Resource.

Subject classifications