PhD thesis of Bart Vandewoestyne
Quasi-Monte Carlo techniques for the approximation of high-dimensional integrals
Bart Vandewoestyne
- Advisor: Ronald Cools
- Defense: June 2008
- KULeuven digital library copy: http://hdl.handle.net/1979/1852
High-dimensional multivariate integrals are often computed using Monte Carlo methods. The main advantage of these methods is that they do not suffer from the curse of dimensionality. However, their rather slow convergence is a disadvantage. In so-called quasi-Monte Carlo (qMC) methods, the random samples are replaced by carefully chosen deterministic points with a more uniform distribution. For many problems, the use of qMC-methods speeds up the convergence.
An example of a Monte Carlo method is the SIR-algorithm for generating samples from a distribution with an unknown normalizing constant. In a first part of this thesis, we investigate the convergence of the SIR-scheme with the random points replaced by qMC-points.
Next, we examine scrambling methods for two kinds of qMC-sequences. With scrambling one tries to improve the quality of qMC-points by cleverly modifying their individual digits. Several scrambling methods for the Halton and Faure sequence were computationally investigated and new scramblings are introduced.
Important contributions are also made in the area of multivariate numerical integration based on irrational numbers. First, without assuming any periodicity or smoothness of the function, Sobol' sequences are compared with sequences based on irrational numbers. Next, for a certain class of smooth periodic functions, we construct open integration algorithms with second and third order error convergence rates. We finally generalize our approach and obtain algorithms with qth order error convergence rates, where q is only limited by the smoothness of the function.
We conclude with a short discussion on the software developed during this research.
