Re: Motion 31: V04.2 Revision of proposed Level 1 text
Dan Zuras wrote:
In analogy to square(X), might also consider some
polynomial evaluation functions on the grounds that
real improvements are possible over the naive
polynomial expression. I don't know if there are
other things which make no difference in floating-
point but can be improved in intervals but I suspect
there are. Trot them out if you know them.
The mathematical algorithm to evaluate a polynomial in the fewest number of
arithmetic operations is Horner's rule. However, the Level 2 implementation
of this algorithm in floating point is very numerically unstable when the
polynomial coefficients vary greatly in magnitude.
This is why computer graphics and CAD industries use Bezier representations
of polynomials instead. The de Casteljau algorithm evaluates the Bezier
polynomial using just a few additional arithmetic operations than Horner's
rule. But unlike Horner's rule, de Casteljau is very numerically stable in
its Level 2 floating-point implementation. Particularly for applications in
CAD where numerical stability is paramount, this is another reason Bezier
and b-spline basis polynomials are de-facto standards.
For intervals, even without numerical instability problems, Horner's rule
can give very wide and pessimistic results due to all the unrecognized
interval dependence. The de Casteljau algorithm, on the other hand, can give
exceptionally narrow interval enclosures of even high-degree polynomials.
However that algorithm requires modal interval analysis and can't be
evaluated using classical interval arithmetic without doubling the amount of
required arithmetic operations. See, e.g., Chapter 6 of:
http://grouper.ieee.org/groups/1788/Material/Hayes_Modal%20Intervals.pdf
Nate