

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 defined
over reproducing kernel weighted Hilbert spaces of d-variate functions.
Let
denote the minimal number of function values needed to
solve the problem to within
. There are many papers
studying polynomial tractability for which
is to
be bounded by a polynomial in
and d. We study
generalized tractability
for which we want to guarantee that either
is not
exponentially dependent on
and d, which is called
weak tractability,
or is bounded by a power of
for
, which is called
-tractability. Here, the
tractability function T is non-increasing in both arguments
and does not depend exponentially on
and d.
We present necessary conditions on generalized tractability
for arbitrary continuous linear
functionals 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.