Tool to calculate and understand LU decomposition, an efficient method for solving systems of linear equations by factoring via triangular matrices.

LU Decomposition - dCode

Tag(s) : Matrix

dCode is free and its tools are a valuable help in games, maths, geocaching, puzzles and problems to solve every day!

A suggestion ? a feedback ? a bug ? an idea ? *Write to dCode*!

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.

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} $$

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.

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 $

dCode retains ownership of the "LU Decomposition" source code. Except explicit open source licence (indicated Creative Commons / free), the "LU Decomposition" algorithm, the applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, breaker, translator), or the "LU Decomposition" functions (calculate, convert, solve, decrypt / encrypt, decipher / cipher, decode / encode, translate) written in any informatic language (Python, Java, PHP, C#, Javascript, Matlab, etc.) and all data download, script, or API access for "LU Decomposition" are not public, same for offline use on PC, mobile, tablet, iPhone or Android app!

Reminder : dCode is free to use.

The copy-paste of the page "LU Decomposition" or any of its results, is allowed (even for commercial purposes) as long as you credit dCode!

Exporting results as a .csv or .txt file is free by clicking on the *export* icon

Cite as source (bibliography):

*LU Decomposition* on dCode.fr [online website], retrieved on 2024-07-18,

lu,decomposition,lower,upper,matrix,triangular,factorization,linear,algebra,pivoting,permutation

https://www.dcode.fr/matrix-lu-decomposition

© 2024 dCode — El 'kit de herramientas' definitivo para resolver todos los juegos/acertijos/geocaching/CTF.

Feedback