Computational Divided Differencing and Divided-Difference Arithmetics |
| |
| Authors: | Reps Thomas W Rall Louis B |
| |
| Affiliation: | (1) Computer Science Department, University of Wisconsin, 1210 W. Dayton St., Madison, WI 53706, USA;(2) 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 Fx
0, x
1], the first divided difference of F(x), where
![$$F\left {x_0 ,x_1 } \right]\mathop = \limits^{def} \left\{ {\begin{array}{*{20}c} {\frac{{F\left( {x_0 } \right) - F\left( {x_1 } \right)}}{{x_0 - x_0 }}{\text{ }}} \\ {\frac{d}{{dz}}F\left( z \right),\operatorname{evaluatedatz} = x_0 } \\ \end{array} } \right.\begin{array}{*{20}c} {\operatorname{if} x_0 \ne x_1 } \\ {} \\ {\operatorname{if} x_0 = x_1 } \\ \end{array}$$](/content/p718q26052335227/10990_2004_Article_5119119_TeX2GIFIE1.gif)
– 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 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
