Teorema de Sturm

En matemáticas , la sucesión de Sturm de un polinomio univariado p es una sucesión de polinomios asociada a p y su derivada mediante una variante del algoritmo euclidiano para polinomios . El teorema de Sturm expresa el número de raíces reales distintas de p ubicadas en un intervalo en función del número de cambios de signo de los valores de la sucesión de Sturm en los límites del intervalo. Aplicado al intervalo de todos los números reales, proporciona el número total de raíces reales de p . ^{[ 1 ]}

Si bien el teorema fundamental del álgebra proporciona fácilmente el número total de raíces complejas , contadas con multiplicidad , no ofrece 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 aislarlas en intervalos arbitrariamente pequeños, cada uno con una sola raíz. Esto da lugar al algoritmo de aislamiento de raíces reales más antiguo y a un algoritmo de búsqueda de raíces de precisión arbitraria para polinomios univariados.

Para realizar cálculos sobre los números 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 todo cuerpo real cerrado 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 primer orden de los números reales.

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

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

${\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${\displaystyle \operatorname {rem} (P_{i-1},P_{i})}$es el resto de la división euclidiana de${\displaystyle P_{i-1}}$por${\displaystyle P_{i}.}$La longitud de la secuencia de Sturm es como máximo el grado de P.

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í 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 ) (donde a y b son números reales tales que a < b ). ^{[ 1 ]}

El teorema se extiende a intervalos no acotados definiendo el signo de un polinomio en +∞ 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 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 demostración del teorema es la siguiente: cuando el valor de x aumenta de a a b , puede pasar por un cero de algún${\displaystyle P_{i}}$( i > 0 ); cuando esto ocurre, el número de variaciones de signo de${\displaystyle (P_{i-1},P_{i},P_{i+1})}$no cambia. Cuando x pasa por una raíz de${\displaystyle P_{0}=P,}$el número de variaciones de signo de${\displaystyle (P_{0},P_{1})}$disminuye de 1 a 0. Estos son los únicos valores de x donde puede cambiar algún signo.

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

${\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${\displaystyle -{\tfrac {3}{16}}x^{2}-{\tfrac {3}{4}}x-{\tfrac {15}{16}};}$multiplicándolo por −1 obtenemos

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

A continuación, dividiendo p ₁ entre p ₂ y multiplicando el resto por −1 , obtenemos

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

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

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

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

Para hallar el número de raíces reales de${\displaystyle p_{0}}$Hay que evaluar las secuencias de los signos de estos polinomios en −∞ e ∞ , que son respectivamente (+, −, +, +, −) y (+, +, +, −, −) . Por lo tanto,

${\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 al observar 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 +∞ .

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 se mantiene si se reemplaza el negativo del resto por su producto o cociente por una constante positiva o el cuadrado de un polinomio. También resulta útil (véase más adelante) considerar secuencias en las que el segundo polinomio no es la derivada del primero.

Una sucesión de Sturm generalizada es una sucesión finita de polinomios con coeficientes reales.

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

de tal manera que

• Los grados van disminuyendo después del primero:${\displaystyle \deg P_{i}<\deg P_{i-1}}$para i = 2, ..., m ;
• ${\displaystyle P_{m}}$No tiene ninguna raíz real o no presenta 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 sucesión de Sturm original es una sucesión de Sturm generalizada si (y solo si) el polinomio no tiene raíces reales múltiples (de lo contrario, los dos primeros polinomios de su sucesión de Sturm tienen una raíz común).

Al calcular la secuencia de Sturm original mediante división euclidiana, puede ocurrir que uno encuentre un polinomio que tenga un factor que nunca sea negativo, como por ejemplo:${\displaystyle x^{2}}$o${\displaystyle x^{2}+1}$En este caso, si se continúa el cálculo reemplazando el polinomio por su cociente por el factor no negativo, se obtiene una sucesión de Sturm generalizada, que también puede utilizarse para calcular el número de raíces reales, ya que la demostración del teorema de Sturm sigue siendo válida (debido a la tercera condición). Esto puede simplificar el cálculo en ocasiones, aunque generalmente es difícil encontrar tales factores no negativos, excepto para potencias pares de x .

En álgebra computacional , los polinomios considerados tienen coeficientes enteros o pueden transformarse para tenerlos. La sucesión de Sturm de un polinomio con coeficientes enteros generalmente contiene polinomios cuyos coeficientes no son enteros (véase el ejemplo anterior).

Para evitar cálculos 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 de polinomios . Esto equivale a reemplazar la secuencia de restos del algoritmo euclidiano por una secuencia de pseudorestos , siendo una secuencia de pseudorestos una secuencia${\displaystyle p_{0},\ldots ,p_{k}}$de polinomios tales que hay constantes${\displaystyle a_{i}}$y${\displaystyle b_{i}}$de tal manera que${\displaystyle b_{i}p_{i+1}}$es el resto de la división euclidiana de${\displaystyle a_{i}p_{i-1}}$por${\displaystyle p_{i}.}$(Los diferentes tipos de secuencias de pseudoresto se definen por la elección de${\displaystyle a_{i}}$y${\displaystyle b_{i};}$típicamente,${\displaystyle a_{i}}$se elige por no introducir denominadores durante la división euclidiana, y${\displaystyle b_{i}}$es un divisor común de los coeficientes del resto resultante; véase la secuencia de pseudorestos para más detalles.

Por ejemplo, la secuencia de resto del algoritmo euclidiano es una secuencia de pseudo-resto con${\displaystyle a_{i}=b_{i}=1}$para cada i , y la sucesión de Sturm de un polinomio es una sucesión de pseudoresto con${\displaystyle a_{i}=1}$y${\displaystyle b_{i}=-1}$por cada i .

Se han diseñado varias secuencias de pseudoresto para calcular el máximo común divisor de polinomios con coeficientes enteros sin introducir denominadores (véase Secuencia de pseudoresto ). Todas ellas pueden convertirse en secuencias de Sturm generalizadas eligiendo el signo del${\displaystyle b_{i}}$ser lo opuesto al signo de la${\displaystyle a_{i}.}$Esto permite el uso del teorema de Sturm con secuencias de pseudoresto.

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

Esto resulta útil para la búsqueda de raíces , ya que permite seleccionar la raíz que se va 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 realizar cálculos con números algebraicos . Para ello, un método común consiste en representarlos como un par formado por un polinomio del cual el número algebraico es una raíz y un intervalo de aislamiento. Por ejemplo${\displaystyle {\sqrt {2}}}$puede representarse inequívocamente por${\displaystyle (x^{2}-2,[0,2]).}$

El teorema de Sturm proporciona un método para 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.${\displaystyle (a,b]}$que contiene todas las raíces reales, o las raíces de interés (a menudo, típicamente en problemas físicos, solo las raíces positivas son interesantes), y se calcula${\displaystyle V(a)}$y${\displaystyle V(b).}$Para definir este intervalo inicial, se pueden usar límites en el tamaño de las raíces (ver Propiedades de las raíces de polinomios §  Límites en las raíces de polinomios (complejos) ). Luego, se divide este intervalo en dos, eligiendo c en el medio de${\displaystyle (a,b].}$El cálculo de${\displaystyle V(c)}$proporciona el número de raíces reales en${\displaystyle (a,c]}$y${\displaystyle (c,b],}$Se puede repetir la misma operación en cada subintervalo. Si durante este proceso se encuentra un intervalo que no contiene ninguna raíz, se puede omitir de la lista de intervalos a considerar. Si se encuentra un intervalo que contiene exactamente una raíz, se puede dejar de dividirlo, ya que se trata de un intervalo de aislamiento. El proceso finaliza cuando solo quedan intervalos de aislamiento.

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

Las secuencias de Sturm generalizadas permiten contar las raíces de un polinomio donde otro polinomio es positivo (o negativo), sin necesidad de calcular explícitamente dichas raíces. Si se conoce un intervalo de aislamiento para una raíz del primer polinomio, esto también permite hallar el signo del segundo polinomio en esa raíz específica del primero, 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íces comunes y P no tiene raíces múltiples. En otras palabras, P y P'Q son polinomios coprimos . Esta restricción no afecta la generalidad de lo que sigue, ya que los cálculos del MCD permiten reducir el caso general a este caso, y el costo de calcular una secuencia de Sturm es el mismo que el de un MCD.

Sea W ( a ) el número de variaciones de signo en a de una sucesión de Sturm generalizada que comienza en 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${\displaystyle (a,b]}$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 tal que Q ( a ) > 0 y el número de raíces de P tal que Q ( a ) < 0. ^{[ 1 ]}

• Basu, Saugata; Pollack, Richard ; Roy, Marie-Françoise (2006). «Sección 2.2.2». Algoritmos en geometría algebraica real (2.ª  ed.). Springer . 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 a la de la mayor medida común algebraica" . Phil. Trans. R. Soc. Lond . 143 : 407–548 . doi : 10.1098/rstl.1853.0018 . JSTOR 108572 . 
• Thomas, Joseph Miller (1941). " Teorema de Sturm para raíces múltiples". National Mathematics Magazine . 15 (8): 391– 394. doi : 10.2307/3028551 . JSTOR 3028551. MR 0005945 .  
• Heindel, Lee E. (1971). "Algoritmos de aritmética entera para la determinación de ceros reales polinomiales". Actas del segundo simposio de la ACM sobre manipulación simbólica y algebraica - SYMSAC '71 . pág.  415. doi : 10.1145/800204.806312 . MR 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 . Lecture Notes in Computer Science. Vol.  7898. pp. 178–192 . doi : 10.1007/978-3-642-38574-2_12 . ISBN  978-3-642-38573-5. S2CID 9308312 . 
• Panton, Don B.; Verdini, William A. (1981). "Un programa en Fortran para aplicar el teorema de Sturm en el cálculo de las tasas internas de retorno". J. Financ. Quant. 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". Math. Mag . 55 (5): 292– 298. doi : 10.2307/2690097 . JSTOR 2690097 . MR 0678195 .  
• Pedersen, Paul (1991). "Teoría de Sturm multivariada". En Mattson, Harold F.; Mora, Teo; Rao, TRN (eds.). Álgebra aplicada, algoritmos algebraicos y códigos correctores de errores, 9.º Simposio Internacional, AAECC-9, Nueva Orleans, LA, EE. UU., 7-11 de octubre de 1991, Actas . Lecture Notes in Computer Science. Vol.  539. Berlín: Springer. pp. 318-332 . doi : 10.1007/3-540-54522-0_120 . ISBN  978-3-540-54522-4. MR 1229329 . 
• Yap, Chee (2000). Problemas fundamentales en álgebra algorítmica . Oxford University Press . ISBN 0-19-512516-9.
• Rahman, QI; Schmeisser, G. (2002). Teoría analítica de los polinomios . Monografías de la Sociedad Matemática de Londres. Nueva serie. Vol.  26. Oxford: Oxford University Press . ISBN 0-19-853493-0. Zbl 1072.30006 . 
• Baumol, William. Dinámica económica , capítulo 12, sección 3, "Información cualitativa sobre raíces reales".
• DG Hook y PR McAree, "Uso de secuencias de Sturm para acotar las raíces reales de ecuaciones polinómicas" en Graphic Gems I (A. Glassner ed.), Academic Press, págs.  416 – 422, 1990.