| |
|
The notion of uniformity is made precise as the discrepancy defined below. Roughly speaking, the discrepancy of a sequency is low if the number of points falling into a set B is close to the number one would expect from the measure of B.
At least three methods of numerical integration can be phrased as follows. Given a set x1, ..., xN in the interval [0,1], approximate the integral of a function f as the average of the function evaluated at the points:
It is convenient to construct the set x1, ..., xN in such a way that if a set with N+1 elements is constructed, the previous N elements need not be recomputed. The rectangle rule uses points set which have low discrepancy, but in general the elements must be recomputed if N is increased. Elements need not be recomputed in the Monte Carlo method if N is increased, but the point sets do not have minimal discrepancy. By using low-discrepancy sequences, the quasi-Monte Carlo method has the desirable features of the other two methods.
| Table of contents |
|
2 The Koksma-Hlawka inequality 3 References |
Discrepancy is defined as follows, using Niederreiter's notation.
Definition of discrepancy
where P is the set x1, ..., xN,
λs is the s-dimensional Lebesgue measure,
A(B;P) is the function which counts the points in P which fall into B,
and J* is the set of intervals of the form
Let Īs be the s-dimensional unit cube, Īs = [0, 1] × ... × [0, 1].
Let f have bounded variation on Īs in the sense of Hardy and Krause.
Then for any x1, ..., xN in Is = [0, 1) × ... × [0, 1),
The Koksma-Hlawka inequality
References