Generalized Tractability for Linear Functionals

Michael Gnewuch () and Henryk Wozniakowski ()
Additional contact information
Michael Gnewuch: University of Kiel, Institute of Computer Science
Henryk Wozniakowski: Columbia University, Department of Computer Science

A chapter in Monte Carlo and Quasi-Monte Carlo Methods 2006, 2008, pp 359-381 from Springer

Abstract: Summary We study approximation of continuous linear functionals Id defined over reproducing kernel weighted Hilbert spaces of d-variate functions. Let n(ε, Id) denote the minimal number of function values needed to solve the problem to within ε. There are many papers studying polynomial tractability for which n(ε, Id) is to be bounded by a polynomial in ε−1 and d. We study generalized tractability for which we want to guarantee that either n(ε, Id) is not exponentially dependent on ε−1 and d, which is called weak tractability, or is bounded by a power of T(ε−1, d) for (ε−1, d) ∈ Ω ⊆ [1,∞) × N, which is called (T,Ω)-tractability. Here, the tractability function T is non-increasing in both arguments and does not depend exponentially on ε−1 and d. We present necessary conditions on generalized tractability for arbitrary continuous linear functionals Id defined on weighted Hilbert spaces whose kernel has a decomposable component, and sufficient conditions on generalized tractability for multivariate integration for general reproducing kernel Hilbert spaces. For some weighted Sobolev spaces these necessary and sufficient conditions coincide. They are expressed in terms of necessary and sufficient conditions on the weights of the underlying spaces.

Date: 2008
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-540-74496-2_21

Ordering information: This item can be ordered from
http://www.springer.com/9783540744962

DOI: 10.1007/978-3-540-74496-2_21

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().