1998 Reports

What Is the Complexity of Stieltjes Integration?

Werschulz, Arthur G.

We study the complexity of approximating the Stieltjes integral ∫ 0^1 f(x)dg(x) for functions ƒ having r continuous derivatives and functions g whose sth derivative has bounded variation. Let r(n) denote the nth minimal error attainable by approximations using at most~n evaluations of ƒ and g, and let comp(ε) denote the ε-complexity (the minimal cost of computing an ε-approximation). We show that r(n) ≍ n^{-min{r,s+1}} and that comp(ε) ≍ ε^{-1/min{r,s+1}}. We also present an algorithm that computes an ε-approximation at nearly-minimal cost.