确定实根的个数

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