É correto afirmar que:
■ O custo computacional ao aplicar uma substituição progressiva e regressiva na decomposição LU é o mesmo da decomposição em si?
■ O custo computacional ao aplicar uma substituição progressiva e regressiva na decomposição LU é o mesmo da decomposição em si?
Passo 1
Beleza, o enunciado pergunta se o “custo computacional de fazer substituição progressiva + regressiva na decomposição LU é o mesmo da própria decomposição LU”. Estamos vendo conteúdo de análise de algoritmo para métodos numéricos: queremos contar operações aritméticas (flops) de duas etapas – a fatoração LU e a solução (substituições). Para responder, vamos calcular separadamente o número de flops de cada parte e comparar.
Passo 2
Primeiro, o que é cada coisa?
- Decomposição LU: fatorar uma matriz A em L (triangular inferior) e U (triangular superior). Aqui usamos basicamente eliminação de Gauss.
- Substituição progressiva: dado L y = b, resolve-se y linha a linha.
- Substituição regressiva: dado U x = y, resolve-se x de trás pra frente.
“Flops” são somas e multiplicações elementares. Vamos contar quantos flops cada etapa gasta.
Passo 3
Custo das substituições (progressiva + regressiva) em dimensão n:
- Substituição progressiva L y = b:
- Para cada i de 1 até n fazemos
yᵢ = (bᵢ − ∑_{j=1}^{i−1} L_{ij}·yⱼ) / L_{ii}. - O somatório tem (i−1) multiplicações e (i−1) subtrações, e uma divisão.
- Total ≃ ∑_{i=1}^n [ (i−1) mult + (i−1) sub + 1 div ]
- Ignorando constantes menores (divisão conta como O(1)), o dominante é ∑(i−1) ≃ n(n−1)/2 multiplicações e mesmo tanto de somas.
- Para cada i de 1 até n fazemos
- Substituição regressiva U x = y: similar, também dá ≃ n(n−1)/2 mult + somas + divisões.
Somando as duas:
flops_sub ≃ n(n−1) multiplicaçõese + n(n−1) somas ≃ 2·(n²−n) = O(n²).
Em notação assintótica: flops_sub = O(n²).
Passo 4
Custo da decomposição LU via eliminação de Gauss:
- A cada passo k (de 1 até n−1) eliminamos abaixo da diagonal na coluna k: para cada linha i = k+1…n, fazemos:
fator = A_{ik}/A_{kk} (1 divisão)
e depois para cada coluna j = k+1…n:
A_{ij} ← A_{ij} − fator·A_{kj} (1 mult + 1 sub) - Para cada k, temos (n−k) linhas e em cada linha (n−k) colunas a atualizar.
- Então flops ≃ ∑_{k=1}^{n−1} [ (n−k)·1 divisão + (n−k)·(n−k)·(1 mult+1 sub) ].
- A parte dominante é ∑_{k=1}^{n−1} 2·(n−k)² = 2·∑_{m=1}^{n−1} m² = 2·(n−1)n(2n−1)/6 ≃ (1/3)·2n³ = (2/3)n³ para n grande.
Logo flops_LU = O(n³).
Passo 5
Comparando:
- Substituições (progressiva+regressiva): O(n²)
- Decomposição LU: O(n³)
Claramente O(n³) domina O(n²). Não é o mesmo custo – a fatoração LU é muito mais cara para matrizes grandes.
Resposta
A afirmação é FALSA: o custo de fazer substituições é O(n²), enquanto a decomposição LU custa O(n³), bem maior.