×

Quasi-Monte Carlo methods for multidimensional numerical integration. (English) Zbl 0662.65021

Numerical integration III, Proc. Conf. Oberwolfach/FRG 1987, ISNM 85, 157-171 (1988).
[For the entire collection see Zbl 0641.00023.]
The paper contains a survey on the recent researches concerning the integration in several variables by quasi-Monte Carlo methods. It is well known that we can estimate an integral \(\int_{I_ k}f(X)dX=J\) by the relation \((1)\quad J=N^{-1}\sum^{N}_{n=1}f(X_ n)\) where \(I_ k=[0,1]^ k\), and \(X_ n\in I_ k\). If the \(X_ n\) points are an independent random sample from the uniform distribution on \(I_ k\), (1) gives a statistical estimation of J (the classical Monte Carlo method) for which the expected value of the error is O(1/\(\sqrt{N})\). In quasi- Monte Carlo methods the points \(X_ n\) are selected on the contrary such that the deterministic error can satisfy a lower bound. Sequences of sets of N points are known which, for increasing N, allow to attain the bound O((lg N)\({}^{k-1}/N)\), under very weak conditions on f(X).
Sequences with this property can be obtained by various techniques. The author considers the three most important methods: 1) the method of low- discrepancy sequences (quasi-random sequences, 2) the method of good lattice points, 3) method based on pseudorandom numbers, and exposes exhaustively the researches developed about these methods after 1978. The paper contains also a new result (Theorem 4) concerning the generation of low discrepancy sequences by use of hyperderivatives. The final list of references quotes seventysix papers.
Reviewer: M.Cugiani

MSC:

65D32 Numerical quadrature and cubature formulas
65C05 Monte Carlo methods
65-02 Research exposition (monographs, survey articles) pertaining to numerical analysis

Citations:

Zbl 0641.00023