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 computacional , el aislamiento de raíces reales de un polinomio consiste en producir intervalos disjuntos de la línea real , que contienen cada una (y solo una) raíz real del polinomio y, juntos, contienen 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, por lo general, no pueden certificar haber encontrado todas las raíces reales. En particular, si un algoritmo de este tipo no encuentra ninguna raíz, no se sabe si es porque no hay ninguna 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 dedica generalmente a calcular raíces no reales (en promedio, un polinomio de grado n tiene n raíces complejas y solo logaritmo de n raíces reales; consulte Propiedades geométricas de las raíces polinómicas § Raíces reales ). Además, puede ser 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 es el resultado del teorema de Sturm (1829). Sin embargo, cuando los algoritmos de aislamiento de raíces reales comenzaron a implementarse en computadoras, se demostró que los algoritmos derivados del teorema de Sturm eran menos eficientes que los derivados de la regla de 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 los signos de Descartes, obteniendo implementaciones muy eficientes y calculando su complejidad computacional . Las mejores implementaciones pueden aislar rutinariamente 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 habitual es dividir la recta real (o un intervalo de la misma donde se buscan las raíces) en intervalos disjuntos hasta tener como máximo una raíz en cada intervalo. Este procedimiento se denomina aislamiento de raíces y un intervalo resultante que contiene exactamente una raíz es un intervalo aislante de 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 estar cerca de 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íces no puede dar resultados confiables sin usar aritmética exacta. Por lo tanto, si se quieren aislar raíces de un polinomio con coeficientes de punto flotante , a menudo es mejor convertirlas 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, se supone que los polinomios siempre están libres de cuadrados . Hay dos razones para eso. 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 su derivada. Como esto puede producir factores de grados inferiores, generalmente es ventajoso aplicar algoritmos de aislamiento de raíces solo en polinomios sin raíces múltiples, incluso cuando esto no lo requiere el algoritmo. La segunda razón para considerar solo 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 aislar 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 un procedimiento de decisión de este tipo, 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 divisiones posteriores 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, llamada secuencia de Sturm , en los extremos del intervalo. La secuencia de Sturm es la secuencia de residuos que se producen en una variante del algoritmo euclidiano aplicado al polinomio y sus derivadas. Cuando se implementó en computadoras, pareció que el aislamiento de raíces 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 usa 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 coeficientes de un polinomio y el número de sus raíces reales positivas es un entero par no negativo. De ello se deduce que si este número de variaciones de signo es cero, entonces el polinomio no tiene ninguna raíz real positiva y, si este número es uno, entonces el polinomio tiene una única raíz real positiva, que es una raíz simple. Lamentablemente, la inversa no es cierta, es decir, un polinomio que no tiene ninguna raíz real positiva o tiene una sola raíz simple positiva 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 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 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 menores 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 de los valores absolutos de las diferencias de dos raíces (ver Propiedades de las raíces polinómicas ). Luego, 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 lo 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 gruesa 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 contenga varias raíces.

Teoremas de Vincent y relacionados

El teorema de Vincent (1834)^[4]proporciona un método para aislar raíces reales, que es la base de los algoritmos de aislamiento de raíces reales más eficientes. Se refiere a las raíces reales positivas de unpolinomio sin cuadrados(es decir, un polinomio sin raíces múltiples). Sies una secuencia 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}}}}}}}}}}$

sea ​​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 sin cuadrados de grado n y una sucesión 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, hay un entero k tal que cualquiera de las secuencias de coeficientes de tiene como máximo una variación de signo. ${\displaystyle p_{k}(0)=0,}$ ${\displaystyle p_{k}}$

En el primer caso, la convergente c _k 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í mismo: ^[4]

Teorema auxiliar de Vincent  :  si p ( x ) es un polinomio libre de cuadrados de grado n y a , b , c , d son números reales no negativos tales que es suficientemente pequeño (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ño" ha sido cuantificada independientemente por Nikola Obreshkov , ^[5] y Alexander Ostrowski : ^[6]

Teorema de Obreschkoff-Ostrowski: en azul y amarillo, las regiones del plano complejo donde no debe haber raíz por tener 0 o 1 variación de signo; 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 se excluyen por tener una variación de signo, pero se permiten cero variaciones de signo.

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 estar limitada 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 § Separación de raíces . 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 las 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 a la longitud de la fracción continua (el entero k en el teorema de Vincent), para obtener variaciones de signo cero o uno: ^{[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 . Sea

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

Entonces el 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 aislar raíces reales, aunque atribuyó esta idea a Joseph-Louis Lagrange , sin proporcionar una referencia. ^[4] Para elaborar un algoritmo del teorema de Vincent, se debe proporcionar un criterio para elegir las que aparecen en su teorema. El propio Vincent proporcionó algunas opciones (véase más adelante). Son posibles otras opciones, y la eficiencia del algoritmo puede depender drásticamente de ellas. A continuación se presenta un algoritmo en el que estas opciones resultan de una función auxiliar que se analizará 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, generando un intervalo de aislamiento.

Para aislar las raíces reales de un polinomio p ( x ) de grado n , cada intervalo se representa mediante un par donde A ( x ) es un polinomio de grado n y es una transformación de Möbius con coeficientes enteros. Se 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 correspondientes a la partición de los reales en positivos y negativos (se puede suponer que cero no es una raíz, pues, si lo fuera, basta con aplicar el algoritmo a p ( x )/ x ). Luego, para cada intervalo ( A ( x ), M ( x )) de 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. En caso 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 sobre (0, +∞) , para obtener dos nuevos intervalos que se añadirán 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 )}$

La función fracción continua tiene  como entrada P(x), un polinomio sin cuadrados , y como 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 */ Aislado := [ ] /* Cálculo */ mientras 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 /* se encontró el intervalo de aislamiento */ agregar (M(0), M(∞)) a Isol salir 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 suma (B(x), M(b + x)) a L /* raíces en (M(b), M(+∞)) */ si w = 0 entonces salir /* 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 bisecciones adicionales 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 sustituirse por un único cambio de variable x → n + x , pero, no obstante, hay que hacer los cambios intermedios de variable para aplicar el teorema de Budan.

Una forma de mejorar la eficiencia del algoritmo es tomar para 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 finalmente intervalos que contienen cero o una raíz. El intervalo de partida puede ser de 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 las 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 se presentan generalmente como si comenzaran 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 el cambio simple de variable x = (2 By – B ) .)

El método requiere un algoritmo para comprobar si un intervalo tiene cero, una o posiblemente varias raíces y, para garantizar la terminación, este algoritmo de comprobación debe excluir la posibilidad de obtener una cantidad infinita de veces la salida "posibilidad de varias raíces". El teorema de Sturm y el teorema auxiliar de Vincent proporcionan pruebas convenientes de este tipo. Como el uso de la regla de los signos de Descartes y el teorema auxiliar de Vincent es mucho más eficiente computacionalmente que el uso del teorema de Sturm, en esta sección solo 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 bajo el nombre de algoritmo de Uspensky modificado , ^[3] y se ha denominado algoritmo de Uspensky , algoritmo de Vincent-Akritas-Collins 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 mapea el intervalo [0, 1] en [0, +∞]) mediante el cambio de variable dando un polinomio r ( x ) . La regla de 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 lo 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 uno tiene un intervalo de aislamiento. En caso 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 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}},}$

A excepción de 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 , esta última consiste simplemente en invertir el orden de los coeficientes del polinomio. Como la mayor parte del tiempo de cálculo se dedica a los cambios de variable, el método consistente en mapear 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 deben aislarselas 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 números 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 puede calcularse directamente a partir de p , c y k , pero es menos costoso calcularlo de forma incremental, como se hará en el algoritmo; si p tiene coeficientes enteros, lo mismo es cierto para q )

La bisección de la función se  ingresa como : p ( x ) , un polinomio libre de 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 ) , representando 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 */ Aislado := [ ] n := grado( p ) /* Cálculo */ mientras L ≠ [ ] elija (c, k, q ( x ) )  en L, y quítelo de L si  q (0) = 0  entonces  q ( x ) := q ( x )/ x n := n – 1 /* Se encontró una raíz racional */ añadir (c, k, 0) a Isol v := si v = 1 entonces /* Se encuentra un intervalo de aislamiento */ suma (c, k, 1) a Isol si v > 1 entonces /* Bisectriz */ suma (2c, k + 1, a L suma (2c + 1, k + 1, a L fin ${\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 básicamente 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 las variables. Existen 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. Estas 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 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 polinomial rápida, ^[10] atajos para largas cadenas de bisecciones en caso de grupos de raíces cercanas, ^[10] bisecciones en partes desiguales para limitar los problemas de inestabilidad en la evaluación de polinomios. ^[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 la notación O suave , Õ , para omitir los 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. Uspenski 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 ningún "método de Uspensky". Actas del quinto simposio de la 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 polinomiales utilizando la regla de signos de Descartes . SYMSAC '76, Actas del tercer simposio de la ACM sobre computación simbólica y algebraica. Yorktown Heights, NY, EE. UU.: ACM. págs. 272–275. doi : 10.1145/800205.806346 .
• Kobel, Alexander; Rouillier, Fabrice; Sagraloff, Michael (2016). "Cálculo de raíces reales de polinomios reales... ¡y ahora de verdad!". ISSAC '16, Actas del Simposio Internacional sobre Computación Simbólica y Algebraica de la ACM . 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". Journal of Computational and Applied Mathematics . 162 (1): 33–50. Bibcode :2004JCoAM.162...33R. doi : 10.1016/j.cam.2003.08.015 .
• Sagraloff, M.; Mehlhorn, K. (2016). "Cálculo de raíces reales de polinomios reales". Journal of Symbolic Computation . 73 : 46–86. arXiv : 1308.4088 . doi :10.1016/j.jsc.2015.03.004.
• Tsigaridas, Elias P.; Emiris, Ioannis Z. (2006). "Aislamiento univariante de raíces reales polinomiales: reconsideración de las fracciones continuas". En Azar, Yossi; Erlebach, Thomas (eds.). Algorithms - ESA 2006, 14.° Simposio europeo anual, Zúrich, Suiza, 11-13 de septiembre de 2006, Actas . Lecture Notes in Computer Science. Vol. 4168. Springer. págs. 817–828. arXiv : cs/0604066 . doi :10.1007/11841036_72. ISBN . 978-3-540-38875-3.
• Uspensky, James Victor (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 .