Preprint 20/2007

Generalized Tractability for Linear Functionals

Michael Gnewuch and Henryk Woźniakowski

Contact the author: Please use for correspondence this email.
Submission date: 26. Feb. 2007
Pages: 28
published in: Monte Carlo and quasi-Monte Carlo methods 2006 / A. Keller (ed.)
Berlin : Springer, 2008. - P. 359 - 381 
DOI number (of the published article): 10.1007/978-3-540-74496-2_21
Bibtex
Keywords and phrases: tractability, worst-case setting, Multivariate Integration, reproducing kernel Hilbert spaces
Download full preprint: PDF (259 kB), PS ziped (213 kB)

Abstract:
We study approximation of continuous linear functionals formula16 defined over reproducing kernel weighted Hilbert spaces of d-variate functions. Let formula20 denote the minimal number of function values needed to solve the problem to within formula22. There are many papers studying polynomial tractability for which formula20 is to be bounded by a polynomial in formula26 and d. We study generalized tractability for which we want to guarantee that either formula20 is not exponentially dependent on formula26 and d, which is called weak tractability, or is bounded by a power of formula36 for formula38, which is called formula40-tractability. Here, the tractability function T is non-increasing in both arguments and does not depend exponentially on formula26 and d.

We present necessary conditions on generalized tractability for arbitrary continuous linear functionals formula16 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.

04.01.2023, 02:14