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.

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}) \)

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} – 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} }\)

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}) – 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.

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.

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.