Indefinite integration with validation

ABSTRACT

We present an overview of two approaches to validated one-dimensional indefinite integration. The first approach is to find an inclusion of the integrand, then integrate this inclusion to obtain an inclusion of the indefinite integral. Inclusions for the integrand may be obtained from Taylor polynomials, Tschebyscheff polynomials, or other approximating forms which have a known error term. The second approach finds an inclusion of the indefinite integral directly as a linear combination of function evaluations plus an interval-valued error term. This requires a self-validating form of a quadrature formula such as Gaussian quadrature. In either approach, composite formulae improve the accuracy of the inclusion. The result of the validated indefinite integration is an algorithm which may be represented as a character string, a subroutine in a high-level programming language such as Pascal-SC or Fortran, or as a collection of data. An example is given showing the application of validated indefinite integration in constructing a validated inclusion of the error function, erf(x).

REFERENCES

• 1: CAPRANI, O., MADSEN, K., AND RALL, L.B. Integration of interval functions. SIAM J. Math. Anal. 12, (1981), 321-341.
• 2: B. F. Caviness, Computer algebra: past and future, Journal of Symbolic Computation, v.2 n.3, p.217-236, Sept. 1986 [doi>10.1016/S0747-7171(86)80025-6]
• 3: Bruce W. Char , Gregory J. Fee , Keith O. Geddes , Gaston H. Gonnet , Michael B. Monagan, A tutorial introduction to Maple, Journal of Symbolic Computation, v.2 n.2, p.179-200, June 1986 [doi>10.1006/jsco.1995.1045]
• 4: G W Cherry, Integration in finite terms with special functions: the error function, Journal of Symbolic Computation, v.1 n.3, p.283-302, September 1985 [doi>10.1006/jsco.1994.1018]
• 5: George F. Corliss , L. B. Rall, Adaptive, self-validating numerical quadrature, SIAM Journal on Scientific and Statistical Computing, v.8 n.5, p.831-847, September 1, 1987 [doi>10.1137/0908069]
• 6: DAVIS, P. J., AND RABINOWITZ, P. Methods of Numerical Integration. Academic Press, Orlando, Fla., 1975.
• 7: J Fitch, Solving algebraic problems with REDUCE, Journal of Symbolic Computation, v.1 n.2, p.211-227, June 1985 [doi>10.1006/jsco.1993.1015]
• 8: IBM CORPORATION A CRITH High Accuracy Subroutine Library: General information Manual, GC33-6163-02. IBM, BSblingen, West Germany, 1986.
• 9: KAUCHER, E., AND MIRANKER, W.L. Self-Validating Numerics for Function Space Problems: Computation with Guarantees/or Differential and Integral Equations. Academic Press, Orlando, Fla., 1984.
• 10: Gershon Kedem, Automatic Differentiation of Computer Programs, ACM Transactions on Mathematical Software (TOMS), v.6 n.2, p.150-165, June 1980 [doi>10.1145/355887.355890]
• 11: KRENZ, G.S. Computing inclusions of the gamma function and its derivatives. Tech. Rep. 259, Marquette Univ., Dept. of Mathematics, Statistics, and Computer Science, Milwaukee, Wisc., 1987.
• 12: KULISCH, U., Ed. Pascal-SC Manual and System Disks. Wiley-Teubner, Stuttgart, 1986.
• 13: J. N. Lyness , J. J. Kaganove, Comments on the Nature of Automatic Quadrature Routines, ACM Transactions on Mathematical Software (TOMS), v.2 n.1, p.65-81, March 1976 [doi>10.1145/355666.355671]
• 14: MOORE, R.E. Interval Analysis. Prentice-Hall, Englewood Cliffs, New Jersey, 1966.
• 15: Robert E. Moore, Two-sided Approximation to Solutions of Nonlinear Operator Equations - a Comparison of Methods from Classical Analysis, Functional Analysis, and Interval Analysis, Proceedings of the International Symposium on Interval Mathemantics, p.31-47, May 20-24, 1975
• 16: Ramon E. Moore , Fritz Bierbaum, Methods and Applications of Interval Analysis (SIAM Studies in Applied and Numerical Mathematics) (Siam Studies in Applied Mathematics, 2.), Soc for Industrial & Applied Math, 1979
• 17: PIESSENS, R., DE DONCKER-KAPENGA, E., UBERHUBER, C. W., AND KAHANER, D.K. QUAD- PACK: A Subroutine Package for Automatic Integration. Springer Series in Computational Mathematics, 1, Springer-Verlag, New York, 1983.
• 18: RALL, L.B. Automatic Differentition: Techniques and Applications. Springer Lecture Notes in Computer Science, 120, Springer-Verlag, New York, 1981.
• 19: RAND, R. H. Computer Algebra in Applied Mathematics: An Introduction to MACSYMA. Pitman, Marshfield, Mass., 1983.
• 20: RISCH, R.H. The problem of integration in finite terms. Trans. Am. Math. Soc. 139 (1969), 167-189.
• 21: RISCH, R.H. The solution of the problem of integration in finite terms. Bull. Am. Math. Soc. 76 (1970), 605-608.
• 22: ROYDEN, H.L. Real Analysis. 2nd ed. MacMillan, Toronto, 1968.
• 23: STROUD, J. R., AND SECREST, D. Gaussian Quadrature Formulas. Prentice-Hall, Englewood Cliffs, N.J., 1966.
• 24: Robert S. Sutor, The Scratchpad II Computer Algebra Language and System, Research Contributions from the European Conference on Computer Algebra-Volume 2, p.32-33, April 01-03, 1985

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Chebyshev approximation and theory; Elementary function approximation

General Terms:
Algorithms, Theory