1.2.2 Raízes de Equações — Métodos Abertos — Newton Raphson

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

1. Introdução

O método de Newton-Raphson é outro método aberto, pois a convergência à raiz não depende da delimitação de um intervalo, possuindo as propriedades descritas do Método do Ponto Fixo.

Provavelmente é o método numérico mais aplicado computacionalmente para a aproximação de raízes, graças à sua capacidade de rápida convergência.

2. Desenvolvimento do Método



Na Figura metodo, observamos que a partir da aproximação inicial da raiz x_{i} é possível estender uma reta tangente do ponto \left( x_{i}, f(x_{i}) \right) . O ponto onde esta tangente intercepta o eixo das abcissas é a segunda estimativa, x_{i+1} . Desta figura, é visível que a inclinação é equivalente à



\dfrac{ d }{ d x } f(x_{i}) = \dfrac{ f(x_{i}) }{ \left( x_{i} - x_{i+1} \right) }

isolando x_{i+1} , aparece naturalmente a iteração conhecida como o Método de Newton:



x_{i+1} = x_{i} - \dfrac{f(x_{i})}{\dfrac{ d }{ d x } f(x_{i})}

Como no Método do Ponto Fixo, basta executar sucessivas aproximações para convergir à raiz, tendo como critério de parada um erro pré-definido.

3. Implementação

A implementação deste método consiste em basicamente alterar o código do Ponto Fixo de forma utilizar a chamada da expressão deduzida ao invés da própria função G :

  1. def newtonRaphson(G, diffG, x0, errto, imax):
  2.     """
  3.    return the root of a function (using the Newton-Raphson Method)
  4.  
  5.    newtonRaphson(fun, diffFun, x0, errto, imax)
  6.  
  7.    * fun: Function where find the roots
  8.    * diffFun: analytic derivative of fun
  9.    * x0: next point (estimative)
  10.    * errto: tolerated error
  11.    * imax: max of iterations allowed
  12.  
  13.    Author: Pedro Garcia [sawp@sawp.com.br]
  14.    see: http://www.sawp.com.br
  15.    License: Creative Commons
  16.  
  17.    Dec 2009
  18.    """
  19.  
  20.   x1 = x0 – G(x0)/diffG(x0) # fixed point x1 = G(x0)
  21.   iterCount = 0
  22.     errno = fabs((x1 – x0)/x1)
  23.  
  24.   while errno > errto and iterCount < imax:
  25.     x0 = x1
  26.     x1 = x0 – G(x0)/diffG(x0) # in fixed point will be x1 = G(x0)
  27.     iterCount += 1
  28.  
  29.     if x1 != 0:
  30.       errno = fabs((x1 – x0)/x1)
  31.  
  32.   return x1

Veja que a implementação do método de Newton-Raphson é dependente de mais uma função, que precisa ser declarada. Embora este método não dependa da escolha da melhor função G, como ocorre no método do Ponto Fixo, o codificador precisa implementar tanto a função que se deseja conhecer a raiz como a sua derivada.

Um exemplo de utilização deste código pode ser encontrado em http://www.sawp.com.br/code/rootfind/newtonraphson.py

4. Observações

Embora o método do Newton-Raphson seja quase sempre o mais eficiente na busca de raízes, ele nem sempre é aplicável. Um exemplo interessante está em comparar as funções de avaliação do Método do Ponto Fixo e as do código de Newton-Raphson.

Ao utilizarmos Newton-Raphson para buscar a raiz da função:


G1 = exp(1.d0)**(-x/2.d0)

e usando sua derivada:


diffG1 = (1/2)*(exp(1.d0))**(-(1.d0/2.d0)*x)

o programa gera um resultado que não converge à raiz. Provavelmente se o código for compilado e executado, o resultado será “NaN” ou “infinity”.

5. 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

Tags: tag_icon [ 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.