Line 20: | Line 20: | ||
− | + | Types of $LU$ decomposition: | |
− | * | + | * It's possible to have ones on the main diagonal of either $L$ or $U$ |
− | * Then we have $ | + | * Doolittle decomposition - the diagonal entries of $L$ are ones |
+ | * Crout decomposition - the diagonal entries of $U$ are ones | ||
+ | |||
+ | |||
+ | === $PLU$ Decomposition and Pivoting === | ||
+ | * To avoid division by small numbers, we permute rows during the eliminations such that the largest element is the pivot | ||
+ | * We can express row permutation with the permutation matrix P | ||
+ | * Then $PA$ is $A$ with permuted rows, so we have $E \, (PA) = U$ | ||
+ | * So the decomposition becomes $PA = LU$ | ||
=== $LDU$ === | === $LDU$ === | ||
− | We can go further and obtain factorization $A = LU = LDU^*$, where $D$ is diagonal | + | We can go further: |
+ | * and obtain factorization $A = LU = LDU^*$, where $D$ is diagonal | ||
+ | * I.e. we factorize $U = DU^*$ | ||
+ | * this way both $L$ and $U$ will have ones on their diagonals - if $L$ had ones and $U$ didn't | ||
+ | |||
+ | |||
+ | |||
+ | == [[Inverse Matrices|Matrix Inversion]] with LU Decomposition == | ||
+ | To find the matrix inverse, we need to solve the equation $AX = I$, where $X = A^{-1}$ | ||
+ | * Let's decompose $A = LU$, so we have: $LUX = I$ | ||
+ | * Now let $UX = Y$ and thus $LY = I$ | ||
+ | * This gives us two systems: | ||
+ | ** first solve $LY = I$ - it's easy because $L$ is lower-triangular, so we just do the forward pass and obtain $Y$ | ||
+ | ** then we solve $UX = Y$ - it's also easy because $U$ is upper-triangular | ||
+ | * after that we get $X$ which is our inverse | ||
+ | * if we need pivoting, then: | ||
+ | ** we solve $PAX = PI = P$ | ||
+ | ** since $PA = LU$, we have $LUX = P$ | ||
+ | ** then we solve $LY = P$ and $UX = Y$ | ||
== Sources == | == Sources == | ||
* [[Linear Algebra MIT 18.06 (OCW)]] | * [[Linear Algebra MIT 18.06 (OCW)]] | ||
+ | * https://www.gamedev.net/resources/_/technical/math-and-physics/matrix-inversion-using-lu-decomposition-r3637 | ||
[[Category:Linear Algebra]] | [[Category:Linear Algebra]] | ||
[[Category:Matrix Decomposition]] | [[Category:Matrix Decomposition]] |
This is the simplest factorization that can be seen as a by-product of Gaussian Elimination
When we do elimination, we have some elimination matrices:
$L$
Types of $LU$ decomposition:
We can go further:
To find the matrix inverse, we need to solve the equation $AX = I$, where $X = A^{-1}$