Decomposição LU

Predefinição:Mais fontes 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 não singular (se o fosse, então a decomposição poderia não ser única)

$A=LU,\,$

onde L e U são, respectivamente, 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 (Lower) e U (Upper) 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_{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:

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.

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.