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 (AMS), 2002
Erschienen in:
Mathematics of Computation, 72 (2002) 242, Seite 823-838
Sprache:
Englisch
DOI:
10.1090/s0025-5718-02-01440-0
ISSN:
1088-6842;
0025-5718
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 ε \varepsilon depends on ε − 1 {\varepsilon }^{-1} and the dimension s s . Strong tractability means that it does not depend on s s and is bounded by a polynomial in ε − 1 {\varepsilon }^{-1} . The least possible value of the power of ε − 1 {\varepsilon }^{-1} is called the ε \varepsilon -exponent of strong tractability. Sloan and Woź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źniakowski’s assumption. We show that quasi–Monte Carlo algorithms using Niederreiter’s ( t , s ) (t,s) -sequences and Sobol sequences achieve the optimal convergence order O ( N − 1 + δ ) O(N^{-1+\delta }) for any δ > 0 \delta >0 independent of the dimension with a worst case deterministic guarantee (where N 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 ) (t,s) -sequences and Sobol sequences.