Articles / Linear Algebra · Part 18
Matrix Factorization: LU Decomposition for Solving Systems
Learn LU decomposition, factor matrices into lower and upper triangular forms, and solve systems of linear equations using forward and backward substitution.
1. Introduction
When solving a system of linear equations, we often use Gaussian elimination to transform a matrix into an upper triangular form.
But what if we need to solve several systems of equations using the same coefficient matrix but different right-hand sides?
Repeating Gaussian elimination every time would be inefficient.
LU Decomposition solves this problem by breaking a matrix into two simpler matrices:
- L (Lower Triangular Matrix): A matrix with zeros above the main diagonal.
- U (Upper Triangular Matrix): A matrix with zeros below the main diagonal.
Instead of repeatedly performing elimination, we factorize the coefficient matrix once and reuse the factorization.
2. What Is LU Decomposition?
LU decomposition expresses a matrix (A) as the product of two matrices:
\[
\boxed{A=LU}
\]
where:
- (L) is a lower triangular matrix.
- (U) is an upper triangular matrix.
A lower triangular matrix has the form:
\[
L=
\begin{bmatrix}
l_{11}&0&0\
l_{21}&l_{22}&0\
l_{31}&l_{32}&l_{33}
\end{bmatrix}
\]
An upper triangular matrix has the form:
\[
U=
\begin{bmatrix}
u_{11}&u_{12}&u_{13}\\
0&u_{22}&u_{23}\\
0&0&u_{33}
\end{bmatrix}
\]
The idea is to represent a complicated matrix as the product of two matrices that are easier to work with.
3. Understanding LU Decomposition
Consider the matrix:
\[
A=
\begin{bmatrix}
2&1\
4&3
\end{bmatrix}
\]
We want to express it as:
\[
A=LU
\]
Using Gaussian elimination, we eliminate the entry below the first pivot.
The multiplier is:
\[
m_{21}=\frac{4}{2}=2
\]
Perform the row operation:
\[
R_2\rightarrow R_2-2R_1
\]
This gives:
\[
U=
\begin{bmatrix}
2&1\
0&1
\end{bmatrix}
\]
The multiplier used during elimination is stored in the lower triangular matrix (L):
\[
L=
\begin{bmatrix}
1&0\
2&1
\end{bmatrix}
\]
Therefore:
\[
\boxed{
A=
\begin{bmatrix}
1&0\
2&1
\end{bmatrix}
\begin{bmatrix}
2&1\
0&1
\end{bmatrix}
}
\]
Let’s verify the multiplication:
\[
\begin{aligned}
LU
&=
\begin{bmatrix}
1&0\\
2&1
\end{bmatrix}
\begin{bmatrix}
2&1\\
0&1
\end{bmatrix}\\[6pt]
&=
\begin{bmatrix}
2&1\\
4&3
\end{bmatrix}
=A
\end{aligned}
\]
So the decomposition is correct.
4. Solving a System Using LU Decomposition
Consider the system:
\[
\begin{aligned}
2x+y&=5\\
4x+3y&=11
\end{aligned}
\]
Its matrix form is:
\[
A\mathbf{x}=\mathbf{b}
\]
where:
\[
A=
\begin{bmatrix}
2&1\\
4&3
\end{bmatrix},
\qquad
\mathbf{x}=
\begin{bmatrix}
x\\y
\end{bmatrix},
\qquad
\mathbf{b}=
\begin{bmatrix}
5\\11
\end{bmatrix}
\]
We already found:
\[
A=LU
\]
Therefore:
\[
LU\mathbf{x}=\mathbf{b}
\]
Instead of solving this directly, introduce an intermediate vector (\mathbf{z}):
\[
L\mathbf{z}=\mathbf{b}
\]
Then solve:
\[
U\mathbf{x}=\mathbf{z}
\]
This breaks one difficult problem into two easier problems.
5. Step 1: Forward Substitution
First, solve:
\[
L\mathbf{z}=\mathbf{b}
\]
Using our matrices:
\[
\begin{bmatrix}
5\\11
\end{bmatrix}
\]
This gives:
\[
\begin{aligned}
z_1&=5\\
2z_1+z_2&=11
\end{aligned}
\]
Substitute \(z_1=5\):
\[
2(5)+z_2=11
\]
\[
z_2=1
\]
Therefore:
\[
\boxed{
\mathbf{z}=
\begin{bmatrix}
5\\1
\end{bmatrix}
}
\]
This process is called forward substitution because we solve from the first equation toward the last.
6. Step 2: Backward Substitution
Now solve:
\[
U\mathbf{x}=\mathbf{z}
\]
Substituting:
\[
\begin{bmatrix}
5\\1
\end{bmatrix}
\]
This gives:
\[
\begin{aligned}
2x+y&=5\\
y&=1
\end{aligned}
\]
From the second equation:
\[
y=1
\]
Substitute into the first:
\[
2x+1=5
\]
\[
2x=4
\]
\[
x=2
\]
Hence the solution is:
\[
\boxed{x=2,\quad y=1}
\]
We have solved the original system using LU decomposition.
7. LU Decomposition for Larger Matrices
The same idea works for larger matrices.
For a \(3\times3\) matrix:
\[
A=
\begin{bmatrix}
a_{11}&a_{12}&a_{13}\\
a_{21}&a_{22}&a_{23}\\
a_{31}&a_{32}&a_{33}
\end{bmatrix}
\]
We seek:
\[
A=LU
\]
where:
\[
L=
\begin{bmatrix}
1&0&0\\
l_{21}&1&0\\
l_{31}&l_{32}&1
\end{bmatrix}
\]
and:
\[
U=
\begin{bmatrix}
u_{11}&u_{12}&u_{13}\\
0&u_{22}&u_{23}\\
0&0&u_{33}
\end{bmatrix}
\]
Gaussian elimination transforms (A) into (U), while the elimination multipliers are stored in (L).
Once the factorization is obtained, solving (A\mathbf{x}=\mathbf{b}) requires:
- Solve \(L\mathbf{z}=\mathbf{b}\) using forward substitution.
- Solve \(U\mathbf{x}=\mathbf{z}\) using backward substitution.
The same factorization can be reused whenever (A) remains unchanged.
8. What If LU Decomposition Cannot Be Performed Directly?
Sometimes a pivot element becomes zero, or a very small pivot creates numerical instability.
In such cases, we may need to rearrange rows of the matrix before performing elimination.
This leads to LU decomposition with partial pivoting, commonly written as:
\[
\boxed{PA=LU}
\]
Here, (P) is a permutation matrix that represents row swaps.
Pivoting improves numerical stability and allows decomposition in cases where direct LU decomposition may fail.
9. Why LU Decomposition Is Useful
LU decomposition is widely used because it makes solving systems of equations more efficient.
Multiple systems
If we need to solve:
\[
A\mathbf{x}_1=\mathbf{b}_1
\]
and:
\[
A\mathbf{x}_2=\mathbf{b}_2
\]
the matrix (A) does not change.
We can factorize (A) once and then solve each system using forward and backward substitution.
Applications
- Scientific computing and numerical simulations
- Engineering calculations
- Computer graphics
- Machine learning algorithms
- Solving large systems of equations
- Numerical methods in physics and economics
LU decomposition breaks a matrix into a lower triangular matrix and an upper triangular matrix.
Instead of directly solving a system of equations, we solve two simpler systems:
\[
L\mathbf{z}=\mathbf{b}
\]
followed by:
\[
U\mathbf{x}=\mathbf{z}
\]
The main advantage is efficiency, especially when the same coefficient matrix is used with multiple right-hand sides.
Key takeaway: LU decomposition stores the work of Gaussian elimination so that solving systems becomes faster and more organized.
Quick quiz
5 questionsOriginally published at farhanpaal.com — https://farhanpaal.com/articles/matrix-factorization-lu-decomposition-for-solving-systems/
Keep a copy
Read offline as a printout or PDF.
farhanpaal.com