Use o botão abaixo para reportar erros ou dar sugestões.

Cálculo Numérico - Versão Python

4.4 Fatoração LU


Considere um sistema linear Ax = b, onde a matriz A é densa3 . A fim de resolver o sistema, podemos fatorar a matriz A como o produto de uma matriz L triangular inferior e uma matriz U triangular superior, ou seja, A = LU.

Sendo assim, o sistema pode ser reescrito da seguinte forma: Ax = b (4.62) (LU)x = b (4.63) L(Ux) = b (4.64) Ly = b  e  Ux = y (4.65)

Isto significa que, ao invés de resolvermos o sistema original, podemos resolver o sistema triangular inferior Ly = b e, então, o sistema triangular superior Ux = y, o qual nos fornece a solução de Ax = b.

A matriz U da fatoração4 LU é a matriz obtida ao final do escalonamento da matriz A.

A matriz L é construída a partir da matriz identidade I, ao longo do escalonamento de A. Os elementos da matriz L são os múltiplos do primeiro elemento da linha de A a ser zerado dividido pelo pivô acima na mesma coluna.

Por exemplo, para zerar o primeiro elemento da segunda linha de A, calculamos

L21 = A21A11 (4.66)

e fazemos

A2,: A2,: - L21A1,: (4.67)

Note que denotamos Ai,: para nos referenciarmos a linha i de A. Da mesma forma, se necessário usaremos A:,j para nos referenciarmos a coluna j de A.

Para zerar o primeiro elemento da terceira linha de A, temos

L31 = A31A11 (4.68)

e fazemos

A3,: A3,: - L31A1,: (4.69)

até chegarmos ao último elemento da primeira coluna de A.

Repetimos o processo para as próximas colunas, escalonando a matriz A e coletando os elementos Lij abaixo da diagonal5 .

Exemplo 4.4.1. Use a fatoração LU para resolver o seguinte sistema linear:

x1 + x2 + x3 = -2 2x1 + x2 - x3 = 1 2x1 - x2 + x3 = 3 (4.70)

Solução. Começamos fatorando a matriz A dos coeficientes deste sistema: A = 1 1 1 2 1 -1 2 -1 1 . = 1 0 0 0 1 0 0 0 1 I3,3 1 1 1 2 1 -1 2 -1 1 A (4.71) = 1 0 0 2 1 0 2 0 1 1 1 1 0 -1 -3 0 -3 -1 (4.72) = 1 0 0 2 1 0 2 3 1 L 1 1 1 0 -1 -3 0 0 8 U (4.73) (4.74)

Completada a fatoração LU, resolvemos, primeiramente, o sistema Ly = b:

y1 = -2 2y1 + y2 = 1 2y1 + 3y2 + y3 = 3 (4.75)

o qual nos fornece y1 = -2, y2 = 5 e y3 = -8. Por fim, obtemos a solução resolvendo o sistema Ux = y:

x1 + x2 + x3 = -2 - x2 - 3x3 = 5 8x3 = -8 (4.76)

o qual fornece x3 = -1, x2 = -2 e x1 = 1.

4.4.1 Código Python: Fatoração LU


Em Python, podemos implementar o algoritmo para fatoração LU da seguinte forma:

def fatoraLU(A):  
    U = np.copy(A)  
    n = np.shape(U)[0]  
    L = np.eye(n)  
    for j in np.arange(n-1):  
        for i in np.arange(j+1,n):  
            L[i,j] = U[i,j]/U[j,j]  
            for k in np.arange(j+1,n):  
                U[i,k] = U[i,k] - L[i,j]*U[j,k]  
            U[i,j] = 0  
    return L, U

Observação 4.4.1. O custo computacional do algoritmo da fatoração LU é

2n3 3 - n2 2 - n 6 flops. (4.77)

4.4.2 Custo computacional para resolver um sistema linear usando fatoração LU


Para calcularmos o custo computacional de um algoritmo completo, uma estratégia é separar o algoritmo em partes menores, mais fáceis de analisar.

Para resolver o sistema, devemos primeiro fatorar a matriz A nas matrizes L e U. Vimos que o custo é

2n3 3 - n2 2 - n 6 flops. (4.78)

Depois devemos resolver os sistemas Ly = b e Ux = y. O custo de resolver os dois sistemas é (devemos contar duas vezes)

2n2 flops. (4.79)

Somando esses 3 custos, temos que o custo para resolver um sistema linear usando fatoração LU é

2n3 3 + 3n2 2 - n 6 flops. (4.80)

Quando n cresce, prevalessem os termos de mais alta ordem, ou seja,

O(2n3 3 + 3n2 2 - n 6) = O(2n3 3 + 3n2 2 ) = O(2n3 3 ) (4.81)

4.4.3 Custo para resolver m sistemas lineares


Devemos apenas multiplicar m pelo custo de resolver um sistema linear usando fatoração LU, ou seja, o custo será

m(2n3 3 + 3n2 2 - n 6) = 2mn3 3 + 3mn2 2 - mn 6 (4.82)

e com m = n temos

2n4 3 + 3n3 2 - n2 6 . (4.83)

Porém, se estivermos resolvendo m sistemas com a mesma matriz A (e diferente lado direito b para cada sistema) podemos fazer a fatoração LU uma única vez e contar apenas o custo de resolver os sistemas triangulares obtidos.

Custo para fatoração LU de A: 2n3 3 - n2 2 - n 6 .

Custo para resolver m sistemas triangulares inferiores: mn2.

Custo para resolver m sistemas triangulares superiores: mn2.

Somando esses custos obtemos

2n3 3 - n2 2 - n 6 + 2mn2 (4.84)

que quando m = n obtemos

8n3 3 - n2 2 - n 6 flops. (4.85)

4.4.4 Custo para calcular a matriz inversa de A


Como vemos em Álgebra Linear, um método para obter a matriz A-1 é realizar o escalonamento da matriz [A|I] onde I é a matriz identidade. Ao terminar o escalonamento, o bloco do lado direito conterá A-1.

Isto é equivalente a resolver n sistemas lineares com a mesma matriz A e os vetores da base canônica ei = [0,...,0,1,0,....0]T , isto é,

Axi = ei,i = 1 : n (4.86)

onde xi serão as colunas da matriz A inversa, já que AX = I.

O custo para resolver esses n sistemas lineares foi calculado na seção anterior como

8n3 3 - n2 2 - n 6. (4.87)

Exemplo 4.4.2. Qual o melhor método para resolver um sistema linear: via fatoração LU ou calculando a inversa de A e obtendo x = A-1b?

Creative Commons License Este texto é disponibilizado nos termos da licença Creative Commons Atribuição-CompartilhaIgual 3.0 Não Adaptada (CC-BY-SA 3.0). Página gerada em 15/5/2019 às 15:24:50.

Informe erros ou edite você mesmo!