Linear Algebra: LU Decomposition, with Python

Author:Murphy | View: 29989 | Time: 2025-03-23 19:57:57

The first article of this Linear Algebra series has introduced how to solve a linear system using Gaussian elimination and the previous article also explained how to find an inverse matrix and also how to use the inverse matrix to solve the linear system. This article will introduce another way to solve the linear system using LU decomposition.

LU Decomposition

Lower-Upper (LU) decomposition is a way to factorize a matrix as the product of a lower triangular matrix and an upper triangular matrix. It can be considered as the matrix form of Gaussian elimination and is a better way to implement Gaussian elimination, especially for the problem with a repeated number of equations with the same left-hand side, i.e., to solve the equation Ax = b with the same A and different values of b. [1]

Matrix A can be factorized into the product of the lower and upper triangular matrix using elementary matrices. You can refer to the previous article on three different elementary matrices: swapping, rescaling, and pivoting matrix.

Factorization of matrix A into product of lower and upper triangular matrix. (Image by Author)

Now let's go through how to solve the linear system using Lu Decomposition.

Step by step to solve a linear system using LU factorized matrices. (Image by Author)

Example of using LU decomposition to solve linear system:

Given the same left-hand side and different right-hand sides, i.e., with the same A and different values of b. (Image by Author)

Step 1, 2, 3: Factorize matrix A into L & U matrix

Step 4: With Lc₁ = b₁ and Lc₂ = b₂, solve c₁ and c₂!

Step 5: With Ux₁ = c₁ and Ux₂ = c₂, solve x₁ and x₂!

Refer to the previous article on how to get the inverse matrix.

By getting the L & U matrices, we can easily solve the linear system with the repeated left-hand side as mentioned above.

Summary

LU decomposition is used for solving linear systems and finding inverse matrices. It is said to be a better method to solve the linear system with the repeated left-hand side. In this post, you will learn how to solve the linear system using LU decomposition together with some codes.