Open type quasi-Monte Carlo integration based on Halton sequences in weighted Sobolev spaces

详细信息    查看全文

• 作者：Peter Hellekalek^a ; ^{peter.hellekalek@sbg.ac.at" class="auth_mail" title="E-mail the corresponding author} ; Peter Kritzer^b ; ^c ; ^{peter.kritzer@oeaw.ac.at" class="auth_mail" title="E-mail the corresponding author} ; Friedrich Pillichshammer^b ; ^{friedrich.pillichshammer@jku.at" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Quasi-Monte Carlo integration of open type ; Halton sequences ; Worst-case error ; L2L2-discrepancy ; Randomized point sets ; Sobolev space ; p-adic arithmetic
• 刊名：Journal of Complexity
• 出版年：2016
• 出版时间：April 2016
• 年：2016
• 卷：33
• 期：Complete
• 页码：169-189
• 全文大小：467 K

文摘

In this paper, we study quasi-Monte Carlo (QMC) integration in weighted Sobolev spaces. In contrast to many previous results the QMC algorithms considered here are of open type, i.e., they are extensible in the number of sample points without having to discard the samples already used. As the underlying integration nodes we consider randomized Halton sequences in prime bases $p=(p_1,\dots ,p_s)$ for which we study the root mean square (RMS) worst-case error. The randomization method is a $p$-adic shift which is based on $p$-adic arithmetic.

In the class of open methods, the error bounds are optimal with respect to the order of magnitude of the number of sample nodes. Furthermore we obtain conditions on the coordinate weights under which the error bounds are independent of the dimension s$s$. In terms of the field of Information-Based Complexity this means that the corresponding QMC rule achieves a strong polynomial tractability error bound. Our findings on the RMS worst-case error of randomized Halton sequences can be carried over to the RMS L₂$L_2$-discrepancy.

Except for the $p$-adic shift our results are fully constructive and no search algorithms (such as the component-by-component algorithm) are required.