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:
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 é
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:
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.