Decomposição LU

Sendo A uma matriz simples quadrada. Uma fatoração LU refere-se à fatoração de A , com ordenações ou permutações adequadas de linhas e/ou colunas, em dois fatores - uma matriz triangular inferior L e uma matriz triangular superior U : onde L e U são, respectivamente, matrizes inferiores e superiores triangulares. Na matriz triangular inferior, todos os elementos acima da diagonal são zero; na matriz triangular superior, todos os elementos abaixo da diagonal são zero. Para matrizes 3 × 3 {\displaystyle 3\times 3} , sua decomposição LU, é: Sem uma ordenação adequada ou permutações na matriz, a fatoração pode não se materializar. Por exemplo, é fácil verificar (expandindo a multiplicação da matriz) que a 11 = l 11 . u 11 {\displaystyle a_{11}=l_{11}.u_{11}} . Se a 11 = 0 {\displaystyle a_{11}=0} , então pelo menos um de l 11 {\displaystyle l_{11}} e u 11 {\displaystyle u_{11}} tem que ser zero, o que implica que L ou U são singulares. Isso é impossível se A for não singular (invertível). Este é um problema processual. Ele pode ser removido simplesmente reordenando as linhas de A de modo que o primeiro elemento da matriz permutada seja diferente de zero. O mesmo problema nas etapas de fatoração subsequentes pode ser removido da mesma maneira; veja o procedimento básico abaixo.

A = [ 4 3 6 3 ] = [ ℓ 11 0 ℓ 21 ℓ 22 ] [ u 11 u 12 0 u 22 ] . {\displaystyle A={\displaystyle {\begin{bmatrix}4&3\\6&3\end{bmatrix}}={\begin{bmatrix}\ell _{11}&0\\\ell _{21}&\ell _{22}\end{bmatrix}}{\begin{bmatrix}u_{11}&u_{12}\\0&u_{22}\end{bmatrix}}.}} Uma maneira de encontrar a decomposição LU dessa matriz simples seria simplesmente realizar a eliminação de Gauss: A = [ 4 3 6 3 ] {\displaystyle A={\displaystyle {\begin{bmatrix}4&3\\6&3\end{bmatrix}}}} L 2 ( 1 ) ← L 2 − m . L 1 {\displaystyle L_{2}^{(1)}\leftarrow L_{2}-m.L_{1}} Onde m {\displaystyle m} é multiplicador que é dado por: m = a 21 a 11 = 6 4 {\displaystyle m={a_{21} \over a_{11}}={6 \over 4}} U = [ 4 3 0 − 1 , 5 ] {\displaystyle U={\displaystyle {\begin{bmatrix}4&3\\0&-1,5\end{bmatrix}}}} E a matriz L que é uma matriz triangular superior (ou seja, todas as entradas de sua diagonal principal são 1) e os demais componentes são o valor dos multiplicadores utilizados na eliminação de Gauss

As matrizes L e U são únicas, se a matriz não é singular. Em caso contrário podem não ser únicas. Dada a matriz A ∈ R m x n {\displaystyle R^{mxn}} A = L 1 U 1 {\displaystyle A=L_{1}U_{1}\,} e A = L 2 U 2 {\displaystyle A=L_{2}U_{2}\,} Recordemos que L 1 , U 1 , L 2 , U 2 {\displaystyle L_{1},U_{1},L_{2},U_{2}\,} são invertíveis por terem o determinante diferente de zero. L 1 U 1 = L 2 U 2 {\displaystyle L_{1}U_{1}=L_{2}U_{2}\,} L 2 − 1 L 1 = U 2 U 1 − 1 {\displaystyle {L_{2}}^{-1}L_{1}=U_{2}{U_{1}}^{-1}} Então L 2 − 1 L 1 {\displaystyle {L_{2}}^{-1}L_{1}} é uma matriz triangular inferior, com 1s na diagonal e, consequentemente, U 2 U 1 − 1 {\displaystyle U_{2}{U_{1}}^{-1}} possui 1s na diagonal e é triangular superior (recordando que o produto matricial de triangulares superiores/inferiores é triangular superior/inferior). A única matriz que cumpre estas duas propriedades é a matriz identidade. Portanto:

A decomposição LU é basicamente uma forma modificada da eliminação gaussiana. Transformamos a matriz A em uma triangular superior U anulando os elementos debaixo da diagonal. Onde E 1 , E 2 , . . . , E n {\displaystyle E_{1},E_{2},...,E_{n}} são matrizes elementares, que representam os distintos passos da eliminação. Logo, recordando que a inversa de uma matríz elementar é outra matriz elementar: Consequentemente, L E n − 1 ∗ E n − 1 − 1 ∗ . . . ∗ E 1 − 1 {\displaystyle E_{n}^{-1}*E_{n-1}^{-1}*...*E_{1}^{-1}} é uma matriz triangular inferior.