SAWP > 1.2.1 Raízes de Equações — Métodos Abertos

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

March 9th, 2010 by SAWP | Filed under Métodos Computacionais

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.

Tags:

[ Métodos Computacionais ]

Você pode ler as eventuais respostas desta entrada através do RSS 2.0 feed.
As respostas estão encerradas, mas você pode trackback a partir do seu próprio site.

SAWP

Software Advice Working Party