teorema de vincent

En matemáticas, el teorema de Vincent —llamado así en honor a Alexandre Joseph Hidulphe Vincent— es un teorema que aísla las raíces reales de polinomios con coeficientes racionales.

Aunque el teorema de Vincent es la base del método más rápido para el aislamiento de las raíces reales de polinomios, fue casi totalmente olvidado, habiendo sido eclipsado por el teorema de Sturm ; en consecuencia, no aparece en ninguno de los libros clásicos sobre teoría de ecuaciones (del siglo XX), excepto en el libro de Uspensky . Se presentan dos variantes de este teorema, junto con varios métodos de aislamiento de raíces reales (fracciones continuas y bisección) derivados de ellas.

Variación de signos

Sea c ₀ , c ₁ , c ₂ , ... una secuencia finita o infinita de números reales. Supongamos que l < r y se cumplen las siguientes condiciones:

1. Si r = l +1 los números c _l y cr tienen _signos opuestos.
2. Si r ≥ l +2 los números c _{l +1} , ..., _{cr −1} son _todos cero y los números _c l _y cr tienen signos opuestos.

Esto se llama variación de signo o cambio de signo entre _los números c _l y cr .

Cuando se trata del polinomio p ( x ) en una variable, se define el número de variaciones de signo de p ( x ) como el número de variaciones de signo en la secuencia de sus coeficientes.

Se presentan dos versiones de este teorema: la versión de fracciones continuas debida a Vincent, ^{[1] [2] [3]} y la versión de bisección debida a Alesina y Galuzzi. ^{[4] [5]}

Teorema de Vincent: versión de fracciones continuas (1834 y 1836)

Si en una ecuación polinómica con coeficientes racionales y sin raíces múltiples se hacen sucesivas transformaciones de la forma

${\displaystyle x=a_{1}+{\frac {1}{x'}},\quad x'=a_{2}+{\frac {1}{x''}},\quad x''=a_{3}+{\frac {1}{x'''}},\ldots }$

donde hay números positivos mayores o iguales a uno, luego de varias de estas transformaciones, la ecuación transformada resultante tiene variaciones de signo cero o tiene una variación de signo único. En el primer caso no hay raíz, mientras que en el segundo caso hay una única raíz real positiva. Además, la raíz correspondiente de la ecuación propuesta se aproxima mediante la fracción continua finita: ^{[1] [2] [3]} ${\displaystyle a_{1},a_{2},a_{3},\ldots }$

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

Además, si se pueden encontrar infinitos números que satisfacen esta propiedad, entonces la raíz está representada por la fracción continua correspondiente (infinita). ${\displaystyle a_{1},a_{2},a_{3},\ldots }$

La afirmación anterior es una traducción exacta del teorema que se encuentra en los artículos originales de Vincent; ^{[1] [2] [3]} sin embargo, se necesitan las siguientes observaciones para una comprensión más clara:

• Si denota el polinomio obtenido después de n sustituciones (y después de eliminar el denominador), entonces existe N tal que para todos no tiene variación de signo o tiene una variación de signo. En este último caso tiene una única raíz real positiva para todos . ${\displaystyle f_{n}(x)}$ ${\displaystyle n\geq N}$ ${\displaystyle f_{n}(x)}$ ${\displaystyle f_{n}(x)}$ ${\displaystyle n\geq N}$
• La fracción continua representa una raíz positiva de la ecuación original y la ecuación original puede tener más de una raíz positiva. Además, suponiendo que sólo podemos obtener una raíz de la ecuación original que sea > 1. Para obtener una raíz positiva arbitraria debemos suponer que . ${\displaystyle a_{1}\geq 1}$ ${\displaystyle a_{1}\geq 0}$
• Las raíces negativas se obtienen reemplazando x por − x , en cuyo caso las raíces negativas se vuelven positivas.

Teorema de Vincent: versión de bisección (Alesina y Galuzzi 2000)

Sea p ( x ) un polinomio real de grado grados ( p ) que solo tiene raíces simples. Es posible determinar una cantidad positiva δ de modo que para cada par de números reales positivos a , b con , cada polinomio transformado de la forma ${\displaystyle |b-a|<\delta }$

tiene exactamente 0 o 1 variaciones de signo. El segundo caso es posible si y sólo si p ( x ) tiene una única raíz dentro de ( a , b ).

La "prueba de raíces a_b" de Alesina-Galuzzi

De la ecuación ( 1 ) se obtiene el siguiente criterio para determinar si un polinomio tiene raíces en el intervalo ( a , b ):

Realizar en p ( x ) la sustitución

${\displaystyle x\leftarrow {\frac {a+bx}{1+x}}}$

y contar el número de variaciones de signo en la secuencia de coeficientes del polinomio transformado; este número da un límite superior al número de raíces reales que p ( x ) tiene dentro del intervalo abierto ( a , b ). Más precisamente, el número ρ _ab ( p ) de raíces reales en el intervalo abierto ( a , b ) —multiplicidades contadas— del polinomio p ( x ) en R [ x ], de grado grados( p ), está acotado arriba por el número de variaciones de signos var _ab ( p ), donde

${\displaystyle \operatorname {var} _{ab}(p)=\operatorname {var} \left((1+x)^{\deg(p)}p\left({\frac {a+bx}{1+x}}\right)\right),}$

${\displaystyle \operatorname {var} _{ab}(p)=\operatorname {var} _{ba}(p)\geq \rho _{ab}(p).}$

Como en el caso de la regla de los signos de Descartes, si var _ab ( p ) = 0 se sigue que ρ _ab ( p ) = 0 y si var _ab ( p ) = 1 se sigue que ρ _ab ( p ) = 1.

Un caso especial de la "prueba de raíces a_b" de Alesina-Galuzzi es la "prueba de raíces 0_1" de Budan .

Bosquejo de una prueba

En el trabajo de Alesina y Galuzzi se puede encontrar una discusión detallada del teorema de Vincent, su extensión, la interpretación geométrica de las transformaciones involucradas y tres demostraciones diferentes. ^{[4] [5]} Una cuarta prueba se debe a Ostrowski ^[6] quien redescubrió un caso especial de un teorema enunciado por Obreschkoff , ^[7] p. 81, en 1920-1923.

Para probar (ambas versiones del) teorema de Vincent, Alesina y Galuzzi muestran que después de una serie de transformaciones mencionadas en el teorema, un polinomio con una raíz positiva eventualmente tiene una variación de signo. Para demostrar esto, utilizan el siguiente corolario del teorema de Obreschkoff de 1920-1923 mencionado anteriormente; es decir, el siguiente corolario da las condiciones necesarias bajo las cuales un polinomio con una raíz positiva tiene exactamente una variación de signo en la secuencia de sus coeficientes; ver también la figura correspondiente.

Corolario. ( Teorema del cono o sector de Obreschkoff , 1920-1923 ^[7] p. 81): Si un polinomio real tiene una raíz simple x ₀ y todas las demás raíces (posiblemente múltiples) se encuentran en el sector

${\displaystyle S_{\sqrt {3}}=\left\{x=-\alpha +i\beta \ :\ |\beta |\leq {\sqrt {3}}|\alpha |,\alpha >0\right\}}$

entonces la secuencia de sus coeficientes tiene exactamente una variación de signo.

El sector de Obreschkoff y su famosa figura en forma de ocho (de círculos). ${\displaystyle S_{\sqrt {3}}}$

Consideremos ahora la transformación de Möbius.

${\displaystyle M(x)={\frac {ax+b}{cx+d}},\qquad a,b,c,d\in \mathbb {Z} _{>0}}$

y los tres círculos que se muestran en la figura correspondiente; asumir que a/C<b/d.

• El círculo (amarillo)

${\displaystyle \left|x-{\tfrac {1}{2}}\left({\tfrac {a}{c}}+{\tfrac {b}{d}}\right)\right|={\tfrac {1}{2}}\left({\tfrac {b}{d}}-{\tfrac {a}{c}}\right)}$

cuyo diámetro se encuentra en el eje real, con puntos extremosa/C yb/d, se mapea mediante la transformación inversa de Möbius

${\displaystyle M^{-1}(x)={\frac {dx-b}{-cx+a}}}$

sobre el eje imaginario. Por ejemplo el punto

${\displaystyle {\tfrac {1}{2}}\left({\tfrac {a}{c}}+{\tfrac {b}{d}}\right)+{\tfrac {i}{2}}\left({\tfrac {b}{d}}-{\tfrac {a}{c}}\right)}$

se asigna al punto − i d/C. Los puntos exteriores se asignan al semiplano con Re( x ) < 0 .

• Los dos círculos (sólo son visibles sus medias lunas azules) con centro

${\displaystyle {\tfrac {1}{2}}\left({\tfrac {a}{c}}+{\tfrac {b}{d}}\right)\pm {\tfrac {i}{2{\sqrt {3}}}}\left({\tfrac {b}{d}}-{\tfrac {a}{c}}\right)}$

y radio

${\displaystyle {\tfrac {1}{\sqrt {3}}}\left({\tfrac {b}{d}}-{\tfrac {a}{c}}\right)}$

se mapean mediante la transformación inversa de Möbius

${\displaystyle M^{-1}(x)={\frac {dx-b}{-cx+a}}}$

sobre las rectas Im( x ) = ± √ 3 Re( x ) . Por ejemplo el punto

${\displaystyle {\tfrac {1}{2}}\left({\tfrac {a}{c}}+{\tfrac {b}{d}}\right)-{\tfrac {3i}{2{\sqrt {3}}}}\left({\tfrac {b}{d}}-{\tfrac {a}{c}}\right)}$

se mapea al punto

${\displaystyle {\tfrac {-d}{2c}}\left(1-i{\sqrt {3}}\right).}$

Los puntos exteriores (aquellos fuera de la figura en forma de ocho) se asignan al sector. ${\displaystyle S_{\sqrt {3}}}$

De lo anterior resulta obvio que si un polinomio tiene una única raíz positiva dentro de la figura en forma de ocho y todas las demás raíces están fuera de ella, presenta una variación de signo en la secuencia de sus coeficientes. Esto también garantiza la terminación del proceso.

Antecedentes históricos

Primeras aplicaciones del teorema de Vincent

En sus artículos fundamentales, ^{[1] [2] [3]} Vincent presentó ejemplos que muestran precisamente cómo usar su teorema para aislar raíces reales de polinomios con fracciones continuas . Sin embargo, el método resultante tenía un tiempo de cálculo exponencial , un hecho que los matemáticos debieron haber comprendido entonces, como lo hizo Uspensky ^[8] p. 136, un siglo después.

La búsqueda de Vincent de una raíz (aplicando el teorema de Budan)

La naturaleza exponencial del algoritmo de Vincent se debe a la forma en que se calculan los cocientes parciales _ai (en el teorema de Vincent ) . Es decir, para calcular cada cociente parcial a _i (es decir, localizar dónde se encuentran las raíces en el eje x ), Vincent utiliza el teorema de Budan como una "prueba sin raíces" ; en otras palabras, para encontrar la parte entera de una raíz Vincent realiza sustituciones sucesivas de la forma x ← x +1 y se detiene sólo cuando los polinomios p ( x ) y p ( x +1) difieren en el número de variaciones de signo en la raíz. secuencia de sus coeficientes (es decir, cuando el número de variaciones de signo de p ( x +1) disminuye).

Vea el diagrama correspondiente donde la raíz se encuentra en el intervalo (5, 6). Se puede inferir fácilmente que, si la raíz está lejos del origen, se necesita mucho tiempo para encontrar su parte entera de esta manera, de ahí el carácter exponencial del método de Vincent. A continuación se explica cómo se supera este inconveniente.

Desaparición del teorema de Vincent

Vincent fue el último autor del siglo XIX en utilizar su teorema para aislar las raíces reales de un polinomio.

La razón de esto fue la aparición del teorema de Sturm en 1827, que resolvió el problema del aislamiento de raíces reales en tiempo polinómico , al definir el número preciso de raíces reales que tiene un polinomio en un intervalo abierto real ( a , b ). El método resultante (de Sturm) para calcular las raíces reales de polinomios ha sido el único ampliamente conocido y utilizado desde entonces, hasta aproximadamente 1980, cuando fue reemplazado (en casi todos los sistemas de álgebra computacional ) por métodos derivados del teorema de Vincent, el El más rápido es el método Vincent-Akritas-Strzeboński (VAS). ^[9]

Serret incluyó en su Álgebra, ^[10] págs. 363–368, el teorema de Vincent junto con su demostración y dirigió a todos los lectores interesados ​​a los artículos de Vincent para obtener ejemplos de cómo se utiliza. Serret fue el último autor en mencionar el teorema de Vincent en el siglo XIX.

El regreso del teorema de Vincent

En el siglo XX, el teorema de Vincent no se puede encontrar en ninguno de los libros de teoría de ecuaciones; las únicas excepciones son los libros de Uspensky ^[8] y Obreschkoff , ^[7] donde en el segundo sólo aparece el enunciado del teorema.

Fue en el libro de Uspensky ^[8] donde Akritas encontró el teorema de Vincent y lo convirtió en el tema de su doctorado. Tesis "Teorema de Vincent en manipulación algebraica", Universidad Estatal de Carolina del Norte, EE. UU. , 1978. Un logro importante en ese momento fue conseguir el artículo original de Vincent de 1836, algo que se le había escapado a Uspensky , lo que resultó en un gran malentendido . El artículo original de Vincent de 1836 se puso a disposición de Akritas gracias a los esfuerzos encomiables (préstamo interbibliotecario) de un bibliotecario de la Biblioteca de la Universidad de Wisconsin-Madison, EE. UU .

Métodos de aislamiento de raíces reales derivados del teorema de Vincent

El aislamiento de las raíces reales de un polinomio es el proceso de encontrar intervalos abiertos disjuntos tales que cada uno contenga exactamente una raíz real y cada raíz real esté contenida en algún intervalo. Según la escuela francesa de matemáticas del siglo XIX, este es el primer paso para calcular las raíces reales, siendo el segundo su aproximación con cualquier grado de precisión; además, la atención se centra en las raíces positivas , porque para aislar las raíces negativas del polinomio p ( x ) reemplaza x por − x ( x ← − x ) y repite el proceso.

La versión de fracciones continuas del teorema de Vincent se puede utilizar para aislar las raíces positivas de un polinomio dado p ( x ) de grado grados ( p ). Para ver esto, represente por la transformación de Möbius.

${\displaystyle M(x)={\frac {ax+b}{cx+d}},\qquad a,b,c,d\in \mathbb {N} }$

la fracción continua que conduce a un polinomio transformado

con variación de un signo en la secuencia de sus coeficientes. Entonces, la única raíz positiva de f ( x ) (en el intervalo (0, ∞)) corresponde a esa raíz positiva de p ( x ) que está en el intervalo abierto con puntos finales y . Estos puntos finales no están ordenados y corresponden a M (0) y M (∞) respectivamente. ${\displaystyle {\frac {b}{d}}}$ ${\displaystyle {\frac {a}{c}}}$

Por lo tanto, para aislar las raíces positivas de un polinomio, todo lo que se debe hacer es calcular, para cada raíz, las variables a , b , c , d de la correspondiente transformación de Möbius.

${\displaystyle M(x)={\frac {ax+b}{cx+d}}}$

eso conduce a un polinomio transformado como en la ecuación ( 2 ), con una variación de un signo en la secuencia de sus coeficientes.

Observación crucial: las variables a , b , c , d de una transformación de Möbius

${\displaystyle M(x)={\frac {ax+b}{cx+d}}}$

(en el teorema de Vincent) que conduce a un polinomio transformado, como en la ecuación ( 2 ), con una variación de un signo en la secuencia de sus coeficientes se puede calcular:

• ya sea por fracciones continuas , lo que lleva al método de fracciones continuas de Vincent-Akritas-Strzebonski (VAS) , ^[9]
• o por bisección , lo que lleva a (entre otros) el método de bisección Vincent-Collins-Akritas (VCA) . ^[11]

La "parte de bisección" de esta importante observación apareció como un teorema especial en los artículos de Alesina y Galuzzi. ^{[4] [5]}

Todos los métodos que se describen a continuación (consulte el artículo sobre el teorema de Budan para conocer sus antecedentes históricos) necesitan calcular (una vez) un límite superior, ub , de los valores de las raíces positivas del polinomio bajo consideración. La excepción es el método VAS, donde además se deben calcular límites inferiores, lb , en casi todos los ciclos del bucle principal. Para calcular el límite inferior lb del polinomio p ( x ), calcule el límite superior ub del polinomio y establezca . ${\displaystyle x^{\deg(p)}p\left({\frac {1}{x}}\right)}$ ${\displaystyle lb={\frac {1}{ub}}}$

Akritas, Strzeboński y Vigklas han desarrollado excelentes límites (superior e inferior) para los valores de las raíces positivas de polinomios basándose en trabajos previos de Doru Stefanescu. Se describen en el Ph.D. de PS Vigklas. Tesis ^[12] y otros lugares. ^[13] Estos límites ya se han implementado en los sistemas de álgebra informática Mathematica , SageMath , SymPy , Xcas , etc.

Los tres métodos que se describen a continuación siguen la excelente presentación de François Boulier, ^[14] p. 24.

Método de fracciones continuas

Sólo un método de fracciones continuas se deriva del teorema de Vincent. Como se indicó anteriormente, comenzó en la década de 1830 cuando Vincent presentó, en los artículos ^{[1] [2] [3]} varios ejemplos que muestran cómo usar su teorema para aislar las raíces reales de polinomios con fracciones continuas . Sin embargo, el método resultante tenía un tiempo de cálculo exponencial . A continuación se muestra una explicación de cómo evolucionó este método.

Vicente – Akritas – Strzeboński (VAS, 2005)

Este es el segundo método (después del VCA) desarrollado para manejar el comportamiento exponencial del método de Vincent.

El método de fracciones continuas VAS es una implementación directa del teorema de Vincent. Fue presentado originalmente por Vincent de 1834 a 1938 en los artículos ^{[1] [2] [3]} en forma exponencial; es decir, Vincent calculó cada cociente parcial a _i mediante una serie de incrementos unitarios a _i ← a _i + 1, que son equivalentes a sustituciones de la forma x ← x + 1.

El método de Vincent fue convertido a su forma de complejidad polinómica por Akritas, quien en su doctorado de 1978. Thesis ( Teorema de Vincent en manipulación algebraica , Universidad Estatal de Carolina del Norte, EE. UU.) calculó cada cociente parcial a _i como el límite inferior, lb , de los valores de las raíces positivas de un polinomio. Esto se denomina límite de raíz inferior positivo ideal y calcula la parte entera de la raíz positiva más pequeña (consulte la figura correspondiente). Es decir, ahora establezca a _i ← lb o, de manera equivalente, realice la sustitución x ← x + lb , que toma aproximadamente el mismo tiempo que la sustitución x ← x + 1.

VAS en busca de una raíz: el límite inferior ideal es 5, por lo tanto x ← x + 5.

Finalmente, dado que el límite inferior positivo ideal de la raíz no existe, Strzeboński ^[15] introdujo en 2005 la sustitución , siempre que ; en general y el valor 16 se determinó experimentalmente. Además, se ha demostrado ^[15] que el método VAS ( fracciones continuas ) es más rápido que la implementación más rápida del método VCA (bisección), ^[16] hecho que fue confirmado ^[17] de forma independiente; más precisamente, para los polinomios de Mignotte de alto grado, VAS es aproximadamente 50.000 veces más rápido que la implementación más rápida de VCA. ${\displaystyle x\leftarrow lb_{computed}*x}$ ${\displaystyle lb_{computed}>16}$ ${\displaystyle lb>lb_{computed}}$

En 2007, Sharma ^[18] eliminó la hipótesis del límite inferior positivo ideal y demostró que VAS sigue siendo polinomio en el tiempo.

VAS es el algoritmo predeterminado para el aislamiento de raíces en Mathematica , SageMath , SymPy , Xcas .

Para una comparación entre el método de Sturm y VAS, utilice las funciones realroot(poly) y time(realroot(poly)) de Xcas . De forma predeterminada, para aislar las raíces reales de poli realroot se utiliza el método VAS; para utilizar el método de Sturm escriba realroot(sturm, poli). Consulte también los enlaces externos para ver una aplicación de A. Berkakis para dispositivos Android que hace lo mismo.

Así es como funciona VAS( p , M ), donde por simplicidad no se incluye la contribución de Strzeboński:

• Sea p ( x ) un polinomio de grado grados ( p ) tal que p (0) ≠ 0. Para aislar sus raíces positivas, asocie con p ( x ) la transformación de Möbius M ( x ) = x y repita los siguientes pasos mientras hay pares { p ( x ), M ( x )} para procesar.
• Utilice la regla de los signos de Descartes sobre p ( x ) para calcular, si es posible, (utilizando el número var de variaciones de signos en la secuencia de sus coeficientes) el número de sus raíces dentro del intervalo (0, ∞). Si no hay raíces, devuelve el conjunto vacío, ∅ mientras que si hay una raíz, devuelve el intervalo ( a , b ), donde a = min( M (0), M (∞)), y b = max( M (0 ), M (∞)); si b = ∞ establezca b = ub , donde ub es un límite superior de los valores de las raíces positivas de p ( x ). ^{[12] [13]}
• Si hay dos o más variaciones de signos, la regla de los signos de Descartes implica que puede haber cero, una o más raíces reales dentro del intervalo (0, ∞); en este caso, considere por separado las raíces de p ( x ) que se encuentran dentro del intervalo (0, 1) de las que están dentro del intervalo (1, ∞). Se debe realizar una prueba especial para 1.
  • Para garantizar que haya raíces dentro del intervalo (0, 1) se utiliza el límite inferior ideal, lb ; es decir, la parte entera de la raíz positiva más pequeña se calcula con la ayuda del límite inferior, ^{[12] [13]} , sobre los valores de las raíces positivas de p ( x ). Si , la sustitución se realiza para p ( x ) y M ( x ), mientras que si se usan sustituciones x ← x +1 para encontrar la parte entera de las raíces. ${\displaystyle lb_{computed}}$ ${\displaystyle lb_{computed}>1}$ ${\displaystyle x\leftarrow x+lb_{computed}}$ ${\displaystyle lb_{computed}\leq 1}$
  • Para calcular las raíces dentro del intervalo (0, 1), realice la sustitución de p ( x ) y M ( x ) y procese el par ${\displaystyle x\leftarrow {\frac {1}{1+x}}}$

${\displaystyle \left\{(1+x)^{\deg(p)}p\left({\tfrac {1}{1+x}}\right),M({\tfrac {1}{1+x}})\right\},}$

mientras que para calcular las raíces en el intervalo (1, ∞) realice la sustitución x ← x + 1 en p ( x ) y M ( x ) y procese el par { p (1 + x ), M (1 + x )} . Bien puede resultar que 1 sea una raíz de p ( x ), en cuyo caso, M (1) es una raíz del polinomio original y el intervalo de aislamiento se reduce a un punto.

A continuación se muestra una presentación recursiva de VAS( p , M ).

EVA ( p , M ):

Entrada : un polinomio univariado, sin cuadrados , de grado grados ( p ) y la transformación de Möbius ${\displaystyle p(x)\in \mathbb {Z} [x],p(0)\neq 0}$

${\displaystyle M(x)={\frac {ax+b}{cx+d}}=x,\qquad a,b,c,d\in \mathbb {N} .}$

Salida : una lista de intervalos de aislamiento de las raíces positivas de p ( x ).

1 var ← el número de variaciones de signos de p ( x ) // regla de signos de Descartes ;2 si  var = 0 entonces RETORNO ∅;3 si  var = 1 entonces RETORNO {( a , b )} // a = min( M (0), M (∞)), b = max( M (0), M (∞)), pero si b = ∞ establecer b = ub , donde ub es un límite superior de los valores de las raíces positivas de p ( x );4 lb ← el límite inferior ideal de las raíces positivas de p ( x );5 si  lb ≥ 1 entonces  p ← p ( x + lb ), M ← M ( x + lb );6 p 01 ← ( x + 1 ) grado( p )  p (1/x + 1), M 01 ← M (1/x + 1) // Busca raíces reales en (0, 1);7 m ← M (1) // ¿Es 1 una raíz?8 p 1∞ ← p ( x + 1), M 1∞ ← M ( x + 1) // Busca raíces reales en (1, ∞);9 si  p (1) ≠ 0 entonces
10 RETORNO VAS( p 01 , M 01 ) ∪ VAS( p 1∞ , M 1∞ )11 else
12 REGRESO VAS( p 01 , M 01 ) ∪ {[ m , m ]} ∪ VAS( p 1∞ , M 1∞ )13 fin

Observaciones

• Por simplicidad, no se incluye la contribución de Strzeboński.
• En el algoritmo anterior con cada polinomio hay asociada una transformación de Möbius M ( x ).
• En la línea 1 se aplica la regla de los signos de Descartes .
• Si se eliminan las líneas 4 y 5 de VAS( p , M ), el algoritmo resultante es el exponencial de Vincent.
• Cualquier sustitución realizada en el polinomio p ( x ) también se realiza en la transformación de Möbius asociada M ( x ) (líneas 5, 6 y 8).
• Los intervalos de aislamiento se calculan a partir de la transformación de Möbius en la línea 3, excepto las raíces enteras calculadas en la línea 7 (también 12).

Ejemplo de VAS( p , M )

Aplicamos el método VAS a p ( x ) = x ³ − 7 x + 7 (tenga en cuenta que: M ( x ) = x ).

Iteración 1

EVA( x 3 − 7 x + 7, x )1 var ← 2 // el número de variaciones de signo en la secuencia de coeficientes de p ( x ) = x 3 − 7 x + 74 lb ← 1 // el límite inferior ideal: encontrado usando lb calculado y sustituciones x ← x + 15 p ← x 3 + 3 x 2 − 4 x + 1, M ← x + 16 p 01 ← x 3 − x 2 − 2 x + 1, METRO 01 ←x + 2/x + 17 metros ← 18 p 1∞ ← x 3 + 6 x 2 + 5 x + 1, M 1∞ ← x + 210 VAS DE RETORNO ( x 3 − x 2 − 2 x + 1,x + 2/x + 1) ∪ EVA( x 3 + 6 x 2 + 5 x + 1, x + 2)

Lista de intervalos de aislamiento: { }.

Lista de pares { p , M } a procesar:

${\displaystyle \left\{\left\{x^{3}-x^{2}-2x+1,{\tfrac {x+2}{x+1}}\right\},\{x^{3}+6x^{2}+5x+1,x+2\}\right\}.}$

Retire el primero y procese.

Iteración 2

EVA( x 3 − x 2 − 2 x + 1,x + 2/x + 1)1 var ← 2 // el número de variaciones de signo en la secuencia de coeficientes de p ( x ) = x 3 − x 2 − 2 x + 14 lb ← 0 // el límite inferior ideal: encontrado usando lb calculado y sustitución(es) x ← x + 16 pags 01 ← x 3 + x 2 − 2 x − 1, METRO 01 ←2 x + 3/x + 17 metros ←3/28 p 1∞ ← x 3 + 2 x 2 − x − 1, M 1∞ ←x + 3/x + 210 VAS DE RETORNO ( x 3 + x 2 − 2 x − 1,2 x + 3/x + 2) ∪ VAS( x 3 + 2 x 2 − x − 1,x + 3/x + 2)

Lista de intervalos de aislamiento: { }.

Lista de pares { p , M } a procesar:

${\displaystyle \left\{\left\{x^{3}+x^{2}-2x-1,{\tfrac {2x+3}{x+2}}\right\},\left\{x^{3}+2x^{2}-x-1,{\tfrac {x+3}{x+2}}\right\},\{x^{3}+6x^{2}+5x+1,x+2\}\right\}.}$

Retire el primero y procese.

Iteración 3

EVA( x 3 + x 2 − 2 x − 1,2 x + 3/x + 2)1 var ← 1 // el número de variaciones de signo en la secuencia de coeficientes de p ( x ) = x 3 + x 2 − 2 x − 13 VOLVER {(3/2, 2)}

Lista de intervalos de aislamiento: {(3/2, 2)}.

Lista de pares { p , M } a procesar:

${\displaystyle \left\{\left\{x^{3}+2x^{2}-x-1,{\tfrac {x+3}{x+2}}\right\},\{x^{3}+6x^{2}+5x+1,x+2\}\right\}.}$

Retire el primero y procese.

Iteración 4

EVA( x 3 + 2 x 2 − x − 1,x + 3/x + 2)1 var ← 1 // el número de variaciones de signo en la secuencia de coeficientes de p ( x ) = x 3 + 2 x 2 − x − 13 VOLVER {(1,3/2)}

Lista de intervalos de aislamiento: {(1,3/2), (3/2, 2)}.

Lista de pares { p , M } a procesar:

${\displaystyle \left\{\left\{x^{3}+6x^{2}+5x+1,x+2\right\}\right\}.}$

Retire el primero y procese.

Iteración 5

EVA( x 3 + 6 x 2 + 5 x + 1, x + 2)1 var ← 0 // el número de variaciones de signo en la secuencia de coeficientes de p ( x ) = x 3 + 6 x 2 + 5 x + 12 RETORNO ∅

Lista de intervalos de aislamiento: {(1,3/2), (3/2, 2)}.

Lista de pares { p , M } a procesar: ∅ .

Finalizado.

Conclusión

Por lo tanto, las dos raíces positivas del polinomio p ( x ) = x ³ − 7 x + 7 se encuentran dentro de los intervalos de aislamiento (1,3/2) y (3/2, 2) }. Cada raíz se puede aproximar (por ejemplo) dividiendo en dos el intervalo de aislamiento en el que se encuentra hasta que la diferencia de los puntos finales sea menor que 10 ⁻⁶ ; Siguiendo este enfoque, las raíces resultan ser ρ ₁ = 1,3569 y ρ ₂ = 1,69202 .

Métodos de bisección

Existen varios métodos de bisección derivados del teorema de Vincent; Todos ellos se presentan y comparan en otros lugares. ^[19] Aquí se describen los dos más importantes, a saber, el método Vincent-Collins-Akritas (VCA) y el método Vincent-Alesina-Galuzzi (VAG).

El método Vincent-Alesina-Galuzzi (VAG) es el más simple de todos los métodos derivados del teorema de Vincent, pero tiene la prueba que requiere más tiempo (en la línea 1) para determinar si un polinomio tiene raíces en el intervalo de interés; esto lo convierte en el más lento de los métodos presentados en este artículo.

Por el contrario, el método Vincent-Collins-Akritas (VCA) es más complejo pero utiliza una prueba más sencilla (en la línea 1) que el VAG. Esto, junto con ciertas mejoras ^[16], ha convertido al VCA en el método de bisección más rápido.

Vicente – Collins – Akritas (VCA, 1976)

Este fue el primer método desarrollado para superar la naturaleza exponencial del enfoque original de Vincent y ha tenido una historia bastante interesante en lo que respecta a su nombre. Este método, que aísla las raíces reales, utilizando la regla de los signos de Descartes y el teorema de Vincent, sus inventores Collins y Akritas lo habían denominado originalmente algoritmo de Uspensky modificado . ^[11] Después de pasar por nombres como "método Collins-Akritas" y "método de Descartes" (demasiado confuso si se considera el artículo de Fourier ^[20] ), finalmente fue François Boulier, de la Universidad de Lille, quien le dio el nombre de Vincent– Método Collins-Akritas (VCA), ^[14] pág. 24, basándose en que “el método de Uspensky” no existe ^[21] y tampoco el “método de Descartes”. ^[22] La mejor implementación de este método se debe a Rouillier y Zimmerman, ^[16] y hasta la fecha, es el método de bisección más rápido. Tiene la misma complejidad en el peor de los casos que el algoritmo de Sturm, pero casi siempre es mucho más rápido. Se ha implementado en el paquete RootFinding de Maple .

Así es como funciona VCA( p , ( a , b )):

• Dado un polinomio p _orig ( x ) de grado deg( p ), tal que p _orig (0) ≠ 0, cuyas raíces positivas deben aislarse, primero calcule un límite superior, ^{[12] [13]} ub sobre los valores de estos raíces positivas y establecer p ( x ) = p _orig ( ub * x ) y ( a , b ) = (0, ub ). Todas las raíces positivas de p ( x ) se encuentran en el intervalo (0, 1) y hay una biyección entre ellas y las raíces de p _orig ( x ), que se encuentran todas en el intervalo ( a , b ) = (0, ub ) (ver la figura correspondiente); esta biyección se expresa por α _{( a , b )} = a + α _(0,1) ( b − a ). Asimismo, existe una biyección entre los intervalos (0, 1) y (0, ub ).

Biyección entre las raíces de p _orig ( x ) y p ( x ).

• Repita los siguientes pasos mientras haya pares { p ( x ), ( a , b )} para procesar.
• Utilice la " prueba de raíces 0_1 " de Budan en p ( x ) para calcular (usando el número var de variaciones de signo en la secuencia de sus coeficientes) el número de sus raíces dentro del intervalo (0, 1). Si no hay raíces, devuelva el conjunto vacío, ∅ y si hay una raíz, devuelva el intervalo ( a , b ).
• Si hay dos o más variaciones de signos, la " prueba de raíces 0_1 " de Budan implica que puede haber cero, una, dos o más raíces reales dentro del intervalo (0, 1). En este caso córtelo por la mitad y considere por separado las raíces de p ( x ) dentro del intervalo (0,1/2)—y que corresponden a las raíces de p _orig ( x ) dentro del intervalo ( a ,1/2( a + b )) de aquellos dentro del intervalo (1/2, 1) y corresponden a las raíces de p _orig ( x ) dentro del intervalo (1/2( a + b ), b ); es decir, procesar, respectivamente, los pares

${\displaystyle \left\{2^{\deg(p)}p({\tfrac {x}{2}}),(a,{\tfrac {1}{2}}(a+b))\right\},\quad \left\{2^{\deg(p)}p({\tfrac {1}{2}}(x+1)),({\tfrac {1}{2}}(a+b),b)\right\}}$

(ver la figura correspondiente). Bien puede resultar que1/2es una raíz de p ( x ), en cuyo caso1/2( a + b ) es una raíz de p _orig ( x ) y el intervalo de aislamiento se reduce a un punto.

Biyecciones entre las raíces de p ( x ) y las de p (X/2) y P (x + 1/2).

A continuación se muestra una presentación recursiva del algoritmo original VCA( p , ( a , b )).

AVC ( p , ( a , b ))

Entrada : Un polinomio univariante, libre de cuadrados p ( ub * x ) ∈ Z [ x ], p (0) ≠ 0 de grado deg( p ), y el intervalo abierto ( a , b ) = (0, ub ), donde ub es un límite superior de los valores de las raíces positivas de p ( x ). (Las raíces positivas de p ( ub * x ) están todas en el intervalo abierto (0, 1)).
Salida : una lista de intervalos de aislamiento de las raíces positivas de p ( x )

1 var ← el número de variaciones de signo de ( x + 1 ) grados ( p ) p (1/x + 1) // " Prueba de raíces 0_1 " de Budan ;2 si  var = 0 entonces RETORNO ∅;3 si  var = 1 entonces RETORNO {( a , b )};4 p 01/2← 2 grados( p ) p (X/2) // Busca raíces reales en (0,1/2);5 metros ←1/2( a + b ) // es1/2¿una raíz?6p​1/21 ← 2 grados( p ) p (x + 1/2) // Busca raíces reales en (1/2, 1);7 si  p (1/2) ≠ 0 luego
8 RETORNO VCA ( p 01/2, ( a , m )) ∪ VCA ( p1/21 , ( metro , segundo ))9 más
10 DEVOLVER VCA ( p 01/2, ( a , m )) ∪ {[ m , m ]} ∪ VCA ( p1/21 , ( metro , segundo ))11 fin

Observación

• En el algoritmo anterior, cada polinomio tiene asociado un intervalo ( a , b ). Como se muestra en otra parte, ^[22] p. 11, también se puede asociar una transformación de Möbius con cada polinomio, en cuyo caso VCA se parece más a VAS.
• En la línea 1 se aplica la " prueba de raíces 0_1 " de Budan.

Ejemplo de VCA( p , ( a , b ))

Dado el polinomio p _orig ( x ) = x ³ − 7 x + 7 y considerando como cota superior ^{[12] [13]} sobre los valores de las raíces positivas ub = 4 los argumentos del método VCA son: p ( x ) = 64 x ³ − 28 x + 7 y ( a , b ) = (0, 4) .

Iteración 1

1 var ← 2 // el número de variaciones de signo en la secuencia de coeficientes de ( x + 1) 3 p (1/x + 1) = 7 x 3 − 7 x 2 − 35 x + 434 p 01/2← 64 x 3 − 112 x + 565 metros ← 26p​1/21 ← 64 x 3 + 192 x 2 + 80 x + 87 p (1/2) = 18 RETORNO VCA(64 x 3 − 112 x + 56, (0, 2)) ∪ VCA(64 x 3 + 192 x 2 + 80 x + 8, (2, 4))

Lista de intervalos de aislamiento: { }.

Lista de pares { p , I } a procesar:

${\displaystyle \left\{\left\{64x^{3}-112x+56,(0,2)\right\},\left\{64x^{3}+192x^{2}+80x+8,(2,4)\right\}\right\}.}$

Retire el primero y procese.

Iteración 2

VCA(64 x 3 − 112 x + 56, (0, 2))1 var ← 2 // el número de variaciones de signo en la secuencia de coeficientes de ( x + 1) 3 p (1/x + 1) = 56 x 3 + 56 x 2 - 56 x + 84 p 01/2← 64 x 3 − 448 x + 4485 metros ← 16p​1/21 ← 64 x 3 + 192 x 2 − 256 x + 647 p (1/2) = 88 RETORNO VCA(64 x 3 − 448 x + 448, (0, 1)) ∪ VCA(64 x 3 + 192 x 2 − 256 x + 64, (1, 2))

Lista de intervalos de aislamiento: { }.

Lista de pares { p , I } a procesar:

${\displaystyle \left\{\left\{64x^{3}-448x+448,(0,1)\right\},\left\{64x^{3}+192x^{2}-256x+64,(1,2)\right\},\left\{64x^{3}+192x^{2}+80x+8,(2,4)\right\}\right\}.}$

Retire el primero y procese.

Iteración 3

VCA(64 x 3 − 448 x + 448, (0, 1))1 var ← 0 // el número de variaciones de signo en la secuencia de coeficientes de ( x + 1) 3 p (1/x + 1) = 448 x 3 + 896 x 2 + 448 x + 642 RETORNO ∅

Lista de intervalos de aislamiento: { }.

Lista de pares { p , I } a procesar:

${\displaystyle \left\{\left\{64x^{3}+192x^{2}-256x+64,(1,2)\right\},\left\{64x^{3}+192x^{2}+80x+8,(2,4)\right\}\right\}.}$

Retire el primero y procese.

Iteración 4

VCA(64 x 3 + 192 x 2 − 256 x + 64, (1, 2))1 var ← 2 // el número de variaciones de signo en la secuencia de coeficientes de ( x + 1) 3 p (1/x + 1) = 64 x 3 − 64 x 2 − 128 x + 644 p 01/2← 64x3 + 384x2 − 1024x + 512​5 metros ←3/26p​1/21 ← 64 x 3 + 576 x 2 − 64 x + 647 p (1/2) = −88 RETORNO VCA(64 x 3 + 384 x 2 − 1024 x + 512, (1,3/2)) ∪ VCA(64 x 3 + 576 x 2 − 64 x − 64, (3/2, 2))

Lista de intervalos de aislamiento: { }.

Lista de pares { p , I } a procesar:

${\displaystyle \left\{\left\{64x^{3}+384x^{2}-1024x+512,\left(1,{\tfrac {3}{2}}\right)\right\},\left\{64x^{3}+576x^{2}-64x-64,\left({\tfrac {3}{2}},2\right)\right\},\left\{64x^{3}+192x^{2}+80x+8,(2,4)\right\}\right\}.}$

Retire el primero y procese.

Iteración 5

VCA(64 x 3 + 384 x 2 − 1024 x + 512, (1,3/2))1 var ← 1 // el número de variaciones de signo en la secuencia de coeficientes de ( x + 1) 3 p (1/x + 1) = 512 x 3 + 512 x 2 − 128 x − 643 VOLVER {(1,3/2)}

Lista de intervalos de aislamiento: {(1,3/2)}.

Lista de pares { p , I } a procesar:

${\displaystyle \left\{\left\{64x^{3}+576x^{2}-64x-64,\left({\tfrac {3}{2}},2\right)\right\},\left\{64x^{3}+192x^{2}+80x+8,(2,4)\right\}\right\}.}$

Retire el primero y procese.

Iteración 6

VCA(64 x ³ + 576 x ² − 64 x − 64, (3/2, 2))

1 var ← 1 // el número de variaciones de signo en la secuencia de coeficientes de ( x + 1) 3 p (1/x + 1) = −64 x 3 − 256 x 2 + 256 x + 5123 VOLVER {(3/2, 2)}

Lista de intervalos de aislamiento: {(1,3/2), (3/2, 2)}.

Lista de pares { p , I } a procesar:

${\displaystyle \left\{\left\{64x^{3}+192x^{2}+80x+8,(2,4)\right\}\right\}.}$

Retire el primero y procese.

Iteración 7

VCA(64 x 3 + 192 x 2 + 80 x + 8, (2, 4))1 var ← 0 // el número de variaciones de signo en la secuencia de coeficientes de ( x + 1) 3 p (1/x + 1) = 8 x 3 + 104 x 2 + 376 x + 3442 RETORNO ∅

Lista de intervalos de aislamiento: {(1,3/2), (3/2, 2)}.

Lista de pares { p , I } a procesar: ∅ .

Finalizado.

Conclusión

Por lo tanto, las dos raíces positivas del polinomio p ( x ) = x ³ − 7 x + 7 se encuentran dentro de los intervalos de aislamiento (1,3/2) y (3/2, 2) }. Cada raíz se puede aproximar (por ejemplo) dividiendo en dos el intervalo de aislamiento en el que se encuentra hasta que la diferencia de los puntos finales sea menor que 10 ⁻⁶ ; Siguiendo este enfoque, las raíces resultan ser ρ ₁ = 1,3569 y ρ ₂ = 1,69202 .

Vicente–Alesina–Galuzzi (VAG, 2000)

Este fue desarrollado en último lugar y es el método de aislamiento de raíces reales más simple derivado del teorema de Vincent.

Así es como funciona VAG( p , ( a , b )):

• Dado un polinomio p ( x ) de grado deg( p ), tal que p (0) ≠ 0, cuyas raíces positivas deben aislarse, primero calcule un límite superior, ^{[12] [13]} ub sobre los valores de estas raíces positivas y establezca ( a , b ) = (0, ub ). Todas las raíces positivas de p ( x ) se encuentran en el intervalo ( a , b ).
• Repita los siguientes pasos mientras haya intervalos ( a , b ) para procesar; en este caso el polinomio p ( x ) permanece igual.
• Utilice la "prueba de raíces a_b" de Alesina-Galuzzi en p ( x ) para calcular (usando el número var de variaciones de signo en la secuencia de sus coeficientes) el número de sus raíces dentro del intervalo ( a , b ). Si no hay raíces, devuelva el conjunto vacío, ∅ y si hay una raíz, devuelva el intervalo ( a , b ).
• Si hay dos o más variaciones de signos, la "prueba de raíces a_b" de Alesina-Galuzzi implica que puede haber cero, una, dos o más raíces reales dentro del intervalo ( a , b ). En este caso córtelo por la mitad y considere por separado las raíces de p ( x ) dentro del intervalo ( a ,1/2( a + b )) de aquellos dentro del intervalo (1/2( a + b ), b ); es decir, procesar, respectivamente, los intervalos ( a ,1/2( a + b )) y (1/2( a + b ), b ). Bien puede resultar que1/2( a + b ) es una raíz de p ( x ), en cuyo caso el intervalo de aislamiento se reduce a un punto.

A continuación se muestra una presentación recursiva de VAG( p , ( a , b )).

VAG ( p , ( a , b ))
Entrada : Un polinomio univariado sin cuadrados p ( x ) ∈ Z [ x ], p (0) ≠ 0 de grado deg( p ) y el intervalo abierto ( a , b ) = (0, ub ), donde ub es un límite superior de los valores de las raíces positivas de p ( x ).
Salida : una lista de intervalos de aislamiento de las raíces positivas de p ( x ).

1 var ← el número de variaciones de signo de ( x + 1 ) grados ( p )  p (a + bx/1+ x) // La "prueba de raíces a_b" de Alesina-Galuzzi;2 si  var = 0 entonces RETORNO ∅;3 si  var = 1 entonces RETORNO {( a , b )};4 metros ←1/2( a + b ) // Subdivide el intervalo ( a , b ) en dos partes iguales;5 si  p ( m ) ≠ 0 entonces
6 REGRESAR VAG( p , ( a , m )) ∪ VAG( p , ( m , b ))7 más
8 REGRESAR VAG( p , ( a , m )) ∪ {[ m , m ]} ∪ VAG( p , ( m , b ))9 final

Observaciones

• Comparado con VCA, el algoritmo anterior es extremadamente simple; por el contrario, VAG utiliza la "prueba de raíces a_b" que consume mucho tiempo y eso la hace mucho más lenta que VCA. ^[19]
• Como señalan Alesina y Galuzzi, ^[5] p. 189, existe una variante de este algoritmo debida a Donato Saeli. Saeli sugirió que se utilice el mediante de los puntos finales en lugar de su punto medio.1/2( a + b ) . Sin embargo, se ha demostrado ^[19] que el uso del mediante de los puntos finales es en general mucho más lento que la versión de "punto medio".

Ejemplo de VAG( p , ( a , b ))

Dado el polinomio p ( x ) = x ³ − 7 x + 7 y considerando como cota superior ^{[12] [13]} sobre los valores de las raíces positivas ub = 4 los argumentos de VAG son: p ( x ) = x ³ − 7 x + 7 y ( a , b ) = (0, 4).

Iteración 1

1 var ← 2 // el número de variaciones de signo en la secuencia de coeficientes de ( x + 1) 3 p (4x​/x + 1) = 43 x 3 − 35 x 2 − 7 x + 74 metros ←1/2(0 + 4) = 25 pags ( m ) = 18 VOLVER VAG( x 3 − 7 x + 7, (0, 2)) ∪ VAG( x 3 − 7 x + 7, (2, 4)

Lista de intervalos de aislamiento: {}.

Lista de intervalos a procesar: {(0, 2), (2, 4)}.

Retire el primero y procese.

Iteración 2

VAG( x 3 − 7 x + 7, (0, 2))1 var ← 2 // el número de variaciones de signo en la secuencia de coeficientes de ( x + 1) 3 p (2x​/x + 1) = x 3 − 7 x 2 + 7 x + 74 metros ←1/2(0 + 2) = 15 pags ( m ) = 18 VOLVER VAG( x 3 − 7 x + 7, (0, 1)) ∪ VAG( x 3 − 7 x + 7, (1, 2)

Lista de intervalos de aislamiento: {}.

Lista de intervalos a procesar: {(0, 1), (1, 2), (2, 4)}.

Retire el primero y procese.

Iteración 3

VAG( x 3 − 7 x + 7, (0, 1))1 var ← 0 // el número de variaciones de signo en la secuencia de coeficientes de ( x + 1) 3 p (X/x + 1) = x 3 + 7 x 2 + 14 x + 72 RETORNO ∅

Lista de intervalos de aislamiento: {}.

Lista de intervalos a procesar: {(1, 2), (2, 4)}.

Retire el primero y procese.

Iteración 4

VAG( x 3 − 7 x + 7, (1, 2))1 var ← 2 // el número de variaciones de signo en la secuencia de coeficientes de ( x + 1) 3 p (2x + 1/x + 1) = x 3 - 2 x 2 - x + 14 metros ←1/2(1 + 2) =3/25 pags ( metro ) = -1/88 RETORNO VAG( x 3 − 7 x + 7, (1,3/2)) ∪ VAG( x 3 − 7 x + 7, (3/2, 2))

Lista de intervalos de aislamiento: {}.

Lista de intervalos a procesar: {(1,3/2), (3/2, 2), (2, 4)}.

Retire el primero y procese.

Iteración 5

VAG( x 3 − 7 x + 7, (1,3/2))1 var ← 1 // el número de variaciones de signo en la secuencia de coeficientes de 2 3 ( x + 1) 3 p (3/2x + 1/x + 1) = x 3 + 2 x 2 - 8 x - 83 RETORNO (1,3/2)

Lista de intervalos de aislamiento: {(1,3/2)}.

Lista de intervalos a procesar: {(3/2, 2), (2, 4)}.

Retire el primero y procese.

Iteración 6

VAG( x 3 − 7 x + 7, (3/2, 2))1 var ← 1 // el número de variaciones de signo en la secuencia de coeficientes de 2 3 ( x + 1) 3 p (2 veces +3/2/x + 1) = 8 x 3 + 4 x 2 - 4 x - 13 VOLVER (3/2, 2)

Lista de intervalos de aislamiento: {(1,3/2), (3/2, 2)}.

Lista de intervalos a procesar: {(2, 4)}.

Retire el primero y procese.

Iteración 7

VAG( x 3 − 7 x + 7, (2, 4))1 var ← 0 // el número de variaciones de signo en la secuencia de coeficientes de ( x + 1) 3 p (4 x + 2/x + 1) = 344x3 + 376x2 + 104x + 82 RETORNO ∅

Lista de intervalos de aislamiento: {(1,3/2), (3/2, 2)}.

Lista de intervalos a procesar: ∅.

Finalizado.

Conclusión

Por lo tanto, las dos raíces positivas del polinomio p ( x ) = x ³ − 7 x + 7 se encuentran dentro de los intervalos de aislamiento (1,3/2) y (3/2, 2) }. Cada raíz se puede aproximar (por ejemplo) dividiendo en dos el intervalo de aislamiento en el que se encuentra hasta que la diferencia de los puntos finales sea menor que 10 ⁻⁶ ; Siguiendo este enfoque, las raíces resultan ser ρ ₁ = 1,3569 y ρ ₂ = 1,69202 .

Ver también

• Propiedades de las raíces polinómicas
• Algoritmo de búsqueda de raíces
• Las fórmulas de Vieta
• El método de Newton

Referencias

1. 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 : 1–34.
2. 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.
3. 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 28 de abril de 2012 .
4. 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 7 de mayo de 2012 .
5. Alesina, Alberto; Massimo Galuzzi (2000). "El teorema de Vincent desde un punto de vista moderno" (PDF) . Estudios categóricos en Italia 2000, Rediconti del Circolo Matematico di Palermo, Serie II, N. 64 : 179–191.
6. 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.
7. Obreschkoff, Nikola (1963). Verteilung und Berechnung der Nullstellen reeller Polynome . Berlín: VEB Deutscher Verlag der Wissenschaften .
8. Uspensky, James Victor (1948). Teoría de ecuaciones. Nueva York: McGraw-Hill Book Company.
9. Akritas, Alkiviadis G.; AW Strzeboński; PS Vigklas (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.
10. Serret, José A. (1877). Cours d'algèbre supérieure. Tomo I. Gauthier-Villars.
11. Collins, George E.; Alkiviadis G. Akritas (1976). "Aislamiento de raíz real polinómica mediante la regla de los signos de Descarte". 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. ISBN 9781450377904. S2CID  17003369.
12. Vigklas, Panagiotis, S. (2010). Límites superiores de los valores de las raíces positivas de polinomios (PDF) . Tesis doctoral, Universidad de Tesalia, Grecia.{{cite book}}: CS1 maint: multiple names: authors list (link)
13. Akritas, Alkiviadis, G. (2009). "Límites de complejidad lineal y cuadrática de los valores de las raíces positivas de polinomios". Revista de Informática Universal . 15 (3): 523–537.{{cite journal}}: CS1 maint: multiple names: authors list (link)
14. Boulier, François (2010). Sistemas polinomiales: ¿qué significa "résoudre"? (PDF) . Université Lille 1. Archivado desde el original (PDF) el 24 de diciembre de 2013 . Consultado el 3 de mayo de 2012 .
15. Akritas, Alkiviadis G.; Adam W. Strzeboński (2005). "Un estudio comparativo de dos métodos reales de aislamiento de raíces" (PDF) . Análisis no lineal: modelado y control . 10 (4): 297–304. doi :10.15388/NA.2005.10.4.15110.
16. Rouillier, F .; P. Zimmerman (2004). "Aislamiento eficiente de raíces reales de polinomios". Revista de Matemática Computacional y Aplicada . 162 : 33–50. doi : 10.1016/j.cam.2003.08.015 .
17. Tsigaridas, Elías P.; Emiris, Ioannis Z. (2006). "Aislamiento de raíz real de polinomio univariado: revisión de fracciones continuas". 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.
18. Sharma, Vikram (2007). Análisis de complejidad de algoritmos en computación algebraica (PDF) . Doctor. Tesis, Instituto Courant de Ciencias Matemáticas, Universidad de Nueva York, EE.UU.
19. Akritas, Alkiviadis G.; Adam W. Strzeboński; Panagiotis S. Vigklas (2008). "Sobre los diversos métodos de bisección derivados del teorema de Vincent". Revista Serdica de Computación . 2 (1): 89–104. doi :10.55630/sjc.2008.2.89-104. hdl : 10525/376 . S2CID  126142131. Archivado desde el original el 10 de abril de 2016 . Consultado el 9 de mayo de 2012 .
20. Fourier, Jean Baptiste José (1820). "Sur l'usage du théorème de Descartes dans la recherche des limites des racines". Bulletin des Sciences, par la Société Philomatique de Paris : 156–165.
21. Akritas, Alkiviadis G. (1986). "No existe ningún "método de Uspensky".". No existe un "método de Uspensky". En: Actas del quinto Simposio ACM sobre Computación Simbólica y Algebraica (SYMSAC '86, Waterloo, Ontario, Canadá), págs. 88–90. págs. 88–90. doi :10.1145/ 32439.32457 . 0897911997. S2CID  15446040.
22. Akritas, Alkiviadis G. (2008). No existe un "método de Descartes". En: MJWester y M. Beaudin (Eds), Álgebra informática en la educación, AullonaPress, EE.UU., págs. 19–35. ISBN 9780975454190.

enlaces externos

• Berkakis, Antonis: RealRoots, una aplicación gratuita para dispositivos Android para comparar el método de Sturm y VAS
• https://play.google.com/store/apps/details?id=org.kde.necessitas.berkakis.realroots