TOPICS
Search

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=A.
(1)

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)]
(2)
[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)].
(3)

This gives three types of equations

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

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

Ax=(LU)x=L(Ux)=b,
(7)

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

y_1=(b_1)/(l_(11))
(8)
y_i=1/(l_(ii))(b_i-sum_(j=1)^(i-1)l_(ij)y_j)
(9)

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

x_N=(y_N)/(u_(NN))
(10)
x_i=1/(u_(ii))(y_i-sum_(j=i+1)^(N)u_(ij)x_j)
(11)

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

References

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. https://mathworld.wolfram.com/LUDecomposition.html

Subject classifications