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}
Si quieres conocer otros artículos parecidos a Sturm's theorem puedes visitar la categoría Computer algebra.
Deja una respuesta