Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
Medientyp:
E-Artikel
Titel:
Strong Tractability of Multivariate Integration Using Quasi-Monte Carlo Algorithms
Beteiligte:
Wang, Xiaoqun
Erschienen:
American Mathematical Society, 2003
Erschienen in:
Mathematics of Computation, 72 (2003) 242, Seite 823-838
Sprache:
Englisch
ISSN:
0025-5718;
1088-6842
Entstehung:
Anmerkungen:
Beschreibung:
We study quasi-Monte Carlo algorithms based on low discrepancy sequences for multivariate integration. We consider the problem of how the minimal number of function evaluations needed to reduce the worst-case error from its initial error by a factor of ε depends on ε-1and the dimension s. Strong tractability means that it does not depend on s and is bounded by a polynomial in ε-1. The least possible value of the power of ε-1is called the$\varepsilon-exponent$of strong tractability. Sloan and$Wo\acute{z}niakowski$established a necessary and sufficient condition of strong tractability in weighted Sobolev spaces, and showed that the$\varepsilon-exponent$of strong tractability is between 1 and 2. However, their proof is not constructive. In this paper we prove in a constructive way that multivariate integration in some weighted Sobolev spaces is strongly tractable with$\varepsilon-exponent$equal to 1, which is the best possible value under a stronger assumption than Sloan and$Wo\acute{z}niakowski's$assumption. We show that quasi-Monte Carlo algorithms using Niederreiter's (t, s)-sequences and Sobol sequences achieve the optimal 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 strong tractability with the best$\varepsilon-exponent$can be achieved in appropriate weighted Sobolev spaces by using Niederreiter's (t, s)-sequences and Sobol sequences.