×

Counterexamples in optimal quadrature. (English) Zbl 0615.65016

Author’s summary: It is widely believed that order of exactness is a good measure of the quality of an algorithm for numerical quadrature. We show that this is not the case, by exhibiting a situation in which the optimal algorithm does not even integrate constants exactly. We also show that there are situations in which the penalty for using equidistant nodes is unbounded. Finally, we show that the complexity of obtaining an \(\epsilon\)-approximation can be an arbitrary function of \(\epsilon\), i.e., there is no hardest quadrature problem.
Reviewer: M.Reimer

MSC:

65D32 Numerical quadrature and cubature formulas
41A55 Approximate quadratures
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] Babenko, V. F.,Asymptotically sharp bounds for the remainder for the best quadrature formulas for several classes of functions. Math. Notes19 (1976), 187–193. · Zbl 0333.41024
[2] Bakhvalov, N. S.,Approximate computation multiple integrals (Russian). Vestmik Moscov. Univ. Ser. Mat. Meh. Astr. Fiz. Him. (1959), no. 4, 3–18.
[3] Bakhvalov, N. S.,The optimality of linear operator approximation methods on convex function classes (Russian). Ž. Vyăisl. Mat. I Mat. Fiz.11 (1971), 1014–1018. · Zbl 0252.41024
[4] Lee, D. andTraub, J. F.,Optimal integration for functions of bounded variation. Research Report, Computer Science Department, Columbia University, New York, 1983.
[5] Lorentz, G. G.,Approximation of functions. Holt, Rinehart and Winston, New York, 1966. · Zbl 0153.38901
[6] Motornyj, V. P., The best quadrature formula of the form \(\sum\limits_{k - 1}^n {p_k {\text{ }}f(x_k )}\) for some certain classes of periodic differential functions (Russian). Izv. Akad. Nauk SSSR Ser. Mat.38 (1974), 583–614.
[7] Oden, J. T. andReddy, J. N.,An introduction to the mathematical theory of finite elements. Wiley-Interscience, New York, 1976.
[8] Sard, A.,Linear approximation. American Mathematical Society, Providence, R.I., 1963. · Zbl 0115.05403
[9] Traub, J. F., Wasilkowski, G. andWoźniakowski, H.,Information, uncertainty, complexity. Addison-Wesley, Reading, Mass., 1983. · Zbl 0522.68041
[10] Traub, J. F. andWoźniakowski, H.,A general theory of optimal algorithms. Academic Press, New York-Toronto, 1980. · Zbl 0441.68046
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.