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 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, é:

$\left(\begin{array}{ccc}{a}_{11}& a_{12}& a_{13}\\ a_{21}& a_{22}& a_{23}\\ a_{31}& a_{32}& a_{33}\end{array}\right)=\left(\begin{array}{ccc}{l}_{11}& 0& 0\\ l_{21}& l_{22}& 0\\ l_{31}& l_{32}& l_{33}\end{array}\right)\left(\begin{array}{ccc}{u}_{11}& u_{12}& u_{13}\\ 0& u_{22}& u_{23}\\ 0& 0& u_{33}\end{array}\right)$

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=\left[\begin{array}{cc}4& 3\\ 6& 3\end{array}\right]=\left[\begin{array}{cc}{\ell }_{11}& 0\\ {\ell }_{21}& {\ell }_{22}\end{array}\right]\left[\begin{array}{cc}{u}_{11}& u_{12}\\ 0& u_{22}\end{array}\right].$

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

$A=\left[\begin{array}{cc}4& 3\\ 6& 3\end{array}\right]$$$L_2^{(1)}\leftarrow L_2-m.L_1$$Onde $m$ é multiplicador que é dado por:

$m=\frac{a_{21}}{a_{11}}=\frac{6}{4}$

Logo obtemos a matriz

$U=\left[\begin{array}{cc}4& 3\\ 0& -1,5\end{array}\right]$

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=\left[\begin{array}{cc}1& 0\\ m& 1\end{array}\right]=\left[\begin{array}{cc}1& 0\\ \frac{6}{4}& 1\end{array}\right]$

Portanto podemos escrever a matriz A da seguinte forma:

$\left[\begin{array}{cc}4& 3\\ 6& 3\end{array}\right]=\left[\begin{array}{cc}1& 0\\ 1.5& 1\end{array}\right]\left[\begin{array}{cc}4& 3\\ 0& -1.5\end{array}\right].$

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$ admite fatorações LUP e PLU. Se $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$ é uma matriz de classificação $k$, então ele admite uma uma fatoração LU se o primeiro $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$ (ou $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=L{L}^{*}.$

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:

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.

• Bunch, James R.; Hopcroft, John (1974), "Triangular factorization and inversion by fast matrix multiplication", Mathematics of Computation, 28 (125): 231–236, Doi:10.23072005828 ISSN:0025-5718JSTOR:2005828.
• Thomas_H._Cormen, Charles_E._Leiserson , Ronald_L._Rivest , Clifford_Stein (2001), Introduction_to_Algorithms, MIT Press and McGraw-Hill, ISBN:978-0-262-03293-3.
• Gene_H._Golub; Charles_F._Van_Loan. (1996), Matrix Computations (3rd ed.), Baltimore: Johns Hopkins, ISBN:978-0-8018-5414-9.
• Horn, Roger A.; Johnson, Charles R. (1985), Matrix Analysis, Cambridge University Press, ISBN: 978-0-521-38632-6. See Section 3.5. N − 1
• Householder, Alston S. (1975), The Theory of Matrices in Numerical Analysis, New York: Dover_Publications: MR0378371
• Okunev, Pavel; Johnson, Charles R. (1997), Necessary And Sufficient Conditions For Existence of the LU Factorization of an Arbitrary Matrix, ArXiv:math.NA/0506382.
• Poole, David (2006), Linear Algebra: A Modern Introduction (2nd ed.), Canada: Thomson Brooks/Cole, ISBN: 978-0-534-99845-5.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 2.3" , Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN:978-0-521-88068-8
• Nicholas_Trefethen; Bau, David (1997), Numerical linear algebra, Philadelphia: Society for Industrial and Applied Mathematics, ISBN:978-0-89871-361-9.