Super-polynomial convergence and tractability of multivariate integration for infinitely times differentiable functions

详细信息    查看全文

• 作者：Kosuke Suzuki ; ^{kosuke-suzuki@hiroshima-u.ac.jp}
• 关键词：Numerical integration ; Tractability ; Super-polynomial convergence ; Quasi-Monte Carlo ; Walsh spaces ; Digital nets
• 刊名：Journal of Complexity
• 出版年：2017
• 出版时间：April 2017
• 年：2017
• 卷：39
• 期：Complete
• 页码：51-68
• 全文大小：479 K
• 卷排序：39

文摘

We investigate multivariate integration for a space of infinitely times differentiable functions Fs,u:={f∈C∞[0,1]s∣‖f‖Fs,u<∞}, where ‖f‖Fs,u:=supα=(α1,…,αs)∈N0s‖f(α)‖L1/∏j=1sujαj, f(α):=∂∣α∣∂x1α1⋯∂xsαsf and u={uj}j≥1 is a sequence of positive decreasing weights. Let e(n,s)e(n,s) be the minimal worst-case error of all algorithms that use nn function values in the ss-variate case. We prove that for any u and ss considered e(n,s)≤C(s)exp(−c(s)(logn)2)e(n,s)≤C(s)exp(−c(s)(logn)2) holds for all nn, where C(s)C(s) and c(s)c(s) are constants which may depend on ss. Further we show that if the weights u decay sufficiently fast then there exist some 1<p<21<p<2 and absolute constants CC and cc such that e(n,s)≤Cexp(−c(logn)p)e(n,s)≤Cexp(−c(logn)p) holds for all ss and nn. These bounds are attained by quasi-Monte Carlo integration using digital nets. These convergence and tractability results come from those for the Walsh space into which Fs,u is embedded.