期刊
JOURNAL OF APPROXIMATION THEORY
卷 200, 期 -, 页码 227-258出版社
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jat.2015.07.007
关键词
Information-based complexity; Multivariate numerical problems; Hilbert spaces; Tractability; Approximation; Integration
类别
资金
- National Science Centre of Poland [DEC-2012/07/N/ST1/03200]
- Institute for Computational and Experimental Research in Mathematics (ICERM)
- Deutsche Forschungsgemeinschaft DFG [DA 360/19-1]
In the last 20 years a whole hierarchy of notions of tractability was proposed and analyzed by several authors. These notions are used to classify the computational hardness of continuous numerical problems S = (S-d)(d is an element of N) in terms of the behavior of their information complexity n(epsilon, S-d) as a function of the accuracy epsilon and the dimension d. By now a lot of effort was spent on either proving quantitative positive results (such as, e.g., the concrete dependence on epsilon and d within the well-established framework of polynomial tractability), or on qualitative negative results (which, e.g., state that a given problem suffers from the so-called curse of dimensionality). Although several weaker types of tractability were introduced recently, the theory of information-based complexity still lacks a notion which allows to quantify the exact (sub-/super-) exponential dependence of n(epsilon, S-d) on both parameters epsilon and d. In this paper we present the notion of (s, t)-weak tractability which attempts to fill this gap. Within this new framework the parameters s and t are used to quantitatively refine the huge class of polynomially intractable problems. For linear, compact operators between Hilbert spaces we provide characterizations of (s, t)-weak tractability w.r.t. the worst case setting in terms of singular values. In addition, our new notion is illustrated by classical examples which recently attracted some attention. In detail, we study approximation problems between periodic Sobolev spaces and integration problems for classes of smooth functions. (c) 2015 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据