In
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, the Sturm sequence of a
univariate polynomial
In mathematics, a polynomial is a mathematical expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication and exponentiation to nonnegative integer ...
is a sequence of polynomials associated with and its derivative by a variant of
Euclid's algorithm for polynomials. Sturm's theorem expresses the number of distinct
real root
In vascular plants, the roots are the plant organ, organs of a plant that are modified to provide anchorage for the plant and take in water and nutrients into the plant body, which allows plants to grow taller and faster. They are most often bel ...
s of 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 .
Whereas the
fundamental theorem of algebra
The fundamental theorem of algebra, also called d'Alembert's theorem or the d'Alembert–Gauss theorem, states that every non-constant polynomial, constant single-variable polynomial with Complex number, complex coefficients has at least one comp ...
readily yields the overall number of
complex
Complex commonly refers to:
* Complexity, the behaviour of a system whose components interact in multiple ways so possible interactions are difficult to describe
** Complex system, a system composed of many components which may interact with each ...
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
In mathematics, and, more specifically in numerical analysis and computer algebra, real-root isolation of a polynomial consist of producing disjoint intervals of the real line, which contain each one (and only one) real root of the polynomial, and ...
algorithm, and arbitrary-precision
root-finding algorithm
In numerical analysis, a root-finding algorithm is an algorithm for finding zeros, also called "roots", of continuous functions. A zero of a function is a number such that . As, generally, the zeros of a function cannot be computed exactly nor ...
for univariate polynomials.
For computing over the
reals, Sturm's theorem is less efficient than other methods based on
Descartes' rule of signs
In mathematics, Descartes' rule of signs, described by René Descartes in his ''La Géométrie'', counts the roots of a polynomial by examining sign changes in its coefficients. The number of positive real roots is at most the number of sign chang ...
. However, it works on every
real closed field
In mathematics, a real closed field is a field F that has the same first-order properties as the field of real numbers. Some examples are the field of real numbers, the field of real algebraic numbers, and the field of hyperreal numbers.
Def ...
, and, therefore, remains fundamental for the theoretical study of the
computational complexity
In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations ...
of
decidability and
quantifier elimination
Quantifier elimination is a concept of simplification used in mathematical logic, model theory, and theoretical computer science. Informally, a quantified statement "\exists x such that ..." can be viewed as a question "When is there an x such ...
in the
first order theory of real numbers.
The Sturm sequence and Sturm's theorem are named after
Jacques Charles François Sturm
Jacques Charles François Sturm (29 September 1803 – 15 December 1855) was a French mathematician, who made a significant addition to equation theory with his work, Sturm's theorem.
Early life
Sturm was born in Geneva, France in 1803. The fam ...
, who discovered the theorem in 1829.
The theorem
The Sturm chain or Sturm sequence of a
univariate polynomial
In mathematics, a polynomial is a mathematical expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication and exponentiation to nonnegative integer ...
with real coefficients is the sequence of polynomials
such that
:
for , where is the
derivative
In mathematics, the derivative is a fundamental tool that quantifies the sensitivity to change of a function's output with respect to its input. The derivative of a function of a single variable at a chosen input value, when it exists, is t ...
of , and
is the remainder of the
Euclidean division
In arithmetic, Euclidean division – or division with remainder – is the process of dividing one integer (the dividend) by another (the divisor), in a way that produces an integer quotient and a natural number remainder strictly smaller than ...
of
by
The length of the Sturm sequence is at most the degree of .
The number of
sign variations at of the Sturm sequence of is the number of sign changes (ignoring zeros) in the sequence of real numbers
:
This number of sign variations is denoted here .
Sturm's theorem states that, if is a
square-free polynomial
In mathematics, a square-free polynomial is a univariate polynomial (over a field or an integral domain) that has no multiple root in an algebraically closed field containing its coefficients. In characteristic 0, or over a finite field, a univar ...
, the number of distinct real roots of in the
half-open interval
In mathematics, a real interval is the set of all real numbers lying between two fixed endpoints with no "gaps". Each endpoint is either a real number or positive or negative infinity, indicating the interval extends without a bound. A real in ...
is (here, and are real numbers such that ).
The theorem extends to unbounded intervals by defining the sign at of a polynomial as the sign of its
leading coefficient
In mathematics, a coefficient is a multiplicative factor involved in some term of a polynomial, a series, or any other type of expression. It may be a number without units, in which case it is known as a numerical factor. It may also be a c ...
(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 nor is a multiple root of , then is the number of ''distinct'' real roots of .
The proof of the theorem is as follows: when the value of increases from to , it may pass through a zero of some
(); when this occurs, the number of sign variations of
does not change. When passes through a root of
the number of sign variations of
decreases from 1 to 0. These are the only values of where some sign may change.
Example
Suppose we wish to find the number of roots in some range for the polynomial
. So
:
The remainder of the
Euclidean division
In arithmetic, Euclidean division – or division with remainder – is the process of dividing one integer (the dividend) by another (the divisor), in a way that produces an integer quotient and a natural number remainder strictly smaller than ...
of by is
multiplying it by we obtain
:
.
Next dividing by and multiplying the remainder by , we obtain
:
.
Now dividing by and multiplying the remainder by , we obtain
:
.
As this is a constant, this finishes the computation of the Sturm sequence.
To find the number of real roots of
one has to evaluate the sequences of the signs of these polynomials at and , which are respectively and . Thus
:
where denotes the number of sign changes in the sequence, which shows that has two real roots.
This can be verified by noting that can be factored as , where the first factor has the roots and , and second factor has no real roots. This last assertion results from the
quadratic formula
In elementary algebra, the quadratic formula is a closed-form expression describing the solutions of a quadratic equation. Other ways of solving quadratic equations, such as completing the square, yield the same solutions.
Given a general quadr ...
, 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
In arithmetic, Euclidean division – or division with remainder – is the process of dividing one integer (the dividend) by another (the divisor), in a way that produces an integer quotient and a natural number remainder strictly smaller than ...
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
:
such that
* the degrees are decreasing after the first one:
for ;
*
does not have any real root or has no sign changes near its real roots.
* if for and a real number, then .
The last condition implies that two consecutive polynomials do not have any common real root. In particular the original Sturm sequence is a generalized Sturm sequence, if (and only if) the polynomial has no multiple real root (otherwise the first two polynomials of its Sturm sequence have a common root).
When computing the original Sturm sequence by Euclidean division, it may happen that one encounters a polynomial that has a factor that is never negative, such a
or
. In this case, if one continues the computation with the polynomial replaced by its quotient by the nonnegative factor, one gets a generalized Sturm sequence, which may also be used for computing the number of real roots, since the proof of Sturm's theorem still applies (because of the third condition). This may sometimes simplify the computation, although it is generally difficult to find such nonnegative factors, except for even powers of .
Use of pseudo-remainder sequences
In
computer algebra
In mathematics and computer science, computer algebra, also called symbolic computation or algebraic computation, is a scientific area that refers to the study and development of algorithms and software for manipulating expression (mathematics), ...
, the polynomials that are considered have integer coefficients or may be transformed to have integer coefficients. The Sturm sequence of a polynomial with integer coefficients generally contains polynomials whose coefficients are not integers (see above example).
To avoid computation with
rational number
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (for example,
The set of all ...
s, a common method is to replace
Euclidean division
In arithmetic, Euclidean division – or division with remainder – is the process of dividing one integer (the dividend) by another (the divisor), in a way that produces an integer quotient and a natural number remainder strictly smaller than ...
by
pseudo-division for computing
polynomial greatest common divisor
In algebra, the greatest common divisor (frequently abbreviated as GCD) of two polynomials is a polynomial, of the highest possible degree, that is a factor of both the two original polynomials. This concept is analogous to the greatest common d ...
s. This amounts to replacing the remainder sequence of the
Euclidean algorithm
In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is a ...
by a
pseudo-remainder sequence, a pseudo remainder sequence being a sequence
of polynomials such that there are constants
and
such that
is the remainder of the Euclidean division of
by
(The different kinds of pseudo-remainder sequences are defined by the choice of
and
typically,
is chosen for not introducing denominators during Euclidean division, and
is a common divisor of the coefficients of the resulting remainder; see
Pseudo-remainder sequence for details.)
For example, the remainder sequence of the Euclidean algorithm is a pseudo-remainder sequence with
for every , and the Sturm sequence of a polynomial is a pseudo-remainder sequence with
and
for every .
Various pseudo-remainder sequences have been designed for computing greatest common divisors of polynomials with integer coefficients without introducing denominators (see
Pseudo-remainder sequence). They can all be made generalized Sturm sequences by choosing the sign of the
to be the opposite of the sign of the
This allows the use of Sturm's theorem with pseudo-remainder sequences.
Root isolation
For a polynomial with real coefficients, ''root isolation'' consists of finding, for each real root, an interval that contains this root, and no other roots.
This is useful for
root finding
In numerical analysis, a root-finding algorithm is an algorithm for finding Zero of a function, zeros, also called "roots", of continuous functions. A zero of a function is a number such that . As, generally, the zeros of a function cannot be com ...
, allowing the selection of the root to be found and providing a good starting point for fast numerical algorithms such as
Newton's method
In numerical analysis, the Newton–Raphson method, also known simply as Newton's method, named after Isaac Newton and Joseph Raphson, is a root-finding algorithm which produces successively better approximations to the roots (or zeroes) of a ...
; it is also useful for certifying the result, as if Newton's method converge outside the interval one may immediately deduce that it converges to the wrong root.
Root isolation is also useful for computing with
algebraic numbers
In mathematics, an algebraic number is a number that is a root of a non-zero polynomial in one variable with integer (or, equivalently, rational) coefficients. For example, the golden ratio (1 + \sqrt)/2 is an algebraic number, because it is a ...
. For computing with algebraic numbers, a common method is to represent them as a pair of a polynomial to which the algebraic number is a root, and an isolation interval. For example
may be unambiguously represented by
Sturm's theorem provides a way for isolating real roots that is less efficient (for polynomials with integer coefficients) than other methods involving
Descartes' rule of signs
In mathematics, Descartes' rule of signs, described by René Descartes in his ''La Géométrie'', counts the roots of a polynomial by examining sign changes in its coefficients. The number of positive real roots is at most the number of sign chang ...
. However, it remains useful in some circumstances, mainly for theoretical purposes, for example for algorithms of
real algebraic geometry that involve
infinitesimal
In mathematics, an infinitesimal number is a non-zero quantity that is closer to 0 than any non-zero real number is. The word ''infinitesimal'' comes from a 17th-century Modern Latin coinage ''infinitesimus'', which originally referred to the " ...
s.
For isolating the real roots, one starts from an interval
containing all the real roots, or the roots of interest (often, typically in physical problems, only positive roots are interesting), and one computes
and
For defining this starting interval, one may use bounds on the size of the roots (see ). Then, one divides this interval in two, by choosing in the middle of
The computation of
provides the number of real roots in
and
and one may repeat the same operation on each subinterval. When one encounters, during this process an interval that does not contain any root, it may be suppressed from the list of intervals to consider. When one encounters an interval containing exactly one root, one may stop dividing it, as it is an isolation interval. The process stops eventually, when only isolating intervals remain.
This isolating process may be used with any method for computing the number of real roots in an interval. Theoretical
complexity analysis and practical experiences show that methods based on
Descartes' rule of signs
In mathematics, Descartes' rule of signs, described by René Descartes in his ''La Géométrie'', counts the roots of a polynomial by examining sign changes in its coefficients. The number of positive real roots is at most the number of sign chang ...
are more efficient. It follows that, nowadays, Sturm sequences are rarely used for root isolation.
Application
Generalized Sturm sequences allow counting the roots of a polynomial where another polynomial is positive (or negative), without computing these root explicitly. If one knows an isolating interval for a root of the first polynomial, this allows also finding the sign of the second polynomial at this particular root of the first polynomial, without computing a better approximation of the root.
Let and be two polynomials with real coefficients such that and have no common root and has no multiple roots. In other words, and are
coprime polynomials. This restriction does not really affect the generality of what follows as
GCD computations allows reducing the general case to this case, and the cost of the computation of a Sturm sequence is the same as that of a GCD.
Let denote the number of sign variations at of a generalized Sturm sequence starting from and . If are two real numbers, then is the number of roots of in the interval
such that minus the number of roots in the same interval such that . Combined with the total number of roots of in the same interval given by Sturm's theorem, this gives the number of roots of such that and the number of roots of such that .
See also
*
Routh–Hurwitz theorem
In mathematics, the Routh–Hurwitz theorem gives a test to determine whether all roots of a given polynomial lie in the left-half complex plane. Polynomials with this property are called Hurwitz stable polynomials. The Routh–Hurwitz theorem ...
*
Hurwitz's theorem (complex analysis)
*
Descartes' rule of signs
In mathematics, Descartes' rule of signs, described by René Descartes in his ''La Géométrie'', counts the roots of a polynomial by examining sign changes in its coefficients. The number of positive real roots is at most the number of sign chang ...
*
Rouché's theorem
*
Properties of polynomial roots
*
Gauss–Lucas theorem
*
Turán's inequalities
References
*
*
*
*
*
*
*
*
*
*
*
*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.
{{DEFAULTSORT:Sturm's Theorem
Theorems in real analysis
Articles containing proofs
Theorems about polynomials
Computer algebra
Real algebraic geometry