A constructive approach to strong tractability using quasi-Monte Carlo algorithms
We prove in a constructive way that multivariate integration in appropriate weighted Sobolev classes is strongly tractable and the e-exponent of strong tractability is I (which is the best-possible value) under a stronger assumption than Sloan and Wozniakowski's assumption. We show that quasi-Monte Carlo algorithms based on the Sobol sequence and Halton sequence achieve the convergence order O(n(-1+delta)) for any delta > 0 independent of the dimension with a worst-case deterministic guarantee (where n is the number of function evaluations). This implies that quasi-Monte Carlo algorithms based on the Sobol and Halton sequences converge faster and therefore are superior to Monte Carlo methods independent of the dimension for integrands in suitable weighted Sobolev classes. (C) 2002 Elsevier Science (USA).
tractability quasi-monte carlo methods low-discrepancy sequences multi-dimensional integration information-based complexity