LU Decomposition Calculator
Decompose square matrices into lower (L) and upper (U) triangular matrices using Doolittle or Crout methods. Enter your matrix to see step-by-step LU factorization with detailed calculations and solve linear systems efficiently.
Input Matrix A
LU Decomposition
L Matrix
U Matrix
Solve Linear System Ax = b
Understanding LU Decomposition
Matrix Factorization
Decompose matrix A into product of lower triangular matrix L and upper triangular matrix U, where A = LU.
Doolittle Method
L matrix has ones on the diagonal, U matrix contains the computed upper triangular elements.
Crout Method
U matrix has ones on the diagonal, L matrix contains the computed lower triangular elements.
Partial Pivoting
Row exchanges for numerical stability, resulting in PA = LU where P is a permutation matrix.
Mathematical Theory & Applications
What is LU Decomposition?
LU decomposition is a matrix factorization technique that decomposes a square matrix A into the product of a lower triangular matrix L and an upper triangular matrix U. This factorization is fundamental in numerical linear algebra and provides an efficient method for solving linear systems, computing determinants, and matrix inversion.
Basic Form: A = LU
With Pivoting: PA = LU
Doolittle: L has unit diagonal (lᵢᵢ = 1)
Crout: U has unit diagonal (uᵢᵢ = 1)
Historical Development
LU decomposition was developed by mathematicians Myrick Doolittle and Prescott Crout in the early 20th century. The Doolittle method (1878) and Crout method (1941) became standard techniques for solving large systems of linear equations in engineering and scientific computing.
The introduction of partial pivoting by Alan Turing and others improved numerical stability, making LU decomposition a cornerstone of modern computational linear algebra and the foundation for libraries like LAPACK and BLAS.
Decomposition Methods
Doolittle Method
L matrix: lᵢᵢ = 1 for all i
Process row by row from top
Most common in practice
Crout Method
U matrix: uᵢᵢ = 1 for all i
Process column by column
Alternative formulation
Partial Pivoting
Row exchanges for stability
Prevents division by small numbers
Results in PA = LU
Complete Pivoting
Both row and column exchanges
Maximum numerical stability
Results in PAQ = LU
Real-World Applications
Linear System Solving
Efficient solution of Ax=b using forward and back substitution: Ly=b, then Ux=y
Matrix Inversion
Compute A⁻¹ by solving AX=I using LU decomposition for each column of identity matrix
Determinant Calculation
det(A) = det(L) × det(U) = product of diagonal elements of U (for Doolittle)
Finite Element Analysis
Solve large sparse systems in structural mechanics, heat transfer, and fluid dynamics
Circuit Analysis
Nodal analysis and mesh analysis in electrical engineering for complex circuit networks
Computer Graphics
Solve transformation equations, lighting models, and physics simulations in 3D graphics
Machine Learning
Solve normal equations in linear regression and optimization problems in neural networks
Economic Modeling
Input-output analysis, equilibrium models, and optimization in economic systems
Frequently Asked Questions
Doolittle method sets the diagonal of L matrix to 1 (lᵢᵢ = 1), while Crout method sets the diagonal of U matrix to 1 (uᵢᵢ = 1). Both produce the same decomposition but with different computational approaches and storage requirements.
LU decomposition without pivoting fails when a zero appears on the diagonal during the process. This happens for singular matrices or when leading principal minors are zero. Partial pivoting can often resolve this issue.
LU decomposition is more efficient when solving multiple systems with the same coefficient matrix A but different right-hand sides b. Once A=LU is computed, each new system Ax=b can be solved quickly using forward and back substitution.
Partial pivoting selects the largest element in each column as the pivot, avoiding division by small numbers that can amplify rounding errors. This significantly improves the numerical stability of the decomposition, especially for ill-conditioned matrices.
LU decomposition has O(n³/3) time complexity for an n×n matrix, which is about 1/3 the cost of Gaussian elimination. The space complexity is O(n²) for storing the L and U matrices, though they can often share the same storage as the original matrix.
First decompose A=LU, then solve in two steps: (1) Forward substitution: solve Ly=b for y, (2) Back substitution: solve Ux=y for x. This two-step process is more efficient than direct Gaussian elimination for multiple right-hand sides.
Standard LU decomposition requires square matrices. For rectangular matrices, you can use QR decomposition or singular value decomposition (SVD). However, LU decomposition can be extended to rectangular matrices with appropriate modifications.