Compare os métodos Diretos e Iterativos para resolução de Sistemas Lineares quanto a convergência e esparsidade da matriz A.

Passo 1

Beleza, aqui a gente tem que “comparar os métodos Diretos e Iterativos para resolver sistemas lineares” – ou seja, ver no que eles se diferenciam quando o assunto é convergência (se e como eles chegam à solução) e como eles lidam com a esparsidade da matriz (as positividades e zeros dela).
Conteúdo da matéria: resolução de sistemas por métodos diretos (como eliminação de Gauss / LU) e por métodos iterativos (como Jacobi, Gauss–Seidel, Gradiente Conjugado).
O que vamos precisar:
  • Definir brevemente cada método
  • Falar das “condições de convergência” (quando e por que cada um funciona)
  • Explicar o impacto da esparsidade (quantos zeros a matriz tem) em cada abordagem

Passo 2

Métodos Diretos – o que são e convergência
  1. A ideia é factorizar A = L,U (ou eliminar variáveis) em um número finito de operações exatas (ou quase exatas, considerando erro de ponto flutuante).
  2. Exemplo clássico: eliminação de Gauss faz transformações elementares até achar (triangular superior) e, opcionalmente, (triangular inferior), de modo que
  3. Convergência: sempre chega à solução exata (na matemática exata), desde que seja não-singular. Em aritmética real, rodelas de pivotamento garantem estabilidade.
  4. Custo geral: operações, independente de quanta parte de seja zero.

Passo 3

Métodos Iterativos – o que são e convergência
  1. Em vez de resolver tudo de uma vez, começamos com um chute x^(k+1) = G,x^(k) + c, e refinamos: onde e vêm da decomposição de .
  2. Exemplos:
    • Jacobi: separa , usa .
    • Gauss–Seidel: .
    • Gradiente Conjugado (CG): para simétrica definida positiva, converge em no máximo passos teoricamente.
  3. Convergência depende de propriedades de ou do espectro de :
    • Jacobi/G–Seidel precisam de dominância diagonal ou matriz estritamente diagonalmente dominante (ou simetria e PD) para garantir .
    • CG exige que seja simétrica definida positiva (SPD).
  4. Cada iteração custa , onde = número de elementos não nulos.

Passo 4

Esparsidade e impacto prático
  1. Para matrizes grandes e muito esparsas (muitas entradas zero):
    • Métodos diretos geram fill-in (novos elementos não nulos aparecem em e ), destruindo a esparsidade original.
    • Isso eleva o custo em memória e tempo, mesmo que fosse cheia de zeros.
  2. Iterativos mantêm a esparsidade: cada passo só envolve multiplicar por vetores, custando .
  3. Então, quando é muito grande e esparsa, iterativos costumam ser bem mais eficientes, desde que eles realmente converjam rápido.

Passo 5

Resumindo a comparação
  • Convergência
    Diretos: sempre convergem (para não singular), custo .
    Iterativos: convergem só sob condições (diagonal dominante, SPD etc.), mas cada passo é barato.
  • Esparsidade
    Diretos: perdem zeros (fill-in), memória e tempo crescem muito.
    Iterativos: preservam zeros, ideal para matrizes esparsas.

Resposta

Métodos diretos garantem solução exata em número finito de operações, sem depender de propriedades especiais de , mas custam e geram fill-in que estraga a esparsidade. Já os iterativos (Jacobi, Gauss–Seidel, CG) exploram a esparsidade, cada passo custa e mantêm a matriz “leve”, porém só convergem sob condições como dominância diagonal ou SPD.

Exercícios relacionados