Knowledge base dedicated to Linux and applied mathematics.

Home > Mathematics > Linear Systems > **LU decomposition**

All the versions of this article: [English] [français]

We will study a direct method for solving linear systems: the LU decomposition. Given a matrix A, the aim is to build a lower triangular matrix L and an upper triangular matrix which has the following property: diagonal elements of L are unity and A=LU.

Let be matrix . factorization is a procedure for decomposing into a product of a lower triangular matrix (diagonal elements of L are unity) and an upper triangular matrix such as with

and

For the resolution of linear system : , the system becomes

We solve the system (1) to find the vector , then the system (2) to find the vector . The resolution is facilitated by the triangular shape of the matrices.

if an LU factorization exists, then it is unique.

An invertible matrix admits an LU factorization if and only if all its principal minors are non-zero (principal minor of order is the determiant of the matrix ).

If is only invertible, then can be written where is a permutation matrix.

We suppose that admits an LU factorization, the LU Decomposition algorithm is:

The LU decomposition also makes it possible to calculate the determinant of , which is equal to the product of the diagonal elements of the matrix if admits an LU factorization since