In linear algebra, LU Decomposition, i.e., lower–upper (LU) decomposition or factorization of a matrix, can be defined as the product of a lower and an upper triangular matrices. This product sometimes comprises a permutation matrix as well. We can relate the LU decomposition method with the matrix form of the Gaussian elimination method of solving a system of linear equations. In this article, you will learn the LU Decomposition method and the solved example in detailed steps.
LU Decomposition Method or Factorisation
Consider the system of equations in three variables:
a11x1 + a12x2 + a13x3 = b1
a21x1 + a22x2 + a23x3 = b2
a31x1 + a32x2 + a33x3 = b3
These can be written in the form of AX = B as:
\(\begin{array}{l}\begin{bmatrix}a_{11} & a_{12} & a_{13} \\a_{21} & a_{22} & a_{23} \\a_{31} & a_{32} & a_{33} \\\end{bmatrix}\ \begin{bmatrix}x_1 \\x_2 \\x_3\end{bmatrix}=\begin{bmatrix}b_1 \\b_2 \\b_3\end{bmatrix}\end{array} \)
Here,
\(\begin{array}{l}A=\begin{bmatrix}a_{11} & a_{12} & a_{13} \\a_{21} & a_{22} & a_{23} \\a_{31} & a_{32} & a_{33} \\\end{bmatrix},\ X=\begin{bmatrix}x_1 \\x_2 \\x_3\end{bmatrix},\ B=\begin{bmatrix}b_1 \\b_2 \\b_3\end{bmatrix}\end{array} \)
Now follow the steps given below to solve the above system of linear equations by LU Decomposition method.
Step 1: Generate a matrix A = LU such that L is the lower triangular matrix with principal diagonal elements being equal to 1 and U is the upper triangular matrix.
That means,
\(\begin{array}{l}L=\begin{bmatrix}1 & 0 & 0 \\l_{21} & 1 & 0 \\l_{31} & l_{32} & 1 \\\end{bmatrix}\end{array} \)
and\(\begin{array}{l}U=\begin{bmatrix}u_{11} & u_{12} & u_{13} \\0 & u_{22} & u_{23} \\0 & 0 & u_{33} \\\end{bmatrix}\end{array} \)
Step 2: Now, we can write AX = B as:
LUX = B….(1)
Step 3: Let us assume UX = Y….(2)
\(\begin{array}{l}\text{Where } Y=\begin{bmatrix}y_1 \\y_2 \\y_3 \\\end{bmatrix}\end{array} \)
Step 4: From equations (1) and (2), we have;
LY = B
On solving this equation, we get y1, y2, y3.
Step 5: Substituting Y in equation (2), we get UX = Y
By solving equation, we get X, x1, x2, x3.
The above process is also called the Method of Triangularisation.
Read more:
|
|---|
LU Decomposition Example
Let’s understand how to solve the system of linear equations in three variables by LU Decomposition method with the help of an solved example given below.
Example:
Solve the system of equations x1 + x2 + x3 = 1, 3x1 + x2 – 3x3 = 5 and x1 – 2x2 – 5x3 = 10 by LU decomposition method.
Solution:
Given system of equations are:
x1 + x2 + x3 = 1
3x1 + x2 – 3x3 = 5
x1 – 2x2 – 5x3 = 10
These equations are written in the form of AX = B as:
\(\begin{array}{l}\begin{bmatrix}1 & 1 & 1 \\3 & 1 & -3 \\1 & -2 & -5 \\\end{bmatrix}\ \begin{bmatrix}x_1 \\x_2 \\x_3\end{bmatrix}=\begin{bmatrix}1 \\ 5\\10\end{bmatrix}\end{array} \)
Step 1: Let us write the above matrix as LU = A.
That means,
\(\begin{array}{l}\begin{bmatrix}1 & 0 & 0 \\l_{21} & 1 & 0 \\l_{31} & l_{32} & 1 \\\end{bmatrix}\begin{bmatrix}u_{11} & u_{12} & u_{13} \\0 & u_{22} & u_{23} \\0 & 0 & u_{33} \\\end{bmatrix}=\begin{bmatrix}1 & 1 & 1 \\3 & 1 & -3 \\1 & -2 & -5 \\\end{bmatrix}\end{array} \)
By expanding the left side matrices, we get;
\(\begin{array}{l}\begin{bmatrix}u_{11} & u_{12} & u_{13} \\l_{21}u_{11} & l_{21}u_{12}+u_{22} & l_{21}u_{13} + u_{23} \\l_{31}u_{11} & l_{31}u_{12} + l_{32}u_{22} & l_{31}u_{13}+l_{32}u_{23}+u_{33} \\\end{bmatrix}=\begin{bmatrix}1 & 1 & 1 \\3 & 1 & -3 \\1 & -2 & -5 \\\end{bmatrix}\end{array} \)
Thus, by equating the corresponding elements, we get;
u11 = 1, u12 = 1, u13 = 1
l21u11 = 3,
l21u12 + u22 = 1,
u21u13 + u23 = -3
l31u11 = 1,
l31u12 + l32u22 = -2,
l31u13 + l32u23 + u33 = -5
Solving these equations, we get;
u22 = -2, u23 = -6, u33 = 3
l21 = 3, l31 = 1, l32 = 3/2
Step 2: LUX = B
Step 3: Let UX = Y
Step 4: From the previous two steps, we have LY = B
Thus,
\(\begin{array}{l}\begin{bmatrix}1 & 0 & 0 \\3 & 1 & 0 \\1 & \frac{3}{2} & 1 \\\end{bmatrix}\ \begin{bmatrix}y_1 \\y_2 \\y_3\end{bmatrix}=\begin{bmatrix}1 \\ 5\\10\end{bmatrix}\end{array} \)
So,
y1 = 1
3y1 + y2 = 5
y1 + (3/2)y2 + y3 = 10
Solving these equations, we get;
y1 = 1, y2 = 2, y3 = 6
Step 5: Now, consider UX = Y. So,
\(\begin{array}{l}\begin{bmatrix}1 & 1 & 1 \\0 & -2 & -6 \\0 & 0 & 3 \\\end{bmatrix}\ \begin{bmatrix}x_1 \\x_2 \\x_3\end{bmatrix}=\begin{bmatrix}1 \\ 2\\6\end{bmatrix}\end{array} \)
By expanding this equation, we get;
x1 + x2 + x3 = 1
-2x2 – 6x3 = 2
3x3 = 6
Solving these equations, we can get;
x3 = 2, x2 = -7 and x1 = 6
Therefore, the solution of the given system of equations is (6, -7, 2).
LU Decomposition Method Problems
- Solve the following equations by LU decomposition method.
6x1 + 18x2 + 3x3 = 3, 2x1 + 12x2 + x3 = 19, 4x1 + 15x2 + 3x3 = 0
- Solve the below given system of equations by LU decomposition.
x + y + z = 1, 4x + 3y – z = 6, 3x + 5y + 3z = 4 - Find the solution of the system of equations by LU decomposition.
x + 2y + 3z = 9, 4x + 5y + 6z = 24, 3x + y – 2z = 4
To learn similar methods of solving the system of linear equations, visit byjus.com today!
