Complexity of Oscillatory Integration for Univariate Sobolev Spaces

Abstract

We analyze univariate oscillatory integrals for the standard Sobolev spaces $H^s$ of periodic and non-periodic functions with an arbitrary integer $s\ge 1$. We find matching lower and upper bounds on the minimal worst case error of algorithms that use $n$ function or derivative values. We also find sharp bounds on the information complexity which is the minimal $n$ for which the absolute or normalized error is at most $\epsilon$. We show surprising relations between the information complexity and the oscillatory weight. We also briefly consider the case of $s=\infty$.

40 pages

Cited by in corpus (6)

• Optimal quadrature formulas for computing of Fourier integrals in a Hilbert space
• Optimal Quadrature Formulas for the Sobolev Space $H^1$
• On an optimal quadrature formula for approximation of Fourier integrals in the space $W_2^{(1,0)}$
• Kernel interpolation with continuous volume sampling
• Complexity of Oscillatory Integrals on the Real Line
• Some Results on the Complexity of Numerical Integration