O que é um critério de parada de um método iterativo?

Passo 1

O que o enunciado pede: explicar, de forma didática e passo a passo, o que é um critério de parada de um método iterativo.
Informações dadas (explícitas ou implícitas): não há números nem um método específico fornecido — a explicação deve ser geral, com exemplos (por exemplo, métodos de raiz como Newton, ou métodos para sistemas lineares como Jacobi/Gauss–Seidel). A tarefa é definir, listar tipos comuns, mostrar fórmulas, dar exemplos numéricos simples e indicar como escolher/usar na prova.

Passo 2

Definição básica (introdução e notação).
Um método iterativo gera uma sequência de aproximações \{x^{(k)}\}_{k=0}^{\infty} que, espera-se, converge para a solução x^* de um problema (por exemplo, raiz de f, ou solução de Ax=b). Um critério de parada é uma condição booleana avaliada nas iterações que decide quando interromper o processo e aceitar x^{(k)} como solução aproximada. Formalmente, parametrize a condição por uma função booleana
C\big(x^{(k)},x^{(k-1)},r^{(k)},k\big),
onde r^{(k)} é o residuo (se aplicável) e k é o número da iteração; parar quando C for verdadeira.

Passo 3

Critérios mais usados — apresentação e fórmulas (cada fórmula com explicação das variáveis).
  1. Critério pelo tamanho da diferença entre iterados (erro de iteração, absoluto):
\|x^{(k)}-x^{(k-1)}\| \le \text{tol}_{\text{abs}}.
Aqui \|\cdot\| é uma norma (por ex. norma Euclidiana \|\cdot\|_2 ou norma infinita \|\cdot\|_\infty), e \text{tol}_{\text{abs}} é a tolerância absoluta escolhida.
  1. Critério relativo entre iterados (mais estável se solução grande ou pequena):
\frac{\|x^{(k)}-x^{(k-1)}\|}{\|x^{(k)}\|} \le \text{tol}_{\text{rel}}.
Aqui \text{tol}_{\text{rel}} é a tolerância relativa (ex.: 10^{-6}).
  1. Critério pelo residuo (útil em sistemas lineares e em busca de raízes):
  • Para sistemas lineares Ax=b: \;r^{(k)}=b-Ax^{(k)} e
\|r^{(k)}\| \le \text{tol}_{\text{abs}}\quad\text{ou}\quad \frac{\|r^{(k)}\|}{\|b\|}\le\text{tol}_{\text{rel}}.
  • Para raiz de função f(x)=0: usar \lvert f(x^{(k)})\rvert \le \text{tol}.
  1. Critério de parada por número máximo de iterações:
k \ge k_{\max},
útil para garantir término e evitar loops infinitos.
  1. Detecção de estagnação (mudanças muito pequenas por muitas iterações): exemplo prático: se \|x^{(k)}-x^{(k-1)}\|<\epsilon_s por m iterações consecutivas, parar por provável estagnação.

Passo 4

Exemplos numéricos concretos para “ver com a mão” (raiz com Newton e sistema linear).
Exemplo A — Newton para f(x)=0. Critérios possíveis:
  • Residuo: parar se \lvert f(x^{(k)})\rvert < 10^{-8}.
  • Diferença de iterações: parar se \lvert x^{(k)}-x^{(k-1)}\rvert < 10^{-10}.
    Ambos em conjunto: parar quando qualquer um se satisfaz.
Exemplo B — Sistema linear Ax=b. Pegue A, b, aprox inicial x^{(0)}. Em cada iteração calcula-se r^{(k)}=b-Ax^{(k)}. Critério prático:
\frac{\|r^{(k)}\|_2}{\|b\|_2}\le 10^{-6}.
Isto diz que o erro relativo no residuo está abaixo de uma tolerância típica.

Passo 5

Prós e contras dos critérios (por que escolher um ou outro).
  • Diferença entre iterados:
    • Prós: fácil de calcular; indica que a sequência estabilizou.
    • Contras: pode indicar estabilização longe da solução (stagnation) — \|x^{(k)}-x^{(k-1)}\| pequeno não garante \|x^{(k)}-x^*\| pequeno.
  • Residuo:
    • Prós: diretamente ligado à equação que se quer satisfazer; se \|r^{(k)}\| pequeno, normalmente a solução satisfaz a equação com boa precisão.
    • Contras: para problemas mal condicionados, residuo pequeno pode corresponder a erro grande na solução; daí usar residuo relativo é melhor.
  • Critério combinado:
    • Muito recomendado: combinar um critério de residuo (relativo) com limite de iterações e detecção de estagnação. Isso evita falso conforto e também iterações infinitas.

Passo 6

Como escolher tolerâncias na prática e regras de bolso para prova.
  • Relacione tol ao número de dígitos desejados: se quer p casas decimais corretas, escolha \text{tol}_{\text{rel}}\approx 10^{-p}. Ex.: para 6 dígitos, use 10^{-6}.
  • Não peça tolerâncias menores que a precisão da máquina: em precisão dupla, \epsilon_{\text{mach}}\approx 2,22\times 10^{-16}. Evite tol muito perto de \epsilon_{\text{mach}}.
  • Em sistemas lineares, use residuo relativo: \|r^{(k)}\|/\|b\| porque isso normaliza pela escala do problema.
  • Em provas: escreva explicitamente o critério escolhido (fórmula), o valor da tolerância e justifique por que é adequado (ex.: “tol =10^{-6} para obter 6 dígitos”).

Passo 7

Exemplo de esquema prático (pseudo-algoritmo simples) com um critério combinado.
\text{Inicialize }x^{(0)},\;k\leftarrow0
Enquanto k<k_{\max}:
\text{compute }x^{(k+1)} \quad\text{e}\quad r^{(k+1)}=b-Ax^{(k+1)}\\ (\text{se aplicável})á
Se
\frac{\|r^{(k+1)}\|}{\|b\|}\le\text{tol}_{\text{rel}}\quad\text{ou}\quad \frac{\|x^{(k+1)}-x^{(k)}\|}{\|x^{(k+1)}\|}\le\text{tol}_{\text{rel2}}
então pare e aceite x^{(k+1)}. Caso contrário, k\leftarrow k+1 e continue. Se atingir k_{\max}, pare e reporte não-convergência.

Passo 8

Dicas para a prova (o que escrever e como justificar rapidamente).
  • Declare o critério com a fórmula e explique as variáveis (ex.: “paro quando \|r^{(k)}\|_2/\|b\|_2\le10^{-6}, onde r^{(k)}=b-Ax^{(k)}”).
  • Justifique a escolha da tolerância (escala do problema, precisão desejada).
  • Se pedir, mostre que o critério foi satisfeito calculando o valor numérico do teste na iteração indicada.
  • Sempre inclua um k_{\max} na resposta para cobrir casos de não-convergência.

Passo 9

Resumo prático curto e incentivo final.
Um critério de parada é a regra que diz “chega, aceita isso como solução aproximada”, normalmente baseada em tamanho da mudança entre iterações, tamanho do residuo, ou um limite de iterações. Na prova, seja explícito na fórmula, escolha tolerâncias justificadas e, se puder, use critérios combinados para segurança. Você consegue — foco nas fórmulas e pratique um exemplo rápido para fixar.

Resposta

Um critério de parada é uma condição que determina quando encerrar as iterações de um método iterativo; exemplos típicos são \|x^{(k)}-x^{(k-1)}\|\le\text{tol}_{\text{abs}}, \dfrac{\|x^{(k)}-x^{(k-1)}\|}{\|x^{(k)}\|}\le\text{tol}_{\text{rel}}, \dfrac{\|r^{(k)}\|}{\|b\|}\le\text{tol}_{\text{rel}} (com r^{(k)}=b-Ax^{(k)} em sistemas lineares), e sempre combinar isso com um limite máximo de iterações k_{\max}.

Exercícios relacionados