É 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?

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:
  1. 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.
  2. 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.

Exercícios relacionados