MiS Preprint Repository

We have decided to discontinue the publication of preprints on our preprint server end of 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.

MiS Preprint
20/2007

Generalized Tractability for Linear Functionals

Michael Gnewuch and Henryk Woźniakowski

Abstract

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.

Received:
26.02.07
Published:
26.02.07
Keywords:
tractability, worst-case setting, Multivariate Integration, reproducing kernel Hilbert spaces

Related publications

inBook
2008 Repository Open Access
Michael Gnewuch and Henryk Wozniakowski

Generalized tractability for linear functionals

In: Monte Carlo and quasi-Monte Carlo methods 2006 / Alexander Keller (ed.)
Berlin : Springer, 2008. - pp. 359-381