Xref: utzoo sci.math:3038 comp.graphics:2000 Path: utzoo!mnetor!uunet!husc6!tut.cis.ohio-state.edu!bloom-beacon!gatech!rutgers!gauss.rutgers.edu!math.rutgers.edu!bumby From: bumby@math.rutgers.edu (Richard Bumby) Newsgroups: sci.math,comp.graphics Subject: Re: Solution of quartic equation Message-ID: Date: 16 Mar 88 23:11:18 GMT References: <1656@thorin.cs.unc.edu> <7662@agate.BERKELEY.EDU> <7741@alice.UUCP> Reply-To: bumby@math.rutgers.edu (Richard Bumby) Organization: Rutgers Univ., New Brunswick, N.J. Lines: 49 Keywords: Sturm chains, Newton's method Summary: proofs are better than theorems In article <7741@alice.UUCP> td@alice.UUCP writes: > > >I believe that the Sturm chain algorithm as described >in the referenced article has at least two bugs. > >...(stuff omitted)... > p[n+2](x)= -(p[n](x) mod p[n-1](x)) >....(more stuff omitted)... >The article describes the method of counting roots on an interval [a,b] >as follows: >> Now let S(a) be the number of sign changes >>in the sequence p0(a),p1(a),...,pk(a), i.e. the number of times >>that pi(a) is positive and p{i+1}(a) is negative, or vice versa. >>Then the number of roots in the interval [a,b] is S(a)-S(b). > >This is wrong for two reasons: first, the interval must be open at >the bottom (i.e. (a,b], not [a,b]). >....(more stuff omitted)... The proof of Sturm's theorem, which you can find in lovely detail in Weber's "Algebra", makes clear why the method works and what the theorem really says. For example, the polynomial that you start with should have no multiple roots so that any Euclidean algorithm starting from these two polynomials will always have consecutive terms without common factor. Next, you observe what happens as you pass through a zero of any of the polynomials in your chain: the role of the sign change is to guarantee that p{i-1}(a) and p{i+1}(a) have opposit signs if pi(a) = 0. Thus, the number of changes of sign does not change, however you interpret the sign of 0. Finally, going through a zero of p from left to right is easily seen to always remove a change of sign between p and p'. The same method of proof gives "Descartes' rule of signs" and other related results. A thoroughly robust program must be able to handle the accidental discovery of the root of the polynomial, but the first version should be allowed to handle it in a sloppier fashion. Similarly, the decision of whether to use a rapid iterative solution once the root has been isolated can be postponed. It is sobering to realize that much more time is spent telling students why 'bisection' is a poor rootfinding method than would be spent in using it for all relevant problems in a numerical analysis course. -- --R. T. Bumby ** Math ** Rutgers ** New Brunswick ** (in one form or another for all kinds of mail)