Exercício 6 (Análise Teórica - 1,5 pontos)
Explique as vantagens e desvantagens dos métodos iterativos (Jacobi e Gauss-Seidel) em comparação com métodos diretos para resolução de sistemas lineares.

Passo 1

O enunciado pede para compararmos as vantagens e desvantagens dos métodos iterativos de Jacobi e Gauss–Seidel com os métodos diretos (por exemplo, eliminação de Gauss ou fatoração LU) na resolução de um sistema linear Ax=b. O conteúdo envolve análise de complexidade, uso de memória, desempenho em sistemas esparsos e questões de convergência.

Passo 2

As principais vantagens dos métodos iterativos são:
  • Cada iteração exige apenas operações de multiplicação e soma envolvendo os coeficientes não nulos de A. Se \mathrm{nnz} é o número de elementos não nulos, o custo de cada iteração é \mathcal{O}(\mathrm{nnz}), que pode ser muito menor que \mathcal{O}(n^3).
  • Ocupam pouca memória extra, apenas precisam armazenar o próprio vetor solução e, se bem implementados, mantêm A na forma esparsa.
  • Podem ser paralelizados de forma simples (especialmente Jacobi, pois cada componente de x^{(k+1)} é calculado independentemente).
  • São adequados quando se necessita apenas de uma solução aproximada com certa tolerância, pois podemos interromper após algumas iterações.

Passo 3

As principais desvantagens dos métodos iterativos são:
  • A convergência não é garantida para todo A. Geralmente exige que A seja estritamente diagonalmente dominante ou simétrico definido positivo (no caso de Gauss–Seidel).
  • Podem convergir muito lentamente se o raio espectral do operador de iteração for próximo de 1, exigindo centenas ou milhares de iterações.
  • É necessário escolher critério de parada e tolerância, o que pode levar a erro de aproximação.
  • Em certas aplicações, pode ser necessário aplicar pré-condicionamento, acrescentando complexidade ao método.

Passo 4

Em contraste, métodos diretos possuem estas características:
  • Resolvem o sistema em número finito de operações (teoricamente exato, sujeito a erros de arredondamento) com custo típico \mathcal{O}(n^3) e memória \mathcal{O}(n^2).
  • São robustos: convergem para a solução exata (na aritmética real) sem depender de condição de diagonal dominante.
  • Sofrem fill-in quando aplicados a matrizes esparsas, o que pode transformar A em uma matriz densa temporária, aumentando drasticamente o custo de memória e de processamento.
  • São menos fáceis de paralelizar do que Jacobi ou Gauss–Seidel, embora existam implementações eficientes em grandes arquiteturas.

Passo 5

Em resumo, escolhe-se:
  • Iterativos quando A é muito grande e esparso, quando só se quer uma solução aproximada ou quando há infraestrutura de paralelismo leve.
  • Diretos quando n é moderado, A é denso ou bem condicionada, ou quando se requer a solução exata (dentro dos erros numéricos), sem preocupação de muitas iterações.

Resposta

Métodos iterativos (Jacobi e Gauss–Seidel) são mais leves em memória e custo por iteração \mathcal{O}(\mathrm{nnz}), paralelizáveis e ideais para grandes sistemas esparsos quando basta aproximação, mas têm convergência condicional e podem ser lentos. Métodos diretos garantem solução exata em \mathcal{O}(n^3), são robustos e não exigem critério de parada, porém consomem mais memória \mathcal{O}(n^2), sofrem fill-in e escalam mal para problemas muito grandes.

Exercícios relacionados