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:
Conteúdo da matéria: resolução de sistemas
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
- A ideia é factorizar
(ou eliminar variáveis) em um número finito de operações exatas (ou quase exatas, considerando erro de ponto flutuante). - Exemplo clássico: eliminação de Gauss faz transformações elementares até achar
(triangular superior) e, opcionalmente, (triangular inferior), de modo que - 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. - Custo geral:
operações, independente de quanta parte de seja zero.
Passo 3
Métodos Iterativos – o que são e convergência
- Em vez de resolver tudo de uma vez, começamos com um chute
e refinamos: onde e vêm da decomposição de . - Exemplos:
- Jacobi: separa
, usa . - Gauss–Seidel:
. - Gradiente Conjugado (CG): para
simétrica definida positiva, converge em no máximo passos teoricamente.
- Jacobi: separa
- 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).
- Jacobi/G–Seidel precisam de dominância diagonal ou matriz estritamente diagonalmente dominante (ou simetria e PD) para garantir
- Cada iteração custa
, onde = número de elementos não nulos.
Passo 4
Esparsidade e impacto prático
- 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.
- Métodos diretos geram fill-in (novos elementos não nulos aparecem em
- Iterativos mantêm a esparsidade: cada passo só envolve multiplicar
por vetores, custando . - 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 (paranã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.