Teorema de Sturm

Contar raíces polinómicas en un intervalo

En matemáticas , la sucesión de Sturm de un polinomio univariante p es una sucesión de polinomios asociados con 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 sucesión 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 proporciona 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 un algoritmo de búsqueda de raíces de precisión arbitraria para polinomios univariados.

Para el cálculo de 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]

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í 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 no acotados 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 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 ( i > 0 ); cuando esto ocurre, el número de variaciones de signo de no cambia. Cuando x pasa por una raíz de el 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 un rango determinado para el 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 tiene que evaluar las secuencias de los signos de estos polinomios en −∞ y ∞ , que son respectivamente (+, −, +, +, −) y (+, +, +, −, −) . Por lo tanto ${\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 sucesiones de Sturm se han generalizado en dos direcciones. Para definir cada polinomio de la sucesión, Sturm utilizó el negativo del resto de la división euclidiana de los dos anteriores. El teorema sigue siendo válido 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 (véase más adelante) considerar sucesiones en las que 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}}$

de tal manera que

• los grados van disminuyendo 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 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 sucesión original de Sturm mediante división euclidiana, puede suceder que se 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 sucesión de Sturm generalizada, que también se puede utilizar para calcular el número de raíces reales, ya que la prueba del teorema de Sturm todavía se aplica (debido a la tercera condición). Esto a veces puede simplificar el cálculo, aunque generalmente es difícil encontrar dichos factores no negativos, excepto para potencias pares de x . ${\displaystyle x^{2}}$ ${\displaystyle x^{2}+1}$

Uso de secuencias de pseudorestos

En álgebra computacional , los polinomios que se consideran tienen coeficientes enteros o pueden transformarse para que tengan coeficientes enteros. La sucesión de Sturm de un polinomio con coeficientes enteros generalmente contiene polinomios cuyos coeficientes no son 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 los máximos comunes divisores de polinomios . Esto equivale a reemplazar la secuencia de resto del algoritmo euclidiano por una secuencia de pseudoresto , siendo una secuencia de pseudoresto una secuencia de polinomios tales que hay constantes y tal que es el resto de la división euclidiana de por (Los diferentes tipos de secuencias de pseudoresto se definen por la elección de y típicamente, se elige por no introducir denominadores durante la división euclidiana, y es un divisor común de los coeficientes del resto resultante; vea Secuencia de pseudoresto para 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 pseudoresiduo para calcular máximos comunes divisores de polinomios con coeficientes enteros sin introducir denominadores (véase Secuencia de pseudoresiduo ). Todas ellas pueden convertirse en secuencias de Sturm generalizadas eligiendo el signo de como opuesto al signo de Esto permite el uso del teorema de Sturm con secuencias de pseudoresiduo. ${\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 , permitiendo seleccionar la raíz a encontrar y proporcionando 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, uno puede deducir inmediatamente que converge a la raíz equivocada.

El aislamiento de raíces también es útil para realizar cálculos con números algebraicos . Para realizar cálculos con números algebraicos, un método común es representarlos como un par de polinomios cuya raíz es el número algebraico y un intervalo de aislamiento. Por ejemplo, se puede representar de forma inequívoca mediante ${\displaystyle {\sqrt {2}}}$ ${\displaystyle (x^{2}-2,[0,2]).}$

El teorema de Sturm proporciona una forma de aislar raíces reales que es menos eficiente (para polinomios con coeficientes enteros) que otros métodos que involucran la regla de signos de Descartes . Sin embargo, sigue siendo útil en algunas circunstancias, principalmente para 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, típicamente en problemas físicos, solo las raíces positivas son interesantes), y se calcula y Para definir este intervalo de inicio, se pueden usar 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 uno encuentra, durante este proceso, 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, se puede dejar de dividirlo, ya que es un intervalo de aislamiento. El proceso se detiene eventualmente, cuando solo 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 complejidad teórica y las experiencias prácticas muestran que los métodos basados ​​en la regla de signos de Descartes son más eficientes. De ello se desprende que, en la actualidad, las sucesiones de Sturm rara vez se utilizan para el aislamiento de raíces.

Solicitud

Las sucesiones de Sturm generalizadas permiten contar las raíces de un polinomio en el que otro polinomio es positivo (o negativo), sin calcular explícitamente estas raíces. Si se conoce un intervalo de aislamiento para una raíz del primer polinomio, esto permite también 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 no afecta realmente a 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 signo en a de una sucesión de Sturm generalizada que comienza desde 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 tal que Q ( a ) > 0 y el número de raíces de P tal que Q ( a ) < 0 . ^[1] ${\displaystyle (a,b]}$

Véase 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 de Historia de las Matemáticas de MacTutor . Universidad de St Andrews .
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.). 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 máxima 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". Revista Nacional de Matemáticas . 15 (8): 391–394. doi :10.2307/3028551. JSTOR  3028551. MR  0005945.
• Heindel, Lee E. (1971). Algoritmos aritméticos de enteros para la determinación de ceros reales de polinomios . Proc. 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 reales, cerradas, infinitesimales y trascendentales de los racionales". Deducción automatizada – CADE-24 . Apuntes de clase en 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  .
• Panton, Don B.; Verdini, William A. (1981). "Un programa en FORTRAN para aplicar el teorema de Sturm en el conteo de 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). "Multivariate Sturm theory". En Mattson, Harold F.; Mora, Teo; Rao, TRN (eds.). Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, 9th International Symposium, AAECC-9, Nueva Orleans, LA, EE. UU., 7-11 de octubre de 1991, Actas . Lecture Notes in Computer Science. 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  .
• 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 polinomios . Monografías de la London Mathematical Society. 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 las raíces reales”
• DG Hook y PR McAree, "Uso de secuencias de Sturm para encerrar raíces reales de ecuaciones polinomiales" en Graphic Gems I (A. Glassner ed.), Academic Press, págs. 416–422, 1990.