Aislamiento de raíces reales

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 n tiene siempre n raíces complejas (incluyendo las reales), pero solo log n 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 siglo XX 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.^[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 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 ${\displaystyle 10^{20};}$, esto implica que un error de ${\displaystyle 10^{-10}}$ en el valor de la raíz puede producir un valor del polinomio en la raíz aproximada que es del orden de ${\displaystyle 10^{10}.}$. 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.^[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 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 (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 de f(x + b), entonces v 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 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.

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 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 (véase 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 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 [–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.

Teorema de Vincent y afines

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 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 ${\displaystyle a_{1},a_{2},\ldots ,}$ es una secuencia de números reales positivos, sea

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

el k-esimo término de la fracción continua convergente

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

Teorema de Vincent Sea ${\displaystyle p_{0}(x)}$ un polinomio libre de cuadrados de grado n y ${\displaystyle a_{1},a_{2},\ldots ,}$ una secuencia de números reales. Para i = 1, 2,..., considérese el polinomio ${\displaystyle p_{i}(x)=x^{n}p_{i-1}\left(a_{i}+1/x\right).}$ Entonces, existe un entero k tal que ${\displaystyle p_{k}(0)=0,}$ o la secuencia de los coeficientes de ${\displaystyle p_{k}}$ tiene como máximo una variación de signo. En el primer caso, el ck convergente es una raíz positiva de ${\displaystyle p_{0}.}$ De lo contrario, este número de variaciones de signo (0 o 1) es el número de raíces reales de ${\displaystyle p_{0}}$ en el intervalo definido por ${\displaystyle c_{k-1}}$ y ${\displaystyle c_{k}.}$

Para demostrar su teorema, Vincent probó un resultado que es útil por sí solo:^[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 ${\displaystyle \left|{\frac {a}{c}}-{\frac {b}{d}}\right|}$ es lo suficientemente pequeño (pero no 0), entonces hay como máximo una variación de signo en los coeficientes del polinomio ${\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 ${\displaystyle {\frac {a}{c}}}$ y ${\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 de "suficientemente pequeño" fue 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íces por tener 0 o 1 variaciones 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 potencialmente excluidas por poder tener una variación de signo, pero permitidas por tener 0 variaciones de signo

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 ${\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. (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. 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 k necesario, en el teorema de Vincent, para obtener variaciones de un signo o cero:^[1]​^[7]​

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 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{y}}\quad F_{h-1}F_{k}\operatorname {sep} (p)>{\frac {1}{\varepsilon }},}$ donde ${\displaystyle F_{h}}$ es el h-ésimo término de la sucesión de Fibonacci. (Uspensky)

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.^[4]​ Para codificar un algoritmo del teorema de Vincent, se debe proporcionar un criterio para elegir el ${\displaystyle a_{i}}$ 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 p(x) de grado n, cada intervalo está representado por un par ${\displaystyle (A(x),M(x)),}$ donde A(x) es un polinomio de grado n y ${\displaystyle M(x)={\frac {px+r}{qx+s}}}$ es una transformación de Möbius con coeficientes enteros. Se tiene que

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

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

El algoritmo trabaja con una lista de intervalos que, al principio, contiene los dos intervalos ${\displaystyle (A(x)=p(x),M(x)=x)}$ y ${\displaystyle (A(x)=p(-x),M(x)=-x),}$ 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). Luego, para cada intervalo (A(x), M(x)), 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 ${\displaystyle M(0)}$ y ${\displaystyle M(\infty )}$ es un intervalo de aislamiento. 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. En pseudocódigo, este procedimiento toma la forma siguiente, donde var(A) denota el número de variaciones de signo de los coeficientes del polinomio A.

función fracción continua es
    entrada: P (x), un polinomio libre de 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 de inicio */
        Isol: = []
    /* Computación */
    mientras L ≠ [] hacer
        Elija (A (x), M (x)) en L, y elimínelo de L
        v: = var ( A )
        si v = 0 entonces salir /* sin raíz en el intervalo */
        si v = 1 entonces /* intervalo de aislamiento encontrado */
            agregar (M (0), M (∞)) a Isol
            Salida
        b: = algún entero positivo
        B (x) = A (x + b)
        w: = v - var (B)
        si B (0) = 0 entonces /* raíz racional encontrada */
            agregar (M (b), M (b)) a Isol
            B (x): = B (x) / x
        agregar (B (x), M (b + x) a L /* raíces en (b, + ∞) */
        si w = 0 entonces salir /* Teorema de  Budan */
        si w = 1 entonces /* Teorema de Budan nuevamente */
            agregar (M (0), M (b)) a Isol
        si w> 1 entonces
            suma A (b / (1 + x)), M (b / (1 + x)) a L /* raíces en (0, b) */
        final 

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 que b = 1, con la diferencia de que Uspensky no usó 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 ser reemplazados por un solo cambio de variable x → n + x, pero, sin embargo, se tienen que hacer los cambios intermedios de variables 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 (véase 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 lo divide de forma recursiva en dos partes hasta obtener finalmente intervalos que contienen una raíz o ninguna. El intervalo de inicio 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 el artículo dedicado a las propiedades de las raíces polinómicas. Por razones técnicas (cambios más simples de variable, análisis de algoritmos más simples, 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 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. Este algoritmo de prueba debe excluir la posibilidad de obtener infinitas veces la salida "posibilidad de varias raíces". El teorema de Sturm y el teorema auxiliar de Vincent proporcionan verificaciones convenientes al efecto. 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, solo el primero se describe en esta sección.

El método de bisección basado en las reglas de los 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 ha sido conocido como el Algoritmo de Uspensky, el "Algoritmo de Vincent-Akritas-Collins", o el "Método Descartes", aunque ni Descartes, ni Vincent ni Uspensky 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 hacer corresponder 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 la variable ${\displaystyle x\to {\frac {1}{x+1}},}$ que da 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 se ha aplicado 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 se tiene un intervalo de aislamiento. De lo contrario, se divide el intervalo [0, 1] en [0, 1/2] y [1/2, 1], 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 finalización de este procedimiento.

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 escalados por dos aplicaciones x → x/2 : la traslación x → x + 1, y la inversión x → 1/x , esta última consistente simplemente en revertir 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 aplicar cada intervalo en [0, 1] es fundamental para asegurar una buena eficiencia.

Pseudocódigo

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

• p(x) es el polinomio para el que deben aislarse las 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 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)

función bisección es
    entrada: p(x), un polinomio libre de cuadrados, tal que p(0) p(1) ≠ 0,
                      para el que se buscan las raíces en el intervalo [0, 1]
    salida: una lista de tripletes (c, k, h),
                      representando intervalos de aislamiento de la forma ${\displaystyle \left[{\frac {c}{2^{k}}},{\frac {c+h}{2^{k}}}\right]}$
    /* Inicialización */
    L: = [(0, 0, p (x))] /* un solo elemento en la lista de trabajo L */
    Isol: = []
    n: = grado (p)
    /* Computación */
    mientras L ≠ [] hacer
        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 /* Una raíz racional encontrada */
            agregar (c, k, 0) a Isol
        v: = ${\displaystyle \operatorname {var} ((x+1)^{n}q(1/(x+1)))}$
        si v = 1 entonces /* Se encontró un intervalo de aislamiento */
            agregar (c, k, 1) a Isol
        si v> 1 entonces /* Bisecar */
            agregar (2c, k + 1, ${\displaystyle 2^{n}q(x/2)}$ a L
            agregar (2c + 1, k + 1, ${\displaystyle 2^{n}q((x+1)/2)}$ a L
    final

Este procedimiento es esencialmente el descrito por Collins y Akritas.^[3]​ El tiempo de ejecución depende principalmente del número de intervalos que deben considerarse 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 aritmética aproximada (mediante la coma flotante y la aritmética de intervalos) 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 cadenas largas de bisecciones en caso de grupos de raíces cercanas,^[10]​ o bisecciones en partes desiguales para limitar 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 cota superior asintótica, Õ, 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, y t es el máximo de dígitos de los coeficientes.^[10]​

El desarrollo de este algoritmo parece ser más eficiente que cualquier otro método ideado para calcular las raíces reales de un polinomio, incluso en el caso de polinomios que tienen raíces muy próximas (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. Vincent, 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

Bibliografía

• Alesina, Alberto; Massimo Galuzzi (1998). «A new proof of Vincent's theorem». 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). There's no "Uspensky's Method". Proceedings of the fifth ACM Symposium on Symbolic and Algebraic Computation (SYMSAC '86). Waterloo, Ontario, Canada. pp. 88-90. 
• Akritas, Alkiviadis G.; Strzeboński, A. W.; Vigklas, P. S. (2008). «Improving the performance of the continued fractions method using new bounds of positive roots». Nonlinear Analysis: Modelling and Control 13 (3): 265-279. doi:10.15388/NA.2008.13.3.14557. Archivado desde el original el 24 de diciembre de 2013. Consultado el 3 de mayo de 2021. 
• Akritas, Alkiviadis G.; Strzeboński, Adam W. (2005). «A Comparative Study of Two Real Root Isolation Methods». Nonlinear Analysis: Modelling and Control 10 (4): 297-304. doi:10.15388/NA.2005.10.4.15110. Archivado desde el original el 24 de diciembre de 2013. Consultado el 3 de mayo de 2021. 
• Collins, George E.; Akritas, Alkiviadis G. (1976). Polynomial Real Root Isolation Using Descartes' Rule of Signs. SYMSAC '76, Proceedings of the third ACM symposium on Symbolic and algebraic computation. Yorktown Heights, NY, USA: ACM. pp. 272-275. doi:10.1145/800205.806346. 
• Kobel, Alexander; Rouillier, Fabrice; Sagraloff, Michael (2016). «Computing real roots of real polynomials ... and now for real!». ISSAC '16, Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation (Waterloo, Canada). arXiv:1605.00410. doi:10.1145/2930889.2930937. 
• Obreschkoff, Nikola (1963). Verteilung und Berechnung der Nullstellen reeller Polynome (en alemán). Berlin: VEB Deutscher Verlag der Wissenschaften. p. 81. 
• Ostrowski, A. M. (1950). «Note on Vincent's theorem». Annals of Mathematics. Second Series 52 (3): 702-707. JSTOR 1969443. doi:10.2307/1969443. 
• Rouillier, F.; Zimmerman, P. (2004). «Efficient isolation of polynomial's real roots». Journal of Computational and Applied Mathematics 162: 33-50. doi:10.1016/j.cam.2003.08.015. 
• Sagraloff, M.; Mehlhorn, K. (2016). «Computing real roots of real polynomials». Journal of Symbolic Computation 73: 46-86. arXiv:1308.4088. doi:10.1016/j.jsc.2015.03.004. 
• Tsigaridas, P. E.; Emiris, I. Z. (2006). «Univariate polynomial real root isolation: Continued fractions revisited». LNCS. Lecture Notes in Computer Science 4168: 817-828. Bibcode:2006cs........4066T. ISBN 978-3-540-38875-3. arXiv:cs/0604066. doi:10.1007/11841036_72. 
• Uspensky, James Victor (1948). Theory of Equations. New York: McGraw–Hill Book Company. 
• Vincent, 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. 
• Vincent, Alexandre Joseph Hidulphe (1836). «Note sur la résolution des équations numériques». Journal de Mathématiques Pures et Appliquées 1: 341-372. 
• Vincent, Alexandre Joseph Hidulphe (1838). «Addition à une précédente note relative à la résolution des équations numériques». Journal de Mathématiques Pures et Appliquées 3: 235-243. Archivado desde el original el 29 de octubre de 2013. Consultado el 16 de diciembre de 2018. 

Enlaces externos

• Portal:Matemáticas. Contenido relacionado con Matemáticas.

• Datos: Q60790239