We study the worst case integration error of combinations of quadrature rules in a reproducing kernel Hilbert space. We show that the error, with respect to the total number $N$ of function evaluations used, cannot decrease faster than $O(N^{-1})$ for an equal-weight rule. However, if the errors of the quadrature rules constituting a compound rule have an order of convergence $O(N^{-\alpha})$ for $\alpha>1$ then, by introducing weights, this order of convergence can be shown to be recovered for the compound rule. The theory applies to lattice sequences as well as digital sequences.We study the worst case integration error of combinations of quadrature rules in a reproducing kernel Hilbert space. We show that the error, with respect to the total number $N$ of function evaluations used, cannot decrease faster than $O(N^{-1})$ for an equal-weight rule. However, if the errors of the quadrature rules constituting a compound rule have an order of convergence $O(N^{-\alpha})$ for $\alpha>1$ then, by introducing weights, this order of convergence can be shown to be recovered for the compound rule. The theory applies to lattice sequences as well as digital sequences.

Sep 1, 20090 citations

High-dimensional integration: The quasi-Monte Carlo way

Josef Dick, Frances Y. Kuo, Ian H. Sloan

This paper is a contemporary review of QMC (‘quasi-Monte Carlo’) methods, that is, equal-weight rules for the approximate evaluation of high-dimensional integrals over the unit cube [0,1] s , where s may be large, or even infinite. After a general introduction, the paper surveys recent developments in lattice methods, digital nets, and related themes. Among those recent developments are methods of construction of both lattices and digital nets, to yield QMC rules that have a prescribed rate of convergence for sufficiently smooth functions, and ideally also guaranteed slow growth (or no growth) of the worst-case error as s increases. A crucial role is played by parameters called ‘weights’, since a careful use of the weight parameters is needed to ensure that the worst-case errors in an appropriately weighted function space are bounded, or grow only slowly, as the dimension s increases. Important tools for the analysis are weighted function spaces, reproducing kernel Hilbert spaces, and discrepancy, all of which are discussed with an appropriate level of detail.This paper is a contemporary review of QMC (‘quasi-Monte Carlo’) methods, that is, equal-weight rules for the approximate evaluation of high-dimensional integrals over the unit cube [0,1] s , where s may be large, or even infinite. After a general introduction, the paper surveys recent developments in lattice methods, digital nets, and related themes. Among those recent developments are methods of construction of both lattices and digital nets, to yield QMC rules that have a prescribed rate of convergence for sufficiently smooth functions, and ideally also guaranteed slow growth (or no growth) of the worst-case error as s increases. A crucial role is played by parameters called ‘weights’, since a careful use of the weight parameters is needed to ensure that the worst-case errors in an appropriately weighted function space are bounded, or grow only slowly, as the dimension s increases. Important tools for the analysis are weighted function spaces, reproducing kernel Hilbert spaces, and discrepancy, all of which are discussed with an appropriate level of detail.

Acta NumericaApr 2, 2013615 citations

We study the worst case integration error of combinations of quadrature rules in a reproducing kernel Hilbert space. We show that the error, with respect to the total number

N

of function evaluations used, cannot decrease faster than

O(N^{-1})

for an equal-weight rule. However, if the errors of the quadrature rules constituting a compound rule have an order of convergence

O(N^{-\alpha})

for

\alpha>1

then, by introducing weights, this order of convergence can be shown to be recovered for the compound rule. The theory applies to lattice sequences as well as digital sequences.