Diferencia entre revisiones de «Aislamiento de raíces reales»

Contenido eliminado Contenido añadido

En renglón

Revisión del 17:19 3 may 2021

En matemáticas, y más específicamente en análisis numérico y cálculo simbólico, el aislamiento de raíz real de un polinomio consiste en producir intervals disjuntos del recta real, que contienen cada uno (y solo uno) root real del polinomio, y , juntos, contienen todas las raíces reales del polinomio.

El aislamiento de raíz real es útil porque los resolución numérica de ecuaciones no lineales 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 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 de su tiempo de cálculo se emplea generalmente para calcular raíces no reales (en promedio, un polinomio de grado $n$ tiene raíces complejas $n$ , y solo raíces reales $log n$ ; ver Plantilla:Slink). Además, puede ser difícil distinguir las raíces reales de las raíces no reales con una pequeña parte imaginaria (ver el ejemplo de Wilkinson's polynomial en la siguiente sección).

El primer algoritmo completo de aislamiento de raíz real es el resultado de Teorema de Sturm (1829). Sin embargo, cuando los algoritmos de aislamiento de raíz real comenzaron a implementarse en computadora, pareció que los algoritmos derivados del teorema de Sturm son menos eficientes que los derivados de Regla de los signos de Descartes (1637).

Desde principios del siglo XX existe una activa actividad investigadora para mejorar los algoritmos derivados de la regla de signos de Descartes, conseguir implementaciones muy eficientes y calcular su computational complexity. 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 el recta real (o un intervalo del mismo 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.

Wilkinson's polynomial 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 $10^{20};$ , esto implica que un error de $10^{-10}$ en el valor del root puede producir un valor del polinomio en la raíz aproximada que es del orden de $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 confiables sin usar aritmética exacta. Por lo tanto, si uno quiere aislar raíces de un polinomio con coeficientes coma flotante, a menudo es mejor convertirlos a número racionals y luego tomar el primitive part del polinomio resultante, por 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 terminan en números racionales. Además, siempre se supone que los polinomios son square free. Hay dos razones para eso. En primer lugar, Yun's algorithm para calcular el square-free factorization es menos costoso que el doble del costo del cálculo del greatest common 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 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 múltiples raíces.

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 de Teorema de Sturm (1829), que expresa el número de raíces reales en un intervalo en términos del número de sign variation de los valores de una secuencia de polinomios, denominada `` secuencia de Sturm , en el finales del intervalo. Sturm's

secuencia es la secuencia de residuos que ocurren en una variante de Euclidean algorithm aplicada al polinomio y sus derivados. Cuando se implementó en computadoras, pareció que el aislamiento de la 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

Regla de los signos de Descartes afirma que la diferencia entre el número de sign variation 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 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 Budan's theorem (1807), en un resultado similar para las raíces reales en un intervalo (matemática) $(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)$ , luego $v$ menos el número de raíces reales en el intervalo, contadas con sus multiplicidades, es un número entero par no negativo. Ésta 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íz real para un square-free polynomial (un polinomio sin raíz múltiple): 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 Properties of polynomial roots). Entonces, si uno 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 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 varios raíces.

Teoremas de Vincent y afines

'Plantilla:Vanchor' (1834)^[4] proporciona un método para el aislamiento de raíz real, que es la base de los algoritmos de aislamiento de raíz real más eficientes. Se trata de las raíces reales positivas de un square-free polynomial (que es un polinomio sin raíces múltiples). Si $a_{1},a_{2},\ldots ,$ es una secuencia de números reales positivos, sea

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

ser el $k$ th convergent del fracción continua

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

Plantilla:Math theorem

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

Para trabajar con números reales, siempre se puede elegir $c = d = 1$ , pero, como los cálculos efectivos se realizan con número racional, 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]

Plantilla:Math theorem

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 Plantilla:Slink. Esto permite el análisis de worst-case complexity 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 dramáticamente para diferentes raíces del mismo polinomio.

James V. Uspensky dio un límite en 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] Plantilla:Math theorem

Método de fracción continua

Vincent introdujo el uso de fracción continua para el aislamiento de raíz real, 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, uno debe proporcionar un criterio para elegir el $a_{i}$ que ocurre en su teorema. Vincent mismo proporcionó 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.

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 genera 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 $(A(x),M(x)),$ donde $A (x)$ es un polinomio de grado $n$ y $M(x)={\frac {px+r}{qx+s}}$ es

un Transformación de Möbius con coeficientes enteros. Uno tiene

A(x)=p(M(x)),

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

El algoritmo trabaja con una lista de intervalos que, al principio, contiene los dos intervalos $(A(x)=p(x),M(x)=x)$ y $(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, como si fueron, 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 $M(0)$ y $M(\infty )$ es un intervalo de aislamiento. De lo contrario, se elige un número real positivo $b$ para dividir el intervalo $(0, +\infty)$ en $(0, b)$ y $(b, +\infty)$ y, para cada subintervalo, se compone $M$ con una transformación de Möbius que mapea el intervalo en $(0, +\infty)$ , para obtener dos nuevos intervalos que se agregará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$ .

 'función'  fracción continua  'es' 
     'entrada' : P (x), a square-free polynomial,
     '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  $\neq$  []  'hacer' 
         'Elija'  (A (x), M (x))  'en'  L,  'y elimínelo de'  L
        v: = var ( A )
         'si'  v = 0  'entonces salga'  / * 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 salga'  / * Budan's theorem * /
         '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) * /

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 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 \to 1 + x$ . Estos pueden ser reemplazados por un solo cambio de variable $x \to n + x$ , pero, sin embargo, uno tiene 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 (ver Properties of polynomial roots 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 cero. 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 Plantilla:Slink. Por razones técnicas (cambios más simples de variable, análisis de algoritmos más simple, posibilidad de aprovechar el análisis binario de 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 salida "posibilidad de varias raíces". Teorema de Sturm y el teorema auxiliar de Vincent proporcionan pruebas tan convenientes. Como el uso de 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 Uspensky modificado ,^[3] y ha sido conocido como el Algoritmo Uspensky . t

El "algoritmo Vincent-Akritas-Collins", o el "método 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, +\infty])$ mediante el cambio de la variable $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 tanto, sobre el número de raíces del polinomio inicial en el intervalo que se ha 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. 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 terminació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 $x \to x /2$ , el translation $x \to x + 1$ , y la inversión $x \to 1/ x$ , este último 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 mapear cada intervalo a $[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 sign variation 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 $\left[{\frac {c}{2^{k}}},{\frac {c+1}{2^{k}}}\right],$
- $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 square-free polynomial, tal que  $p (0) p (1) \neq 0$ ,
                      para el que se buscan las raíces en el intervalo  $[0, 1]$ 
     'salida' : una lista de triples  $(c, k, h)$ ,
                      representando intervalos de aislamiento de la forma  $\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  $\neq$  []  '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: =  $\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,  $2^{n}q(x/2)$   'a'  L
             'agregar'  (2c + 1, k + 1,  $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 (coma flotante y interval arithmetic) cuando permite obtener el valor correcto para el número de variaciones de signo,^[9] el uso de 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] 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 el complexity (usando cota superior asintótica, $Õ$ , para omitir factores logarítmicos)

{\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 digits 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

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. Parámetro desconocido |url-status= ignorado (ayuda)
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.
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.
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.
Plantilla:Cite proceedings
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. Parámetro desconocido |doi-access= ignorado (ayuda)
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. Parámetro desconocido |url-status= ignorado (ayuda)

Datos: Q60790239

[TE-1] Tsigaridas y Emiris, 2006

[KRS-2] Kobel, Rouillier y Sagraloff, 2016

[CA-3] Collins y Akritas, 1976

[Vincent-memoire-4] Vincent, 1834

[Obr_1920-5] Obreschkoff, 1963

[O_1950-6] Ostrowski, 1950

[Uspensky-7] Uspensky, 1948

[8] Akritas y Strzeboński, 2005

[RZ-9] Rouillier y Zimmerman, 2004

[SM-10] Sagraloff y Mehlhorn, 2016

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]