Decomposição LU

(Redirecionado de Fatoraçã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çõesEditar

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   , 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  . Se  , então pelo menos um de  e   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 parcialEditar

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:

 ,

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 completoEditar

Uma fatoração LU com pivotamento completo envolve permutações de linha e coluna:

 ,

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)Editar

Uma decomposição inferior diagonal superior (LDU) é uma decomposição da forma

 ,

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.

ExemplosEditar

Fatoramos a seguinte matriz 2 por 2:

 

Uma maneira de encontrar a decomposição LU dessa matriz simples seria simplesmente realizar a eliminação de Gauss:

 

 
Onde   é multiplicador que é dado por:

 

Logo obtemos a matriz

 

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

 

Portanto podemos escrever a matriz A da seguinte forma:

 

UnicidadeEditar

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 

  e  

Recordemos que   são invertíveis por terem o determinante diferente de zero.

Então:

 

 

Então   é uma matriz triangular inferior, com 1s na diagonal e, consequentemente,   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:

  e  

Com o qual:

  e  

Existência e singularidadeEditar

Matrizes quadradasEditar

Qualquer matriz quadrada  admite fatorações LUP e PLU. Se   é invertível[1], então admite uma fatoração LU (ou LDU) se e somente se todos os seu principais menores são diferentes de 0.Se   é uma matriz de classificação  , então ele admite uma uma fatoração LU se o primeiro   os principais menores são diferentes de 0, embora o inverso não seja verdadeiro.[2]

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.[3] Nesse caso, a fatoração LU também é única se exigirmos que a diagonal de   (ou  ) consiste em uns.

Matrizes simétricas positivas-definidasEditar

Se A for uma matriz simétrica (ou matriz hermitiana[4], se A for complexa) positiva definida matrix[5], podemos organizar as coisas de forma que U seja a transposta conjugada de L. Ou seja, podemos escrever A como

 

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 geraisEditar

Para uma matriz (não necessariamente invertível) sobre qualquer campo, as condições exatas necessárias e suficientes sob as quais ela tem uma fatoração LU são conhecidas. As condições são expressas em termos de 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. [6]


AlgoritmosEditar

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   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   é uma matriz triangular inferior.

AplicaçõesEditar

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

Dada a equação matricial

 

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

  1. Primeiro, resolvemos   para y
  2. Segundo, resolvemos   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 inversaEditar

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

 

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

 

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

Determinante de uma matrizEditar

As matrizes   e   podem ser usadas para calcular o determinante da matriz   muito eficientemente porque   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:

 

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   é o número de permutações de filas na decomposição.

ReferênciasEditar

  1. «Invertible matrix». Wikipedia (em inglês). 19 de abril de 2021. Consultado em 6 de maio de 2021 
  2. Horn & Johnson (1985), Theorem 3.5.2
  3. Horn & Johnson (1985), Corollary 3.5.5
  4. «Matriz hermitiana». Wikipédia, a enciclopédia livre. 14 de agosto de 2020. Consultado em 6 de maio de 2021 
  5. «Definite matrix». Wikipedia (em inglês). 4 de maio de 2021. Consultado em 6 de maio de 2021 
  6. Okunev & Johnson ( 1997)