1.1.3 Raízes de Equações — Métodos Intervalares — Método de Rider
1. Introdução
O Método de Ridder consiste em avaliar a aproximação parcial — obtida em cada iteração pelo Método da Falsa Posição — em uma função de ajuste exponencial, a fim de otimizar a busca pela raiz.
A ideia é semelhante àquela usada pelo Método de Brent, cuja busca intervalar é combinada com um método aberto que possua taxa de convergência superior. Assim como o Método de Brent, possui a vantagem de convergir sempre a uma taxa média superior aos dos métodos intervalares normais. </p>
2. Desenvolvimento do Método
Como queremos encontrar , vamos tomar
$$f \left( x \right) = A+B{e^{Cx}$$
| Sejam três valores de x que estejam delimitando de alguma forma um intervalo que contenha a raiz tal que , cuja amplitude seja $$d_{0}= \left | x_{left}-x_{right} \right | $$ .Podemos utilizar o Método da Falsa posição para obter uma aproximação da raiz a partir desses pontos neste intervalo: |
$$ x_{predictor}=FalsaPosicao \left( x_{left},x_ \right) $$
A proposição feita por Ridder é de realizar uma segunda aproximação a partir da fórmula:
$$ x_{corrector}=x_{left}+d_{0} \left\{ {\frac {\ln \left( \beta \right) }{\ln \left( \alpha \right) } \right\} $$
onde:
$$ \alpha={\frac {f_{left}-f_{predictor}}{f_{predictor}-f_{right}} $$
$$\beta={\frac {f_{left}-f_{predictor}}{f_{predictor}-\alpha\,f_{right}} $$
$$ f_{predictor}=f \left( x_{predictor} \right) $$
$$ f_{left}=f \left( x_{left} \right) $$
$$ f_{right}=f \left( x_{right} \right) $$
Da série logarítmica[afken], temos:
$$ \ln \left( 1+x \right) =\sum _{n=1}^{\infty }{\frac { \left( -1\right) ^{n-1}{x}^{n}{n} = x-\dfrac{1}{2}\,{x}^{2}+\dfrac{1}{3}\,{x}^{3} $$
Uma aproximação satisfatória para o caso pode ser obtida usando-se até o terceiro termo. Desta forma, para temos:
$$ \ln \left( 1+ \left\{ \beta-1 \right\} \right) =\beta-1-\dfrac{1}{2}\, \left( \beta-1 \right) ^{2}+\dfrac{1}{3}\, \left( \beta-1 \right) ^{3} $$
portanto,
$$ \ln \left( \beta \right) =\beta-1-\dfrac{1}{2}\, \left( \beta-1 \right) ^{2}+\dfrac{1}{3}\, \left( \beta-1 \right) ^{3} $$
Para simplificarmos a notação, adotaremos e . Desta forma, obtemos facilmente as expressões necessárias para aplicarmos ao método:
$$ \ln \left( \beta \right) =\phi_{\beta}-\dfrac{1}{2}\,{\phi_{\beta}}^{2}+\dfrac{1}{3}\,{\phi_{\beta}}^{3} $$
e
$$ \ln \left( \alpha \right) =\phi_{\alpha}-\dfrac{1}{2}\, {\phi_{\alpha}}^{2} +\dfrac{1}{3}\,{\phi_{\alpha}}^{3} $$
</p>
3. Implementação
def ridders(F, xl, xr, errto=0.01, imax=1000):
"""
Return the root of a function (Using the Ridder's Method)
ridders(fun, xl, xr, imax, errto)
* fun: Function where find the roots
* xl: left bound of interval
* xr: right bound of interval
* imax: max of iterations allowed
* errto: tolerated error
Author: Pedro Garcia [sawp@sawp.com.br]
License: Creative Commons
<http ://creativecommons.org/licenses/by-nc-nd/2.5/br/>
"""
x = 0
iterCount = 0
errno = 1
while errno > errto and iterCount < imax:
fr = F(xr)
fl = F(xl)
d0 = abs(fr - fl)
x = xr - fr*(xl-xr)/(fl - fr)
fx = F(x)
a = (fl - fx)/(fx - fr)
b = (fl - fx)/(fl - a*fx)
beta = b - 1
alfa = a - 1
lnb = beta - beta*beta/2 + beta*beta*beta/3
lna = alfa - alfa*alfa/2 + alfa*alfa*alfa/3
root = xl + d0*lnb/lna
froot = F(root)
if fl * fx < 0:
if xl < root and root < x:
if fx * froot < 0:
xl = root
xr = x
else:
xr = root
else:
xr = x
elif fl * fx > 0:
if x < root and root < xr:
if fx * froot < 0:
xl = x
xr = root
else:
xl = root
fl = froot
else:
xl = x
fl = fx
else:
if fl == 0:
x = xl
break
errno = abs(xr - xl)
iterCount += 1
return x
Disponível para download em http://www.sawp.com.br/code/rootfind/riders.py </p> </p>
4. Copyright
Este documento é 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/.