LU Decomposition, also known as LU Factorization, is a method of decomposing a square matrix into two triangular matrices: a lower triangular matrix L and an upper triangular matrix U. This is useful for solving linear equations, computing determinants, and inverting matrices efficiently.
What is LU Decomposition?
LU Decomposition expresses a matrix A as:
\[ A = LU \]where:
- L is a lower triangular matrix with ones on the diagonal.
- U is an upper triangular matrix.
Step-by-Step Process
Consider the matrix:
\[ A = \begin{bmatrix} 2 & 3 & 1 \\ 4 & 7 & 3 \\ 6 & 18 & 5 \end{bmatrix} \]Step 1: Initialize L as an Identity Matrix
Start with an identity matrix for \( L \):
\[ L = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \]Step 2: Convert A into an Upper Triangular Form (Build U)
We perform row operations to eliminate elements below the main diagonal:
First, eliminate below the first pivot (2 in row 1, column 1):
- Row 2: Subtract \( 2 \times \) Row 1 from Row 2. - Row 3: Subtract \( 3 \times \) Row 1 from Row 3. \[ \begin{bmatrix} 2 & 3 & 1 \\ 0 & 1 & 1 \\ 0 & 9 & 2 \end{bmatrix} \]Simultaneously, update \( L \) with the multipliers used:
\[ L = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 3 & 0 & 1 \end{bmatrix} \]Step 3: Eliminate Below the Second Pivot
Now, eliminate the element below the second pivot (1 in row 2, column 2):
- Row 3: Subtract \( 9 \times \) Row 2 from Row 3. \[ \begin{bmatrix} 2 & 3 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & -7 \end{bmatrix} \]Again, update \( L \) with the multiplier used:
\[ L = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 3 & 9 & 1 \end{bmatrix} \]Step 4: Verify the Decomposition
We now have:
\[ L = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 3 & 9 & 1 \end{bmatrix} \quad \text{and} \quad U = \begin{bmatrix} 2 & 3 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & -7 \end{bmatrix} \]Multiplying \( L \) and \( U \) should give back the original matrix \( A \).
- Express the matrix as the product of a lower and upper triangular matrix.
- Use Gaussian elimination to transform the matrix.
- Keep track of row multipliers to construct the lower matrix.
Practice Problems
Find the LU decomposition for the following matrices:
Problem 1:
\[ A = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 10 \end{bmatrix} \]Solution:
Step 1: Start with \( L \) as an identity matrix.
Step 2: Perform Gaussian elimination while tracking multipliers.
\[ U = \begin{bmatrix} 1 & 2 & 3 \\ 0 & -3 & -6 \\ 0 & 0 & 1 \end{bmatrix} \quad \text{and} \quad L = \begin{bmatrix} 1 & 0 & 0 \\ 4 & 1 & 0 \\ 7 & 2 & 1 \end{bmatrix} \]Multiplying \( L \) and \( U \) gives back \( A \), confirming correctness.
Problem 2:
\[ A = \begin{bmatrix} 3 & -7 & -2 \\ -3 & 5 & 1 \\ 6 & -4 & 0 \end{bmatrix} \]Solution:
Step 1: Start with \( L \) as an identity matrix.
Step 2: Use Gaussian elimination and track row multipliers.
\[ U = \begin{bmatrix} 3 & -7 & -2 \\ 0 & -1 & -1 \\ 0 & 0 & 2 \end{bmatrix} \quad \text{and} \quad L = \begin{bmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 2 & -2 & 1 \end{bmatrix} \]Verifying \( A = LU \), the decomposition is correct.
Conclusion
LU Decomposition is a fundamental matrix factorization technique that simplifies solving linear systems. It is a core component in numerical methods and computational linear algebra.