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 $f \left( x \right) =0$ , vamos tomar

$eq1$

$$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 $\{x\_{left}, x\_{predictor}, x\_{right}\}$ , 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:

$eq2$

$$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:

$eq3$

$$x_{corrector}=x_{left}+d_{0} \left\{ {\frac {\ln \left( \beta \right) }{\ln \left( \alpha \right) } \right\}$$

onde:

$eq4$

$$\alpha={\frac {f_{left}-f_{predictor}}{f_{predictor}-f_{right}}$$

$eq5$

$$\beta={\frac {f_{left}-f_{predictor}}{f_{predictor}-\alpha\,f_{right}}$$

$eq6$

$$f_{predictor}=f \left( x_{predictor} \right)$$

$eq7$

$$f_{left}=f \left( x_{left} \right)$$

$eq8$

$$f_{right}=f \left( x_{right} \right)$$

Da série logarítmica[afken], temos:

$eq9$

$$\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 $x=\beta-1$ temos:

$eq10$

$$\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,

$eq11$

$$\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 $\phi\_{\beta}=\beta-1$ e $\phi\_{\alpha}=\alpha-1$ . Desta forma, obtemos facilmente as expressões necessárias para aplicarmos ao método:

$eq12$

$$\ln \left( \beta \right) =\phi_{\beta}-\dfrac{1}{2}\,{\phi_{\beta}}^{2}+\dfrac{1}{3}\,{\phi_{\beta}}^{3}$$

e

$eq13$

$$\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/.

References

[afken] G. ARFKEN and H. WEBER, Mathematical methods for physicists, Elsevier, 6th Edition$ISBN 978-85-352-2050-6$ $2007$, 269–270.
[1] http://en.wikipedia.org/wiki/Ridders%27_method