Podemos encontrar a fatoração LU de A diretamente, usando simplesmente a definição de produto de matrizes. Esquemas deste tipo são conhecidos como esquemas compactos, e o equivalente à fatoração A=LU com L triangular inferior com diagonal unitária e U triangular superior é chamado de redução de Doolittle.
Supondo que a fatoração LU de A seja possível, de uma forma única,
escreva um algoritmo para a fatoração LU de A usando a redução de Doolittle;

Passo 1

Beleza, vamos entender o que a questão está pedindo. A gente tem uma matriz A e quer escrevê-la como produto de duas matrizes L e U, onde L é triangular inferior com 1 na diagonal (chamamos isso de “unitário”) e U é triangular superior. Esse método de construir L e U direto usando a definição do produto é chamado redução de Doolittle. Em termos de matéria, é fatoração LU sem pivoteamento.
O que vamos precisar:
  • Saber que, se A = LU, então cada entrada de A satisfaz Aij=sumk=1^nLik,Ukj
    - Extrair fórmulas para os elementos de U e L a partir dessa definição.
    - Montar um esquema de loops (i,j) para preencher U e L.

Passo 2

Teoria e derivação das fórmulas:
  1. Pela definição de produto, para todo i,j: Aij ;=; sumk=1^nLikUkj
    2. Como L é unitária na diagonal, temos Lii=1 e Lik=0 se k>i (já que L é triangular inferior). Também U_{kj}=0 se k>j.
    3. Para determinar Uij (elementos de U, com i≤j):
    - A gente isola Uij na soma:
    Aij=sumk=1^i-1LikUkj+LiiUij ;=;sumk=1^i-1LikUkj+Uij
    • Então Uij ;=; Aij ;-;sumk=1^i-1LikUkj
      4. Para determinar Lij (elementos de L, com i>j):
      - Olhando de novo para a mesma soma, mas considerando j<i, isolamos LijUjj:
      Aij=sumk=1^j-1LikUkj+LijUjj
    • Como Ujj não é zero (supomos que a fatoração exista e seja única), Lij ;=;Aij-sumk=1^j-1LikUkjUjj
Então resumindo:
  • Para cada linha i e coluna j≥i: Uij=Aij-sumk=1^i-1LikUkj
    - Para cada linha i>j:
    Lij=Aij-sumk=1^j-1LikUkjUjj
  • E Lii=1 para todo i.

Passo 3

Agora vamos pensar em como programar isso em passos bem claros:
  1. Inicializa uma matriz L e uma matriz U do mesmo tamanho de A.
  2. Coloca L_{ii}=1 para todo i.
  3. Para i de 1 até n:
    a) Preenche a linha i de U (ou seja, U_{ij} para j=i…n) usando a fórmula acima.
    b) Preenche a coluna i de L (ou seja, L_{ji} para j=i+1…n) usando a fórmula acima.
  4. No final, A = L·U.

Resposta

Entrada: A (matriz n×n)
Saída: L (triangular inferior com diag=1), U (triangular superior)

// 1) Inicialização
para i = 1 até n:
    L[i,i] ← 1
    para j = 1 até n:
        U[i,j] ← 0
        L[i,j] ← 0  // opcional, só pra garantir zeros fora da estrutura

// 2) Loop principal de Doolittle
para i = 1 até n:

    // 2a) calcular U[i,j] para j = i..n
    para j = i até n:
        soma ← 0
        para k = 1 até i−1:
            soma ← soma + L[i,k] * U[k,j]
        U[i,j] ← A[i,j] − soma

    // 2b) calcular L[j,i] para j = i+1..n
    para j = i+1 até n:
        soma ← 0
        para k = 1 até i−1:
            soma ← soma + L[j,k] * U[k,i]
        L[j,i] ← (A[j,i] − soma) / U[i,i]

Retorne L, U

Exercícios relacionados