Sturm's theorem: Difference between revisions
R. J. Mathar (talk | contribs) →References: 7 refs added |
|||
Line 88: | Line 88: | ||
==References== |
==References== |
||
* {{cite journal |
|||
*Chee Yap, [http://www.cs.nyu.edu/yap/book/berlin/ ''Fundamental Problems in Algorithmic Algebra''], Oxford University Press, 2000. ISBN 0-19-512516-9 |
|||
|first1=J. J. |
|||
|last1=Sylvester |
|||
|year=1853 |
|||
|title=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 |
|||
|journal=Phil. Trans. Roy. Soc. London |
|||
|volume=143 |
|||
|pages=407-548 |
|||
|jstor=108572 |
|||
}} |
|||
* {{cite journal |
|||
|first1=Joseph Miller |
|||
|last1=Thomas |
|||
|title=Sturm's theorem for multiple roots |
|||
|year=1941 |
|||
|journal=National Mathematics Magazine |
|||
|volume=15 |
|||
|number=8 |
|||
|pages=391-394 |
|||
|jstor=3028551 |
|||
|mr=0005945 |
|||
}} |
|||
* {{citation |
|||
|first1=Lee E. |
|||
|last1=Heindel |
|||
|title=Integer arithmetic algorithms for polynonial real zero determination |
|||
|journal=Proc. SYMSAC '71 |
|||
|year=1971 |
|||
|page=415 |
|||
|mr=0300434 |
|||
|doi=10.1145/800204.806312 |
|||
}} |
|||
* {{citation |
|||
|first1=George E. |
|||
|last1=Collins |
|||
|first2=Alkiviadis G. |
|||
|last2=Akritas |
|||
|title=Polynomial real root isolationusing Descarte's rule of signs |
|||
|year=1976 |
|||
|page=272 |
|||
|journal=Proc. SYMSAC '76 |
|||
|doi=10.1145/800205.806346 |
|||
}} |
|||
* {{cite journal |
|||
|first1=Don B. |
|||
|last1=Panton |
|||
|first2=William A. |
|||
|last2=Verdini |
|||
|title=A fortran program for applying Sturm's theorem in counting internal rates of return |
|||
|journal=J. Financ. Quant. Anal. |
|||
|year=1981 |
|||
|volume=16 |
|||
|number=3 |
|||
|pages=381-388 |
|||
|jstor=2330245 |
|||
}} |
|||
* {{cite journal |
|||
|title=Reflections on a pair of theorems by Budan and Fourier |
|||
|journal=Math. Mag. |
|||
|first1=Alkiviadis G. |
|||
|last1=Akritas |
|||
|mr=0678195 |
|||
|year=1982 |
|||
|volume=55 |
|||
|number=5 |
|||
|pages=292-298 |
|||
|jstor=2690097 |
|||
}} |
|||
* {{cite journal |
|||
|title=Multivariate Sturm theory |
|||
|journal=Lecture Notes in Comp. Science |
|||
|year=1991 |
|||
|volume=539 |
|||
|pages=318-332 |
|||
|mr=1229329 |
|||
|doi=10.1007/3-540-54522-0_120 |
|||
|first1=Paul |
|||
|last1=Petersen |
|||
}} |
|||
* {{cite book| |
|||
|first1=Chee |
|||
|last1=Yap |
|||
|url=http://www.cs.nyu.edu/yap/book/berlin/ |
|||
|title=Fundamental Problems in Algorithmic Algebra |
|||
|publisher=Oxford University Press |
|||
|year=2000 |
|||
|isbn=0-19-512516-9 |
|||
}} |
|||
==External links== |
==External links== |
Revision as of 19:38, 4 March 2012
This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. (March 2012) |
This article relies largely or entirely on a single source. (March 2012) |
In mathematics, Sturm's theorem yields a symbolic procedure to count the number of distinct real roots of a polynomial located in an interval. It was named for Jacques Charles François Sturm. Whereas the fundamental theorem of algebra readily yields the overall number of complex roots, counted with multiplicity, Sturm's theorem gives information about their location, albeit limited only to the real roots and without counting multiplicity.
Sturm chains
A Sturm chain or Sturm sequence is a finite sequence of polynomials
of decreasing degree with these following properties:
- is square free (no square factors, i.e., no repeated roots);
- if , then
- if for then
- does not change its sign.
To obtain a Sturm chain, Sturm himself proposed to choose the intermediary results when applying Euclid's algorithm to p and its derivative:
That is, successively take the remainders with polynomial division and change their signs. Since for , the algorithm terminates. The final polynomial, pm, is the greatest common divisor of p and its derivative. If p is square free, it shares no roots with its derivative, hence pm will be a non-zero constant polynomial. The Sturm chain, called the canonical Sturm chain, then is
If p is not square-free, this sequence does not formally satisfy the definition of a Sturm chain above, nevertheless it still satisfies the conclusion of Sturm's theorem (see below).
Statement
Let be a Sturm chain, where p is a square-free polynomial, and let σ(ξ) denote the number of sign changes (zeroes are not counted) in the sequence
Sturm's theorem then states that for two real numbers a < b, the number of distinct roots of p in the half-open interval (a,b] is σ(a) − σ(b).
The non-square-free case
Let be the canonical Sturm sequence of a polynomial p, not necessarily square-free. Then σ(a) − σ(b) is the number of distinct roots of p in (a,b] whenever a < b are real numbers such that neither a nor b is a multiple root of p.
Proof
Polynomials are continuous functions, and any sign change must occur at a root, so consider the behavior of a Sturm chain around the roots of its constituent polynomials.
First, note that two adjacent polynomials can share a common root only when it is a multiple root of p (in which case it is a root of every pi). Indeed, if pi and pi−1 are both zero at , then pi+1 also have to be zero at , since . The zero then propagates recursively up and down the chain, so that is a root of all the polynomials p0, ..., pm.
Next, consider roots of polynomials in the interior (i.e., ) of the Sturm chain that are not multiple roots of p. If , then we know from the previous paragraph that and . Furthermore, , so in the vicinity of we've got a single sign change across pi−1, pi, pi+1. In other words, sign changes in the interior of the Sturm chain do not affect the total number of sign changes across the chain.
So only roots of the original polynomial, at the top of the chain, can affect the total number of sign changes. Consider a root Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle \xi} , so , and assume first that it is a simple root. Then p's derivative, which is p1, must be non-zero at , so p must be either increasing or decreasing at . If it's increasing, then its sign is changing from negative to positive as we move from left to right while its derivative (again, p1) is positive, so the total number of sign changes decreases by one. Conversely, if it's decreasing, then its sign changes from positive to negative while its derivative is negative, so again the total number of sign changes decreases by one.
Finally, let be a multiple root of p, and let p0, ..., pm be the canonical Sturm chain. Let d = gcd(p,p'), q = p/d, and let q0, ..., qm' be the canonical Sturm chain of q. Then m = m' and pi = qid for every i. In particular, σ(x) is the same for both chains whenever x is not a root of d. Then the number of sign changes (in either chain) around decreases by one, since is a simple root of q.
In summary, only sign changes at roots of the original polynomial affect the total number of sign changes across the chain, and the total number of sign changes always decreases by one as we pass a root. The theorem follows directly.
Applications
Bounds
This can be used to compute the total number of real roots a polynomial has (to use, for example, as an input to a numerical root finder) by choosing a and b appropriately. For example, a bound due to Cauchy says that all real roots of a polynomial with coefficients ai are in the interval [−M, M], where
Alternatively, we can use the fact that for large x, the sign of
is , whereas is .
In this way, simply counting the sign changes in the leading coefficients in the Sturm chain readily gives the number of distinct real roots of a polynomial.
We can also determine the multiplicity of a given root, say ξ, with the help of Sturm's theorem. Indeed, suppose we know a and b bracketing ξ, with σ(a) − σ(b) = 1. Then, ξ has multiplicity k precisely when ξ is a root with multiplicity k − 1 of pm (since it is the GCD of p and its derivative).
Quotient
The remainder is needed to compute the chain using Euclid's algorithm. For two polynomials and this is accomplished (for non-vanishing ) by
where the quotient is built solely of the first two leading coefficients.
Generalized Sturm chains
Let ξ be in the compact interval [a,b]. A generalized Sturm chain over [a,b] is a finite sequence of real polynomials (X0,X1,…,Xr) such that:
- X(a)X(b) ≠ 0
- sign(Xr) is constant on [a,b]
- If Xi(ξ) = 0 for 1 ≤ i ≤ r−1, then Xi−1(ξ)Xi+1(ξ) < 0.
One can check that each Sturm chain is indeed a generalized Sturm chain.
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
- 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, p. 416–422, 1990.
References
- 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. Roy. Soc. London. 143: 407–548. JSTOR 108572.
- Thomas, Joseph Miller (1941). "Sturm's theorem for multiple roots". National Mathematics Magazine. 15 (8): 391–394. JSTOR 3028551. MR 0005945.
- Heindel, Lee E. (1971), "Integer arithmetic algorithms for polynonial real zero determination", Proc. SYMSAC '71: 415, doi:10.1145/800204.806312, MR 0300434
- Collins, George E.; Akritas, Alkiviadis G. (1976), "Polynomial real root isolationusing Descarte's rule of signs", Proc. SYMSAC '76: 272, doi:10.1145/800205.806346
- 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. JSTOR 2330245.
- Akritas, Alkiviadis G. (1982). "Reflections on a pair of theorems by Budan and Fourier". Math. Mag. 55 (5): 292–298. JSTOR 2690097. MR 0678195.
- Petersen, Paul (1991). "Multivariate Sturm theory". Lecture Notes in Comp. Science. 539: 318–332. doi:10.1007/3-540-54522-0_120. MR 1229329.
- Yap, Chee (2000). Fundamental Problems in Algorithmic Algebra. Oxford University Press. ISBN 0-19-512516-9.
{{cite book}}
: Cite has empty unknown parameter:|1=
(help)
External links
- C code from Graphic Gems by D.G. Hook and P.R. McAree.