A probabilistic theory for error estimation in automatic integration
type: Item
instance of: scholarly article
title: A probabilistic theory for error estimation in automatic integration
zbMATH Open document ID: 0666.65023
DOI: 10.1007/BF01396607
author: S. H. Smith
published in: Numerische Mathematik
publication date: 1989-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/133399
review text: We show that probabilistic analysis provides a mathematical foundation for heuristic error estimation in automatic integration. Let \(\int^{b}_{a} f(t)dt\) be approximated by \(Q_ n (f) = \sum^{n}_{i=1} a_ i f(t_ i)\) and assume on a uniform mesh there exists a constant \(c>0\), such that \(| \int^{b}_{a} f(t)dt - Q_ n(f) | \leq c/n^ k \sup_{a\leq t\leq b} | f^{(k)}(t) |,\) for any \(f\in C^ k_ 0 [a,b]\). Consider the following heuristic error criterion: \(| \int^{b}_{a} f(t)dt -Q_ n(f) | \approx c/n^ k \max_{1\leq i\leq n} | [t_{i-k },\ldots,t_ i]f|,\) where \([t_{i-k},\ldots,t_ i]f\) is the \(k\)th divided difference of \(f\) at \(t_{i-k},\dots,t_ i\), \(k<n\), and by convention \(t_{-i} = a-t_ i\), \(f(t_ i) = 0\), \(i=1,\dots,n\). Our main result is the following theorem. There exist constants \(c_1\geq0\), \(c_2>0\), such that \[ \text{Average } \left| \int^{b}_{a} g(t)dt - Q_ n(f) \right|^2 \leq \frac{c_ 1}{n^{2k+2}} + c_2 n \left(\frac{c}{n^ k} \max_{1\leq i\leq n} | [t_{i-k},\dots,t_ i]f|\right)^2 \] \[ g \in C^ k_0[a,b] \qquad g(t_ i) = f(t_ i) \qquad i=1,\ldots,n \] for any \((f(t_ 1),\ldots,f(t_ n))^ T\in R^ n\). Here the average represen ts integration over \(C^ k_ 0[a,b]\) with respect to the conditional Wiener meas ure induced from the Wiener measure on \(C^ k_ 0[a,b]\) by the constraints \(g(t_ i)=f(t_ i)\), \(i=1,...,n\). The computational aspects of the theory are also discussed. In particular, we show that estimating the conditional average error is equivalent to estimating error with the spline interpolation as a test integrand, and that this process can be made implicit using error criteria with local error- checks.
Mathematics Subject Classification ID: 65D32
Mathematics Subject Classification ID: 41A55
zbMATH DE Number: 4090680
zbMATH Keywords: heuristic error estimation
zbMATH Keywords: automatic integration
zbMATH Keywords: Wiener measure
zbMATH Keywords: conditional average error
zbMATH Keywords: spline interpolation
zbMATH Keywords: local error-checks
MaRDI profile type: Publication
cites work: Feedback and adaptive finite element solution of one-dimensional boundary value problems
cites work: Q3323133
cites work: Q4078501
cites work: Q3042037
cites work: A Correspondence Between Bayesian Estimation on Stochastic Processes and Smoothing by Splines
cites work: Weak probability distributions on reproducing kernel Hilbert spaces
cites work: Gaussian measures in Banach spaces
cites work: Gaussian measure in Hilbert space and applications in numerical analysis
cites work: Approximation of linear functionals on a Banach space with a Gaussian measure
cites work: Q5533878
cites work: A Metalgorithm for Adaptive Quadrature
cites work: Q4042533
cites work: Best Approximate Integration Formulas; Best Approximation Formulas
cites work: Q3895980
cites work: Computational Complexity: On the Geometry of Polynomials and a Theory of Cost: II
cites work: The fundamental theorem of algebra and complexity theory
cites work: On the efficiency of algorithms of analysis
cites work: Average case optimality for linear problems
cites work: On the Condition Number of Local Bases for Piecewise Cubic Polynomials
cites work: Q3277794
OpenAlex ID: W1988584566
Recommended article: Q4764355
Recommended article: Exact Error Estimates and Optimal Randomized Algorithms for Integration
Recommended article: Q4854412
Recommended article: Q3703180
Recommended article: Probabilistic analysis of numerical integration algorithms
Recommended article: Practical error estimation in numerical integration
Recommended article: The optimal error of Monte Carlo integration
description: scientific article; zbMATH DE number 4090680