[Linear Algebra] 11. LU decomposition
1. Definition of LU decomposition
Let 𝐀 be a square matrix. An 𝐋𝐔 decomposition of 𝐀 refers to the factorization of A, with proper row and/or column orderings or permutations, into two triangular matrices, one lower triangular matrix 𝐋 and one upper triangular matrix 𝐔, such that the product(matrix multiplication) of these two matrices 𝐋𝐔 is identical to the original matrix 𝐀.
According to its definition, in the lower triangular matrix, all entries above the diagonal are zero, and in the upper triangular matrix, all the elements below the diagonal are zero.
- why permutations(orderings) are required?
Let’s think about the case: 𝑎₁₁ = 𝑙₁₁⨯𝑢₁₁ = 0. Since 𝑎₁₁ is zero, either 𝑙₁₁ or 𝑢₁₁ has to be zero, which implies that one of 𝐋 and 𝐔 is a singular matrix. However, this problem can be solved by reordering the rows(or columns) of 𝐀 so that the first entry of the permuted matrix is nonzero.
2. How does Lu decomposition work
Above figure is showing the flow of 𝐋𝐔 decomposition of the 2⨯2 square matrix 𝐀. In that example, permutations were not necessary but one restriction was required to find the unique solutions of entries in the matrix 𝐋 and 𝐔, which is setting all the diagonal entries of 𝐋 as one. With the help of the restriction, the unique 𝐋𝐔 decomposition can be found.
- Why setting all diagonal elements in 𝐋 is necessary to find the unique solution of 𝐋𝐔 decomposition?
Let’s think about the case 𝑎₁₁ in the example mentioned above. In order to find the solution of 𝑙₁₁ and 𝑢₁₁, we need to solve the following equation.
3. LU decomposition with the Gauss elimination
- Recap of the Gauss elimination
The general steps for finding 𝐔 matrix for 𝐋𝐔 decomposition of 𝐀 is as below in figure 3.
Using Gauss elimination, reduce 𝐀 into the upper triangular matrix then substitute it into 𝐔. Then one thing left for completing the 𝐋𝐔 decomposition is to find 𝐋. With the restriction which sets all diagonal entries to zero for finding the unique solution, we need to calculate some equations as we’ve done in figure2, but this time, with less calculation since we already know all entries in 𝐔 with the help of Gauss elimination.
4. Codes
5. Reference
[1] https://en.wikipedia.org/wiki/LU_decomposition
[2] https://www.quantstart.com/articles/LU-Decomposition-in-Python-and-NumPy
[3] https://medium.com/linear-algebra-basics/lu-decomposition-c8f9b75ddeff
[4] https://www.geeksforgeeks.org/l-u-decomposition-system-linear-equations/
Any corrections, suggestions, and comments are welcome