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:

- $E_1 \cdots E_k A = U$, where $E_1 \cdots E_k$ are elimination matrices for each elimination step
- Let $E = E_1 \cdots E_k$

- $E_1 \cdots E_k \ A = U$
- or $EA = U$
- let $L = E^{-1}$, so we have $A = LU$
- $U$ is upper-triangular by construction - because we eliminate all elements down the main diagonal
- $L$ is lower-triangular

$L$

- $L = E^{-1} = (E_1 \cdots E_k)^{-1} = E_k^{-1} \cdots E_1^{-1}$
- $E_i$ have zeros up the diagonal, so when we inverse them, they become lower-diagonal
- when we multiply a bunch of lower-diagonal matrices, we get a lower-diagonal matrix

Types of $LU$ decomposition:

- It's possible to have ones on the main diagonal of either $L$ or $U$
- Doolittle decomposition - the diagonal entries of $L$ are ones
- Crout decomposition - the diagonal entries of $U$ are ones

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

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

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$