I'm trying to approximate a 1D definite integral to within an additive $\epsilon$ for a given $\epsilon$. I was wondering whether there is an $O(\text{polylog}(1/\epsilon))$-time algorithm for this. The usual numerical methods (trapezoidal, Simpson's, etc) seem to yield only $O(\text{poly}(1/\epsilon))$ time.

EDIT: Maybe I should flesh out my thinking a little bit. If $I=\int_a^bf(x)dx$ and $I_T$ is the rectangular approximation with $n$ points, then for some $c_i$s each in $(a+(i-1)\Delta,a+i\Delta)$ (where $\Delta=(b-a)/n$), we have:

\begin{align*} |I-I_T| &= \sum_{i=1}^n \frac{(b-a)^2}{2n^2}|f'(c_i)| \\ &\leqslant \frac{(b-a)^2}{2n}\max_{x'\in(a,b)}|f'(x')| \leqslant \epsilon. \end{align*}

which requires an order of $1/\epsilon$ points. I don't know if this makes...


1 Answer 1


Potentially yes. What you need is to raise the order of the formula when adding more points. Assume that we do not have to compute the nodes and the weights for any quadrature rule we're using.

Using $n$ values on a segment $[a,b]$ one can numerically compute $\int_a^n f(x) dx$ with a gaussian rule with $n$ nodes. That rule would have an error of magnitude $$ \epsilon_n = \frac{(b-a)^{2n+1} (n!)^4}{(2n+1)[(2n)!]^3}f^{(2n)}(\xi)\\ \log |\epsilon_n| = (2n+1)\log (b-a) + 4\log n!-\log(2n+1)-3\log(2n)! + \log |f^{(2n)}(\xi)| = \\ = (2n+1)\log(b-a)+4n(\log n-1)-\log2 + \log n-6n(\log n + \log 2-1) + \log |f^{(2n)}(\xi)| + O(n^{-1}) = \\ = -2n\log n +\log |f^{(2n)}(\xi)| + 2n\left[\log(b-a) +1-3\log 2\right] + O(1) $$ For not too fast growing $f(x)$, for examlpe $\max_\xi |f^{2n}(\xi)| = O(n!)$ $$ \log |\epsilon_n| = -n \log n + O(n). $$ So that means that error decays at least as fast as $n^{-n}$ which itself decays faster that $e^{-n}$. So $$ n = O(\log 1/\epsilon_n). $$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .