1.3.1 Raízes de Equações — Raízes de Polinômios — Newton-Raphson para polinômios

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

1. Introdução

Tanto os métodos intervalares quanto os abertos funcionam quase sempre bem para a busca de raízes em um polinômio, dependendo da natureza destas raízes.

Se este tiver apenas raízes reais, qualquer método para encontrar raízes pode ser utilizado. Entretanto, quando o polinômio apresenta raízes complexas, os métodos que as isolam não podem ser utilizados devido ao problema de se definir um critério de detecção da raiz, já que os limites dos intervalos não se estendem às aproximações complexas. Sendo assim, a maioria dos métodos intervalares e abertos não são aplicáveis para polinômios de raízes complexas.

Contudo, o Método de Newton-Raphson pode fornecer as raízes complexas, podendo ser implementado em linguagens que suportem um tipo complexo. Sua única desvantagem é que, dependendo do polinômio, ele poderia ter problemas de convergência. Porém, existem outros algoritmos mais eficientes que buscam raízes — reais e complexas — de funções polinomiais.

2. Newton-Raphson para polinômios

  1. ! -
  2. ! newtonRaphson_c
  3. ! return the [complex] root of a function (using the Newton-Raphson Method)
  4. ! G: function pointer
  5. ! x: some initial point
  6. ! imax: max of iterations allowed
  7. ! errto: tolerated error
  8. !
  9. ! Author: Pedro Garcia sawp@sawp.com.br
  10. ! see: http:!www.sawp.com.br
  11. !
  12. ! License: Creative Commons
  13. !          <http ://creativecommons.org/licenses/by-nc-nd/2.5/br/>
  14. ! ago 2009
  15. !
  16. complex function newtonRaphson_c(G, diffG, x, errto, imax)
  17.   implicit none;
  18.   complex, external :: G, diffG;
  19.   real, intent(in) :: x, errto;
  20.   integer :: imax;
  21.  
  22.   ! iteration counter !
  23.   integer :: iterCount;
  24.  
  25.   ! relative error !
  26.   real(kind=8) :: errno;
  27.  
  28.   ! xi+1 !
  29.   complex :: x1,x0;
  30.  
  31.   x0 = (0.,0.);
  32.   x1 = cmplx(x, 0.d0);
  33.   errno = 100.d0;
  34.   iterCount = 0;
  35.  
  36.   do
  37.     x0 = x1;
  38.     x1 = x0 – G(x0)/diffG(x0);
  39.     iterCount = iterCount + 1;
  40.  
  41.     if(x1 /= (0.d0,0.d0) )then      
  42.       errno = abs( (cabs(x1) – cabs(x0))/cabs(x1) ) * 100.d0
  43.     end if
  44.  
  45.     if(errno < errto .or. iterCount > imax)then
  46.       exit;
  47.     end if  
  48.   end do
  49.  
  50.   newtonRaphson_c = x1;
  51.   return;
  52. end function newtonRaphson_c

Este código pode ser encontrado em http://www.sawp.com.br/code/rootfind/NR_polinomial.f90

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

[1] Ralston, Anthony and Rabinowitz, Philip, A First Course in Numerical Analysis.,(2nd ed.) McGraw-Hill and Dover, (2001), 346–347.


[2] N.B Franco, Cálculo Numérico, Pearson Prentice Hall, (2006), 76.

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.