7 Métodos Iterativos
Sobre os métodos iterativos para solução de sistemas lineares, é correto afirmar que:
- São particularmente úteis quando a matriz dos coeficientes é esparsa.
- Convergem apenas se a matriz dos coeficientes for estritamente diagonal dominante.
Sobre os métodos iterativos para solução de sistemas lineares, é correto afirmar que:
Passo 1
O enunciado apresenta duas afirmações sobre métodos iterativos para resolver sistemas lineares e nos pede avaliar se cada uma é correta. As duas afirmações são:
Lista das informações relevantes que o enunciado dá:
- Temos métodos iterativos para sistemas lineares (por exemplo Jacobi, Gauss–Seidel, Gradientes Conjugados, etc.).
- Devemos julgar a veracidade de duas afirmações acima, separadamente.
Passo 2
O que são, em poucas palavras, os métodos iterativos e como eles funcionam (aula rápida e necessária para entender as respostas).
Um método iterativo constrói uma sequência de aproximações para a solução de
Um método iterativo constrói uma sequência de aproximações
começando de um chute inicial
e repetindo uma fórmula do tipo
onde
é chamada matriz de iteração e
um vetor fixo. A convergência (ou seja,
solução) depende da matriz
. A condição necessária e suficiente para convergência (para métodos lineares estacionários) é
onde
é o raio espectral de
, definido como
Explicando: se todos os autovalores de
têm módulo estritamente menor que
, as potências
tendem a zero e a iteração converge.
Para construir
em métodos clássicos: escrevemos
onde
é a diagonal de
,
é a estritamente triangular inferior e
a estritamente triangular superior. Exemplos:
- Jacobi:
, então
- Gauss–Seidel:
, então
A convergência desses métodos depende de
ou
.
Passo 3
Explicando por que a primeira afirmação é correta (detalhadinho, sem enrolar).
O que significa matriz esparsa? Uma matriz é esparsa quando a maioria dos seus elementos é zero — por exemplo matrizes de malhas, problemas de diferenças finitas, grafos grandes etc. Para essas matrizes:
O que significa matriz esparsa? Uma matriz é esparsa quando a maioria dos seus elementos é zero — por exemplo matrizes de malhas, problemas de diferenças finitas, grafos grandes etc. Para essas matrizes:
- Métodos diretos (por exemplo eliminação de Gauss / fatoração
) tendem a causar “fill-in”: zeros na matriz original viram não-zeros nas matrizes fatoradas, aumentando muito o custo de armazenamento e de CPU. Em problemas grandes isso pode ser proibitivo. - Métodos iterativos usam principalmente produtos matriz-vetor
e operações com vetores, que exploram diretamente a esparsidade: só é preciso acessar os elementos não-zero. Assim a complexidade e memória tornam-se proporcionais ao número de não-zeros, e não ao quadrado da dimensão. - Além disso, métodos como Gradiente Conjugado, GMRES, etc., são projetados para matrizes grandes e esparsas e têm custo por iteração linear no número de não-zeros.
Conclusão: é verdade que métodos iterativos são particularmente úteis quando
é esparsa. Portanto a afirmação
é verdadeira.
Passo 4
Explicando por que a segunda afirmação é falsa — e ensinando a ideia correta sobre convergência.
A afirmação diz que “convergem apenas se a matriz for estritamente diagonal dominante”. Isso afirma que a diagonal dominante estrita é condição necessária para convergência. Mas na verdade:
A afirmação
- A diagonal dominante estrita por linhas (ou por colunas) é uma condição suficiente para a convergência de Jacobi e Gauss–Seidel: se para todo
vale
então
e, portanto,
(e também Gauss–Seidel converge). Aqui usei a norma infinito: para a matriz
a soma absoluta de cada linha é
, então
.
- Contudo, diagonal dominante estrita NÃO é necessária. Existem muitas matrizes que não são diagonalmente dominantes e para as quais métodos iterativos convergem. Exemplos de situações em que convergência ocorre sem diagonal dominante:
- Se
é simétrica definida positiva (SPD), o método do Gradiente Conjugado (Conjugate Gradient) converge (na prática é muito usado para sistemas SPD grandes e esparsos). SPD não implica diagonal dominante estrita, logo há convergência sem esta condição. - Para Gauss–Seidel também existe teoria: se
é simétrica definida positiva então Gauss–Seidel converge — outra vez sem precisar de diagonal dominante estrita.
- Se
Vou dar um exemplo concreto (contra-exemplo da necessidade): considere
- Esta matriz não é estritamente diagonal dominante pela primeira linha, porque
e , logo . Portanto não é estritamente diagonal dominante por linhas. - Contudo,
é simétrica e definida positiva: o determinante é e o traço é , então os autovalores são positivos. Para uma matriz SPD o método do Gradiente Conjugado converge (e Gauss–Seidel também converge). Assim temos convergência sem diagonal dominante estrita. Logo a afirmação de que convergem apenas se houver diagonal dominante estrita é falsa.]
Passo 5
Resumo dos critérios de convergência práticos (coisas para decorar e usar na prova)
- Condição geral (para métodos lineares estacionários): convergência ⇔
, onde é a matriz de iteração. Isso é a regra básica, matemática e necessária/suficiente. - Condições suficientes comuns:
- Diagonal dominante estrita por linhas ⇒ Jacobi e Gauss–Seidel convergem.
-
simétrica definida positiva ⇒ Gradiente Conjugado converge; Gauss–Seidel também converge. - Se
em alguma norma matricial ⇒ convergência (porque ).
- Não confundir: condições suficientes (úteis porque são fáceis de checar) não são necessárias — há muitas matrizes que convergem mesmo sem satisfazê‑las.
Passo 6
Motivação prática curta (estou torcendo por você)
- Na prova: quando virem uma frase do tipo “apenas se” — cuidado: verifiquem se é condição necessária ou suficiente.
- Se pedirem justificar por que um método é bom para matrizes esparsas, cite a operação produto matriz-vetor e o problema de fill-in em métodos diretos.
- Se perguntarem sobre convergência de Jacobi/Gauss–Seidel, mencione diagonal dominante estrita como condição suficiente e a condição geral
.