Zeros de funções e o Método de Newton

No post sobre o Método do Ponto Fixo terminei com a observação de que a vantagem real do MPF não é velocidade, mas sim que ele serve de base para métodos mais rápidos, por exemplo, o método de newton.

A ideia central do MPF é construir uma função de iteração $\varphi(x)$ tal que $|\varphi'(\xi)| < 1$ na vizinhança da raiz. Quanto menor $|\varphi'(\xi)|$, mais rápida a convergência. Então o que acontece se a gente escolher $\varphi$ de forma que $\varphi'(\xi) = 0$ exatamente?

Derivando a fórmula

Toda função de iteração válida tem a forma

Derivando:

Na raiz $\xi$, $f(\xi) = 0$, então

Para que $\varphi'(\xi) = 0$:

Assumindo essa forma para todo $x$, ou seja, $A(x) = -1/f'(x)$, e substituindo:

Essa é a função de iteração do Método de Newton. A relação de recorrência fica:

A interpretação geométrica

Tem uma forma mais intuitiva de chegar na mesma fórmula. A reta tangente à curva $f(x)$ no ponto $(x_k, f(x_k))$ é:

O zero dessa reta, ou seja, onde ela cruza o eixo $x$:

Que é exatamente $x_{k+1}$. Newton está aproximando a função por sua tangente a cada iteração e usando o zero dessa reta como próxima estimativa. Se a função for “bem comportada” perto da raiz, a tangente é uma boa aproximação local e o método avança rápido.

Veja como as iterações saltam direto para perto da raiz. A partir do segundo passo, já está na 5ª casa decimal.

Convergência quadrática

O que faz Newton especial é a ordem de convergência. Para o MPF, em geral, a ordem é linear ($p = 1$): o erro cai por um fator constante a cada iteração. Para Newton, como $\varphi'(\xi) = 0$, a análise da convergência mostra que o erro satisfaz:

Ordem $p = 2$: o erro na iteração seguinte é proporcional ao quadrado do erro atual. Na prática, isso significa que o número de dígitos corretos dobra a cada iteração.

A derivada de $\varphi$ do método de Newton é $\varphi'(x) = f(x)f''(x)/[f'(x)]^2$. Na raiz, $f(\xi) = 0$, logo $\varphi'(\xi) = 0$, que é justamente o que queríamos quando derivamos a fórmula.

Implementando em Python

1
import math
2

3
def f(x):
4
    return x * math.log10(x) - 1
5

6
def df(x):
7
    return math.log10(x) + 1 / math.log(10)
8

9
def newton(f, df, x0, eps=1e-5):
10
    x = x0
11
    k = 0
12
    while True:
13
        fx  = f(x)
14
        dfx = df(x)
15
        x_novo = x - fx / dfx
16
        erro = abs(x_novo - x) / abs(x_novo)
17
        k += 1
18
        print(f"Iteração {k:2d}: x = {x_novo:.8f}, f(x) = {f(x_novo):.2e}, erro = {erro:.2e}")
19
        if erro < eps:
20
            return x_novo
21
        x = x_novo
22

23
raiz = newton(f, df, x0=2)
24
print(f"\nRaiz encontrada: {raiz:.6f}")

Rodando para a mesma $f(x) = x \cdot \log_{10}(x) - 1$ do post da bissecção, a partir de $x_0 = 2$:

1
Iteração  1: x = 2.54117607, f(x) = 2.93e-02, erro = 2.13e-01
2
Iteração  2: x = 2.50630938, f(x) = 1.04e-04, erro = 1.39e-02
3
Iteração  3: x = 2.50618415, f(x) = 1.36e-09, erro = 5.00e-05
4
Iteração  4: x = 2.50618415, f(x) = 0.00e+00, erro = 6.51e-10
5

6
Raiz encontrada: 2.506184

4 iterações para $\varepsilon = 10^{-5}$. A bissecção precisou de 17 para o mesmo resultado.

O padrão de convergência quadrática aparece nas colunas de erro: de 1.39e-02 para 1.06e-04 é uma queda de $10^4$, não $10^2$ como seria no caso linear, porque o erro já está pequeno o suficiente para o termo quadrático dominar.

A influência do chute inicial

Para ver na prática o que o teorema diz, considere $f(x) = x^3 - x - 1$, com $f'(x) = 3x^2 - 1$.

a) Chute inicial $x_1 = 1$

Raiz $x \approx 1{,}324718$ com 6 casas decimais, convergida em 5 iterações.

b) Chute inicial $x_1 = 0{,}6$

A derivada $f'(x) = 3x^2 - 1$ se anula em $x = 1/\sqrt{3} \approx 0{,}577$. O ponto $x_1 = 0{,}6$ está exatamente nessa vizinhança crítica:

A derivada quase nula faz a reta tangente ficar quase horizontal, disparando $x_2$ para longe da raiz. O método não diverge, ele encontra a raiz, mas leva 12 iterações para chegar lá, contra 5 do chute $x_1 = 1$:

Desvantagens

O método exige $f'(x_k) \neq 0$ em todo passo. Se a derivada for zero ou muito próxima de zero, a divisão explode e o método diverge.

A convergência também não é garantida globalmente. O teorema diz que existe um intervalo $\bar{I}$ em torno de $\xi$ tal que, para qualquer $x_0 \in \bar{I}$, o método convergel, mas não especifica o tamanho desse intervalo. Em funções com muitos zeros ou regiões planas, um chute inicial ruim pode levar o método para longe da raiz que você quer encontrar.

Para esses casos, a estratégia comum é usar a bissecção primeiro para isolar a raiz num intervalo pequeno, e então entregar esse intervalo para Newton refinar rapidamente.