Dada uma matriz A não singular, considere a fatoração
, com
triangular inferior com
, e
triangular superior.
escreva um algoritmo para a fatoração LU de A usando a redução de Doolittle;
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.
- 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}. - 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