LU Decomposition

Question 1

What is LU Decomposition? (Definition)

Answer

LU decomposition is a technique for factoring a square matrix $M$ into two triangular matrices: a lower triangular matrix $L$ and an upper triangular matrix $U$ such that $M = L.U$ .

The $L$ matrix has 1s on its diagonal and non-zero elements below the diagonal, while the $U$ matrix has non-zero elements above the diagonal and on the diagonal.

This method facilitates the resolution of systems of linear equations (algebra) and certain calculations such as the matrix determinant or matrix inversion.

Question 2

How to calculate an LU Decomposition?

Answer

One method to find the LU decomposition of a matrix is to solve linear equations.

Example: Factorize in $L.U$ the matrix $M = \begin{bmatrix} 1 & 2 \\ 3 & 5 \end{bmatrix} = L \cdot U = \begin{bmatrix} 1 & 0 \\ l_{21} & 1 \end{bmatrix} \cdot \begin{bmatrix} u_{11} & u_{12} \\ 0 & u_{22} \end{bmatrix}$ The corresponding equations are: $\begin{aligned} 1 \cdot u_{11} + 0 \cdot 0 &= 1 \\ 1 \cdot u_{12} + 0 \cdot u_{22} &= 2 \\ l_{21} \cdot u_{11} + 1 \cdot 0 &= 3 \\ l_{21} \cdot u_{12} + 1 \cdot u_{22} &= 5 \end{aligned}$ The resolution gives: $L = \begin{bmatrix} 1 & 0 \\ 3 & 1 \end{bmatrix} \quad U = \begin{bmatrix} 1 & 2 \\ 0 & -1 \end{bmatrix}$

Question 3

What are the conditions for using LU Decomposition?

Answer

To use LU decomposition, the matrix must be a square matrix (same number of rows and columns).

The matrix (or one of its row permutations) must be invertible. Some matrices may require row permutations to enable factorization, giving rise to LU decomposition with pivoting.

Example: If $M_{11} = 0$ then as $M_{11} = l_{11} \cdot u_{11}$ , either $l_{11}$ or $u_{11}$ must be zero, which implies that $L$ or $U$ is a singular (non-invertible) matrix. It is then necessary to permute the rows of $M$ so that the first element of the permuted matrix is non-zero.

Question 4

What is pivoting in LU Decomposition?

Answer

Pivoting in LU decomposition consists of permuting the rows of matrix A to avoid zeros on the main diagonal of matrix U.

If pivoting is required, dCode reports the permutation matrix $P$ and the resulting modified matrix $P.M$ . The matrices $L$ and $U$ found are such that $L.U = P.M$

LU Decomposition

LE Decomposition of a Matrix

Answers to Questions (FAQ)

What is LU Decomposition? (Definition)

How to calculate an LU Decomposition?

What are the conditions for using LU Decomposition?

What is pivoting in LU Decomposition?

Source code

Cite dCode

Need Help ?

Questions / Comments