# Decomposição LU

Em álgebra linear, a decomposição LU (em que LU vem do inglês lower e upper) é uma forma de fatoração de uma matriz não singular como o produto de uma matriz triangular inferior (lower) e uma matriz triangular superior (upper). Às vezes se deve pré-multiplicar a matriz a ser decomposta por uma matriz de permutação. Esta decomposição se usa em análise numérica para resolver sistemas de equações (mais eficientemente) ou encontrar as matrizes inversas.

## Definições

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 :
    $A=LU,\,$
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\times 3$ , sua decomposição LU, é:
    ${\begin{pmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33}\\\end{pmatrix}}={\begin{pmatrix}l_{11}&0&0\\l_{21}&l_{22}&0\\l_{31}&l_{32}&l_{33}\\\end{pmatrix}}{\begin{pmatrix}u_{11}&u_{12}&u_{13}\\0&u_{22}&u_{23}\\0&0&u_{33}\\\end{pmatrix}}$
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}$. Se $a_{11}=0$, então pelo menos um de $l_{11}$e $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.

### Fatoração LU com pivotamento parcial

Acontece que uma permutação apropriada em linhas (ou colunas) é suficiente para a fatoração LU. Fatoração LU com pivotamento parcial (LUP) se refere frequentemente à fatoração LU apenas com permutações de linha:
$PA=LU$,
onde L e U são novamente inferior e superior matrizes triangulares, e P é uma matriz de permutação , que, quando deixou-multiplicado a um , reordena as linhas de Uma . Acontece que todas as matrizes quadradas podem ser fatoradas desta forma, e a fatoração é numericamente estável na prática. Isso torna a decomposição do LUP uma técnica útil na prática.

### Fatoração LU com pivotamento completo

Uma fatoração LU com pivotamento completo envolve permutações de linha e coluna:
$PAQ=LU$,
onde L , L e P são definidos como anteriormente, e Q é uma matriz de permutação que reordena as colunas de um.

### Decomposição diagonal inferior-superior (LDU)

Uma decomposição inferior diagonal superior (LDU) é uma decomposição da forma
$A=LDU$,
onde D é uma matriz diagonal e L e U são matrizes unitriangulares , o que significa que todas as entradas nas diagonais de L e U são 1.
Acima exigimos que A seja uma matriz quadrada, mas essas decomposições podem ser generalizadas para matrizes retangulares também. Nesse caso, G e D são matrizes quadradas sendo que ambos têm o mesmo número de filas como um , e L possui exactamente as mesmas dimensões que um . O triangular superior deve ser interpretado como tendo apenas zero entradas abaixo da diagonal principal, que começa no canto superior esquerdo.

## Exemplos

Fatoramos a seguinte matriz 2 por 2:
$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={\displaystyle {\begin{bmatrix}4&3\\6&3\end{bmatrix}}}$$L_{2}^{(1)}\leftarrow L_{2}-m.L_{1}$Onde $m$ é multiplicador que é dado por:
$m={a_{21} \over a_{11}}={6 \over 4}$
Logo obtemos a matriz
$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
$L={\displaystyle {\begin{bmatrix}1&0\\m&1\end{bmatrix}}}={\displaystyle {\begin{bmatrix}1&0\\{6 \over 4}&1\end{bmatrix}}}$
Portanto podemos escrever a matriz A da seguinte forma:
${\displaystyle {\begin{bmatrix}4&3\\6&3\end{bmatrix}}={\begin{bmatrix}1&0\\1.5&1\end{bmatrix}}{\begin{bmatrix}4&3\\0&-1.5\end{bmatrix}}.}$

## Unicidade

As matrizes L e U são únicas, se a matriz não é singular. Em caso contrário podem não ser únicas.
Demonstração:
Dada a matriz A ∈ $R^{mxn}$
$A=L_{1}U_{1}\,$ e $A=L_{2}U_{2}\,$
Recordemos que $L_{1},U_{1},L_{2},U_{2}\,$ são invertíveis por terem o determinante diferente de zero.
Então:
$L_{1}U_{1}=L_{2}U_{2}\,$
${L_{2}}^{-1}L_{1}=U_{2}{U_{1}}^{-1}$
Então ${L_{2}}^{-1}L_{1}$ é uma matriz triangular inferior, com 1s na diagonal e, consequentemente, $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:
${L_{2}}^{-1}L_{1}=I$ e $U_{2}{U_{1}}^{-1}=I$
Com o qual:
    $L_{1}=L_{2}\,$ e $U_{1}=U_{2}\,$

## Existência e singularidade
### Matrizes quadradas

Qualquer matriz quadrada A{\textstyle A} admite fatorações LUP e PLU. Se A{\textstyle A} é invertível, então admite uma fatoração LU (ou LDU) se e somente se todos os seu principais menores são diferentes de 0.Se A{\textstyle A} é uma matriz de classificação k{\textstyle k}, então ele admite uma uma fatoração LU se o primeiro k{\textstyle k} os principais menores são diferentes de 0, embora o inverso não seja verdadeiro.
Se uma matriz quadrada e invertível tem uma LDU (fatoração com todas as entradas diagonais de L e U iguais a 1), então a fatoração é única. Nesse caso, a fatoração LU também é única se exigirmos que a diagonal de L{\textstyle L} (ou U{\textstyle U}) consiste em uns.

### Matrizes simétricas positivas-definidas

Se A for uma matriz simétrica (ou matriz hermitiana, se A for complexa) positiva definida , podemos organizar as coisas de forma que U seja a transposta conjugada de L. Ou seja, podemos escrever A como
    $A=LL^{*}.\,$
Esta decomposição é chamada de Decomposição de Cholesky. A decomposição de Cholesky sempre existe e é única — desde que a matriz seja definida positiva. Além disso, calcular a decomposição de Cholesky é mais eficiente e numericamente mais estável do que calcular algumas outras decomposições LU.

### Matrizes gerais

Para uma matriz (não necessariamente invertível) sobre qualquer corpo, as condições exatas necessárias e suficientes sob as quais ela tem uma fatoração LU são conhecidas. Tais condições são expressas em termos da classificação de certas submatrizes. O algoritmo de eliminação gaussiana para obter a decomposição LU também foi estendido para este caso mais geral.

## Algoritmos

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.
    $E_{1}*E_{2}*...*E_{n}*A=U$
Onde $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:
    $A=E_{n}^{-1}*E_{n-1}^{-1}*...*E_{1}^{-1}*U\,$
Consequentemente, L $E_{n}^{-1}*E_{n-1}^{-1}*...*E_{1}^{-1}$ é uma matriz triangular inferior.

## Aplicações
### Resolução de sistemas de equações lineares

Dada a equação matricial
    $Ax=LUx=b\,$
Queremos a solução para um determinando A e b. Os passos são os seguintes:
* Primeiro, resolvemos $Ly=b\,$ para y
* Segundo, resolvemos $Ux=y\,$ para x.
Note-se que já temos as matrizes L e U. A vantagem deste método é a eficiência computacional porque podemos escolher qualquer novo o vetor b que não teremos que voltar a fazer a eliminação de Gauss a cada vez.

### Matriz inversa

As matrizes L e U podem ser usadas para calcular a matriz inversa. Algumas implementações que invertem matrizes usam este método.
No caso em que
    $Ax=LUx=b,\,$
x e b são tratados como vetores. Ao trocar o vetor x pela matriz X e o vetor b pela matriz B passamos a ter
    $AX=LUX=B.\,$
Agora, supondo que B seja a matriz identidade, teremos então que X será a inversa de A.

### Determinante de uma matriz

As matrizes $L$ e $U$ podem ser usadas para calcular o determinante da matriz $A$ muito eficientemente porque $det(A)=det(L)det(U)\,$ e os determinantes de matrizes triangulares são simplesmente o produto dos elementos de suas diagonais. Em particular, se L é uma matriz triangular em cuja diagonal todos os elementos são 1s, então:
    $\det(A)=\det(L)\det(U)=\prod _{i=1}^{n}u_{ii}.$
A mesma aproximação ao problema pode ser usada para decomposições LUP nas que aparecem matrizes de permutação, pois o determinante de uma matriz de permutação P é (−1)$^S$, onde $S$ é o número de permutações de filas na decomposição.