Zeros de funções e o Método do Ponto Fixo

No post anterior eu implementei a bissecção, aquele método que divide o intervalo ao meio repetidamente até se aproximar da raiz. Ele é bem útil em muitos casos, pois sempre converge e consegue prever quantas iterações vai precisa.

O único problema dele é ser lento. Cada iteração reduz o erro pela metade, nem mais, nem menos, não importa o formato da função. A curva pode ser quase reta perto da raiz, o que daria pra convergir em 3 passos, mas a bissecção não sabe disso. Ela divide, olha o sinal, e divide de novo.

Para $\varepsilon = 10^{-5}$ no exemplo do post anterior, precisamos de 17 iterações. Para $\varepsilon = 10^{-10}$, seriam 33. O número de iterações cresce com $\log_2(1/\varepsilon)$, cada casa decimal a mais custa 3,3 iterações.

O Método do Ponto Fixo é o próximo algoritmo. Troca a garantia de convergencia por velocidade na convergencia.

Método do Ponto Fixo (MPF)

A equação $f(x) = 0$ pode ser reescrita como $x = \varphi(x)$ de infinitas formas. Por exemplo, para $x^2 + x - 6 = 0$:

• $x = 6 - x^2$, ou seja, $\varphi_1(x) = 6 - x^2$
• $x = \sqrt{6 - x}$, ou seja, $\varphi_2(x) = \sqrt{6-x}$

Ambas são algebricamente equivalentes, porém o comportamento são diferentes.

Se $\xi$ é raiz de $f$, então $f(\xi) = 0$, logo $\varphi(\xi) = \xi$. A raiz que buscamos é um ponto fixo de $\varphi$, ou seja, o ponto onde a curva $y = \varphi(x)$ cruza a reta $y = x$.

O algoritmo é: dado um chute inicial $x_0$, gera-se a sequência $\{x_k\}$ pela relação de recorrência

repetindo até o critério de parada:

1
# Pseudo-código do Método do Ponto Fixo
2

3
x = x₀
4
enquanto verdadeiro:
5
    x₁ = φ(x)
6
    se |x₁ - x| / |x₁| < ε:
7
        retorna x₁
8
    x = x₁

Visualizando geometricamente

Uma forma interessante de ver o que acontece é plotar $\varphi(x)$ e a reta $y = x$ no mesmo gráfico. A raiz $\xi$ é o ponto de interseção entre as duas curvas, porque nesse ponto $\varphi(\xi) = \xi$.

A sequência de iterações aparece como um caminho em espiral entre as duas curvas, você sobe até $\varphi(x_k)$, depois anda horizontalmente até a diagonal $y = x$, e aí esse ponto é $x_{k+1}$. Se a curva de $\varphi$ “aperta” o caminho a cada passo, o método converge. Se ela “abre”, diverge.

Alterne entre as duas funções de iteração para a mesma equação $x^2 + x - 6 = 0$. Com $\varphi_2(x) = \sqrt{6-x}$ a sequência espirala para $\xi = 2$. Com $\varphi_1(x) = 6 - x^2$ ela explode, veja o valor de $x_k$ saltando para fora da região logo na segunda iteração.

Quando converge?

O Teorema do Ponto Fixo dá o critério, se ambas as condições abaixo são satisfeitas:

• $|\varphi'(x)| \leq M < 1$ para todo $x$ em um intervalo $I$ contendo $\xi$
• $x_0 \in I$

então a sequência $\{x_k\}$ converge para $\xi$.

Ou seja, a derivada de $\varphi$ na vizinhança da raiz precisa ser menor que 1 em módulo. Quanto menor $|\varphi'(\xi)|$, mais rápida a convergência.

Verificando o exemplo:

Para $\varphi_2(x) = \sqrt{6-x}$:

A cada iteração o erro cai por um fator de 0,25. Convergência linear com taxa $\frac{1}{4}$.

Para $\varphi_1(x) = 6 - x^2$:

A cada iteração o erro multiplica por 4. Diverge.

A forma geral de toda função de iteração válida é

com $A(\xi) \neq 0$.

Implementando em Python

1
import math
2

3
def phi(x):
4
    return math.sqrt(6 - x)
5

6
def ponto_fixo(phi, x0, eps=1e-5):
7
    x = x0
8
    k = 0
9
    while True:
10
        x_novo = phi(x)
11
        erro = abs(x_novo - x) / abs(x_novo)
12
        k += 1
13
        print(f"Iteração {k:2d}: x = {x_novo:.8f}, erro = {erro:.2e}")
14
        if erro < eps:
15
            return x_novo
16
        x = x_novo
17

18
raiz = ponto_fixo(phi, x0=3)
19
print(f"\nRaiz encontrada: {raiz:.6f}")

1
Iteração  1: x = 1.73205081, erro = 7.32e-01
2
Iteração  2: x = 2.06590154, erro = 1.62e-01
3
Iteração  3: x = 1.98345619, erro = 4.16e-02
4
Iteração  4: x = 2.00413168, erro = 1.03e-02
5
Iteração  5: x = 1.99896681, erro = 2.58e-03
6
Iteração  6: x = 2.00025828, erro = 6.46e-04
7
Iteração  7: x = 1.99993543, erro = 1.61e-04
8
Iteração  8: x = 2.00001614, erro = 4.04e-05
9
Iteração  9: x = 1.99999596, erro = 1.01e-05
10
Iteração 10: x = 2.00000101, erro = 2.52e-06
11

12
Raiz encontrada: 2.000001

O padrão é claro é: o erro cai por um fator de aproximadamente 4 a cada iteração, exatamente o que $|\varphi'(2)| = 0,25$ prevê. São 10 iterações para $\varepsilon = 10^{-5}$.

Vantagens e limitações

O método do ponto fixo tem convergência linear com taxa $|\varphi'(\xi)|$. A bissecção também tem convergência linear com taxa $\frac{1}{2}$, mas sempre converge.

A vantagem real do MPF não é velocidade por si só, é que ele serve de base para métodos mais rápidos.