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.

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:
\;(1) São particularmente úteis quando a matriz dos coeficientes é esparsa.
\;(2) Convergem apenas se a matriz dos coeficientes for estritamente diagonal dominante.
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 \{x^{(k)}\} para a solução de
A x = b,
começando de um chute inicial x^{(0)} e repetindo uma fórmula do tipo
x^{(k+1)} = T\,x^{(k)} + c,
onde T é chamada matriz de iteração e c um vetor fixo. A convergência (ou seja, x^{(k)}\to x solução) depende da matriz T. A condição necessária e suficiente para convergência (para métodos lineares estacionários) é
\rho(T) < 1,
onde \rho(T) é o raio espectral de T, definido como
\rho(T)=\max\{|\lambda|:\lambda\\ \text{é autovalor de }T\}.é
Explicando: se todos os autovalores de T têm módulo estritamente menor que 1, as potências T^k tendem a zero e a iteração converge.
Para construir T em métodos clássicos: escrevemos
A = D + L + U,
onde D é a diagonal de A, L é a estritamente triangular inferior e U a estritamente triangular superior. Exemplos:
  • Jacobi: \;x^{(k+1)} = -D^{-1}(L+U)\,x^{(k)} + D^{-1}b, então
T_{J} = -D^{-1}(L+U).
  • Gauss–Seidel: \;x^{(k+1)} = -(D+L)^{-1}U\,x^{(k)} + (D+L)^{-1}b, então
T_{GS} = -(D+L)^{-1}U.
A convergência desses métodos depende de \rho(T_J) ou \rho(T_{GS}).

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:
  • Métodos diretos (por exemplo eliminação de Gauss / fatoração LU) 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 A v 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 A é esparsa. Portanto a afirmação (1) é verdadeira.

Passo 4

Explicando por que a segunda afirmação é falsa — e ensinando a ideia correta sobre convergência.
A afirmação (2) 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 diagonal dominante estrita por linhas (ou por colunas) é uma condição suficiente para a convergência de Jacobi e Gauss–Seidel: se para todo i vale
|a_{ii}| > \sum_{j\ne i} |a_{ij}|,
então \|D^{-1}(L+U)\|_\infty <1 e, portanto, \rho(T_J)<1 (e também Gauss–Seidel converge). Aqui usei a norma infinito: para a matriz D^{-1}(L+U) a soma absoluta de cada linha é \frac{1}{|a_{ii}|}\sum_{j\ne i}|a_{ij}| <1, então \|T_J\|_\infty<1\Rightarrow\rho(T_J)<1.
  • 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 A é 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 A é simétrica definida positiva então Gauss–Seidel converge — outra vez sem precisar de diagonal dominante estrita.
Vou dar um exemplo concreto (contra-exemplo da necessidade): considere
A=\begin{pmatrix}2 & 3 \\[4pt] 3 & 5\end{pmatrix}.
  • Esta matriz não é estritamente diagonal dominante pela primeira linha, porque |a_{11}|=2 e \sum_{j\ne1}|a_{1j}|=3, logo 2 \not> 3. Portanto não é estritamente diagonal dominante por linhas.
  • Contudo, A é simétrica e definida positiva: o determinante é 2\cdot5-3\cdot3 = 1>0 e o traço é 7>0, 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 ⇔ \rho(T)<1, onde T é 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.
    • A simétrica definida positiva ⇒ Gradiente Conjugado converge; Gauss–Seidel também converge.
    • Se \|T\| < 1 em alguma norma matricial ⇒ convergência (porque \rho(T) \le \|T\| < 1).
  • 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 \rho(T)<1.

Resposta

(1) Verdadeiro.
(2) Falso.

Exercícios relacionados