Xref: utzoo sci.math:3028 comp.graphics:1993
Path: utzoo!mnetor!uunet!husc6!uwvax!umn-d-ub!rutgers!bellcore!faline!thumper!ulysses!andante!alice!td
From: td@alice.UUCP
Newsgroups: sci.math,comp.graphics
Subject: Re: Solution of quartic equation
Message-ID: <7741@alice.UUCP>
Date: 15 Mar 88 19:04:50 GMT
References: <1656@thorin.cs.unc.edu> <7662@agate.BERKELEY.EDU>
Organization: AT&T Bell Laboratories, Murray Hill NJ
Lines: 44
Keywords: Sturm chains, Newton's method
Summary: method has 2 bugs



I believe that the Sturm chain algorithm as described in the referenced article
has at least two bugs.

The article describes sturm chains thus:
>  You take the polynomial p(x), which we may call
>p0(x), and you take its derivative, p1(x) = p'(x).  Now let pn(x)
>be the remainder obtained when you divide p{n-2}(x) by p{n-1}(x).
>Quit when you obtain a constant polynomial (the degree goes down
>by at least one every time).
Restating, this is
	p0(x)=p(x)
	p1(x)=p'(x)
	p[n+2](x)=p[n](x) mod p[n-1](x)
where a(x) mod b(x) is the remainder left after `synthetic division.'

This is incorrect.  Sturm chains have

	p[n+2](x)= -(p[n](x) mod p[n-1](x))

i.e. the sign of the remainders in jiff!greg's version must be flipped
for even n>2.

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]).  Verify this for yourself by
considering the case a=b where p(a)=0.  Second the method of counting
sign changes is subtly wrong.  It is possible for p[k](a) to be zero.
Any zeros in the sequence must be deleted before counting sign changes.

Another criticism of the method is that his numerical method for converging
to the root once it's isolated is over-elaborate.  Since the root is bracketed,
methods like regula falsi are guaranteed to converge, albeit slowly.
A good way to proceed is to take Newton steps starting at one end of the
interval, contracting the interval as you go.  If a Newton step takes you
outside the interval, or involves division by zero, take a regula falsi
step instead.