MATLAB LU Decomposition Code for Solving Linear System of Equations

by admin in on April 11, 2019

The code solves a given system of linear equations using LU Decomposition, and LUP Decomposition. The answers are on three parts: The first results part is the LU Decomposition where L is Lower-Triangle matrix and U is Upper-Triangle matrix. The second results part is LUP Decomposition where L is a diagonal unity matrix, U is Upper-Triangle matrix and P is the Permutation matrix. The third results part is solving the linear system [A] [X] = [B].

Lower–Upper (LU) Decomposition or Factorization factors a matrix as the product of a lower triangular matrix and an upper triangular matrix. The product sometimes includes a permutation matrix as well. LU decomposition can be viewed as the matrix form of Gaussian elimination. Computers usually solve square systems of linear equations using LU decomposition, and it is also a key step when inverting a matrix or computing the determinant of a matrix.

Method Definition:

Let A be a square matrix. An LU factorization refers to the factorization of A, with proper row and/or column orderings or permutations, into two factors – a lower triangular matrix L and an upper triangular matrix U:

In the lower triangular matrix all elements above the diagonal are zero, in the upper triangular matrix, all the elements below the diagonal are zero. For example, for a 3 × 3 matrix A, its LU decomposition looks like this:

Without a proper ordering or permutations in the matrix, the factorization may fail to materialize. For example, it is easy to verify (by expanding the matrix multiplication) that A11 = L11. U11. If A11 = 0, then at least one of L11  and U11 has to be zero, which implies that either L or U is singular. This is impossible if A is nonsingular (invertible). This is a procedural problem. It can be removed by simply reordering the rows of A so that the first element of the permuted matrix is nonzero. The same problem in subsequent factorization steps can be removed the same way; see the basic procedure below.

Solving Linear Equations:

Given a system of linear equations in matrix form

we want to solve the equation for x, given A and b. Suppose we have already obtained the LUP decomposition of A such that P.A = L.U, so L.Ux = Pb. In this case the solution is done in two logical steps:

1. First, we solve the equation Ly = Pb for y.
2. Second, we solve the equation Ux = y for x.

Note that in both cases we are dealing with triangular matrices (L and U), which can be solved directly by forward and backward substitution without using the Gaussian elimination process (however we do need this process or equivalent to compute the LU decomposition itself).

The above procedure can be repeatedly applied to solve the equation multiple times for different b. In this case it is faster (and more convenient) to do an LU decomposition of the matrix A once and then solve the triangular matrices for the different b, rather than using Gaussian elimination each time. The matrices L and U could be thought to have ‘encoded’ the Gaussian elimination process.

Share Now!

Release Information

• Price
:

\$4.99

• Released
:

April 11, 2019

• Last Updated
:

May 29, 2019