1、確定實根的個數定理：設a,b均非f(x)的零點，以為基的sturm多項式序列在（a,b）內任一點x的變號數為V(x),則方程f(x)=0在（a,b）內共有V(a)-V(b)個相異的實根。若sturm序列的最后非零函數沒有實零點，則f(x)=0的實根均為單根；若有實零點，則這些根都是f(x)=0的重根，其重數為的零點重數加1.(引自1P192)證明：1) 單根 對于有重根的多項式方程f(x)，通過得到只有單根的多項式方程。構造sturm序列：設，且在（a，b）上無重根，則以為基按“負輾轉相除法”生成如下序列： （余式的次數越來越小，故必有此式出現。）注意：構造sturm序列中，可以對任意個乘以一

2、個正數而不改變結果，故構造過程中避免分數的出現。則該序列具有如下性質：1. 在（a，b）內無實根。否則必有重根。2. 當存在，。可以直接從序列式中推出。3. 相鄰兩個多項式在區間（a,b）內無公共零點。否則與（1）矛盾。4. 可能有重根。推理 1) 根據多項式的連續性，多項式只有經過零點符號（，）才（當i>1時，可能）發生變化。2) 當i>0 時，設，則符號變化情況為符號組合方向符號變化數是否變化1/11>否2/11>否 表11 符號變化情況（i>0）（當i1時，只能為“”或“”，當i>1時，可能為“”或“”或“”或“”）3) 當i=0時，設，則符號變化情況

3、為符號組合符號變化數是否變化110>是210>是表12 符號變化情況（i>0）總上，只有在的零點，sturm序列的符號變化次數才發生變化，即證。2) 重根1) 對于非零點的零點，取零點的一個鄰域做為研究對象，相對于上述證明過程中給所有的sturm序列都乘一個大小不定、符號確定的數，故符號變化情況不變。2) 對于零點的零點，由sturm序列知必有同樣的零點，且有比次數高一階的零點。下面將要確定零點對過程（1）計算零點有無影響？它計算出的零點中包括零點的沒？這種情況下，相當于在（1）中的sturm序列中都乘一個類似于的因子，這樣無論在上述（1）的i>0還是i=0變化情況都不

4、變。例如i=0時，、，無論變成、還是、還是、，符號變化次數均減少一次。 i>0時，、無論變成、還是、還是、，符號變化次數均為1次。 根本原因在于無論在零點的前還是后，相對（1），只是乘了同一個符號因子（在前與后乘的因子的大小和符號可能不一樣）。綜上，對于任意多項式，可根據上述定理直接運用sturm序列來判斷實根的個數。參考文獻：1 數值計算 周國標 宋寶瑞 謝建利 高等教育出版社 2008附錄：英文原版證明sturm 定理proof of Sturm's theorem (idea)（1）The proof of Sturm's theorem is of less in

5、terest than the theorem itself. While the theorem is interesting for its applications (in logic, in some calculations) and for its novelty, the proof is interesting due to the weird and wonderful mixture of algebra and elementary real analysis to get at the desired result. The mixture is almost inev

6、itable, given its echoes in the formulation of the theorem. This proof uses the concepts and terminology of the theorem; why not read it first? Let P(x) be a real separable polynomial, and let P0(x)=P(x), P1(x)=P'(x), . be its Sturm chain and N(x) be the number of sign changes in the chain at po

7、int x. To prove that the number of roots in an interval a,b with P(a),P(b)0 is N(a)-N(b), we need to show that N(x) is constant except at roots of P, and that it decreases by one at each root. Lemma. For any t, the Sturm chain cannot have two consecutive zeroes at t. Proof. We prove by induction on

8、i that Pi-1(t) and Pi(t) cannot both be zero. For i=1: P0(x)=P(x) and P1(x)=P'(x). By our assumption that P(x) is separable (see Noether's writeup there), P(x) and P'(x) have no common factor. In particular, if P(t)=P'(t)=0 then x-t is a common factor (and therefore t is a root with

9、multiplicity >1 and P(x) is not separable). Thus P0(t) and P1(t) cannot both be 0. For i>1: Suppose we had Pi(t)=Pi+1(t)=0. We know that Pi-1(x) = q(x)Pi(x) - Pi+1(x),      (*) so then Pi-1(t)=0 too, contrary to the induction hypothesis. To prove the theorem, imagine a left

10、 to right sweep of the real number line. Polynomials are continuous functions, so clearly N(x) cannot change except when passing through a root of one of the Pi(x)'s. We need to show it decreases by 1 for a root of P0(x), and stays constant for a root of Pi(x), i>0. When P(a)=P0(a)=0: If P(x)

11、 switches from being positive to being negative when passing through a, then it is (locally) decreasing there, and P'(x)<0 in the neighborhood of a (recall that - by our lemma - P'(a)0). Thus, the chain of signs switches from "+-." to "-." when passing through a, so N

12、decreases by 1. If P(x) switches from being negative to being positive at a, then it is (locally) increasing there, and P'(x)>0 near a. This time the sign of the chain switches from "-+." to "+.", and again N decreases by 1 when passing through a. The value of N at a itsel

13、f is of no interest, as the theorem specifically does not apply there when one of the endpoints is a root. When Pi(a)=0, i>0: From (*) we have that Pi-1(a) = 0 - Pi+1(a), and from the lemma we know that Pi-1(a), Pi+1(a) 0. So, passing through a, the chain of signs either switches from ".+-.&

14、quot; to ".+-.", or from ".+-." to ".+-.", or from ".-+." to ".-+.", or from ".-+." to ".-+". Each of these patterns of signs contributes exactly one sign change. So the total number of sign changes remains the same, passing throu

15、gh a. Even at a, the pattern of signs is ".-0+." or ".+0-.", and contributes one sign change. So N(x) is constant in the neighborhood of a. That's it! A little mixture of real analysis and algebra, and Sturm's theorem is proved. proof of Sturm's theorem (idea)（2）Newsg

16、roups: sci.math.num-analysisFrom: hbaker (Henry G. Baker)Subject: FAQ: # real poly roots in an interval, perhaps (oo,oo)Date: Wed, 7 Feb 1996 17:03:43 GMTSummary: Sturm chains/sequences, gcd-with-multipliers(p(x),p'(x)From "100 Great Problems of Elementary Mathematics: Their History andSolu

17、tion", by Heinrich Doerrie, translated by David Antin, Dover,1965. ISBN 0-486-61348-8.24. Sturm's Problem of the Number of Roots"Find the number of real roots of an algebraic equation with realcoefficients over a given interval".This very important algebraic problem was solved in

18、a surprisinglysimple way in 1829 by the French mathematician Charles Sturm(1803-1855). The paper containing the famous Sturm theorem appearedin the eleventh volume of the Bulletin des sciences de Ferussac andbears the title, "Memoire sur la resolution des equations numeriques.""With t

19、his discovery," says Liouville, "Sturm at once simplified andperfected the elements of algebra, enriching them with new results."SOLUTION. We distinguish two cases:I. The real roots of the equation in question are all simple over thegiven interval.II. The equation also possesses multi

20、ple real roots over the interval.We will first show that the second case leads us back to the first.Let the prescribed equation F(x)=0 have the distinct roots alpha,beta, gamma, ., and let the root alpha be a-fold, beta b-fold, gammac-fold, ., so thatF(x) = (x-alpha)a (x-beta)b (x-gamma)c .For the d

21、erivative F'(x) of F(x) we obtainF'(x)/F(x) = a/(x-alpha) + b/(x-beta) + c/(x-gamma) + . a(x-beta)(x-gamma)(x-delta).+b(x-alpha)(x-gamma)(x-delta).+. = - (x-alpha)(x-beta)(x-gamma).If we then call the numerator of this fraction p(x) and thedenominator q(x) and set the whole rational function

22、 F(x)/q(x) equalto G(x), thenF(x) = G(x) q(x) and F'(x) = G(x) p(x).Now the functions p(x) and q(x) have no common divisor. (The factorx-beta of q(x) may, for example, go into all the terms of p(x) exceptthe second with no remainder.) It follows from this that G(x) is thegreatest common divisor

23、of F(x) and F'(x). This can be determinedeasily from the divisional algorithm and can therefore be consideredknown, as a result of which q(x) is known also.The equation F(x)=0 then falls into the two equationsq(x)=0 and G(x)=0,the first of which possesses only simple roots, while the second canb

24、e further reduced in the same way that F(x)=0 was.An equation with multiple roots can therefore always be transformedinto equations (with known coefficients) possessing only simple roots.Consequently, it is sufficient to solve the problem for the firstcase.Let f(x)=0 be an algebraic equation all of

25、whose roots are simple.The derivative f'(x) of f(x) then vanishes for none of these roots andthe highest common divisor of the functions f(x) and f'(x) is aconstant K that differs from zero. We use the divisional algorithm todetermine the highest common divisor of f(x) and f'(x), writing

26、, forthe sake of convenience in representation, f0(x) and f1(x) instead off(x) and f'(x), and calling the quotients resulting from thesuccessive divisions q0(x), q1(x), q2(x), . and the remainders-f2(x), -f3(x), .If we also drop the argument sign for the sake of brevity, we obtain thefollowing s

27、cheme:(0) f0 = q0 f1 - f2(1) f1 = q1 f2 - f3(2) f2 = q2 f3 - f4, etc.In this scheme there must at last appear - at the very latest withthe remainder K - a remainder -fs(x) that does not vanish at anypoint of the interval and consequently possesses the same sign overthe whole interval. Here we break

28、off the algorithm. The functionsinvolvedf0, f1, f2, ., fsform a "Sturm chain" and in this connections are called Sturm functions.The Sturm functions possess the following three properties:1. Two neighboring functions do not vanish simultaneously at anypoint of the interval.2. At a null poi

29、nt of a Sturm function its two neighboring functionsare of different sign.3. Within a sufficiently small area surrounding a zero point off0(x), f1(x) is everywhere greater than zero or everywhere smallerthan zero.PROOF OF 1. If, for example, f2 and f3 vanish at any point of aninterval, f4 according

30、to (2) also vanishes at this point, andconsequently f5 also according to (3), and so forth, so that finallyaccording to the last line of the algorithm fs also vanishes, which,however, contradicts our assumption.PROOF OF 2. If the function f3 vanishes at the point sigma, forexample, of the interval,

31、then it follows from (2) thatf2(sigma) = -f4(sigma).PROOF OF 3. This proof follows from the known theorem: A functionf0(x) rises or falls at a point depending on whether its derivativef1(x) at that point is greater or smaller than zero.We now select any point x of the interval, note the sign of the

32、valuesf0(x), f1(x), ., fs(x), and obtain a "Sturm sign chain" (to obtainan unequivocal sign, however, it must be assumed that none of thedesignated s+1 function values is zero). The sign chain will containsign sequences (+ and -) and sign changes (+- and -+).We will consider the number Z(x

33、) of sign changes in the sign chain andthe changes undergone by Z(x) when x passes through the interval. Achange can occur only if one or more of the Sturm functions changessign, i.e., passes over from negative (positive) values through zeroto positive (negative) values. We will accordingly study th

34、e effectproduced on Z(x) by the passage of a function fv(x) through zero.Let k be a point at which fv disappears, h a point situated to theleft, and l a point to the right of k and so close to k that over theinterval h to l the following holds true:(1) fv(x) does not vanish except when x=k;(2) every

35、 neighbor (fv+1,fv-1) of fv does not change sign.We must distinguish between the cases v>0 and v=0; in the first casewe are concerned with the triplet fv-1, fv, fv+1, in the second, withthe pair f0, f1.In the triplet, fv-1 and fv+1 possess either the + and - sign or the -and + sign at all three p

36、oints h, k, l. Thus, whatever the sign of fvmay be at these points, the triplet possesses one change of sign foreach of the three arguments h, k, l. The passage through zero of thefunction fv does not change the number of sign changes in the chain!In the pair, f1 has either the + or - sign at all th

37、ree points h, k,l. In the first case, f0 is increasing and is thus negative at h andpositive at l. In the second case, f0 is decreasing and is positiveat point h, and negative at l. In both cases a sign change is lost.From our investigation we learn that: The Sturm sign chain undergoes achange in th

38、e number of sign changes Z(x) only when x passes through anull point of f(x); and specifically, the chain then loses (with anincreasing x) exactly one sign change. Thus, if x passes through theinterval (the ends of which do not represent roots of f(x)=0) fromleft to right, the sign chain loses exact

39、ly as many sign changes asthere are null points of f(x) within the interval.Result:STURM'S THEOREM: The number of real roots of an algebraic equationwith real coefficients whose real roots are simple over an intervalthe end points of which are not roots is equal to the differencebetween the numb

40、ers of sign changes of the Sturm sign chains formedfor the interval ends.NOTE. The same considerations can also be applied unchanged to theseries formed when we multiply f0, f1, f2, ., fs by any positiveconstants; this series is then likewise designated as a Sturm chain.In the formation of the Sturm

41、 function chain all fractionalcoefficients are accordingly avoided.EXAMPLE 1. Determine the number and situation of the real roots ofthe equation x5 - 3 x - 1 = 0.The Sturm chain isf0 = x5 - 3 x - 1,f1 = 5 x4 - 3,f2 = 12 x + 5,f3 = 1.The signs of f for x = -2, -1, 0, +1, +2 are- x | f0 | f1 | f2 | f

42、3-2 | - | + | - | +-1 | + | + | - | + 0 | - | - | + | +1 | - | + | + | +2 | + | + | + | +-The equation thus has three real roots: one between -2 and -1, onebetween -1 and 0, one between +1 and +2. The other two roots arecomplex.EXAMPLE 2. Determine the number of real roots of the equationx5-ax-b=0 w

43、hen a and b are positive magnitudes and44 a5 > 55 b4.The Sturm chain readsx5-ax-b,5x4-a,4ax+5b,44 a5 - 55 b4.For the values x = -oo - infinity and +oo it has the signs -+-+ and+, respectively. The equation has three real roots and two complexroots.EOF=From: rjohnson (Robert Johnson)Newsgroups: sc

44、i.math.num-analysis,sci.mathSubject: Re: Q Polynomial root interval estimation .Date: 8 Feb 1996 19:39:42 -0800In article <SHREINER.96Jan26143025timon.cam-ani.co.uk>,Dave Shreiner <shreiner> wrote:> In a book on ray tracing, the author made reference to something I>believe called &

45、quot;Sturm sequences", which could be used to generate intervals>in which roots of a polynomial reside in . or at least that's the>impression that I got. Could someone please point me to some additional>resources or give the cocktail-napkin explanation?Sturm sequences are used to f

46、ind how many real roots of a polynomial Plie between two real numbers. By dividing P by gcd(P,P'), we can reduceall multiple roots to simple roots. Therefore, assume that P has onlysimple roots.Generate the sequence of polynomials P_k as follows: P_0 = P P_1 = P' P_k = -(P_k-2 mod P_k-1) for

47、 k>1 1Except for the sign change, 1 is the polynomial Euclidean Algorithm.Therefore, the last polynomial in the sequence is a constant polynomialbecause P and P' are relatively prime. Furthermore, for k>0, if P_k(x) = 0, then P_k+1(x) = -P_k-1(x) 2This means that if P_k(x) = P_k-1(x) = 0,

48、then P is identically 0.Assume this is not the case.Now, define Sturm(P,x) to be the number of sign changes in the sequence P_k(x) . The only place where Sturm(P,x) can change is where one ofthe P_k vanishes. However, for k>0, 2 says that if P_k(x) = 0, thenP_k+1(x) and P_k-1(x) have opposite sig

49、ns. Therefore, no matter howP_k behaves near x, it provides no change in Sturm(P,x).Thus, only where P (P_0) vanishes can Sturm(P,x) change. If P increasesthrough 0 at x, then P' (P_1) is positive; thus, Sturm(P,x) decreases by1. If P decreases through 0 at x, then P' is negative; thus, Stur

50、m(P,x)decreases by 1 again. Thus, Sturm(P,x) decreases by 1 at every root ofP. Thus, assuming neither P(x) nor P(y) is 0, the number of roots of Pin x,y is given by Sturm(P,x) - Sturm(P,y) 3Rob JohnsonApple Computer, Inc.rjohnson=From: rjohnson (Robert Johnson)Newsgroups: sci.math.num-analysis,sci.m

51、athSubject: Re: Determining if the Roots of a Quartic are RealDate: 9 Feb 1996 03:13:00 -0800In article <4fa4j3$4>,Matthew Brenneman <> wrote:>I am working with a quartic eqn having the general form:>> x4 + a3 x3 + a2 x2 + a1 x + a0 = 0>>

52、;What I need to know is: IF all of the roots are real> THEN is there some condition that the> coefficients have to satisfy?Use Sturm sequences to count the number of real roots. Strictly speaking,Sturm sequences only work for polynomials with simple roots, but dividinga polynomial P by gcd(P,P

53、') reduces all multiple roots to simple ones.If all roots of P/gcd(P,P') are real then all roots of P are real.Here is a copy of an article on Sturm sequences that I just posted tosci.math and sci.math.num-analysis.previous article quoted; now deleted - djrBy looking at the degree and sign of the highest order term in each P_k,we can compute Sturm(P,-oo) - Sturm(P,+oo) which is the