Método de Bairstow

En análisis numérico , el método de Bairstow es un algoritmo eficiente para hallar las raíces de un polinomio real de grado arbitrario. El algoritmo apareció por primera vez en el apéndice del libro de 1920, *Aerodinámica Aplicada*, de Leonard Bairstow . ^{[ 1 ]} El algoritmo halla las raíces en pares complejos conjugados utilizando únicamente aritmética real.

Consulte el algoritmo de búsqueda de raíces para ver otros algoritmos.

El enfoque de Bairstow consiste en utilizar el método de Newton para ajustar los coeficientes u y v en la ecuación cuadrática.${\displaystyle x^{2}+ux+v}$hasta que sus raíces coincidan con las del polinomio que se está resolviendo. Entonces se pueden determinar las raíces del polinomio cuadrático y dividirlo entre dicho polinomio para eliminar esas raíces. Este proceso se repite hasta que el polinomio se convierte en cuadrático o lineal y se han determinado todas las raíces.

División larga del polinomio a resolver

${\displaystyle P(x)=\sum _{i=0}^{n}a_{i}x^{i}}$

por${\displaystyle x^{2}+ux+v}$produce un cociente${\displaystyle Q(x)=\sum _{i=0}^{n-2}b_{i}x^{i}}$y un resto${\displaystyle cx+d}$de tal manera que

${\displaystyle P(x)=(x^{2}+ux+v)\left(\sum _{i=0}^{n-2}b_{i}x^{i}\right)+(cx+d).}$

Una segunda división de${\displaystyle Q(x)}$por${\displaystyle x^{2}+ux+v}$se realiza para obtener un cociente${\displaystyle R(x)=\sum _{i=0}^{n-4}f_{i}x^{i}}$y el resto${\displaystyle gx+h}$con

${\displaystyle Q(x)=(x^{2}+ux+v)\left(\sum _{i=0}^{n-4}f_{i}x^{i}\right)+(gx+h).}$

Las variables${\displaystyle c,\,d,\,g,\,h}$y el${\displaystyle \{b_{i}\},\;\{f_{i}\}}$son funciones de${\displaystyle u}$y${\displaystyle v}$Se pueden encontrar recursivamente de la siguiente manera.

${\displaystyle {\begin{aligned}b_{n}&=b_{n-1}=0,&f_{n}&=f_{n-1}=0,\\b_{i}&=a_{i+2}-ub_{i+1}-vb_{i+2}&f_{i}&=b_{i+2}-uf_{i+1}-vf_{i+2}\qquad (i=n-2,\ldots ,0),\\c&=a_{1}-ub_{0}-vb_{1},&g&=b_{1}-uf_{0}-vf_{1},\\d&=a_{0}-vb_{0},&h&=b_{0}-vf_{0}.\end{aligned}}}$

La función cuadrática divide exactamente al polinomio cuando

${\displaystyle c(u,v)=d(u,v)=0.\,}$

Valores de${\displaystyle u}$y${\displaystyle v}$Se puede descubrir para qué ocurre esto eligiendo valores iniciales e iterando el método de Newton en dos dimensiones.

${\displaystyle {\begin{bmatrix}u\\v\end{bmatrix}}:={\begin{bmatrix}u\\v\end{bmatrix}}-{\begin{bmatrix}{\frac {\partial c}{\partial u}}&{\frac {\partial c}{\partial v}}\\[3pt]{\frac {\partial d}{\partial u}}&{\frac {\partial d}{\partial v}}\end{bmatrix}}^{-1}{\begin{bmatrix}c\\d\end{bmatrix}}:={\begin{bmatrix}u\\v\end{bmatrix}}-{\frac {1}{vg^{2}+h(h-ug)}}{\begin{bmatrix}-h&g\\[3pt]-gv&gu-h\end{bmatrix}}{\begin{bmatrix}c\\d\end{bmatrix}}}$

hasta que se produzca la convergencia. Este método para hallar las raíces de los polinomios puede implementarse fácilmente con un lenguaje de programación o incluso con una hoja de cálculo.

La tarea consiste en determinar un par de raíces del polinomio.

${\displaystyle f(x)=6\,x^{5}+11\,x^{4}-33\,x^{3}-33\,x^{2}+11\,x+6.}$

Como primer polinomio cuadrático se puede elegir el polinomio normalizado formado a partir de los tres coeficientes principales de f ( x ),

${\displaystyle u={\frac {a_{n-1}}{a_{n}}}={\frac {11}{6}};\quad v={\frac {a_{n-2}}{a_{n}}}=-{\frac {33}{6}}.\,}$

La iteración produce entonces la tabla

Tras ocho iteraciones, el método produjo un factor cuadrático que contiene las raíces −1/3 y −3 dentro de la precisión indicada. La longitud del paso a partir de la cuarta iteración demuestra la velocidad de convergencia superlineal.

El algoritmo de Bairstow hereda la convergencia cuadrática local del método de Newton, excepto en el caso de factores cuadráticos de multiplicidad mayor que 1, cuando la convergencia a dicho factor es lineal. Se observa un tipo particular de inestabilidad cuando el polinomio tiene grado impar y una sola raíz real. Los factores cuadráticos que tienen un valor pequeño en esta raíz real tienden a divergir hacia el infinito.

Las imágenes representan pares${\displaystyle (s,t)\in [-3,3]^{2}}$Los puntos en el semiplano superior t  >  0 corresponden a un factor lineal con raíces${\displaystyle s\pm it}$, eso es${\displaystyle x^{2}+ux+v=(xs)^{2}+t^{2}}$Los puntos en el semiplano inferior t  <  0 corresponden a factores cuadráticos con raíces${\displaystyle s\pm t}$, eso es,${\displaystyle x^{2}+ux+v=(xs)^{2}-t^{2}}$, así que en general${\displaystyle (u,\,v)=(-2s,\,s^{2}+t\,|t|)}$Los puntos están coloreados según el punto final de la iteración de Bairstow; los puntos negros indican un comportamiento divergente.

La primera imagen muestra el caso de una sola raíz real. La segunda indica que se puede corregir la divergencia introduciendo una raíz real adicional, aunque esto ralentiza la convergencia. En el caso de polinomios de grado impar, también se puede encontrar primero una raíz real mediante el método de Newton o un método de reducción de intervalos, de modo que, tras la reducción, se obtenga un polinomio de grado par con mejor comportamiento. La tercera imagen corresponde al ejemplo anterior.

• El algoritmo de Bairstow en Mathworld
• Recetas numéricas en Fortran 77 en línea
• Ejemplo de solucionador de raíces polinómicas (grados P  ≤  10) utilizando el método de Bairstow .
• LinBairstowSolve, una implementación de código abierto en C++ del método Lin-Bairstow disponible como un método de la biblioteca VTK.
• Búsqueda de raíces de un polinomio en línea: método de Bairstow por Farhad Mazlumi