Raízes e Método de Newton

Encontrar $x$ com $f(x) = 0$ é um dos problemas mais recorrentes da computação numérica. Otimização, interseção de raios, cinemática inversa e calibração de modelos recaem nele.

Bisseção

Se $f$ é contínua e $f(a)f(b) < 0$, existe raiz no intervalo (teorema do valor intermediário). Divida ao meio repetidamente.

• Converge sempre, desde que a hipótese valha.
• Convergência linear: um bit de precisão por iteração.
• Cerca de 50 iterações para precisão de máquina.

É lenta, mas é a única que não falha. Serve como rede de segurança para métodos mais rápidos.

Newton-Raphson

$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$

A ideia: substituir $f$ pela reta tangente em $x_n$ e tomar a raiz dessa reta. É a expansão de Taylor de primeira ordem resolvida para zero.

def newton(f, df, x0, tol=1e-12, max_iter=100):
    x = x0
    for i in range(max_iter):
        fx = f(x)
        if abs(fx) < tol:
            return x, i
        dfx = df(x)
        if dfx == 0:
            raise ZeroDivisionError('derivada nula')
        passo = fx / dfx
        x -= passo
        if abs(passo) < tol * max(1.0, abs(x)):
            return x, i
    raise RuntimeError('não convergiu')

Convergência quadrática perto da raiz: o número de dígitos corretos dobra a cada iteração. Na prática, 5 ou 6 iterações bastam a partir de um chute razoável.

O preço: precisa da derivada, e a convergência é apenas local. Longe da raiz, Newton pode divergir, oscilar entre dois pontos ou saltar para outra bacia de atração. As fronteiras entre bacias de atração de Newton no plano complexo são fractais — o que ilustra bem quão sensível o método é ao ponto inicial.

Secante

Substitui a derivada por diferença finita entre os dois últimos pontos:

$$x_{n+1} = x_n - f(x_n)\frac{x_n - x_{n-1}}{f(x_n)-f(x_{n-1})}$$

Ordem de convergência $\varphi \approx 1{,}618$ — a razão áurea. Mais lento que Newton por iteração, mas não exige derivada e cada iteração custa apenas uma avaliação de $f$. Em termos de avaliações de função, muitas vezes vence Newton.

Comparação

Método	Ordem	Precisa de $f'$	Garantia
Bisseção	1 (linear)	Não	Sempre converge
Secante	~1,62	Não	Local
Newton	2 (quadrática)	Sim	Local
Brent	Superlinear	Não	Sempre converge

O método de Brent combina bisseção com interpolação quadrática inversa: mantém a garantia da bisseção e a velocidade dos métodos superlineares. É o padrão de scipy.optimize.brentq e a escolha correta em quase toda situação prática.

from scipy.optimize import brentq
raiz = brentq(f, a, b)     # rápido e sem risco de divergir

Critérios de parada

Este é o detalhe que separa código robusto de código que trava. Três critérios, e cada um falha sozinho:

• $|f(x_n)| < \varepsilon$ — falha se $f$ é muito achatada perto da raiz.
• $|x_{n+1}-x_n| < \varepsilon$ — falha se a convergência é lenta.
• Número máximo de iterações — a proteção final.

Use os três em conjunto, e prefira tolerância relativa ao valor de $x$. Um método iterativo sem limite de iterações é um laço infinito esperando acontecer.

Raízes múltiplas

Se a raiz tem multiplicidade $m > 1$, Newton perde a convergência quadrática e cai para linear. A correção:

$$x_{n+1} = x_n - m\frac{f(x_n)}{f'(x_n)}$$

Alternativa que não exige conhecer $m$: aplicar Newton a $u = f/f'$, cuja raiz é simples.

Newton em várias dimensões

$$x_{n+1} = x_n - J(x_n)^{-1}F(x_n)$$

com $J$ a matriz jacobiana. Na prática não se inverte $J$: resolve-se o sistema $J\Delta = -F$ e faz-se $x_{n+1} = x_n + \Delta$.

Em otimização, aplicar Newton a $\nabla f = 0$ dá o método de Newton para minimização, com a hessiana no lugar do jacobiano. Como formar e fatorar a hessiana é caro em dimensão alta, usam-se métodos quase-Newton (BFGS, L-BFGS) que a aproximam a partir do histórico de gradientes.

Exemplo trabalhado

Calcular $\sqrt{2}$ resolvendo $f(x) = x^2 - 2 = 0$. Com $f'(x) = 2x$:

$$x_{n+1} = x_n - \frac{x_n^2-2}{2x_n} = \frac{x_n + 2/x_n}{2}$$

Partindo de $x_0 = 1$:

$n$	$x_n$	Dígitos corretos
0	1	0
1	1,5	0
2	1,41666…	2
3	1,4142156…	5
4	1,4142135623746…	11

Os dígitos dobram a cada passo, como a teoria prevê. Essa recorrência é o método babilônico, conhecido há milênios — e continua sendo a base de implementações de raiz quadrada em hardware.

Aplicações em computação

Gráficos. Interseção de raio com superfície implícita; cinemática inversa de esqueletos animados.

Otimização. Newton e quase-Newton para treinar modelos e resolver problemas de engenharia.

Simulação. Métodos implícitos resolvem um sistema não linear a cada passo de tempo.

Finanças. Volatilidade implícita é a raiz de uma equação de precificação, tipicamente resolvida com Newton ou Brent.

Hardware. Divisão e raiz quadrada em processadores usam iteração de Newton sobre uma estimativa inicial de tabela.

Erros comuns

• Newton sem limite de iterações.
• Chute inicial ruim, levando a divergência ou à raiz errada.
• Derivada nula ou quase nula, causando passo enorme.
• Critério de parada só em $|f(x)|$.
• Inverter o jacobiano em vez de resolver o sistema.
• Ignorar Brent e implementar Newton à mão quando a biblioteca já resolve melhor.

Leituras recomendadas

• Burden e Faires, capítulo 2 — todos os métodos com análise de convergência.
• Trefethen e Bau — perspectiva de álgebra linear numérica sobre iterações.
• Documentação do scipy.optimize — brentq, newton, fsolve e quando usar cada um.
• Press et al., Numerical Recipes, capítulo 9 — implementações comentadas e discussão prática.

Richard L. Burden and J. Douglas Faires and Annette M. Burden (2015). Numerical Analysis. Cengage Learning. ISBN 9781305253667. Jorge Nocedal and Stephen J. Wright (2006). Numerical Optimization. Springer. DOI: 10.1007/978-0-387-40065-5.

Referências

1. Richard L. Burden; J. Douglas Faires; Annette M. Burden (2015). Numerical Analysis. Cengage Learning.
2. Jorge Nocedal; Stephen J. Wright (2006). Numerical Optimization. Springer.