teorema de sturm

Conteo de las raíces de un polinomio en un intervalo, sin calcularlas

En matemáticas , la secuencia de Sturm de un polinomio univariado p es una secuencia de polinomios asociados a p y su derivada mediante una variante del algoritmo de Euclides para polinomios . El teorema de Sturm expresa el número de raíces reales distintas de p ubicadas en un intervalo en términos del número de cambios de signo de los valores de la secuencia de Sturm en los límites del intervalo. Aplicado al intervalo de todos los números reales, da el número total de raíces reales de p . ^[1]

Mientras que el teorema fundamental del álgebra arroja fácilmente el número total de raíces complejas , contadas con multiplicidad , no proporciona un procedimiento para calcularlas. El teorema de Sturm cuenta el número de raíces reales distintas y las ubica en intervalos. Al subdividir los intervalos que contienen algunas raíces, puede aislar las raíces en intervalos arbitrariamente pequeños, cada uno de los cuales contiene exactamente una raíz. Esto produce el algoritmo de aislamiento de raíces reales más antiguo y el algoritmo de búsqueda de raíces de precisión arbitraria para polinomios univariados.

Para calcular sobre los reales , el teorema de Sturm es menos eficiente que otros métodos basados ​​en la regla de los signos de Descartes . Sin embargo, funciona en todos los campos reales cerrados y, por lo tanto, sigue siendo fundamental para el estudio teórico de la complejidad computacional de la decidibilidad y la eliminación de cuantificadores en la teoría de números reales de primer orden .

La secuencia de Sturm y el teorema de Sturm llevan el nombre de Jacques Charles François Sturm , quien descubrió el teorema en 1829. ^[2]

el teorema

La cadena de Sturm o secuencia de Sturm de un polinomio univariado P ( x ) con coeficientes reales es la secuencia de polinomios tales que ${\displaystyle P_{0},P_{1},\ldots ,}$

${\displaystyle {\begin{aligned}P_{0}&=P,\\P_{1}&=P',\\P_{i+1}&=-\operatorname {rem} (P_{i-1},P_{i}),\end{aligned}}}$

para i ≥ 1 , donde P' es la derivada de P , y es el resto de la división euclidiana de por La longitud de la secuencia de Sturm es como máximo el grado de P . ${\displaystyle \operatorname {rem} (P_{i-1},P_{i})}$ ${\displaystyle P_{i-1}}$ ${\displaystyle P_{i}.}$

El número de variaciones de signo en ξ de la secuencia de Sturm de P es el número de cambios de signo (ignorando los ceros) en la secuencia de números reales.

${\displaystyle P_{0}(\xi ),P_{1}(\xi ),P_{2}(\xi ),\ldots .}$

Este número de variaciones de signo se denota aquí como V ( ξ ) .

El teorema de Sturm establece que, si P es un polinomio libre de cuadrados , el número de raíces reales distintas de P en el intervalo semiabierto ( a , b ] es V ( a ) − V ( b ) (aquí, a y b son números reales tales que a < b ^[1 ]

El teorema se extiende a intervalos ilimitados al definir el signo en +∞ de un polinomio como el signo de su coeficiente principal (es decir, el coeficiente del término de mayor grado). En –∞ el signo de un polinomio es el signo de su coeficiente principal para un polinomio de grado par, y el signo opuesto para un polinomio de grado impar.

En el caso de un polinomio no libre de cuadrados, si ni a ni b son raíces múltiples de p , entonces V ( a ) − V ( b ) es el número de raíces reales distintas de P.

La prueba del teorema es la siguiente: cuando el valor de x aumenta de a a b , puede pasar por un cero de algún ( i > 0 ); cuando esto ocurre, el número de variaciones de signos de no cambia. Cuando x pasa por una raíz del número de variaciones de signo de disminuye de 1 a 0. Estos son los únicos valores de x donde algún signo puede cambiar. ${\displaystyle P_{i}}$ ${\displaystyle (P_{i-1},P_{i},P_{i+1})}$ ${\displaystyle P_{0}=P,}$ ${\displaystyle (P_{0},P_{1})}$

Ejemplo

Supongamos que deseamos encontrar el número de raíces en algún rango del polinomio . Entonces ${\displaystyle p(x)=x^{4}+x^{3}-x-1}$

${\displaystyle {\begin{aligned}p_{0}(x)&=p(x)=x^{4}+x^{3}-x-1\\p_{1}(x)&=p'(x)=4x^{3}+3x^{2}-1\end{aligned}}}$

El resto de la división euclidiana de p ₀ por p ₁ es multiplicarlo por −1 obtenemos ${\displaystyle -{\tfrac {3}{16}}x^{2}-{\tfrac {3}{4}}x-{\tfrac {15}{16}};}$

${\displaystyle p_{2}(x)={\tfrac {3}{16}}x^{2}+{\tfrac {3}{4}}x+{\tfrac {15}{16}}}$.

Luego dividiendo p ₁ por p ₂ y multiplicando el resto por −1 , obtenemos

${\displaystyle p_{3}(x)=-32x-64}$.

Ahora dividiendo p ₂ por p ₃ y multiplicando el resto por −1 , obtenemos

${\displaystyle p_{4}(x)=-{\tfrac {3}{16}}}$.

Como se trata de una constante, esto finaliza el cálculo de la secuencia de Sturm.

Para encontrar el número de raíces reales de uno hay que evaluar las secuencias de los signos de estos polinomios en −∞ y ∞ , que son respectivamente (+, −, +, +, −) y (+, +, +, −, −) . De este modo ${\displaystyle p_{0}}$

${\displaystyle V(-\infty )-V(+\infty )=3-1=2,}$

donde V denota el número de cambios de signo en la secuencia, lo que muestra que p tiene dos raíces reales.

Esto se puede verificar observando que p ( x ) se puede factorizar como ( x ² − 1)( x ² + x + 1) , donde el primer factor tiene las raíces −1 y 1 , y el segundo factor no tiene raíces reales. Esta última afirmación resulta de la fórmula cuadrática , y también del teorema de Sturm, que da las secuencias de signos (+, –, –) en −∞ y (+, +, –) en +∞ .

Generalización

Las secuencias de Sturm se han generalizado en dos direcciones. Para definir cada polinomio de la secuencia, Sturm utilizó el negativo del resto de la división euclidiana de los dos anteriores. El teorema sigue siendo verdadero si se reemplaza el negativo del resto por su producto o cociente por una constante positiva o el cuadrado de un polinomio. También es útil (ver más abajo) considerar secuencias donde el segundo polinomio no es la derivada del primero.

Una secuencia de Sturm generalizada es una secuencia finita de polinomios con coeficientes reales

${\displaystyle P_{0},P_{1},\dots ,P_{m}}$

tal que

• los grados van decreciendo después del primero: para i = 2, ..., m ; ${\displaystyle \deg P_{i}<\deg P_{i-1}}$
• ${\displaystyle P_{m}}$no tiene ninguna raíz real o no tiene cambios de signo cerca de sus raíces reales.
• si P _i ( ξ ) = 0 para 0 < i < m y ξ un número real, entonces P _{i −1} ( ξ ) P _{i + 1} ( ξ ) < 0 .

La última condición implica que dos polinomios consecutivos no tienen ninguna raíz real común. En particular, la secuencia de Sturm original es una secuencia de Sturm generalizada, si (y sólo si) el polinomio no tiene raíz real múltiple (de lo contrario, los dos primeros polinomios de su secuencia de Sturm tienen una raíz común).

Al calcular la secuencia de Sturm original mediante división euclidiana, puede suceder que uno encuentre un polinomio que tenga un factor que nunca sea negativo, como o . En este caso, si se continúa el cálculo con el polinomio reemplazado por su cociente por el factor no negativo, se obtiene una secuencia de Sturm generalizada, que también puede usarse para calcular el número de raíces reales, ya que la prueba del teorema de Sturm aún se aplica ( debido a la tercera condición). A veces esto puede simplificar el cálculo, aunque generalmente es difícil encontrar factores no negativos, excepto potencias pares de x . ${\displaystyle x^{2}}$ ${\displaystyle x^{2}+1}$

Uso de secuencias pseudo-restos.

En álgebra informática , los polinomios que se consideran tienen coeficientes enteros o pueden transformarse para tener coeficientes enteros. La secuencia de Sturm de un polinomio con coeficientes enteros generalmente contiene polinomios cuyos coeficientes no son números enteros (ver el ejemplo anterior).

Para evitar el cálculo con números racionales , un método común es reemplazar la división euclidiana por una pseudodivisión para calcular el máximo común divisor polinomial . Esto equivale a reemplazar la secuencia restante del algoritmo euclidiano por una secuencia pseudo-resto , siendo una secuencia pseudo-resto una secuencia de polinomios tales que hay constantes y que es el resto de la división euclidiana de por (Los diferentes tipos de pseudo -las secuencias de resto se definen mediante la elección de y , por lo general, se eligen para no introducir denominadores durante la división euclidiana y son un divisor común de los coeficientes del resto resultante; consulte Secuencia de pseudo-resto para obtener más detalles.) Por ejemplo, la secuencia de resto; del algoritmo euclidiano es una secuencia de pseudoresto con para cada i , y la secuencia de Sturm de un polinomio es una secuencia de pseudoresto con y para cada i . ${\displaystyle p_{0},\ldots ,p_{k}}$ ${\displaystyle a_{i}}$ ${\displaystyle b_{i}}$ ${\displaystyle b_{i}p_{i+1}}$ ${\displaystyle a_{i}p_{i-1}}$ ${\displaystyle p_{i}.}$ ${\displaystyle a_{i}}$ ${\displaystyle b_{i};}$ ${\displaystyle a_{i}}$ ${\displaystyle b_{i}}$ ${\displaystyle a_{i}=b_{i}=1}$ ${\displaystyle a_{i}=1}$ ${\displaystyle b_{i}=-1}$

Se han diseñado varias secuencias de pseudoresto para calcular los máximos divisores comunes de polinomios con coeficientes enteros sin introducir denominadores (ver Secuencia de pseudoresto ). Todas ellas pueden convertirse en secuencias de Sturm generalizadas eligiendo que el signo de sea opuesto al signo de Esto permite el uso del teorema de Sturm con secuencias de pseudoresto. ${\displaystyle b_{i}}$ ${\displaystyle a_{i}.}$

Aislamiento de raíces

Para un polinomio con coeficientes reales, el aislamiento de raíces consiste en encontrar, para cada raíz real, un intervalo que contenga esta raíz y ninguna otra raíz.

Esto es útil para encontrar raíces , ya que permite seleccionar la raíz a encontrar y proporciona un buen punto de partida para algoritmos numéricos rápidos como el método de Newton ; también es útil para certificar el resultado, ya que si el método de Newton converge fuera del intervalo se puede deducir inmediatamente que converge a la raíz incorrecta.

El aislamiento de raíces también es útil para calcular números algebraicos . Para calcular con números algebraicos, un método común es representarlos como un par de un polinomio del cual el número algebraico es una raíz y un intervalo de aislamiento. Por ejemplo, puede estar representado inequívocamente por ${\displaystyle {\sqrt {2}}}$ ${\displaystyle (x^{2}-2,[0,2]).}$

El teorema de Sturm proporciona una manera de aislar raíces reales que es menos eficiente (para polinomios con coeficientes enteros) que otros métodos que involucran la regla de los signos de Descartes . Sin embargo, sigue siendo útil en algunas circunstancias, principalmente con fines teóricos, por ejemplo para algoritmos de geometría algebraica real que involucran infinitesimales . ^[3]

Para aislar las raíces reales, se parte de un intervalo que contiene todas las raíces reales, o las raíces de interés (a menudo, normalmente en problemas físicos, sólo las raíces positivas son interesantes), y se calcula y Para definir este intervalo inicial, se puede utilizar límites en el tamaño de las raíces (ver Propiedades de las raíces polinómicas § Límites en raíces polinómicas (complejas) ). Luego, se divide este intervalo en dos, eligiendo c en el medio de El cálculo de proporciona el número de raíces reales en y y se puede repetir la misma operación en cada subintervalo. Cuando durante este proceso se encuentra un intervalo que no contiene ninguna raíz, se puede suprimir de la lista de intervalos a considerar. Cuando uno encuentra un intervalo que contiene exactamente una raíz, puede dejar de dividirlo, ya que es un intervalo de aislamiento. El proceso finalmente se detiene, cuando sólo quedan intervalos de aislamiento. ${\displaystyle (a,b]}$ ${\displaystyle V(a)}$ ${\displaystyle V(b).}$ ${\displaystyle (a,b].}$ ${\displaystyle V(c)}$ ${\displaystyle (a,c]}$ ${\displaystyle (c,b],}$

Este proceso de aislamiento se puede utilizar con cualquier método para calcular el número de raíces reales en un intervalo. El análisis de la complejidad teórica y las experiencias prácticas muestran que los métodos basados ​​en la regla de los signos de Descartes son más eficientes. De ello se deduce que, hoy en día, las secuencias de Sturm rara vez se utilizan para el aislamiento de raíces.

Solicitud

Las secuencias de Sturm generalizadas permiten contar las raíces de un polinomio donde otro polinomio es positivo (o negativo), sin calcular estas raíces explícitamente. Si se conoce un intervalo de aislamiento para una raíz del primer polinomio, esto también permite encontrar el signo del segundo polinomio en esta raíz particular del primer polinomio, sin calcular una mejor aproximación de la raíz.

Sean P ( x ) y Q ( x ) dos polinomios con coeficientes reales tales que P y Q no tienen raíz común y P no tiene raíces múltiples. En otras palabras, P y P'Q  son polinomios coprimos . Esta restricción realmente no afecta la generalidad de lo que sigue, ya que los cálculos de MCD permiten reducir el caso general a este caso, y el costo del cálculo de una secuencia de Sturm es el mismo que el de un MCD.

Sea W ( a ) el número de variaciones de signos en a de una secuencia de Sturm generalizada a partir de P y P'Q  . Si a < b son dos números reales, entonces W ( a ) – W ( b ) es el número de raíces de P en el intervalo tal que Q ( a ) > 0 menos el número de raíces en el mismo intervalo tal que Q ( a ) < 0 . Combinado con el número total de raíces de P en el mismo intervalo dado por el teorema de Sturm, esto da el número de raíces de P tales que Q ( a ) > 0 y el número de raíces de P tales que Q ( a ) <0 . ^[1] ${\displaystyle (a,b]}$

Ver también

• Teorema de Routh-Hurwitz
• Teorema de Hurwitz (análisis complejo)
• La regla de los signos de Descartes
• Teorema de Rouché
• Propiedades de las raíces polinómicas
• Teorema de Gauss-Lucas
• Las desigualdades de Turán

Referencias

1. (Basu, Pollack y Roy 2006)
2. O'Connor, John J.; Robertson, Edmund F. "Teorema de Sturm". Archivo MacTutor de Historia de las Matemáticas . Universidad de San Andrés .
3. (de Moura y Passmore 2013)

• Basu, Saugata; Pollack, Richard ; Roy, Marie-Françoise (2006). "Sección 2.2.2". Algoritmos en geometría algebraica real (2ª ed.). Saltador . págs. 52–57. ISBN 978-3-540-33098-1.
• Sturm, Jacques Charles François (1829). "Mémoire sur la résolution des équations numériques". Boletín de Ciencias de Férussac . 11 : 419–425.
• Sylvester, JJ (1853). "Sobre una teoría de las relaciones sizigéticas de dos funciones integrales racionales, que comprende una aplicación a la teoría de las funciones de Sturm y la de la mayor medida común algebraica". Fil. Trans. R. Soc. Londres . 143 : 407–548. doi : 10.1098/rstl.1853.0018 . JSTOR  108572.
• Thomas, José Miller (1941). "Teorema de Sturm para raíces múltiples". Revista Nacional de Matemáticas . 15 (8): 391–394. doi :10.2307/3028551. JSTOR  3028551. SEÑOR  0005945.
• Heindel, Lee E. (1971). Algoritmos aritméticos de enteros para la determinación del cero real polinómico . Proc. SYMSAC'71 . pag. 415. doi : 10.1145/800204.806312. SEÑOR  0300434. S2CID  9971778.
• de Moura, Leonardo; Passmore, Grant Olney (2013). "Computación en Extensiones Infinitesimales y Trascendentales Reales Cerradas de los Racionales". Deducción Automatizada – CADE-24 . Apuntes de conferencias sobre informática. vol. 7898. pág. 178-192. doi :10.1007/978-3-642-38574-2_12. ISBN 978-3-642-38573-5. S2CID  9308312.
• Pantón, Don B.; Verdini, William A. (1981). "Un programa de Fortran para aplicar el teorema de Sturm al contar las tasas internas de rendimiento". J. Finanzas. Cuant. Anal . 16 (3): 381–388. doi :10.2307/2330245. JSTOR  2330245. S2CID  154334522.
• Akritas, Alkiviadis G. (1982). "Reflexiones sobre un par de teoremas de Budan y Fourier". Matemáticas. Mag . 55 (5): 292–298. doi :10.2307/2690097. JSTOR  2690097. SEÑOR  0678195.
• Pedersen, Paul (1991). "Teoría de Sturm multivariante". En Mattson, Harold F.; Mora, Teo; Rao, TRN (eds.). Álgebra aplicada, algoritmos algebraicos y códigos de corrección de errores, noveno simposio internacional, AAECC-9, Nueva Orleans, LA, EE. UU., 7 al 11 de octubre de 1991, Actas . Apuntes de conferencias sobre informática. vol. 539. Berlín: Springer. págs. 318–332. doi :10.1007/3-540-54522-0_120. ISBN 978-3-540-54522-4. SEÑOR  1229329.
• Sí, Chee (2000). Problemas fundamentales en álgebra algorítmica. Prensa de la Universidad de Oxford . ISBN 0-19-512516-9.
• Rahman, QI; Schmeisser, G. (2002). Teoría analítica de polinomios . Monografías de la Sociedad Matemática de Londres. Series nuevas. vol. 26. Oxford: Prensa de la Universidad de Oxford . ISBN 0-19-853493-0. Zbl  1072.30006.
• Baumol, Guillermo. Dinámica Económica , capítulo 12, Sección 3, "Información cualitativa sobre raíces reales"
• DG Hook y PR McAree, "Using Sturm Sequences To Bracket Real Roots of Polynomial Equations" en Graphic Gems I (A. Glassner ed.), Academic Press, págs. 416–422, 1990.