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
LE Decomposition of a Matrix
Answers to Questions (FAQ)
What is LU Decomposition? (Definition)
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.
How to calculate an LU Decomposition?
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} $$
What are the conditions for using LU Decomposition?
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.
What is pivoting in LU Decomposition?
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 $
Source code
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.
Cite dCode
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-10-18,
