Product rules are optimal for numerical integration in classical smoothness spaces

详细信息    查看全文

• 作者：Aicke Hinrichs^a ; ^{aicke.hinrichs@jku.at} ; Erich Novak^b ; ^{erich.novak@uni-jena.de} ; Mario Ullrich^a ; ^{mario.ullrich@jku.at} ; Henryk Woźniakowski^c ; ^d ; ^{henryk@cs.columbia.edu}
• 关键词：Product rules ; Optimal error bounds ; Integration ; Optimization
• 刊名：Journal of Complexity
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：38
• 期：Complete
• 页码：39-49
• 全文大小：405 K
• 卷排序：38

文摘

We mainly study numerical integration of real valued functions defined on the dd-dimensional unit cube with all partial derivatives up to some finite order r≥1r≥1 bounded by one. It is well known that optimal algorithms that use nn function values achieve the error rate n−r/dn−r/d, where the hidden constant depends on rr and dd. Here we prove explicit error bounds without hidden constants and, in particular, show that the optimal order of the error is min{1,dn−r/d}, where now the hidden constant only depends on rr, not on dd. For n=mdn=md, this optimal order can be achieved by (tensor) product rules.We also provide lower bounds for integration defined over an arbitrary open domain of volume one. We briefly discuss how lower bounds for integration may be applied for other problems such as multivariate approximation and optimization.