Complexity of Oscillatory Integrals on the Real Line

Abstract

We analyze univariate oscillatory integrals defined on the real line for functions from the standard Sobolev space $H^s(\mathbb{R})$ and from the space $C^s(\mathbb{R})$ with an arbitrary integer $s\ge 1$. We find tight upper and lower bounds for the worst case error of optimal algorithms that use $n$ function values. More specifically, we study integrals of the form \[ I_k^ρ(f) = \int_{ {\mathbb{R}}} f(x) \,e^{-i\,kx} ρ(x) \, {\rm d} x\ \ \ \mbox{for}\ \ f\in H^s({\mathbb{R}})\ \ \mbox{or}\ \ f\in C^s({\mathbb{R}}) \] with $k\in \mathbb{R}$ and a smooth density function $\rho$ such as $\rho (x)=\frac{1}{\sqrt{2\pi }}\exp (-x^2/2)$. The optimal error bounds are $\Theta ((n+\max (1,|k|){)}^{-s})$ with the factors in the $\Theta$ notation dependent only on $s$ and $\rho$.

21 pages