Higher-Order and Symbolic Computation, 16(1/2)93-149
Computational Divided Differencing and Divided-Difference ArithmeticsThomas W. Reps, Computer Science Department, University of Wisconsin, 1210 W. Dayton St., Madison, WI 53706, USA
Louis B. Rall, Department of Mathematics, University of Wisconsin, 480 Lincoln Dr., Madison, WI 53706, USA
|
Abstract: 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: -- It presents a program transformation that, given a numerical function F(x) defined by a program, creates a program that computes F[x0, x1], the first divided difference of F(x), where F[x_0,x_1] =def d/dz F(z) evaluated at z = x_0, if x_0 = x_1 - It shows how computational first divided differencing generalizes computational differentiation. - It presents a second program transformation that permits the creation of higher-order divided differences of a numerical function defined by a program. - It shows how to extend these techniques to handle functions of several variables. The paper also discusses how computational divided-differencing techniques could lead to faster and/or more robust programs in scientific and graphics applications. 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. Keywords: divided differences, computational differentiation, interpolation, multivariate interpolation, program transformation, round-off error |
This article can be downloaded [here].