Disserte sobre os tipos de métodos iterativos

Passo 1

O que você pediu: “Disserte sobre os tipos de métodos iterativos”. Vou tratar do assunto de forma ampla e didática: explicar a ideia geral, classificar os métodos iterativos mais importantes, mostrar as fórmulas essenciais, dar intuições sobre convergência e custo, mostrar um pequeno exemplo numérico simples (para ver a mecânica de uma iteração) e dar dicas práticas para escolher e aplicar métodos em provas e implementação.
Informações que vou usar/assumir: sistemas lineares e problemas de raiz ou otimização são os contextos mais comuns onde métodos iterativos aparecem; denotarei por A uma matriz (quando for o caso), por b um vetor de termos independentes, por x o vetor incógnita, e por f(x) uma função vetorial quando falarmos de problemas não lineares.

Passo 2

Ideia geral dos métodos iterativos — o “quê” e o “porquê”:
  • Objetivo: produzir uma sequência \{x_k\}_{k\ge0} com \lim_{k\to\infty} x_k = x^*, onde x^* é a solução do problema (por exemplo solução de A x = b ou raiz de f(x)=0). Começamos com um chute inicial \,x_0.
  • Forma típica: atualizamos por uma regra simples a cada passo, por exemplo
x_{k+1} = G(x_k),
onde G é um operador (matriz, função, algoritmo) que melhora a aproximação. Essa é a forma de ponto fixo.
  • Conceito-chave de convergência: se G for uma contração (existir L\in[0,1) tal que \|G(x)-G(y)\|\le L\|x-y\|), então \{x_k\} converge linearmente para o ponto fixo. Em provas, frequentemente usará o Teorema do Ponto Fixo Contrátil.
  • Tipos de convergência: linear (erro decresce geometricamente), superlinear, e quadrática (cada iteração aproxima muito rápido — exemplo típico: Newton, quando perto da solução).

Passo 3

Métodos estacionários para sistemas lineares (splittings):
  • Contexto: resolver \,A x = b\, com A\in\mathbb{R}^{n\times n}. Faz-se uma decomposição (splitting)
A = M - N,
e a iteração estacionária é
M x_{k+1} = N x_k + b.
  • Iteração equivalente em forma de ponto fixo:
x_{k+1} = M^{-1} N x_k + M^{-1} b.
  • Critério de convergência: a iteração converge para a solução para qualquer x_0 se, e somente se,
\rho\big(M^{-1}N\big) < 1,
onde \rho(\cdot) é o raio espectral (maior valor absoluto dos autovalores).
  • Exemplos clássicos:
    • Jacobi: tome A = D + L + U (diagonal D, estritamente triangular L, U). Use M=D e N=-(L+U). Iteração:
    x_{k+1} = D^{-1}\big((L+U) x_k + b\big).
    • Gauss–Seidel: M = D+L, N = -U. Usa valores atualizados imediatamente dentro da iteração (sweep).
    • SOR (Successive Over-Relaxation): relaxação com parâmetro \omega, generaliza Gauss–Seidel para acelerar; escolha de \omega crítica (existem resultados teóricos para matrizes SPD).
  • Vantagens/desvantagens:
    • Simples, pouco custo por iteração, paralelizáveis (Jacobi é bem paralelizável).
    • Podem convergir muito lentamente se A tiver espectro desfavorável (condicionamento ruim).

Passo 4

Exemplo numérico simples (Jacobi, uma iteração) — para ver cálculos passo a passo:
  • Sistema:
A=\begin{pmatrix}4 & 1\\\\ 2 & 3\end{pmatrix},\qquad b=\begin{pmatrix}1\\\\ 1\end{pmatrix}.
  • Identificamos D=\operatorname{diag}(4,3), L=\begin{pmatrix}0&0\\\ 2&0\end{pmatrix}, U=\begin{pmatrix}0&1\\\ 0&0\end{pmatrix}.
  • Jacobi: x_{k+1}=D^{-1}\big((L+U)x_k + b\big). Escolha x_0=(0,0)^\top.
  • Cálculo de x_1:
    • Primeiro componente:
    x_{1}^{(1)} = \frac{1 - (1)\cdot x_0^{(2)}}{4} = \frac{1-0}{4} = \frac{1}{4}.
    • Segundo componente:
    x_{1}^{(2)} = \frac{1 - (2)\cdot x_0^{(1)}}{3} = \frac{1-0}{3} = \frac{1}{3}.
  • Logo x_1 = \big(\tfrac{1}{4},\tfrac{1}{3}\big)^\top. Isso mostra a mecânica: cada componente é atualizado isoladamente usando a diagonal.

Passo 5

Métodos de subespaço de Krylov (métodos projectionais) — para grandes sistemas esparsos:
  • Ideia: construir aproximações em espaços gerados pelos resíduos: o m-ésimo subespaço de Krylov é
\mathcal{K}_m(A,r_0) = \operatorname{span}\{r_0, A r_0, A^2 r_0,\dots,A^{m-1} r_0\},
onde r_0=b-A x_0.
  • Métodos importantes:
    • Conjugate Gradient (CG): para A simétrica e definida positiva (SPD). Propriedades: cada iteração produz uma solução ótima sobre \mathcal{K}_k no sentido da norma A-energy; em aritmética exata converge em no máximo n passos; converge muito mais rápido quando o condicionamento é bom.
    • GMRES: para matrizes gerais (nãossimétricas). Minimiza o resíduo em norma 2 sobre \mathcal{K}_m — armazenamento cresce com m, por isso usa-se restart.
    • BiCG, BiCGSTAB: variantes para sistemas não simétricos com menos armazenamento que GMRES.
  • Taxa de convergência (CG): depende do número de condição \kappa(A)=\lambda_{\max}/\lambda_{\min}. Um limite clássico é
\|e_k\|_A \le 2\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^k \|e_0\|_A,
onde \|v\|_A=\sqrt{v^\top A v} e e_k=x_k-x^*.
  • Observação prática: Krylov é a escolha usual para grandes sistemas esparsos; eficiência depende fortemente de pré-condicionamento (ver Passo 10).

Passo 6

Métodos baseados em gradiente para problemas quadráticos e otimização:
  • Steepest Descent (descida mais íngreme) para minimizar f(x)=\tfrac{1}{2}x^\top A x - b^\top x (com A SPD): atualiza por
x_{k+1}=x_k - \alpha_k r_k,\qquad r_k = A x_k - b,
com passo ótimo
\alpha_k = \frac{r_k^\top r_k}{r_k^\top A r_k}.
  • Steepest Descent é simples, mas pode convergir muito lentamente (zig-zag) se \kappa(A) grande.
  • Conjugate Gradient pode ser visto como uma versão bem melhorada do método do gradiente para quadráticas: constrói direções conjugadas e evita zig-zag.

Passo 7

Métodos Newton e quasi-Newton para problemas não lineares:
  • Problema: encontrar x^* tal que f(x^*)=0 (função vetorial) ou minimizar g(x).
  • Newton (multidimensional): iteração
x_{k+1} = x_k - \big(J_f(x_k)\big)^{-1} f(x_k),
onde J_f é a Jacobiana de f. Para otimização, substitui-se pela Hessiana de g.
  • Convergência: quadrática local se J_f(x^*) é invertível e o chute inicial está suficientemente perto.
  • Custo por iteração: montar e resolver um sistema linear com a Jacobiana — caro para problemas grandes.
  • Quasi-Newton (por exemplo BFGS): aproxima a inversa da Jacobiana/Hessiana atualizando uma matriz H_k barato; consegue convergência superlinear sem fatoração completa a cada passo.
  • Dicas práticas: em provas, mostre derivação do passo Newton por linearizar f (aproximação de Taylor) e cite condição de convergência local.

Passo 8

Métodos iterativos para autovalores:
  • Power method: encontra o autovalor dominante \lambda_1 e vetor próprio associado; itera y_{k+1}=A y_k normalizando a cada passo. Converge com taxa aproximadamente |\lambda_2/\lambda_1|^k.
  • Inverse iteration e Rayleigh quotient iteration: para aproximar autovalores próximos a um shift \mu. Rayleigh iteration tem convergência cúbica em algumas condições.
  • QR algorithm: método clássico para todos os autovalores (mais matriz-densa, não tanto iterativo de larga escala como Krylov).

Passo 9

Multigrid e métodos de hierarquia:
  • Ideia: erros têm componentes de baixa e alta frequência; métodos locais (Jacobi/GS) eliminam bem erros de alta frequência (smoothing) mas não os de baixa frequência. Usar uma grade mais grossa para tratar erros de baixa frequência — intercalar suavização e correção em grades mais grossas.
  • Tipos: geometric multigrid (quando se conhece a malha) e algebraic multigrid (AMG) para matrizes gerais.
  • Propriedade poderosa: complexidade O(n) para muitos problemas elípticos — ou seja, custo ótimo. Em provas, explique o ciclo V/W e a ideia de restrição/prolongamento.
  • Em implementação prática, multigrid costuma ser a técnica mais rápida para equações diferenciais elípticas.

Passo 10

Pré-condicionamento — o truque número um para acelerar:
  • Objetivo: transformar o sistema para melhorar as propriedades espectrais e acelerar a convergência de métodos iterativos (especialmente Krylov).
  • Forma simples: resolver aproximadamente
M^{-1} A x = M^{-1} b
ou usar pré-condicionamento à direita (A M^{-1}) y = b com x = M^{-1} y.
  • Bons pré-condicionadores fazem \kappa(M^{-1}A) ser muito menor que \kappa(A). Exemplos:
    • Jacobi (diagonal) M=D — barato, efeito limitado.
    • ILU (incomplete LU), IC (incomplete Cholesky) — fatorações incompletas que capturam estrutura de A e são eficazes.
    • Multigrid como pré-condicionador.
  • Em provas, indique o tipo de pré-condicionador apropriado: se A diagonally dominant, Jacobi pode já ajudar; para matrizes PDE, ILU/AMG costumam ser melhores.

Passo 11

Critérios de parada, erros e estabilidade:
  • Critério comum: norma do resíduo \|r_k\| = \|b-A x_k\| pequena. Ex.: parar quando \|r_k\|/\|b\| < \varepsilon.
  • Atenção: resíduo pequeno não garante erro absoluto pequeno se A for mal condicionado. Relação (teórica) entre erro e resíduo:
\frac{\|x_k-x^*\|}{\|x^*\|} \le \kappa(A) \frac{\|r_k\|}{\|b\|}.
  • Estar atento a: estagnação (sem progresso devido a cancelamentos numéricos), efeitos de arredondamento, necessidade às vezes de reiniciar métodos (ex.: GMRES restarted).

Passo 12

Como escolher método na prática (resumo rápido para prova/implementação):
  • Se A pequeno e denso: fatoração direta (LU, Cholesky) é preferível.
  • Se A grande e esparso:
    • A SPD: use Conjugate Gradient + pré-condicionador (IC, Jacobi, AMG).
    • A não-simétrico: GMRES (com restart) ou BiCGSTAB; escolha pré-condicionador compatível.
  • Se problema é não linear: tente Newton quando puder computar/usar Jacobiana; se não, quasi-Newton (BFGS) ou métodos de gradiente.
  • Se problema vem de PDEs elípticas estruturadas: pense em multigrid (muito eficiente).
  • Sempre verifique custo por iteração (produto matriz-vetor, fatoração incompleta, armazenamento) e paralelização (Jacobi é fácil de paralelizar; Gauss–Seidel menos).

Passo 13

Dicas práticas rápidas e truques de prova:
  • Ao pedir prova de convergência de um método estacionário, mostre o splitting A=M-N e foque em \rho(M^{-1}N).
  • Para Newton, deduza o passo linearizando f(x) por Taylor: f(x_k+h)\approx f(x_k)+J_f(x_k)h e imponha f(x_k+h)=0 para obter h.
  • Para CG, memorize a relação com espaços de Krylov e o fato de ser ótimo na norma A.
  • Em exercícios de prova, comente sobre custo (número de produtos A v, necessidade de armazenar vetores) — o examinador costuma valorizar essa análise.
  • Quando pede “qual método escolher”, justifique com propriedades da matriz (simetria, positividade, esparsidade) e restrições computacionais (memória, paralelismo).

Passo 14

Recapitulando com linguagem direta e motivadora:
  • Métodos iterativos são suas ferramentas quando a solução exata direta é cara ou impossível; a ideia é melhorar um chute passo a passo.
  • Principais famílias:
    • estacionários (Jacobi, Gauss–Seidel, SOR), simples e com iteração de forma M^{-1}N;
    • Krylov (CG, GMRES, BiCGSTAB), poderosos para grandes sistemas esparsos;
    • gradiente e variantes (steepest descent, conjugate gradient — para quadráticas);
    • Newton e quasi-Newton (problemas não lineares; convergência local rápida);
    • multigrid (hierárquico, ótimo para PDEs elípticas);
    • métodos para autovalores (power, inverse, Rayleigh, QR);
    • pré-condicionamento (melhora o espectro — quase sempre necessário em problemas reais).
  • Foco prático: aprenda a identificar propriedades da matriz/problema e combine método + pré-condicionador; na prova, explique convergência com argumentos espectrais ou por linearização (Newton).

Resposta

Stationary: Jacobi, Gauss–Seidel, SOR (splitting A=M-N, converge se \rho(M^{-1}N)<1).
Krylov/subespaço: Conjugate Gradient (SPD), GMRES (geral), BiCG/BiCGSTAB (não-simétrico) — constróem \mathcal{K}_m(A,r_0).
Gradient-based: Steepest Descent, Conjugate Gradient (para quadráticas).
Newton e quasi-Newton: Newton (quadrática local), BFGS, L-BFGS (menos custo por iteração).
Eigenvalue iterativos: Power method, inverse iteration, Rayleigh quotient iteration, QR.
Multigrid/Hierárquicos: geometric AMG / algebraic AMG, ciclo V/W, ótimo para PDE elípticas.
Pré-condicionamento: Jacobi, ILU, IC, multigrid como pré-condicionador (melhora \kappa(M^{-1}A)).
Critérios práticos: controle por resíduo \|r_k\|, atenção ao condicionamento e ao custo por iteração.

Exercícios relacionados