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
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;
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:
O que vamos precisar:
- Saber que, se A = LU, então cada entrada de A satisfaz
- 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:
- Pela definição de produto, para todo i,j:
2. Como L é unitária na diagonal, temose se k>i (já que L é triangular inferior). Também U_{kj}=0 se k>j.
3. Para determinar(elementos de U, com i≤j):
- A gente isolana soma:
- Então
4. Para determinar(elementos de L, com i>j):
- Olhando de novo para a mesma soma, mas considerando j<i, isolamos:
- Como
não é zero (supomos que a fatoração exista e seja única),
- Então
Então resumindo:
- Para cada linha i e coluna j≥i:
- Para cada linha i>j:
- E
para todo i.
Passo 3
Agora vamos pensar em como programar isso em passos bem claros:
- Inicializa uma matriz L e uma matriz U do mesmo tamanho de A.
- Coloca L_{ii}=1 para todo i.
- 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. - 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