Configure LU Decomposition
Enter a square matrix and optionally solve Ax = b.
Example matrices
P is a permutation matrix, L is lower triangular, and U is upper triangular.
Decomposition Results
Calculation completeFactorization Verification
The following matrices are calculated using Gaussian elimination with the selected pivoting method.
Permutation Matrix P
Lower Triangular Matrix L
Upper Triangular Matrix U
Reconstructed Matrix PA
Permuted original matrix PA
Product LU
These matrices should agree within floating-point precision.
Solving the Linear System Ax = b
Step-by-Step Gaussian Elimination
Follow the pivot selection, row exchanges, elimination multipliers, and triangular matrix construction.
What Is LU Decomposition?
LU decomposition, also called LU factorization, is a matrix factorization technique that expresses a square matrix as the product of two triangular matrices.
The letter L represents a lower triangular matrix, while U represents an upper triangular matrix.
When row exchanges are required, a permutation matrix is introduced:
In this representation:
- P: Permutation matrix that records row exchanges.
- L: Lower triangular matrix with ones on its diagonal.
- U: Upper triangular matrix.
- A: Original square matrix.
1. Lower triangular matrix
A lower triangular matrix contains zeros above its main diagonal. In the Doolittle convention, its diagonal entries are all one.
2. Upper triangular matrix
An upper triangular matrix contains zeros below its main diagonal.
3. Permutation matrix
A permutation matrix is obtained by rearranging the rows of an identity matrix. Multiplication by P on the left rearranges the rows of A.
In this example, the first two rows are exchanged.
How Does LU Decomposition Work?
LU decomposition is closely related to Gaussian elimination. During elimination, the multipliers used to eliminate entries below the pivot are stored in L, while the resulting upper triangular matrix becomes U.
Doolittle's method
In Doolittle's method, the diagonal entries of L are set to one. The matrix factors can be calculated using the following formulas.
These formulas describe the factorization when the required pivots are nonzero. Partial pivoting extends the method by exchanging rows when necessary.
Partial pivoting
Partial pivoting selects the entry with the largest absolute value in the current pivot column, among the remaining rows. The selected row is moved into the pivot position.
This reduces the likelihood of division by zero or very small pivot values and generally improves numerical stability.
When rows are exchanged during elimination, the corresponding previously calculated entries of L must also be exchanged. This preserves the factorization identity.
Worked Example of LU Decomposition
Consider the matrix:
We want to find lower triangular L and upper triangular U such that A = LU.
Step 1: Find the first row of U
The first row of U is the first row of A:
Step 2: Find the first column of L
The first diagonal element of L is one. The remaining entry is calculated by dividing the corresponding matrix entry by the first pivot.
Step 3: Calculate the remaining entry of U
Step 4: Construct L and U
Step 5: Verify the result
Therefore, the decomposition is correct.
Solving Linear Systems Using LU Decomposition
One of the most important applications of LU decomposition is solving systems of linear equations.
Consider:
If the matrix factorization is known, the equation becomes:
Introduce an intermediate vector y:
Forward substitution
The first triangular system is solved from top to bottom because L is lower triangular.
Backward substitution
The second triangular system is solved from bottom to top because U is upper triangular.
The main advantage is that once a matrix has been factorized, multiple systems with different right-hand-side vectors can be solved efficiently by reusing L and U.
Determinant Using LU Decomposition
The determinant of a triangular matrix is the product of its diagonal entries.
Since the decomposition satisfies PA = LU:
Therefore:
Every row exchange changes the sign of the determinant. Consequently, the sign of the determinant depends on whether the number of row exchanges is even or odd.
Applications of LU Decomposition
LU decomposition is widely used in numerical mathematics and scientific computing.
- Solving linear equations: Efficiently solve systems of simultaneous equations.
- Numerical analysis: Factor matrices used in numerical algorithms.
- Engineering: Solve structural, electrical, and mechanical system equations.
- Computer simulations: Perform repeated calculations using the same coefficient matrix.
- Scientific computing: Support computational models in physics, chemistry, and applied mathematics.
- Economics: Solve systems of equations in economic models.
- Optimization: Support numerical methods involving linear systems.
Frequently Asked Questions
1. What is LU decomposition?
LU decomposition is a matrix factorization method that expresses a square matrix as the product of a lower triangular matrix L and an upper triangular matrix U. When row exchanges are necessary, the form PA = LU is used.
2. What is the difference between LU and LUP decomposition?
Standard LU decomposition expresses A as LU without row permutations. LUP decomposition introduces a permutation matrix P to account for row exchanges.
3. Why is partial pivoting important?
Partial pivoting chooses the largest absolute entry in the current pivot column. This helps avoid zero pivots and reduces numerical errors caused by very small pivot values.
4. Can every square matrix be decomposed into LU?
Not every matrix has a standard LU decomposition without row exchanges. Partial pivoting allows nonsingular square matrices to be factorized in the form PA = LU, subject to exact arithmetic and numerical limitations.
5. What happens if the matrix is singular?
A singular matrix has a determinant of zero and cannot be used to obtain a unique solution to every linear system. Its LU factorization may encounter a zero pivot, even with partial pivoting.
6. What is the difference between L and U?
L is lower triangular, meaning its entries above the main diagonal are zero. U is upper triangular, meaning its entries below the main diagonal are zero.
7. How is the determinant calculated from LU?
Multiply the diagonal entries of U and account for the sign of the row permutation. Each row exchange changes the determinant's sign.
8. Can LU decomposition solve multiple systems?
Yes. Once a matrix has been factorized, the same L and U matrices can be reused for multiple right-hand-side vectors.
9. What is the computational complexity?
LU decomposition generally requires O(n³) arithmetic operations. Forward and backward substitution each require O(n²) operations.
10. What is the difference between LU decomposition and Gaussian elimination?
Gaussian elimination transforms a matrix into upper triangular form through row operations. LU decomposition stores the elimination multipliers in L and the resulting upper triangular matrix in U.