Algorithmic Differencing
An algorithmic representation of a function is a step-by-step specification of its evaluation in terms of known operations and functions, such as a computer program. In addition to function values, the algorithmic representation can be used to compute rel
- PDF / 1,326,820 Bytes
- 14 Pages / 481.92 x 691.68 pts Page_size
- 70 Downloads / 218 Views
*
University of Wisconsin-Madison, Madison WI 53706, USA. 1 ralllDmath. wise. edu 2 repsGes.wise.edu Abstract. An algorithmic representation of a function is a step-by-step specification of its evaluation in terms of known operations· and functions, such as a computer program. In addition to function values, the algorithmic representation can be used to compute related quantities such as derivatives of the function. A process similar to automatic (or algorithmic) differentiation will be applied to obtain differences and divided differences of functions. Advantages of this approach are that it often reduces the sometimes catastrophic cancellation errors in computation of differences and divided differences and provides numerical convergence of divided differences to derivatives.
1
Algorithmic Representation of Functions
An algorithmic representation Rf of a function f is a step-by-step specification of evaluation of f(x) for given x in terms of previously defined operations and functions. Typically, application of Rf will result in a sequence of values
(1) where tl = gl (x), and the value at the kth step (2)
is well-defined in terms of the values at one or more of the previous steps, and tn = f(x). Possible dependence of n = n(x) on x will be suppressed for simplicity of notation. Examples of algorithmic representations are entire or parts of computer programs, which will be referred to simply as routines for f(x). Numerical routines consist of arithmetic operations and evaluation of standard (or library) functions, and may include loops and branches. It is assumed that a routine Rf for evaluation of f will give the exact value of f(x) if performed in * Supported in part by the National Science Foundation under grants CCR-
9625667, CCR-9619219, and CCR-9986308, by the United States-Israel Binational Science Foundation under grant 96-00337, by the Office of Navel Research under contract N00014-00-1-0607, by the Alexander von Humboldt Foundation, and by the John Simon Guggenheim Memorial Foundation.
U. Kulisch et al., Perspectives on Enclosure Methods © Springer-Verlag/Wien 2001
134
L. B. RaIl and T. W. Reps
exact arithmetic, or at least a sufficiently accurate approximation to f(x) in case exact evaluation requires an infinite number of steps. Here, "sufficiently accurate" is a problem specific and user defined concept which could range from exactness to just the correct sign of the result. With this in mind, it will be convenient to refer to the result of executing the routine RJ as f(x).
2
Transformation of Algorithms
Often, values (}f(x) are required in addition to values of f(x), where {} is some operator. For this purpose, transformation of an algorithmic representation RJ of f into a corresponding algorithmic representation {}RJ = RaJ is sought. For example, this can be done if a (generalized) chain rule holds for the functions in (2),
so if both tl and {}tl = (}gdx) are known, then (}f(x) = tn. This forward mode transformation generates the algorithmic representation
(4) for {}f in a step-by-s
Data Loading...
