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

A uma matriz não singular (se o fosse, então a decomposição poderia não ser única)

$A = LU, \,$

onde L e U são matrizes inferiores e superiores triangulares.

Para matrizes $3 \times 3$ , isto é:

$\begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 \\ l_{21} & 1 & 0 \\ l_{31} & l_{32} & 1 \\ \end{pmatrix} \begin{pmatrix} u_{11} & u_{12} & u_{13} \\ 0 & u_{22} & u_{23} \\ 0 & 0 & u_{33} \\ \end{pmatrix}$

A decomposição PLU tem esta forma:

$A = PLU, \,$ ou também: $PA = LU \,$ (lembrando que as matrizes de permutação são inversíveis e a sua inversa é a sua transposta).

Onde L e U são, de novo, duas matrizes triangulares inferior e superior respectivamente e P é uma matriz de permutação.

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} \,$

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^{-1}_{1}*E^{-1}_{2}*...*E^{-1}_{n}*U \,$

Consequentemente, L $E^{-1}_{1}*E^{-1}_{2}*...*E^{-1}_{n}$ é uma matriz triangular inferior.

Aplicações

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

Dada a equação matricial

$A x = L U x = b \,$

Queremos a solução para um determinando A e b. Os passos são os seguintes:

1. Primeiro, resolvemos $Ly = b \,$ para y
2. 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.

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.