Método de Bairstow

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 polinomio $\ 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 fórmula 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_{2}x^{2}+a_{1}x+a_{0}$

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

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

con un residuo $\,R=b_{1}{x-r}+b_{0},$ , el residuo será cero solo si $\,b_{1}yb_{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}yb_{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}$

Bairstow 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

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

Datos: Q384021