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.

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_{{{\it right}}} \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} \)

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

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