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 la 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 sucesión finita o infinita de números reales. Supóngase que l < r y se cumplen las siguientes condiciones:

1. Si r = l +1 los números c _l y c _r tienen signos opuestos.
2. Si r ≥ l +2 los números c _{l +1} , ..., c _{r −1} son todos cero y los números c _l y c _r tienen signos opuestos.

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

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 para fracciones continuas (1834 y 1836)

Si en una ecuación polinómica con coeficientes racionales y sin raíces múltiples, se hacen transformaciones sucesivas 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 cualesquiera mayores o iguales a uno, entonces después de una serie de transformaciones de este tipo, la ecuación transformada resultante tiene cero variaciones de signo o tiene una sola variación de signo. En el primer caso no hay raíz, mientras que en el segundo caso hay una sola 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 (infinita) correspondiente. ${\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 quitar el denominador), entonces existe N tal que para todo o bien no tiene variación de signo o tiene una variación de signo. En el último caso tiene una única raíz real positiva para todo . ${\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 , solo 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 deg( p ) que sólo tiene raíces simples. Es posible determinar una cantidad positiva δ tal 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 solo si p ( x ) tiene una sola 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 deg( p ), está acotado por encima por el número de variaciones de signo 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 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 .

Boceto de una prueba

Una discusión detallada del teorema de Vincent, su extensión, la interpretación geométrica de las transformaciones involucradas y tres pruebas diferentes se puede encontrar en el trabajo de Alesina y Galuzzi. ^{[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 demostrar (ambas versiones del) teorema de Vincent, Alesina y Galuzzi demuestran que, después de una serie de transformaciones mencionadas en el teorema, un polinomio con una raíz positiva acaba teniendo una variación de signo. Para demostrarlo, 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; véase 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; supongamos que a/do⁠ < ⁠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 finalesa/do⁠ y ⁠b/d⁠ , se representa 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/do⁠ . Los puntos exteriores se asignan al semiplano con Re( x ) < 0 .

• Los dos círculos (solo son visibles sus crecientes azules) con el 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 representan 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 asigna al punto

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

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

De lo anterior se desprende que si un polinomio tiene una sola 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 con precisión cómo utilizar 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 una raíz por parte de Vincent (aplicando el teorema de Budan)

La naturaleza exponencial del algoritmo de Vincent se debe a la forma en que se calculan los cocientes parciales a _i (en el teorema de Vincent). Es decir, para calcular cada cociente parcial a _i (es decir, para localizar dónde se encuentran las raíces en el eje x ), Vincent utiliza el teorema de Budan como una "prueba de ausencia de 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 solo cuando los polinomios p ( x ) y p ( x +1) difieren en el número de variaciones de signo en la secuencia de sus coeficientes (es decir, cuando el número de variaciones de signo de p ( x +1) disminuye).

Véase 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í la naturaleza 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 ello fue la aparición del teorema de Sturm en 1827, que resolvió el problema de aislamiento de raíces reales en tiempo polinomial , definiendo el número preciso de raíces reales que tiene un polinomio en un intervalo abierto real ( a , b ). El método resultante (el de Sturm) para calcular las raíces reales de los 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, siendo el más rápido el método Vincent–Akritas–Strzeboński (VAS). ^[9]

Serret incluyó en su Álgebra, ^[10] pp 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 tesis doctoral "El teorema de Vincent en la 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 encomiables esfuerzos (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 algún grado de precisión; además, el enfoque está en las raíces positivas , porque para aislar las raíces negativas del polinomio p ( x ) se reemplaza x por − x ( x ← − x ) y se 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 deg( p ). Para ver esto, represente mediante 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 una variación de signo en la secuencia de sus coeficientes. Entonces, la raíz positiva única de f ( x ) (en el intervalo (0, ∞)) corresponde a aquella raíz positiva de p ( x ) que está en el intervalo abierto con extremos y . Estos extremos 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 hay que hacer es calcular, para cada raíz, las variables a , b , c , d de la transformación de Möbius correspondiente

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

que conduce a un polinomio transformado como en la ecuación ( 2 ), con una variación de 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 signo en la secuencia de sus coeficientes, se puede calcular:

• ya sea por fracciones continuas , lo que conduce al método de fracciones continuas de Vincent–Akritas–Strzebonski (VAS) , ^[9]
• o por bisección , lo que conduce (entre otros) al método de bisección de 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 descritos 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 , sobre los valores de las raíces positivas del polinomio en 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 (superiores e inferiores) para los valores de las raíces positivas de los polinomios basándose en trabajos previos de Doru Stefanescu. Se describen en la tesis doctoral de PS Vigklas ^[12] y en otros lugares. ^[13] Estos límites ya se han implementado en los sistemas de álgebra computacional Mathematica , SageMath , SymPy , Xcas , etc.

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

Método de fracciones continuas

Del teorema de Vincent se deriva un único método de fracciones continuas . Como se ha indicado anteriormente, comenzó en la década de 1830, cuando Vincent presentó en los artículos ^{[1] [2] [3]} varios ejemplos que mostraban cómo utilizar 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 ofrece una explicación de cómo evolucionó este método.

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

Este es el segundo método (después de 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. Vincent lo presentó originalmente entre 1834 y 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 tesis doctoral de 1978 ( 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 inferior positivo ideal de la raíz que calcula la parte entera de la raíz positiva más pequeña (véase la figura correspondiente). Es decir, ahora establezca a _i ← lb o, equivalentemente, realice la sustitución x ← x + lb , que lleva aproximadamente el mismo tiempo que la sustitución x ← x + 1.

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

Finalmente, dado que no existe la cota de raíz inferior positiva ideal, 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] un hecho que se confirmó ^[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 polinomial en el tiempo.

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

Para comparar 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 poly, realroot utiliza el método VAS; para utilizar el método de Sturm, escriba realroot(sturm, poly). Consulte también los enlaces externos para obtener una aplicación de A. Berkakis para dispositivos Android que hace lo mismo.

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

• Sea p ( x ) un polinomio de grado deg( p ) tal que p (0) ≠ 0. Para aislar sus raíces positivas, asocie a p ( x ) la transformación de Möbius M ( x ) = x y repita los siguientes pasos mientras haya pares { p ( x ), M ( x )} a 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 signo en la secuencia de sus coeficientes) el número de sus raíces dentro del intervalo (0, ∞). Si no hay raíces retorna el conjunto vacío, ∅ mientras que si hay una raíz retorna el intervalo ( a , b ), donde a = min( M (0), M (∞)), y b = max( M (0), M (∞)); si b = ∞ establece b = ub , donde ub es un límite superior sobre los valores de las raíces positivas de p ( x ). ^{[12] [13]}
• Si hay dos o más variaciones de signo, la regla de 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 aquellas dentro del intervalo (1, ∞). Se debe realizar una prueba especial para 1.
  • Para garantizar que existen 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 en p ( x ) y M ( x ), mientras que si se utilizan 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, ∞) se realiza la sustitución x ← x + 1 en p ( x ) y M ( x ) y se procesa 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, libre de cuadrados , de grado deg( 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 signo de p ( x ) // Regla de signos de Descartes ;2 si  var = 0 entonces DEVUELVE ∅;3 si  var = 1 entonces RETURN {( a , b )} // a = min( M (0), M (∞)), b = max( M (0), M (∞)), pero si b = ∞ establece b = ub , donde ub es un límite superior en 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) grados( p )  p ( ⁠1/x + 1⁠ ), M 01 ← M ( ⁠1/x + 1⁠ ) ​​// Busca raíces reales en (0, 1);7 m ← M (1) // ¿1 es 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 DEVOLVER VAS( p 01 , M 01 ) ∪ VAS( p 1∞ , M 1∞ )11 de lo contrario
12 DEVOLVER VAS( p 01 , M 01 ) ∪ {[ m , m ]} ∪ VAS( p 1∞ , M 1∞ )13 fin

Observaciones

• Para simplificar, no se incluye la contribución de Strzeboński.
• En el algoritmo anterior, a cada polinomio se le asocia 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(pag,METRO)

Aplicamos el método VAS a p ( x ) = x ³ − 7 x + 7 (nótese que: M ( x ) = x ).

Iteración 1

VAS( 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, que se obtiene calculando lb y sustituyéndolo(s) x ← x + 15 p ← x 3 + 3 x 2 − 4 x + 1, M ← x + 16 p 01 ← x 3 − x 2 − 2 x + 1, M 01 ← ⁠x + 2/x + 1⁠
7 m ← 18 p 1∞ ← x 3 + 6 x 2 + 5 x + 1, M 1∞ ← x + 210 DEVOLVER VAS( 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 proceselo.

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, que se obtiene calculando lb y sustituyéndolo(s) x ← x + 16 p 01 ← x 3 + x 2 − 2 x − 1, M 01 ← ⁠2x + 3/x + 1⁠
7 m ← ⁠3/2⁠
8 p 1∞ ← x 3 + 2 x 2 − x − 1, M 1∞ ← ⁠x + 3/x + 2⁠
10 DEVOLVER VAS( x 3 + x 2 − 2 x − 1, ⁠2x + 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 proceselo.

Iteración 3

EVA( x 3 + x 2 − 2 x − 1, ⁠2x + 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 REGRESAR {( ⁠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 proceselo.

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 RETORNO {(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 proceselo.

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 otro lugar. ^[19] Aquí se describen los dos más importantes, a saber, el método de Vincent–Collins–Akritas (VCA) y el método de Vincent–Alesina–Galuzzi (VAG).

El método de Vincent–Alesina–Galuzzi (VAG) es el más simple de todos los métodos derivados del teorema de Vincent, pero tiene la prueba que consume 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 simple (en la línea 1) que VAG. Esto, junto con ciertas mejoras ^[16], han hecho que VCA sea 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, había sido llamado originalmente algoritmo de Uspensky modificado por sus inventores Collins y Akritas. ^[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] ), fue finalmente François Boulier, de la Universidad de Lille, quien le dio el nombre de método Vincent-Collins-Akritas (VCA), ^[14] p. 24, basándose en el hecho de que el "método de Uspensky" no existe ^[21] y tampoco existe 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 ser aisladas, primero calcule una cota superior, ^{[12] [13]} ub sobre los valores de estas raíces positivas y haga p ( x ) = p _orig ( ub * x ) y ( a , b ) = (0, ub ). Las raíces positivas de p ( x ) se encuentran todas 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 ) (véase la figura correspondiente); esta biyección se expresa por α _{( a , b )} = a + α _(0,1) ( b − a ). Del mismo modo, hay 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 sobre p ( x ) para calcular (utilizando 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 signo, 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 a 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 figura correspondiente). Bien podría resultar que ⁠1/2⁠ es una raíz de p ( x ), en cuyo caso ⁠1/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 ( ⁠incógnita/2⁠ ) ​​y p ( ⁠x + 1/2⁠ ).

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

ACV ( p , ( a , b ))

Entrada : Un polinomio univariado sin 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) deg( p ) p ( ⁠1/x + 1⁠ ) ​​// " Prueba de raíces 0_1 " de Budan ;2 si  var = 0 entonces DEVUELVE ∅;3 si  var = 1 entonces DEVOLVER {( a , b )};4 pág. 0 ⁠1/2⁠ ← 2 grados( p ) p ( ⁠incógnita/2⁠ ) ​​// Busca raíces reales en (0, ⁠1/2⁠ );5 m ← ⁠1/2⁠ ( a + b ) // Es ⁠1/2¿ una raíz?6 p .1/21 ← 2 grados ( p ) p ( ⁠x + 1/2⁠ ) ​​// Busca raíces reales en ( ⁠1/2⁠ , 1);7 si  p ( ⁠1/2⁠ ) ​​≠ 0 entonces
8 DEVUELVE VCA ( p 0 ⁠1/2⁠ , ( a , m )) ∪ VCA ( p ⁠1/21 , ( m , b ) )9 de lo contrario
10 DEVOLVER VCA ( p 0 ⁠1/2⁠ , ( a , m )) ∪ {[ m , m ]} ∪ VCA ( p ⁠1/21 , ( m , b ) )11 fin

Observación

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

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

Dado el polinomio p _orig ( x ) = x ³ − 7 x + 7 y considerando como límite superior ^{[12] [13]} 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ág. 0 ⁠1/2← 64 x 3 − 112 x + 565m ← 26 p .1/21 ← 64 x 3 + 192 x 2 + 80 x + 87 pág . (1/2⁠ ) ​​= 18 DEVOLVER 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 proceselo.

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ág. 0 ⁠1/2← 64 x 3 − 448 x + 4485 m ← 16 p .1/21 ← 64 x 3 + 192 x 2 − 256 x + 647 pág . (1/2⁠ ) ​​= 88 DEVOLVER 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 proceselo.

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 proceselo.

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ág. 0 ⁠1/2← 64 x 3 + 384 x 2 − 1024 x + 5125 m ← ⁠3/26 p .​1/21 ← 64 x 3 + 576 x 2 − 64 x + 647 pág . (1/2⁠ ) ​​= −88 DEVOLVER 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 proceselo.

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 RETORNO {(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 proceselo.

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 REGRESAR {( ⁠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 proceselo.

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)

Éste fue el último desarrollado 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 una cota superior, ^{[12] [13]} ub sobre los valores de estas raíces positivas y establezca ( a , b ) = (0, ub ). Las raíces positivas de p ( x ) se encuentran todas 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 sobre p ( x ) para calcular (utilizando 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 signo, 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 a 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 que ⁠1/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, libre de 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 aislantes de las raíces positivas de p ( x ).

1 var ← el número de variaciones de signo de ( x + 1) deg( p )  p ( ⁠a + bx/1 + x⁠ ) ​​// La prueba de raíces a_b de Alesina–Galuzzi;2 si  var = 0 entonces DEVUELVE ∅;3 si  var = 1 entonces DEVOLVER {( a , b )};4 m ← ⁠1/2⁠ ( a + b ) // Subdividir el intervalo ( a , b ) en dos partes iguales;5 si  p ( m ) ≠ 0 entonces
6 DEVOLVER VAG( p , ( a , m )) ∪ VAG( p , ( m , b ))7 de lo contrario
8 DEVOLVER VAG( p , ( a , m )) ∪ {[ m , m ]} ∪ VAG( p , ( m , b ))9 fin

Observaciones

• En comparación 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 lo hace mucho más lento 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 utilizara el mediador de los puntos finales en lugar de su punto medio .1/2⁠ ( a + b ) . Sin embargo, se ha demostrado ^[19] que utilizar el mediador de los puntos finales es en general mucho más lento que la versión de "punto medio".

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

Dado el polinomio p ( x ) = x ³ − 7 x + 7 y considerando como cota superior ^{[12] [13]} 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 m ← ⁠1/2⁠ (0 + 4) = 25 p ( m ) = 18 DEVOLVER 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 proceselo.

Iteración 2

VAG( x3 − 7x + 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 m ← ⁠1/2⁠ (0 + 2) = 15 p ( m ) = 18 DEVOLVER 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 proceselo.

Iteración 3

VAG( x3 − 7x + 7, (0, 1))1 var ← 0 // el número de variaciones de signo en la secuencia de coeficientes de ( x + 1) 3 p ( ⁠incógnita/x + 1⁠ ) ​​= x3 + 7 x2 + 14 x + 72 RETORNO ∅

Lista de intervalos de aislamiento: {}.

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

Retire el primero y proceselo.

Iteración 4

VAG( x3 − 7x + 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 m ← ⁠1/2⁠ (1 + 2) = ⁠3/25 p ( m )
= − ⁠1/8⁠
8 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 proceselo.

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/2⁠ x + 1/x + 1⁠ ) ​​= x 3 + 2 x 2 − 8 x − 83 REGRESO (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 proceselo.

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 ( ⁠2x + ⁠​3/2⁠/x + 1⁠ ) ​​= 8 x 3 + 4 x 2 − 4 x − 13 REGRESO ( ⁠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 proceselo.

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 ( ⁠4x + 2/x + 1⁠ ) ​​= 344 x 3 + 376 x 2 + 104 x + 82 RETORNO ∅

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

Listado 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 .

Véase 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íces reales polinómicas utilizando la regla de los signos de Descartes". Aislamiento de raíces reales polinómicas utilizando la regla de los signos de Descartes. SYMSAC '76, Actas del tercer simposio de la ACM sobre computación simbólica y algebraica. Yorktown Heights, NY, EE. UU.: ACM. pp. 272–275. doi :10.1145/800205.806346. ISBN 9781450377904. Número de identificación del sujeto  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 en los valores de las raíces positivas de polinomios". Journal of Universal Computer Science . 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 de aislamiento de raíces reales" (PDF) . Análisis no lineal: modelado y control . 10 (4): 297–304. doi :10.15388/NA.2005.10.4.15110.
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, Elias P.; Emiris, Ioannis Z. (2006). "Aislamiento de raíces reales polinomiales univariadas: revisitación de fracciones continuas". En Azar, Yossi; Erlebach, Thomas (eds.). Algorithms – ESA 2006, 14.° Simposio europeo anual, Zúrich, Suiza, 11-13 de septiembre de 2006, Actas . Lecture Notes in Computer Science. Vol. 4168. Springer. págs. 817-828. arXiv : cs/0604066 . doi :10.1007/11841036_72. ISBN . 978-3-540-38875-3.
18. Sharma, Vikram (2007). Análisis de complejidad de algoritmos en computación algebraica (PDF) . Tesis doctoral, Courant Institute of Mathematical Sciences, 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". Serdica Journal of Computing . 2 (1): 89–104. doi :10.55630/sjc.2008.2.89-104. hdl : 10525/376 . S2CID  126142131. Archivado desde el original el 2016-04-10 . Consultado el 2012-05-09 .
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 ningún "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. ISBN 0897911997.S2CID15446040  .​
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. 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