Bachvalov proved that the optimal order of convergence of a Monte Carlo method for numerical integration of functions with bounded kth order derivatives is O(N~(-k/s-1/2), where s is the dimension. We construct a new Monte Carlo algorithm with such rate of convergence, which adapts to the variations of the sub-integral function and gains substantially in accuracy, when a low-discrepancy sequence is used instead of pseudo-random numbers. Theoretical estimates of the worst-case error of the method are obtained. Experimental results, showing the excellent parallelization properties of the algorithm and its applicability to problems of moderately high dimension, are also presented.
展开▼
