# Sturm's theorem

Sturm's theorem In mathematics, the Sturm sequence of a univariate polynomial p is a sequence of polynomials associated with p and its derivative by a variant of Euclid's algorithm for polynomials. Sturm's theorem expresses the number of distinct real roots of p located in an interval in terms of the number of changes of signs of the values of the Sturm sequence at the bounds of the interval. Applied to the interval of all the real numbers, it gives the total number of real roots of p.[1] Whereas the fundamental theorem of algebra readily yields the overall number of complex roots, counted with multiplicity, it does not provide a procedure for calculating them. Sturm's theorem counts the number of distinct real roots and locates them in intervals. By subdividing the intervals containing some roots, it can isolate the roots into arbitrarily small intervals, each containing exactly one root. This yields the oldest real-root isolation algorithm, and arbitrary-precision root-finding algorithm for univariate polynomials.

For computing over the reals, Sturm's theorem is less efficient than other methods based on Descartes' rule of signs. However, it works on every real closed field, and, therefore, remains fundamental for the theoretical study of the computational complexity of decidability and quantifier elimination in the first order theory of real numbers.

The Sturm sequence and Sturm's theorem are named after Jacques Charles François Sturm, who discovered the theorem in 1829.[2] Contents 1 The theorem 2 Example 3 Generalization 4 Use of pseudo-remainder sequences 5 Root isolation 6 Application 7 See also 8 References The theorem The Sturm chain or Sturm sequence of a univariate polynomial P(x) with real coefficients is the sequence of polynomials {displaystyle P_{0},P_{1},ldots ,} such that {displaystyle {begin{aligned}P_{0}&=P,\P_{1}&=P',\P_{i+1}&=-operatorname {rem} (P_{i-1},P_{i}),end{aligned}}} for i ≥ 1, where P' is the derivative of P, and {displaystyle operatorname {rem} (P_{i-1},P_{i})} is the remainder of the Euclidean division of {displaystyle P_{i-1}} by {displaystyle P_{i}.} The length of the Sturm sequence is at most the degree of P.

The number of sign variations at ξ of the Sturm sequence of P is the number of sign changes–ignoring zeros—in the sequence of real numbers {displaystyle P_{0}(xi ),P_{1}(xi ),P_{2}(xi ),ldots .} This number of sign variations is denoted here V(ξ).

Sturm's theorem states that, if P is a square-free polynomial, the number of distinct real roots of P in the half-open interval (a, b] is V(a) − V(b) (here, a and b are real numbers such that a < b).[1] The theorem extends to unbounded intervals by defining the sign at +∞ of a polynomial as the sign of its leading coefficient (that is, the coefficient of the term of highest degree). At –∞ the sign of a polynomial is the sign of its leading coefficient for a polynomial of even degree, and the opposite sign for a polynomial of odd degree. In the case of a non-square-free polynomial, if neither a nor b is a multiple root of p, then V(a) − V(b) is the number of distinct real roots of P. The proof of the theorem is as follows: when the value of x increases from a to b, it may pass through a zero of some {displaystyle P_{i}} (i > 0); when this occurs, the number of sign variations of {displaystyle (P_{i-1},P_{i},P_{i+1})} does not change. When x passes through a root of {displaystyle P_{0}=P,} the number of sign variations of {displaystyle (P_{0},P_{1})} decreases from 1 to 0. These are the only values of x where some sign may change.

Example Suppose we wish to find the number of roots in some range for the polynomial {displaystyle p(x)=x^{4}+x^{3}-x-1} . So {displaystyle {begin{aligned}p_{0}(x)&=p(x)=x^{4}+x^{3}-x-1\p_{1}(x)&=p'(x)=4x^{3}+3x^{2}-1end{aligned}}} The remainder of the Euclidean division of p0 by p1 is {displaystyle -{tfrac {3}{16}}x^{2}-{tfrac {3}{4}}x-{tfrac {15}{16}};} multiplying it by −1 we obtain {displaystyle p_{2}(x)={tfrac {3}{16}}x^{2}+{tfrac {3}{4}}x+{tfrac {15}{16}}} .

Next dividing p1 by p2 and multiplying the remainder by −1, we obtain {displaystyle p_{3}(x)=-32x-64} .

Now dividing p2 by p3 and multiplying the remainder by −1, we obtain {displaystyle p_{4}(x)=-{tfrac {3}{16}}} .

As this is a constant, this finishes the computation of the Sturm sequence.

To find the number of real roots of {displaystyle p_{0}} one has to evaluate the sequences of the signs of these polynomials at −∞ and ∞, which are respectively (+, −, +, +, −) and (+, +, +, −, −). Thus {displaystyle V(-infty )-V(+infty )=3-1=2,} which shows that p has two real roots.

This can be verified by noting that p(x) can be factored as (x2 − 1)(x2 + x + 1), where the first factor has the roots −1 and 1, and second factor has no real roots. This last assertion results from the quadratic formula, and also from Sturm's theorem, which gives the sign sequences (+, –, –) at −∞ and (+, +, –) at +∞.

Generalization Sturm sequences have been generalized in two directions. To define each polynomial in the sequence, Sturm used the negative of the remainder of the Euclidean division of the two preceding ones. The theorem remains true if one replaces the negative of the remainder by its product or quotient by a positive constant or the square of a polynomial. It is also useful (see below) to consider sequences where the second polynomial is not the derivative of the first one.

A generalized Sturm sequence is a finite sequence of polynomials with real coefficients {displaystyle P_{0},P_{1},dots ,P_{m}} such that the degrees are decreasing after the first one: {displaystyle deg P_{i} 0 minus the number of roots in the same interval such that Q(a) < 0. Combined with the total number of roots of P in the same interval given by Sturm's theorem, this gives the number of roots of P such that Q(a) > 0 and the number of roots of P such that Q(a) < 0.[1] See also Routh–Hurwitz theorem Hurwitz's theorem (complex analysis) Descartes' rule of signs Rouché's theorem Properties of polynomial roots Gauss–Lucas theorem Turán's inequalities References ^ Jump up to: a b c (Basu, Pollack & Roy 2006) ^ O'Connor, John J.; Robertson, Edmund F. "Sturm's theorem". MacTutor History of Mathematics archive. University of St Andrews. Basu, Saugata; Pollack, Richard; Roy, Marie-Françoise (2006). "Section 2.2.2". Algorithms in real algebraic geometry (2nd ed.). Springer. pp. 52–57. ISBN 978-3-540-33098-1.[dead link] Sturm, Jacques Charles François (1829). "Mémoire sur la résolution des équations numériques". Bulletin des Sciences de Férussac. 11: 419–425. Sylvester, J. J. (1853). "On a theory of the syzygetic relations of two rational integral functions, comprising an application to the theory of Sturm's functions, and that of the greatest algebraical common measure". Phil. Trans. R. Soc. Lond. 143: 407–548. doi:10.1098/rstl.1853.0018. JSTOR 108572. Thomas, Joseph Miller (1941). "Sturm's theorem for multiple roots". National Mathematics Magazine. 15 (8): 391–394. doi:10.2307/3028551. JSTOR 3028551. MR 0005945. Heindel, Lee E. (1971). Integer arithmetic algorithms for polynomial real zero determination. Proc. SYMSAC '71. p. 415. doi:10.1145/800204.806312. MR 0300434. S2CID 9971778. Panton, Don B.; Verdini, William A. (1981). "A fortran program for applying Sturm's theorem in counting internal rates of return". J. Financ. Quant. Anal. 16 (3): 381–388. doi:10.2307/2330245. JSTOR 2330245. Akritas, Alkiviadis G. (1982). "Reflections on a pair of theorems by Budan and Fourier". Math. Mag. 55 (5): 292–298. doi:10.2307/2690097. JSTOR 2690097. MR 0678195. Pedersen, Paul (1991). "Multivariate Sturm theory". In Mattson, Harold F.; Mora, Teo; Rao, T. R. N. (eds.). Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, 9th International Symposium, AAECC-9, New Orleans, LA, USA, October 7–11, 1991, Proceedings. Lecture Notes in Computer Science. Vol. 539. Berlin: Springer. pp. 318–332. doi:10.1007/3-540-54522-0_120. ISBN 978-3-540-54522-4. MR 1229329. Yap, Chee (2000). Fundamental Problems in Algorithmic Algebra. Oxford University Press. ISBN 0-19-512516-9. Rahman, Q. I.; Schmeisser, G. (2002). Analytic theory of polynomials. London Mathematical Society Monographs. New Series. Vol. 26. Oxford: Oxford University Press. ISBN 0-19-853493-0. Zbl 1072.30006. Baumol, William. Economic Dynamics, chapter 12, Section 3, "Qualitative information on real roots" D.G. Hook and P. R. McAree, "Using Sturm Sequences To Bracket Real Roots of Polynomial Equations" in Graphic Gems I (A. Glassner ed.), Academic Press, pp. 416–422, 1990. Categories: Theorems in real analysisTheorems about polynomialsComputer algebraReal algebraic geometry

Si quieres conocer otros artículos parecidos a Sturm's theorem puedes visitar la categoría Computer algebra.

Subir

Utilizamos cookies propias y de terceros para mejorar la experiencia de usuario Más información