Aislamiento de raíces reales
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.
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).
[1][2] 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.
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 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.
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.
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.
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.
[3] En consecuencia, el teorema de Sturm rara vez se utiliza para cálculos efectivos, aunque sigue siendo útil para fines teóricos.
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.
Sin embargo, este algoritmo es muy ineficiente, ya que no se puede usar una partición más gruesa del intervalo [–M, M], 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.
Para i = 1, 2,..., considérese el polinomio Entonces, existe un entero k tal que
En el primer caso, el ck convergente es una raíz positiva de
Para demostrar su teorema, Vincent probó un resultado que es útil por sí solo:[4] Teorema auxiliar de VincentSi p(x) es un polinomio libre de cuadrados de grado n, y a, b, c, d son números reales no negativos tales que
Para trabajar con números reales, siempre se puede elegir c = d = 1, pero, como los cálculos efectivos se realizan con números racionales, generalmente es conveniente suponer que a, b, c, d son números enteros.
La condición de "suficientemente pequeño" fue cuantificada de forma independiente por Nikola Obreshkov[5] y Alexander Ostrowski:[6] La conclusión del resultado auxiliar de Vincent es válida si el polinomio p(x) tiene como máximo una raíz α + iβ tal que En particular, la conclusión es válida si donde sep(p) es la distancia mínima entre dos raíces de p. (Obreschkoff–Ostrowski) Para polinomios con coeficientes enteros, la distancia mínima sep(p) 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.
El propio Vincent proporcionó algunas opciones (véase más abajo).
A continuación se presenta un algoritmo, en el que estas elecciones resultan de una función auxiliar que se discutirá más adelante.
donde A(x) es un polinomio de grado n y
Se tiene que y el intervalo representado por esta estructura de datos tiene
correspondientes a la partición de los reales en positivos y negativos (se puede suponer que cero no es raíz, si lo fuera, bastaría con aplicar el algoritmo a p(x)/x).
De lo contrario, se elige un número real positivo b para dividir el intervalo (0, +∞) en (0, b) y (b, +∞) y, para cada subintervalo, se compone M con una transformación de Möbius que hace corresponder el intervalo en (0, +∞), para obtener dos nuevos intervalos que se agregarán a la lista.
No hay pérdida de generalidad, ya que los cambios de las variables x = By y x = –By trasladan respectivamente las raíces positivas y negativas al intervalo [0, 1].
(También se puede utilizar la variable de cambio único x = (2By – B)).
El método requiere un algoritmo para probar si un intervalo tiene cero, una o posiblemente varias raíces, y para garantizar la terminación.
Para buscar las raíces en algún intervalo, primero se cambia la variable para hacer corresponder el intervalo en [0, 1] dando un nuevo polinomio q(x).
Como la mayor parte del tiempo de cálculo se dedica a cambios de variable, el método que consiste en aplicar cada intervalo en [0, 1] es fundamental para asegurar una buena eficiencia.
Este procedimiento es esencialmente el descrito por Collins y Akritas.
Hay formas de mejorar la eficiencia, que han sido un tema activo de investigación desde la publicación del algoritmo, y principalmente desde principios del siglo XXI.
