greg@jiff.berkeley.edu (Greg) (03/19/88)
In article <7748@alice.UUCP> td@alice.UUCP writes: >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) ... >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) Ok, you've convinced me. Both my formula (see a previous posting) and my argument about the equivalence of our formulas would be correct if I had instead p1(x) = -p'(x), and S(b)-S(a) instead of S(a)-S(b). In another posting, Richard Harter mentioned the advantages of the secant method over Newton's method. In my algorithm, where the roots are bracketed away from inflection points, the secant method is guaranteed to converge just like Newton's method, so the best strategy is to take one Newton's step from an endpoint (and incidentally, both the value of p(x0) and p'(x0), which are used in the Newton's step, have already been computed as part of the Sturm chain), and then continue with the secant method. td@alice.uucp also suggested that my method works too hard in the context of ray-tracing. That is sometimes correct. In the simplest case, a ray-tracer needs the smallest positive root only, and computations at neighboring pixels provide a good guess. However, there are many cases where information from neighboring pixels isn't helpful. It would be nice to have a test that gives a sufficient condition for Newton's method or the secant method to work directly from a given "good guess". Without prior knowledge of the positions of the roots, my method seems appropriate enough even if you just want the smallest positive root. Also, a fancy ray-tracer might have CSG modelling, which can model the intersection of two objects. For this to work properly, many roots are often needed. -- Greg