Decomposição LU

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Este artigo não cita fontes fiáveis e independentes. (desde fevereiro de 2014). Por favor, adicione referências e insira-as corretamente no texto ou no rodapé. Conteúdo sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)

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[editar | editar código-fonte]

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 e U são, de novo, duas matrizes triangulares inferior e superior respectivamente e P é uma matriz de permutação.

Unicidade[editar | editar código-fonte]

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[editar | editar código-fonte]

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

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

Aplicações[editar | editar código-fonte]

Resolução de sistemas de equações lineares[editar | editar código-fonte]

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[editar | editar código-fonte]

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

A x = L U x = 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

A X = L U X = B. \,

Agora suponto que B seja a matriz identidade teremos então que X será a inversa de A.

Determinante de uma matriz[editar | editar código-fonte]

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.