Computational Divided Differencing and Divided-Difference Arithmetics
Thomas W. Reps and Louis B. Rall
University of Wisconsin
Tools for computational differentiation transform a program that computes a numerical function F(x) into a related program that computes F'(x) (the derivative of F). This paper describes how techniques similar to those used in computational-differentiation tools can be used to implement other program transformations---in particular, a variety of transformations for computational divided differencing. The specific technical contributions of the paper are as follows:
/ F(x0) - F(x1) | ------------- if x0 != x1 | x0 - x1 F[x0,x1] = < | d | --F(z), evaluated at z = x0 if x0 = x1 \ dz
Finally, the paper describes how computational divided differencing relates to the numerical-finite-differencing techniques that motivated Robert Paige's work on finite differencing of set-valued expressions in SETL programs.
Dedicated to the memory of Robert Paige, 1947-1999.
(Click here to access the paper: PostScript, PDF.)