Aislamiento de raíz real

Métodos para localizar raíces reales de un polinomio.

En matemáticas , y, más específicamente en análisis numérico y álgebra informática , el aislamiento de raíz real de un polinomio consiste en producir intervalos disjuntos de la recta real , que contienen cada una (y sólo una) raíz real del polinomio, y, en conjunto, contiene todas las raíces reales del polinomio.

El aislamiento de raíces reales es útil porque los algoritmos habituales de búsqueda de raíces para calcular las raíces reales de un polinomio pueden producir algunas raíces reales, pero generalmente no pueden certificar haber encontrado todas las raíces reales. En particular, si dicho algoritmo no encuentra ninguna raíz, no se sabe si es porque no existe una 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 del tiempo de cálculo se dedica generalmente a calcular raíces no reales (en promedio, un polinomio de grado n tiene n raíces complejas, y solo log n raíces reales; ver Propiedades geométricas de raíces polinómicas § Raíces reales ). Además, puede resultar difícil distinguir las raíces reales de las raíces no reales con una parte imaginaria pequeña (consulte el ejemplo del polinomio de Wilkinson en la siguiente sección).

El primer algoritmo completo de aislamiento de raíces reales resulta del teorema de Sturm (1829). Sin embargo, cuando los algoritmos de aislamiento de raíces reales comenzaron a implementarse en las computadoras , resultó 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 siglo XX existe una activa actividad de investigación para mejorar los algoritmos derivados de la regla de signos de Descartes, conseguir implementaciones 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. ^{[1] [2]}

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 ella donde se buscan raíces) en intervalos disjuntos hasta tener como máximo una raíz en cada intervalo. Este procedimiento se llama aislamiento de raíces , 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 sólo 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 sea del orden de De ello se deduce que, excepto tal vez para grados muy bajos, un procedimiento de aislamiento de raíces no puede dar resultados confiables sin usar aritmética exacta. Por lo tanto, si uno quiere aislar raíces de un polinomio con coeficientes de punto 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. ${\displaystyle 10^{20};}$ ${\displaystyle 10^{-10}}$ ${\displaystyle 10^{10}.}$

Por esta razón, aunque los métodos que se describen a continuación funcionan teóricamente con números reales, generalmente se usan en la práctica con polinomios con coeficientes enteros e intervalos que terminan en números racionales. Además, siempre se supone que los polinomios están libres de cuadrados . Hay dos razones para eso. En primer lugar, el algoritmo de Yun para calcular la factorización sin cuadrados es menos costoso que el doble del coste del cálculo del máximo común divisor del polinomio y 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 requiere. La segunda razón para considerar sólo polinomios libres de cuadrados es que los algoritmos de aislamiento de raíces más rápidos 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 este 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 recta 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 resulta 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, llamada secuencia de Sturm , en los extremos de el intervalo. La secuencia de Sturm es la secuencia de restos que ocurren en una variante del algoritmo euclidiano aplicado al polinomio y sus derivadas. Cuando se implementó en computadoras, pareció que el aislamiento de raíz con el teorema de Sturm es menos eficiente que los otros métodos que se describen a continuación. ^[3] 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 signos 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 raíz real positiva o tiene una única raíz simple positiva puede tener un número de variaciones de signos 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 semiabierto ( a , b ) : Si f ( x ) es un polinomio y v es la diferencia entre los números de variaciones de signo de las secuencias de los coeficientes de f ( x + a ) y f ( x + b ) , entonces v menos el número de raíces reales en el intervalo, contadas con sus multiplicidades, es un entero par no negativo. Esta es una generalización de la regla de los signos de Descartes, porque, para b suficientemente grande, no hay variación de signo en los coeficientes de f ( x + b ) , y todas las raíces reales son más pequeñas que b .

Budan puede proporcionar un algoritmo de aislamiento de raíces reales para un polinomio sin cuadrados (un polinomio sin raíces múltiples): a partir de los coeficientes del polinomio, se puede calcular un límite superior M de los valores absolutos de las raíces y un límite inferior m en los valores absolutos de las diferencias de dos raíces (ver Propiedades de las raíces polinómicas ). Entonces, si se divide el intervalo [– M , M ] en intervalos de longitud menor que m , 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 tanto, los intervalos para los cuales el teorema de Budan afirma un número impar de raíces.

Sin embargo, este algoritmo es muy ineficiente, ya que no se puede utilizar una partición más burda del intervalo [– M , M ] , porque, si el teorema de Budan da un resultado mayor que 1 para un intervalo de tamaño mayor, no hay forma de asegurar que no contiene varias raíces.

Teoremas de Vincent y relacionados

El teorema de Vincent (1834)^[4]proporciona un método para el aislamiento de raíces reales, que es la base de los algoritmos de aislamiento de raíces reales más eficientes. Se trata de las raíces reales positivas de unpolinomio sin cuadrados(es decir, un polinomio sin raíces múltiples). Sies una sucesión de números reales positivos, sea ${\displaystyle a_{1},a_{2},\ldots ,}$

${\displaystyle c_{k}=a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+{\cfrac {1}{\ddots +{\cfrac {1}{a_{k}}}}}}}}}}$

ser el k ésimo convergente de la fracción continua

${\displaystyle a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+{\cfrac {1}{\ddots }}}}}}.}$

Teorema de Vincent  :  sea un polinomio libre de cuadrados de grado n y una secuencia de números reales. Para i = 1, 2,..., considere el polinomio ${\displaystyle p_{0}(x)}$ ${\displaystyle a_{1},a_{2},\ldots ,}$

${\displaystyle p_{i}(x)=x^{n}p_{i-1}\left(a_{i}+1/x\right).}$

Entonces, existe un número entero k tal que cualquiera de los dos o la secuencia de coeficientes de tiene como máximo una variación de signo. ${\displaystyle p_{k}(0)=0,}$ ${\displaystyle p_{k}}$

En el primer caso, el c _k convergente es una raíz positiva de De lo contrario, este número de variaciones de signo (ya sea 0 o 1) es el número de raíces reales de en el intervalo definido por y ${\displaystyle p_{0}.}$ ${\displaystyle p_{0}}$ ${\displaystyle c_{k-1}}$ ${\displaystyle c_{k}.}$

Para demostrar su teorema, Vincent demostró un resultado que es útil por sí solo: ^[4]

Teorema auxiliar de Vincent  :  si p ( x ) es un polinomio sin cuadrados de grado n , y a , b , c , d son números reales no negativos tales que son lo suficientemente pequeños (pero no 0), entonces hay como máximo una variación de signo. en los coeficientes del polinomio ${\displaystyle \left|{\frac {a}{c}}-{\frac {b}{d}}\right|}$

${\displaystyle q(x)=(cx+d)^{n}p\left({\frac {ax+b}{cx+d}}\right),}$

y este número de variaciones de signo es el número de raíces reales de p ( x ) en el intervalo abierto definido por y ${\displaystyle {\frac {a}{c}}}$ ${\displaystyle {\frac {b}{d}}.}$

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 "suficientemente pequeña" ha sido cuantificada de forma independiente por Nikola Obreshkov , ^[5] y Alexander Ostrowski : ^[6]

Teorema de Obreschkoff-Ostrowski: en azul y amarillo, las regiones del plano complejo donde no debería haber raíz por tener variación de signo 0 o 1; a la izquierda las regiones excluidas para las raíces de p , a la derecha, las regiones excluidas para las raíces del polinomio transformado q ; en azul, las regiones que están excluidas por tener variación de un signo, pero permitidas variaciones de signo cero.

Teorema  (Obreschkoff-Ostrowski)  :  la conclusión del resultado auxiliar de Vincent se cumple si el polinomio p ( x ) tiene como máximo una raíz α + iβ tal que

${\displaystyle \left(\alpha -{\frac {a}{c}}\right)\left(\alpha -{\frac {b}{d}}\right)+\beta ^{2}\leq {\frac {1}{\sqrt {3}}}\left|\beta \left({\frac {a}{c}}-{\frac {b}{d}}\right)\right|.}$

En particular, la conclusión es válida si

${\displaystyle \left|{\frac {a}{c}}-{\frac {b}{d}}\right|<{\frac {\operatorname {sep} (p)}{2{\sqrt {3}}}},}$

donde sep( p ) es la distancia mínima entre dos raíces de p .

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; ver Propiedades de las raíces polinómicas § Separación de raíces . Esto permite el análisis de la complejidad del 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 las proximidades 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 a la longitud de la fracción continua (el entero k en el teorema de Vincent), para obtener variaciones de cero o un signo: ^{[1] [7]}

Teorema  (Uspensky)  :  Sea p ( x ) un polinomio de grado n y sep( p ) la distancia mínima entre dos raíces de p . Dejar

${\displaystyle \varepsilon =\left(n+{\frac {1}{n}}\right)^{\frac {1}{n-1}}-1.}$

Entonces el número entero k , cuya existencia se afirma en el teorema de Vincent, no es mayor que el entero más pequeño h tal que

${\displaystyle F_{h-1}\operatorname {sep} (p)>2\quad {\text{and}}\quad F_{h-1}F_{k}\operatorname {sep} (p)>{\frac {1}{\varepsilon }},}$

¿ Dónde está el h -ésimo número de Fibonacci ? ${\displaystyle F_{h}}$

Método de fracción continua

Vincent introdujo el uso de fracciones continuas para el aislamiento de raíces reales, aunque le dio crédito a Joseph-Louis Lagrange por esta idea, sin proporcionar una referencia. ^[4] Para hacer un algoritmo del teorema de Vincent, se debe proporcionar un criterio para elegir lo que ocurre en su teorema. El propio Vicente ofreció algunas opciones (ver más abajo). Algunas otras opciones son posibles y la eficiencia del algoritmo puede depender dramáticamente 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. ${\displaystyle a_{i}}$

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 posiblemente genere un intervalo de aislamiento.

Para aislar las raíces reales de un polinomio p ( x ) de grado n , cada intervalo está representado por un par donde A ( x ) es un polinomio de grado n y es una transformación de Möbius con coeficientes enteros. Uno tiene ${\displaystyle (A(x),M(x)),}$ ${\displaystyle M(x)={\frac {px+r}{qx+s}}}$

${\displaystyle A(x)=p(M(x)),}$

y el intervalo representado por esta estructura de datos es el intervalo que tiene y como puntos finales. La transformación de Möbius asigna las raíces de p en este intervalo a las raíces de A en (0, +∞) . ${\displaystyle M(\infty )={\frac {p}{q}}}$ ${\displaystyle M(0)={\frac {r}{s}}}$

El algoritmo trabaja con una lista de intervalos que, al principio, contiene los dos intervalos y corresponde a la partición de los reales en positivos y negativos (se puede suponer que el cero no es raíz, ya que, si lo fuera, basta con aplicar el algoritmo a p ( x )/ x ). Luego, para cada intervalo ( A ( x ), M ( x )) en la lista, el algoritmo lo elimina de la lista; si el número de variaciones de signo de los coeficientes de A es cero, no hay raíz en el intervalo y se pasa al siguiente intervalo. Si el número de variaciones de signo es uno, el intervalo definido por y es un intervalo aislante. 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 mapea el intervalo. en (0, +∞) , para agregar dos nuevos intervalos a la lista. En pseudocódigo, esto da lo siguiente, donde var( A ) denota el número de variaciones de signo de los coeficientes del polinomio A . ${\displaystyle (A(x)=p(x),M(x)=x)}$ ${\displaystyle (A(x)=p(-x),M(x)=-x),}$ ${\displaystyle M(0)}$ ${\displaystyle M(\infty )}$

Se  ingresa la función fracción continua : P(x), un polinomio sin cuadrados , salida : una lista de pares de números racionales que definen intervalos de aislamiento. /* Inicialización */ L := [(P(x), x), (P(–x), –x)] /* dos intervalos iniciales */ aislamiento := [ ] /* Computación */ mientras que L ≠ [ ] elija (A(x), M(x)) en L y elimínelo de L v := var( A ) si v = 0 entonces salir /* no hay raíz en el intervalo */ si v = 1 entonces /* intervalo de aislamiento encontrado */ agregar (M(0), M(∞)) a la salida de Isol  b := algún entero positivo B(x) = A(x + b) w := v – var(B) si B(0) = 0 entonces /* raíz racional encontrada */ suma (M(b), M(b)) a Isol B(x) := B(x)/x sume (B(x), M(b + x)) a L /* raíces en (M(b), M(+∞)) */ si w = 0 entonces salga /* Teorema de Budan */ si w = 1 entonces /* teorema de Budan nuevamente */ suma (M(0), M(b)) a Isol si w > 1 entonces  suma ( A(b/(1 + x)), M(b/(1 + x)) ) a L /* raíces en (M(0), M(b)) */

Las diferentes variantes del algoritmo dependen esencialmente de la elección de b . En los artículos de Vincent y en el libro de Uspensky, siempre se tiene b = 1 , con la diferencia de que Uspensky no utilizó el teorema de Budan para evitar más bisecciones del intervalo asociado a (0, b).

El inconveniente de elegir siempre b = 1 es que hay que hacer muchos cambios sucesivos de variable de la forma x → 1 + x . Estos pueden ser reemplazados por un único cambio de variable x → n + x , pero, sin embargo, hay que hacer cambios intermedios de variables para aplicar el teorema de Budan.

Una forma de mejorar la eficiencia del algoritmo es tomar como b un límite inferior de las raíces reales positivas, calculado a partir de los coeficientes del polinomio (ver Propiedades de las raíces polinómicas para dichos límites). ^{[8] [1]}

método de bisección

El método de bisección consiste aproximadamente en partir de un intervalo que contiene todas las raíces reales de un polinomio y dividirlo recursivamente en dos partes hasta obtener eventualmente intervalos que contienen cero o una raíz. El intervalo inicial puede tener la forma (- B , B ) , donde B es un límite superior de los valores absolutos de las raíces, como los que se dan en Propiedades de las raíces polinómicas § Límites de raíces polinómicas (complejas) . Por razones técnicas (cambios de variable más simples, análisis de complejidad más simple , posibilidad de aprovechar el análisis binario de las computadoras), los algoritmos generalmente se presentan comenzando con el intervalo [0, 1] . No hay pérdida de generalidad, ya que los cambios de las variables x = By y x = – By mueven respectivamente las raíces positivas y negativas en el intervalo [0, 1] . ( También se puede utilizar la variable de cambios únicos x = (2 By – 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, este algoritmo de prueba debe excluir la posibilidad de obtener infinitas veces la "posibilidad de varias raíces" de salida. El teorema de Sturm y el teorema auxiliar de Vincent proporcionan pruebas tan convenientes. Como el uso de la regla de signos de Descartes y el teorema auxiliar de Vincent es mucho más eficiente desde el punto de vista computacional que el uso del teorema de Sturm, en esta sección sólo se describe el primero.

El método de bisección basado en las reglas de signos de Descartes y el teorema auxiliar de Vincent fue introducido en 1976 por Akritas y Collins con el nombre de algoritmo de Uspensky modificado , ^[3] y se lo conoce como algoritmo de Uspensky , Vincent-Akritas-Collins. algoritmo , o método de Descartes , aunque Descartes, Vincent y Uspensky nunca lo describieron.

El método funciona de la siguiente manera. Para buscar las raíces en algún intervalo, primero se cambia la variable para mapear el intervalo en [0, 1] dando un nuevo polinomio q ( x ) . Para buscar las raíces de q en [0, 1] , se asigna el intervalo [0, 1] a [0, +∞]) mediante el cambio de variable que da un polinomio r ( x ) . La regla de los signos de Descartes aplicada al polinomio r da indicaciones sobre el número de raíces reales de q en el intervalo [0, 1] y, por tanto, sobre el número de raíces del polinomio inicial en el intervalo que ha sido mapeado en [0 , 1] . Si no hay variación de signo en la secuencia de los coeficientes de r , entonces no hay raíz real en los intervalos considerados. Si hay una variación de signo, entonces hay un intervalo de aislamiento. De lo contrario, se divide el intervalo [0, 1] en [0, 1/2] y [1/2, 1] y se los asigna a [0, 1] mediante los cambios de la variable x = y /2 y x = ( y + 1)/2 . El teorema auxiliar de Vincent asegura la terminación de este procedimiento. ${\displaystyle x\to {\frac {1}{x+1}},}$

Excepto la inicialización, todos estos cambios de variable consisten en la composición de como máximo dos cambios de variable muy simples que son los escalamientos por dos x → x /2 , la traslación x → x + 1 , y la inversión x → 1/ x , consistiendo este último simplemente en invertir el orden de los coeficientes del polinomio. Como la mayor parte del tiempo de cálculo se dedica a cambios de variable, el método que consiste en asignar cada intervalo a [0, 1] es fundamental para asegurar una buena eficiencia.

Pseudocódigo

La siguiente notación se utiliza en el pseudocódigo que sigue.

• p ( x ) es el polinomio para el cual se deben aislarlas raíces reales en el intervalo [0, 1]
• var( q ( x )) denota el número de variaciones de signo en la secuencia de los coeficientes del polinomio q
• Los elementos de la lista de trabajo tienen la forma ( c , k , q ( x )) , donde
  • c y k son dos enteros no negativos tales que c < 2 ^k , que representan el intervalo ${\displaystyle \left[{\frac {c}{2^{k}}},{\frac {c+1}{2^{k}}}\right],}$
  • ${\displaystyle q(x)=2^{kn}p\left({\frac {x+c}{2^{k}}}\right),}$donde n es el grado de p (el polinomio q se puede calcular directamente a partir de p , cy k , pero es menos costoso calcularlo incrementalmente, como se hará en el algoritmo; si p tiene coeficientes enteros, lo mismo es cierto para q )

Se  ingresa la función bisección : p ( x ) , un polinomio sin cuadrados , tal que p (0) p (1) ≠ 0 ,para el cual se buscan las raíces en el intervalo [0, 1] salida : una lista de tripletas ( c , k , h ) , que representa intervalos de aislamiento de la forma /* Inicialización */ ${\displaystyle \left[{\frac {c}{2^{k}}},{\frac {c+h}{2^{k}}}\right]}$ L := [(0, 0, p ( x ))] /* un solo elemento en la lista de trabajo L */ aislamiento := [ ] n := grado( p ) /* Computación */ mientras que L ≠ [ ] elija (c, k, q ( x )) en L, y elimínelo de L si q (0) = 0 entonces q ( x ) := q ( x )/ x     n := n – 1 /* Se encontró una raíz racional */ agregue (c, k, 0) a Isol v := si v = 1 entonces /* Se encontró un intervalo de aislamiento */ agregue (c, k, 1) a Isol si v > 1 entonces /* Bisectriz */ agregue (2c, k + 1, a L agregue (2c + 1, k + 1, hasta el extremo L  ${\displaystyle \operatorname {var} ((x+1)^{n}q(1/(x+1)))}$  ${\displaystyle 2^{n}q(x/2)}$  ${\displaystyle 2^{n}q((x+1)/2)}$ 

Este procedimiento es esencialmente el descrito por Collins y Akritas. ^[3] El tiempo de ejecución depende principalmente del número de intervalos que se deben considerar y de los cambios de variables. 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.

Mejoras recientes

Se han propuesto varias formas de mejorar el algoritmo de bisección de Akritas-Collins. Incluyen un método para evitar almacenar una larga lista de polinomios sin perder la simplicidad de los cambios de variables, ^[9] el uso de la aritmética aproximada ( aritmética de punto flotante y de intervalo ) cuando permite obtener el valor correcto para el número de variaciones de signo. , ^[9] el uso del método de Newton cuando sea posible, ^[9] el uso de aritmética polinómica rápida, ^[10] atajos para largas cadenas de bisecciones en caso de grupos de raíces cercanas, ^[10] bisecciones en partes desiguales para limitar problemas de inestabilidad en evaluación polinomial. ^[10]

Todas estas mejoras conducen a un algoritmo para aislar todas las raíces reales de un polinomio con coeficientes enteros, que tiene la complejidad (usando notación O suave , Õ , para omitir factores logarítmicos)

${\displaystyle {\tilde {O}}(n^{2}(k+t)),}$

donde n es el grado del polinomio, k es el número de términos distintos de cero, t es el máximo de dígitos de los coeficientes. ^[10]

La implementación de este algoritmo parece ser más eficiente que cualquier otro método implementado para calcular las raíces reales de un polinomio, incluso en el caso de polinomios que tienen raíces muy cercanas (el caso que anteriormente era el más difícil para el método de bisección). ^[2]

Referencias

1. Tsigaridas y Emiris 2006
2. Kobel, Rouillier y Sagraloff 2016
3. Collins y Akritas 1976
4. Vicente 1834
5. Obreschkoff 1963
6. Ostrowski 1950
7. Uspensky 1948
8. Akritas y Strzeboński 2005
9. Rouillier y Zimmerman 2004
10. Sagraloff y Mehlhorn 2016

Fuentes

• Alesina, Alberto; Massimo Galuzzi (1998). "Una nueva prueba del teorema de Vincent". L'Enseignement Mathématique . 44 (3–4): 219–256. Archivado desde el original el 14 de julio de 2014 . Consultado el 16 de diciembre de 2018 .
• Akritas, Alkiviadis G. (1986). No existe el "método Uspensky". Actas del quinto Simposio ACM sobre Computación Simbólica y Algebraica (SYMSAC '86). Waterloo, Ontario, Canadá. págs. 88–90.
• Akritas, Alkiviadis G.; Strzeboński, AW; Vigklas, PS (2008). "Mejora del rendimiento del método de fracciones continuas utilizando nuevos límites de raíces positivas" (PDF) . Análisis no lineal: modelado y control . 13 (3): 265–279. doi : 10.15388/NA.2008.13.3.14557 .
• Akritas, Alkiviadis G.; Strzeboński, Adam W. (2005). "Un estudio comparativo de dos métodos de aislamiento de raíces reales" (PDF) . Análisis no lineal: modelado y control . 10 (4): 297–304. doi :10.15388/NA.2005.10.4.15110.
• Collins, George E .; Akritas, Alkiviadis G. (1976). "Aislamiento de raíces reales polinómicas mediante la regla de los signos de Descartes" . SYMSAC '76, Actas del tercer simposio ACM sobre computación simbólica y algebraica. Yorktown Heights, Nueva York, Estados Unidos: ACM. págs. 272-275. doi : 10.1145/800205.806346 .
• Kobel, Alejandro; Rouillier, Fabrice; Sagraloff, Michael (2016). "Calcular raíces reales de polinomios reales... ¡y ahora de verdad!". ISSAC '16, Actas de la ACM sobre el Simposio internacional sobre computación simbólica y algebraica . Waterloo, Canadá. arXiv : 1605.00410 . doi :10.1145/2930889.2930937.
• Obreschkoff, Nikola (1963). Verteilung und Berechnung der Nullstellen reeller Polynome (en alemán). Berlín: VEB Deutscher Verlag der Wissenschaften . pag. 81.
• Ostrowski, AM (1950). "Nota sobre el teorema de Vincent". Anales de Matemáticas . Segunda Serie. 52 (3): 702–707. doi :10.2307/1969443. JSTOR  1969443.
• Rouillier, F.; Zimmerman, P. (2004). "Aislamiento eficiente de raíces reales de polinomios". Revista de Matemática Computacional y Aplicada . 162 (1): 33–50. Código Bib : 2004JCoAM.162...33R. doi : 10.1016/j.cam.2003.08.015 .
• Sagraloff, M.; Mehlhorn, K. (2016). "Calcular raíces reales de polinomios reales". Revista de Computación Simbólica . 73 : 46–86. arXiv : 1308.4088 . doi :10.1016/j.jsc.2015.03.004.
• Tsigaridas, Elías P.; Emiris, Ioannis Z. (2006). "Aislamiento de raíces reales polinómicas univariadas: fracciones continuas revisadas". En Azar, Yossi; Erlebach, Thomas (eds.). Algoritmos - ESA 2006, 14º Simposio Europeo Anual, Zurich, Suiza, 11 al 13 de septiembre de 2006, Actas . Apuntes de conferencias sobre informática. vol. 4168. Saltador. págs. 817–828. arXiv : cs/0604066 . doi :10.1007/11841036_72.
• Uspensky, James Víctor (1948). Teoría de ecuaciones. Nueva York: McGraw-Hill Book Company.
• Vicente, Alexandre Joseph Hidulphe (1834). "Mémoire sur la résolution des équations numériques". Mémoires de la Société Royale des Sciences, de L'Agriculture et des Arts, de Lille (en francés): 1–34.
• Vicente, Alexandre Joseph Hidulphe (1836). "Nota sobre la resolución de ecuaciones numéricas" (PDF) . Revista de Mathématiques Pures et Appliquées . 1 : 341–372.
• Vicente, Alexandre Joseph Hidulphe (1838). "Adición de una nota anterior relativa a la resolución de ecuaciones numéricas" (PDF) . Revista de Mathématiques Pures et Appliquées . 3 : 235–243. Archivado desde el original (PDF) el 29 de octubre de 2013 . Consultado el 16 de diciembre de 2018 .