Método de Bairstow

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

En análisis numérico, el método de Bairstow es un algoritmo eficiente de búsqueda de las raíces de un polinomio real de grado arbitrario. Es un método iterativo, basado en el método de Müller y de Newton Raphson. Dado un polinonio \ f_n(x) se encuentran dos factores, un polinomio cuadrático

\ f_2(x)=x^2-rx-s y \ f_{n-2}(x)

El procedimiento general para el método de Bairstow es el siguiente. Dado:

\ f_n(x) y \ r_0 y \ s_0
  • 1. Utilizando el método de Newton Raphson se calcula:
\ f_2(x)=x^2-rx-s y \ f_{n-2}(x) , tal que, el residuo de \,f_n(x)/ f_2(x) , sea igual a cero.
  • 2. Se determinan la raíces \ f_2(x) , utilizando la formula general.
  • 3. Se calcula \ f_{n-2}(x)=f_n(x)/f_2(x)
  • 4. Se hace \ f_n(x):=f_{n-2}(x)
  • 5. Si el grado del polinomio es mayor que tres regresamos al paso 2; en caso contrario, terminamos.

La principal diferencia de este método, respecto a otros, es que permite calcular todas las raíces de un polinomio (reales e imaginarias).

Para calcular la división de polinomios, hacemos uso de la división sintética. Así dado:

\ f_n(x)=a_n x^n+a_{n-1}x^{n-1}+...+a_2x^2+a_1x+a_0

Al dividir entre \ f_2(x)=x^2-rx-s , se tiene como resultado el siguiente polinomio:

\ f_(n-2)(x)=b_nx^{n-2}+b_{n-1}x^{n-3}+...+b_3x+b_2

con un residuo \, R = b_1 {x-r} + b_0 , , el residuo será cero solo si \, b_1 y b_0 , lo son.

Los términos b, se calculan utilizando división sintética, la cual puede resolverse utilizando la siguiente relación de recurrencia:

\, b_n = a_n ,

\, b_{n-1} = a_{n-1} + rb_n ,

\, b_i = a_i + rb_{i+1} + sb_{i+2} ,

Una manera de determinar los valores de r y s que hacen cero el residuo es utilizar el método de Newton-Raphson. Para ello necesitamos una aproximación lineal de \ b_1 y b_0 , respecto a r y s la cual calculamos utilizando la serie de Taylor

\ b_1(r+dr,s+ds)=b_1+\frac{\partial b_1}{\partial r}dr+\frac{\partial b_1}{\partial s}ds

\ b_0(r+dr,s+ds)=b_0+\frac{\partial b_0}{\partial r}dr+\frac{\partial b_0}{\partial s}ds

donde los valores de r y s están dados y se calculan los incrementos dr y ds que hacen a \ b_1(r+dr, s+ds) y \ b_0(r+dr, s+dr) igual a cero. El sistema de ecuaciones que se tiene que resolver es:

\ \frac{\partial b_1}{\partial r}dr+\frac{\partial b_1}{\partial s}ds=-b_1

\ \frac{\partial b_0}{\partial r}dr+\frac{\partial b_0}{\partial s}ds=-b_0

Bairtow muestra que las derivadas parciales pueden obtener haciendo un procedimiento similar a la división sintética, así:

\ c_n=b_n

\ c_{n-1}=b_{n-1}+rc_n

\ c_i=b_i+rc_{i+1}+sc_{i+2}

donde:

\ \frac{\partial b_0}{\partial r}=c_1

\ \frac{\partial b_1}{\partial r}=\frac{\partial b_0}{\partial s}=c_2

\ \frac{\partial b_1}{\partial s}=c_3


Análisis del algoritmo[editar]

El algoritmo de Bairstow tiene orden de convergencia cuadrático como el método de Newton, excepto en el caso de que el polinomio tenga factores cuadráticos de multiplicidad superior a 1, pudiendo ser el orden de convergencia menor.

Enlaces externos[editar]