Xref: utzoo sci.math:3055 comp.graphics:2009
Path: utzoo!mnetor!uunet!husc6!mailrus!umix!umich!mibte!gamma!ulysses!andante!alice!td
From: td@alice.UUCP
Newsgroups: sci.math,comp.graphics
Subject: Re: Real solutions of quartic [and higher polynomial] equation
Message-ID: <7748@alice.UUCP>
Date: 17 Mar 88 15:05:27 GMT
References: <1656@thorin.cs.unc.edu> <7662@agate.BERKELEY.EDU> <7741@alice.UUCP> <7735@agate.BERKELEY.EDU>
Organization: AT&T Bell Laboratories, Murray Hill NJ
Lines: 44
Keywords: Sturm chains, Newton's method
Summary: effect not trivial

greg@skippy claims that the sequence
	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.'
is an adequate sequence for use in applying Sturm's theorem.
I claimed that it was not, but that
	p0(x)=p(x)
	p1(x)=p'(x)
	p[n+2](x)=-p[n](x) mod p[n-1](x)
greg@skippy followed this up, claiming:
>Given that the purpose of computing the chain is to compute S(a)-S(b),
>where S(x) is the number of sign changes in the chain evaluated at x,
>your modification has a trivial effect on the algorithm.  The new
>number of sign changes is S'(x) = k - S(x), where k is the length of 
>the chain, and therefore S'(b) - S'(a) = S(a) - S(b).
This is untrue for two reasons.  First, I do not claim that S'(b)-S'(a)
is the correct formula.  The correct formula is S'(a)-S'(b).  Second,
the modification does not have the claimed trivial effect.  Rather it
corrects an incorrect method.  I will give an example:
Let p(x)=x^2-x.  This has roots 0 and 1.  According to greg@skippy, a Sturm
sequence for this polynomial and its values at a=-1 and b=2 are:

	p[i](x)		p[i](-1)	p[i](2)
	x^2-x		2		2
	2*x-1		-3		3
	-1/4		-1/4		-1/4
So, S(a)=1 and S(b)=1, yielding S(a)-S(b)=0.  But p(x) has two roots
on the interval (-1,2].

According to me, a Sturm sequence for this polynomial
and its values at a=-1 and b=2 are:
	p[i](x)		p[i](-1)	p[i](2)
	x^2-x		2		2
	2*x-1		-3		3
	1/4		1/4		1/4
In this case, S'(a)=2 and S'(b)=0, so S'(a)-S'(b)=2, as required.

My previous criticism of greg@skippy's numerical methods was based on
not-too-careful reading of his posting.  If you are interested in finding
all real roots of a polynomial, then his method is endorsable.  In a ray-tracing
situation, we are interested in finding the smallest positive root, in which
case I believe his method to be overkill.  I have not implemented it, so
that is an opinion.