Dada uma matriz A não singular, considere a fatoração A=L U, com L=(li j) triangular inferior com li i=1, i=1, ldots, n, e U=(ui j) triangular superior.
escreva um algoritmo para a fatoração LU de A usando a redução de Doolittle;

Passo 1

Beleza, olha só o que a gente tem: uma matriz A qualquer (invertível) e queremos quebrá-la em duas matrizes triangulares L e U, de modo que A = L·U. Isso faz parte da matéria de Álgebra Linear Numérica, mais precisamente de métodos de fatoração LU e eliminação gaussiana. Para resolver, a gente vai usar a ideia do método de Doolittle, que é só uma versão organizada de eliminar e registrar os coeficientes em L e U conforme avança.

Passo 2

Primeiro, entenda o formato dessas matrizes:
  • U é triangular superior, ou seja, u_{ij} = 0 sempre que i > j.
  • L é triangular inferior, mas com l_{ii} = 1 em toda diagonal (isso é característica do Doolittle). Então l_{ij} = 0 para i < j e l_{ii}=1.
    A estratégia geral é: no passo k a gente “limpa” a coluna k e registra os pivôs em U e os multiplicadores em L.

Passo 3

Vamos deduzir as fórmulas que usamos para preencher U e L numa base passo a passo.
  1. Como A = L·U, olhando elemento a_{kj} (linha k, coluna j):
    a_{kj} = ∑_{p=1}^k l_{kp}·u_{pj}
    Mas l_{kk}=1 e l_{kp}=0 para p>k, então isolamos u_{kj}:
    u_{kj} = a_{kj} − ∑_{p=1}^{k−1} l_{kp},u_{pj}.
  2. Para os elementos de L (abaixo da diagonal), olha a_{ik} (linha i>k, coluna k):
    a_{ik} = ∑_{p=1}^k l_{ip}·u_{pk}.
    Só que u_{kk} é pivô e l_{ii}=1; isolando l_{ik}:
    l_{ik} = (a_{ik} − ∑_{p=1}^{k−1} l_{ip},u_{pk}) / u_{kk}.

Passo 4

Pronto, agora a ideia do algoritmo é percorrer k = 1…n, primeiro computar toda a linha k de U (j = k…n) usando a fórmula de u_{kj}, e em seguida computar toda a coluna k de L (i = k+1…n) usando a fórmula de l_{ik}. A diagonal de L a gente já pune como 1.

Resposta

Entrada: matriz A de ordem n (invertível)
Saída: matrizes L e U tal que A = L·U

Para i de 1 até n:
    Para j de 1 até n:
        L[i,j] ← 0
        U[i,j] ← 0
    L[i,i] ← 1

Para k de 1 até n:
    # 1) computa linha k de U
    Para j de k até n:
        U[k,j] ← A[k,j] 
                   − ∑_{p=1}^{k−1} L[k,p]·U[p,j]
    # 2) computa coluna k de L
    Para i de k+1 até n:
        L[i,k] ← ( A[i,k]
                    − ∑_{p=1}^{k−1} L[i,p]·U[p,k] )
                  / U[k,k]

Retorna L, U

Exercícios relacionados