1.2.1 Raízes de Equações — Métodos Abertos — Ponto Fixo

1. Introdução

Diferente dos Métodos da Bissecção e Regula Falsi, que são métodos onde a busca à raiz deve ser realizada dentro de um intervalo, os Métodos Abertos utilizam-se de estratégias para encontrar zeros de funções que não dependam de uma delimitação do local onde se encontra a raiz.

Sendo assim, os métodos abertos não necessitam de um conhecimento prévio da localização da raiz, o que permite a construção de algoritmos que exijam apenas um único valor inicial de $x$ para convergir à resposta.

Diferente dos métodos intervalares, os métodos abertos podem divergir da raiz verdadeira ao longo da execução do programa. Contudo, quando há convergência, os métodos abertos o fazem com velocidade muito superior aos intervalares. </p>

2. O Método do Ponto Fixo

Embora hajam formas mais eficientes para implementação em um programa de computador, todos os métodos abertos são variantes do Método do Ponto Fixo. Por isso, é interessante conhecê-lo para o entendimento das suas variações.

Ele consiste em aplicar sucessivas aproximações de uma função no ponto em que ela se anula, ou seja, quando $x$ for uma raiz.

Sabemos que qualquer $x$ onde $f(x) = 0$ será uma raiz de $f$ . Sendo assim, a idéia por trás do Método do Ponto Fixo consiste em isolar uma variável $x$ de forma que $x$ fica em função de $x$ e utiliza-se a função anterior.

Por exemplo, vamos supor que a função $f(x)$ seja composta por:

(eq1)

$$ f(x) = g(x) + x $$

como $f(x) = 0$ , então

(eq2)

$$ g(x) + x = 0 $$

o que faz com que $x$ fique em função de $x$ , onde esta função é $g$ :

(eq3)

$$ x = g(x) $$

A equação acima fornece uma fórmula para prever um novo valor de $x$ em função de um valor prévio de $x$ . Portanto, o algoritmo só necessita de uma estimativa inicial $x\_{i}$ para aproximar à raiz em $x\_{i+1}$ . Repetindo-se este processo sucessivas vezes, é possível convergir às raízes de uma função.

Logo, na forma iterativa, temos:

(eq4)

$$ x_{i+1} = g(x_{i}) $$

</p>

2.1. Critério de Parada

Como nos métodos intervalares, no Ponto Fixo as sucessivas substituições são feitas até que a aproximação para a solução esteja dentro de um erro de tolerância aceito, dado pela fórmula:

(eq5)

$$ errno = \dfrac{ x_{new} – x_{old} }{ x_{old} } $$

2.2. Exemplo

Seja encontrar a raíz da função não-linear $f(x) = \dfrac{1}{e^x} &#8211; x^2$. Como isto significa $f(x) = 0$ , isolando $x$ , temos:

(eq6)

$$ x^2 = \dfrac{1}{e^x} $$
$$\Downarrow $$

(eq7)

$$ \sqrt{x^2} = \sqrt{ \dfrac{1}{e^x} } $$
$$\Downarrow $$

(eq8)

$$ x = \sqrt{ \dfrac{1}{e^x} }$$

ou seja,

(eq9)

$$ x = \sqrt{e^{-x} = e^{ – \frac{1}{2} x }$$

Substituindo sucessivas vezes a Equação 9, temos que o seguinte processo iterativo pode ser encontrado:

(eq10)

$$ x_{i+1} = e^{ – \frac{1}{2} x_{i} }$$

</p>

3. Convergência do Método do Ponto Fixo

A convergência de uma aproximação numérica está intimamente relacionada com o comportamento do erro. Um método que busca uma raiz está convergindo para ela se o erro relativo diminui ao longo das iterações. Portanto, para saber se a solução será encontrada, deve-se ver como o erro está diminuindo com o aumento do número de iterações.

No caso do Método do Ponto Fixo, a i-ésima iteração é dada por $x\_{i+1} = g(x\_{i})$ e supondo que a solução seja dada por $x\_{sol} = g(x\_{sol})$ , podemos tomar a diferença destas duas equações tal que

(eq11)

$$ x_{sol} – x_{i+1} = g(x_{sol}) – g(x_{i})$$

Pelo Teorema do Valor Médio, se a função $g(x)$ e sua primeira derivada forem contínuas em $\left[ x\_l,x\_r \right]$ , então existe ao menos um valor de e $x$ tal que $x = M$ , onde

(eq12)

$$ \dfrac{d}{dx} g(M) = \dfrac{ g(x_{r}) – g(x_{l}) }{ x_{r} – x_{l} }$$

Assim, para $x\_{l} = x\_{i}$ e $x\_{r} = x\_{sol}$ , a Equação 12 pode ser reescrita como

(eq13)

$$ \dfrac{d}{dx} g(M) = \dfrac{ g(x_{sol}) – g(x_{i}) }{ x_{sol} – x_{i} }$$

Isolando $\Delta g(x) = g(x\_{sol}) &#8211; g(x\_{i})$ no caso acima,

(eq14)

$$ \left( \dfrac{d}{dx} g(M) \right) \left( x_{sol} – x_{i} \right)
= g(x_{sol}) – g(x_{i})$$

onde $M$ pertence ao intervalo $\left[ x\_i, x\_{sol} \right]$ . Substituindo a Equação 14 na Equação 11, podemos obter a relação entre $x\_{sol}$ , $x\_{i+1}$ e $x_{i}$:

(eq15)

$$ x_{sol} – x_{i+1} = \left( \dfrac{d}{dx} g(M) \right)
\left( x_{sol} – x_{i} \right)$$

O erro absoluto é dado pela diferença entre a i-ésima aproximação e a solução real $x\_{sol}$ , então o erro $E\_{i}$ é dado por

(eq16)

$$ E_{i} = x_{sol} – x{i}$$

da mesma forma o erro da próxima iteração $(i+1)$ é:

(eq17)

$$ E_{i+1} = x_{sol} – x_{i+1}$$

Portanto, a relação entre os erros da iteração $i$ e $(i+1)$ será:

(eq18)

$$ E_{i+1} = \left( \dfrac{d}{dx} g(M) \right) E_{i}$$

Os erros de uma iteração em relação à sua anterior é uma proporção fixa, $g'(x)$ por isso o Método do Ponto Fixo é dito “Linearmente Convergente”, ou seja, o erro em $(i+1)$ é uma equação linear em função da iteração anterior, $i$ . Logo, se o coeficiente angular $g'(x)$ for menor que um, o erro $(i+1)$ será menor que $i$ , diminuindo ao longo das iterações. Com $g'(x)$ maior que um, têm-se que o erro de $(i+1)$ é crescente em relação ao erro em $i$ , o que caracteriza a divergência. </p>

4. Considerações sobre o Método do Ponto Fixo

Dada a possibilidade de divergência, devemos ter cuidado ao implementar o Método do Ponto Fixo. Diferente dos Métodos Intervalares — que dependem apenas do intervalo dado e da função que deseja se buscar a raiz — o Método do Ponto Fixo é menos generalizável, pois depende da implementação de quem desenvolve o código na escolha de cada função $g(x)$ .

Ao selecionar a função de iteração $g(x)$ , o programador deve procurar isolar $x$ na forma que minimize $g'(x)$ , pois quão menor for esta taxa, maior será a velocidade de convergência da função.

Por fim, a escolha dos Métodos Abertos deve ser feita quando aplicados à problemas onde as funções que se deseja buscar os zeros tenham propriedades conhecidas. </p>

5. Implementação

Embora o código abaixo tenha como parâmetro de entrada um ponteiro para função, a implementação não é geral. A função que deve ser passada deve ser a de iteração $g$ — obtida a partir do isolamento de uma variável $x$ — e não a função $f$ , cuja raiz queremos encontrar.

def fixedPoint(G, x0, errto, imax):
    """
    return the root of a function (using the Fixed Point Method)

    fixedPoint(fun, x0, errto, imax)

    * fun: Iteration function (used by method)
    * x0: next point (estimative)
    * errto: tolerated error
    * imax: max of iterations allowed

    Author: Pedro Garcia [sawp@sawp.com.br]
    License: Creative Commons
         <http ://creativecommons.org/licenses/by-nc-nd/2.5/br/>
    """

    x1 = G(x0)
    errno = errto + 1
    iterCount = 0
    while errno > errto and iterCount < imax:
        x0 = x1
        x1 = G(x0)
        iterCount += 1
        if x1 != 0:
            errno = fabs((x1 - x0) / x1)
    return x1

Um exemplo de utilização desta implementação está disponível em: http://www.sawp.com.br/code/rootfind/fixedpoint.py

6. Copyright

Este documento está disponível sob a licença Creative Commons. As regras dos direitos de cópia deste conteúdo estão acessíveis em http://creativecommons.org/licenses/by-nc-nd/2.5/br/.

References

[1] N.B Franco, Cálculo Numérico, Pearson Prentice Hall, (2006), 69.