mini|300px|Ejemplo de distribución de raíces en un polinomio de tercer grado. Cuando el eje x se encuentra próximo a un máximo o a un mínimo del polinomio, pueden localizarse pares de raíces arbitrariamente próximos, lo que dificulta su aislamiento
En matemáticas, y más específicamente en análisis numérico y cálculo simbólico, el aislamiento de raíces reales de un polinomio consiste en determinar un conjunto de intervalos disjuntos de la recta real, que contienen cada una (y solo una) raíz real del polinomio, y que conjuntamente contienen todas las raíces reales del polinomio.
Historia El aislamiento de las raíces reales es útil porque los métodos de resolución numérica de ecuaciones no lineales más habituales para calcular las raíces reales de un polinomio pueden producir algunas raíces reales, pero, en general, no pueden certificar haber encontrado todas las raíces reales. En particular, si tal algoritmo no encuentra ninguna raíz, no se sabe si es porque no existe tal raíz real. Algunos algoritmos calculan todas las raíces complejas, pero, como generalmente hay muchas menos raíces reales que raíces complejas, la mayor parte de su tiempo de cálculo se emplea generalmente para calcular raíces no reales (en promedio, un polinomio de grado tiene siempre raíces complejas (incluyendo las reales), pero solo raíces reales; véase propiedades de las raíces polinómicas). Además, puede ser difícil distinguir las raíces reales de las raíces no reales con una pequeña parte imaginaria (véase el ejemplo del polinomio de Wilkinson en la siguiente sección).
El primer algoritmo completo de aislamiento de raíces reales fue el resultado del teorema de Sturm (1829). Sin embargo, cuando los algoritmos de aislamiento de raíces reales comenzaron a desarrollarse para las computadoras, se comprobó que los algoritmos derivados del teorema de Sturm son menos eficientes que los derivados de la regla de los signos de Descartes (1637).
Desde principios del existe una intensa actividad investigadora para mejorar los algoritmos derivados de la regla de signos de Descartes, con el fin de conseguir algoritmos muy eficientes y calcular su complejidad computacional. Las mejores implementaciones pueden aislar de forma rutinaria raíces reales de polinomios de grado superior a 1000.
Especificaciones y estrategia general Para encontrar raíces reales de un polinomio, la estrategia común es dividir la recta real (o un intervalo de la misma donde se busca la raíz) en intervalos disjuntos hasta tener como máximo una raíz en cada intervalo. Este procedimiento se denomina aislamiento de raíz, y un intervalo resultante que contiene exactamente una raíz es un intervalo de aislamiento para esta raíz.
El polinomio de Wilkinson muestra que una modificación muy pequeña de un coeficiente de un polinomio puede cambiar drásticamente no solo el valor de las raíces, sino también su naturaleza (real o compleja). Además, incluso con una buena aproximación, cuando se evalúa un polinomio en una raíz aproximada, se puede obtener un resultado que está lejos de ser cercano a cero. Por ejemplo, si un polinomio de grado 20 (el grado del polinomio de Wilkinson) tiene una raíz cercana a 10, la derivada del polinomio en la raíz puede ser del orden de , esto implica que un error de en el valor de la raíz puede producir un valor del polinomio en la raíz aproximada que es del orden de . De ello se deduce que, excepto quizás para grados muy bajos, un procedimiento de aislamiento de raíz no puede dar resultados fiables sin usar aritmética exacta. Por lo tanto, si se quieren aislar raíces de un polinomio con coeficientes de coma flotante, a menudo es mejor convertirlos a números racionales y luego tomar la parte primitiva del polinomio resultante, para tener un polinomio con coeficientes enteros.
Por esta razón, aunque los métodos que se describen a continuación funcionan teóricamente con números reales, generalmente se utilizan en la práctica con polinomios con coeficientes enteros e intervalos que se determinan con números racionales. Además, siempre se supone que se trata de polinomios libres de cuadrados. Hay dos razones para esto. En primer lugar, el algoritmo de Yun para calcular la factorización libre de cuadrados es menos costoso que el doble del costo del cálculo del máximo común divisor del polinomio y de su derivada. Como esto puede producir factores de grados más bajos, generalmente es ventajoso aplicar algoritmos de aislamiento de raíces solo en polinomios sin raíces múltiples, incluso cuando el algoritmo no lo requiera. La segunda razón para considerar solo polinomios libres de cuadrados es que los algoritmos más rápidos de aislamiento de raíces no funcionan en el caso de raíces múltiples.
Para el aislamiento de raíces, se requiere un procedimiento para contar las raíces reales de un polinomio en un intervalo sin tener que calcularlas, o al menos un procedimiento para decidir si un intervalo contiene cero, una o más raíces. Con tal procedimiento de decisión, se puede trabajar con una lista de trabajo de intervalos que pueden contener raíces reales. Al principio, la lista contiene un único intervalo que contiene todas las raíces de interés, generalmente la línea real completa o su parte positiva. Luego, cada intervalo de la lista se divide en dos intervalos más pequeños. Si uno de los nuevos intervalos no contiene ninguna raíz, se elimina de la lista. Si contiene una raíz, se coloca en una lista de salida de intervalos de aislamiento. De lo contrario, se mantiene en la lista de trabajo para futuras divisiones, y el proceso puede continuar hasta que finalmente se aíslen todas las raíces.
Teorema de Sturm El primer procedimiento completo de aislamiento de raíces es el resultado del teorema de Sturm (1829), que expresa el número de raíces reales en un intervalo en términos del número de variaciones de signo de los valores de una secuencia de polinomios, denominada secuencia de Sturm, en el final del intervalo. Es la secuencia de residuos generados en una variante del algoritmo de Euclides aplicado al polinomio y a sus derivadas. Cuando se desarrolló en las primeras computadoras, se comprobó que el aislamiento de las raíces con el teorema de Sturm era menos eficiente que los otros métodos que se describen a continuación. En consecuencia, el teorema de Sturm rara vez se utiliza para cálculos efectivos, aunque sigue siendo útil para fines teóricos.
La regla de los signos de Descartes y sus generalizaciones
La regla de los signos de Descartes afirma que la diferencia entre el número de variaciones de signo en la secuencia de los coeficientes de un polinomio y el número de sus raíces reales positivas es un número entero par no negativo. Resulta que si este número de variaciones de signo es cero, entonces el polinomio no tiene raíces reales positivas y, si este número es uno, entonces el polinomio tiene una raíz real positiva única, que es una raíz única. Desafortunadamente, lo contrario no es cierto, es decir, un polinomio que no tiene una raíz real positiva o que tiene una raíz simple positiva única puede tener un número de variaciones de signo mayor que 1.
Esto ha sido generalizado por el teorema de Budan (1807), en un resultado similar para las raíces reales en un intervalo : Si es un polinomio, y es la diferencia entre los números de variaciones de signo de las secuencias de los coeficientes de y de , entonces menos el número de raíces reales en el intervalo, contadas con sus multiplicidades, es un número entero par no negativo. Esta es una generalización de la regla de los signos de Descartes, porque, para suficientemente grande, no hay variación de signo en los coeficientes de y todas las raíces reales son más pequeñas que .
El teorema de Budan puede proporcionar un algoritmo de aislamiento de raíces reales para un polinomio libre de cuadrados (un polinomio sin raíces múltiples): a partir de los coeficientes del polinomio, se puede calcular un límite superior de los valores absolutos de las raíces y un límite inferior de los valores absolutos de las diferencias de dos raíces (véase propiedades de las raíces polinómicas). Entonces, si se divide el intervalo en intervalos de longitud menor que , entonces cada raíz real está contenida en algún intervalo y ningún intervalo contiene dos raíces. Los intervalos de aislamiento son, por lo tanto, los intervalos para los que el teorema de Budan afirma un número impar de raíces.
Sin embargo, este algoritmo es muy ineficiente, ya que no se puede usar una partición más gruesa del intervalo , porque, si el teorema de Budan da un resultado mayor que 1 para un intervalo de mayor tamaño, no hay forma de asegurar que no contenga varias raíces.
Teorema de Vincent y afines El teorema de Vincent (1834) proporciona un método para el aislamiento de raíces reales, que es la base de los algoritmos de aislamiento más eficientes. Se trata de las raíces reales positivas de un polinomio libre de cuadrados (que es un polinomio sin raíces múltiples). Si es una secuencia de números reales positivos, sea
el -esimo término de la fracción continua convergente
Para demostrar su teorema, Vincent probó un resultado que es útil por sí solo:
Para trabajar con números reales, siempre se puede elegir , pero, como los cálculos efectivos se realizan con números racionales, generalmente es conveniente suponer que son números enteros.
La condición de "suficientemente pequeño" fue cuantificada de forma independiente por Nikola Obreshkov y Alexander Ostrowski:
thumb|x220px|right|Teorema de Obreschkoff-Ostrowski: en azul y amarillo, las regiones del plano complejo donde no debería haber raíces por tener 0 o 1 variaciones de signo; a la izquierda las regiones excluidas para las raíces de , a la derecha, las regiones excluidas para las raíces del polinomio transformado ; en azul, las regiones potencialmente excluidas por poder tener una variación de signo, pero permitidas por tener 0 variaciones de signo
Para polinomios con coeficientes enteros, la distancia mínima puede tener un límite inferior en términos del grado del polinomio y el valor absoluto máximo de sus coeficientes; véase propiedades de las raíces polinómicas. Esto permite el análisis de la complejidad en el peor de los casos de algoritmos basados en los teoremas de Vincent. Sin embargo, el teorema de Obreschkoff-Ostrowski muestra que el número de iteraciones de estos algoritmos depende de las distancias entre raíces en la vecindad del intervalo de trabajo; por lo tanto, el número de iteraciones puede variar drásticamente para diferentes raíces del mismo polinomio.
James V. Uspensky dio un límite de la longitud de la fracción continua (el entero necesario, en el teorema de Vincent, para obtener variaciones de un signo o cero:
Método de la fracción continua
Vincent introdujo el uso de una fracción continua para el aislamiento de raíces reales, aunque le dio el crédito de la idea a Joseph-Louis Lagrange pero sin proporcionar una referencia. Para codificar un algoritmo del teorema de Vincent, se debe proporcionar un criterio para elegir el que requiere su teorema. El propio Vincent proporcionó algunas opciones (véase más abajo). Algunas otras opciones son posibles y la eficiencia del algoritmo puede depender drásticamente de estas opciones. A continuación se presenta un algoritmo, en el que estas elecciones resultan de una función auxiliar que se discutirá más adelante.
Para ejecutar este algoritmo, se debe trabajar con una lista de intervalos representados por una estructura de datos específica. El algoritmo funciona eligiendo un intervalo, eliminándolo de la lista, agregando cero, uno o dos intervalos más pequeños a la lista y puede o no generar un intervalo de aislamiento.
Para aislar las raíces reales de un polinomio de grado , cada intervalo está representado por un par donde es un polinomio de grado y es una transformación de Möbius con coeficientes enteros. Se tiene que