A Bound for the Error of the Numerical Approximation of a the Integral of a Continuous Function

How to numerically integrate a nasty function?

Suppose $f$ is only continuos; which method can you employ to approximate

$$\int_0^t f(s)ds$$

Since $f$ is continuos the integral exists, but all the numerical approximation methods I studied bound the error term with the hypothesis that $f$ is at least $C^2$ or something.

I also know of the left rectangle method that only requires $f$ to be holder-continuos for some $\alpha$, but suppose this $f$ is not even Holder continuos.

Can we find a meaningful error bound?

This is where using randomness can help. Let $X_i\sim U(0,t)$ be independent and let $$I_n=\frac t n\sum_{i=1}^n f(X_i)$$ Then $I_n$ converges to $I=\int_0^tf(x)\,dx$ a.s. and in $L^2$: $$\sigma^2_n=E((I_n-I)^2)=\frac {\int_0^tf^2(x)\,dx-I^2}n\to 0$$ regardless of how hairy your function is.

To get the simplest bound it's enough to know $M=\max_{x\in[0,t]} |f(x)|$ for then $\sigma_n^2\le\frac {M^2t}n$.

• +1 very nice! this is monte carlo integration right? And the error term you get is just $M^2 t - M^2 \le M^2 t$ for simplicity? :-) – Ant Nov 12 '15 at 13:36
• @Ant Yes, this is Monte Carlo Integration (that doesn't even require $f$ to be continuous - we just need an estimate on $M$ to know how many samples we need). The idea is similar to randomization in game theory against adversary - it saves you from "worst-case" deterministic scenarios. In the error term you need to bound each term separately and you might have $I=0$, so it's not just $M^2t-M^2$. – A.S. Nov 12 '15 at 14:45
• Ah yeah, right.. Well thank you! :-) This is very nice :-) – Ant Nov 12 '15 at 14:46
• Anyhow shouldn't it be $I_n = \frac tn \sum_{i=1}^n f(X_i)$? – Ant Dec 2 '15 at 17:43

Can we find a meaningful error bound?

No. At least, using conventional terms.

Consider $h(x) = \begin{cases} d-d^2*|x-x_0| & | x \in [x_0-{1 \over d}, x_0+{1 \over d}] \\ 0 & otherwise \end{cases}$. When $[x_0-{1 \over d}, x_0+{1 \over d}] \subseteq [0,t]$, $\int_0^th(s)ds = 1$. But unless we somehow try to compute value of h(x) on arbitrarily narrow interval, $h(x)$ can't be distinguished from $0$.

Or, more strictly, let's suppose we have such estimation for given numerical method. Let's take all iterations until error is less than 1. Then let's apply the same method for $f_1(x)=f(x)+2h(x)$, where initial method application didn't estimate $f$ anywhere on $[x_0-{1 \over d}, x_0+{1 \over d}]$. You will have the same result with error less than 1, but actual results will differ by 2.

In more general case, we can take $f_1(x)$ which equals $f(x)$ in all points where our method estimated it and still have $f_1(x)=C$ for any $C$ and all $x$ except arbitrarily small set of intervals. To avoid this, one would have to limit function change on given interval, which is problematic to express in conventional notation.

• Thank you! But I'm not completely convinced; I mean we can easily modify the function $h$ to be $C^\infty$ there and be equal to $0$ outside this interval, but we can find in this case an error term, can't we? – Ant Nov 11 '15 at 13:04
• @Ant Yes, we can express error in terms of derivative of $h$. When derivative is limited, error is also limited. Likewise, here we can express error in terms of maximal value of $h$, but the problem is with "meaningful": estimate "if $a \le f(x) \le b$, then $at \le \int_0^tf(s)ds \le bt$" is trivial, but practically useless. Worst part is that unless $a=b$, error can't be reduced arbitrarily close to 0. – Abstraction Nov 11 '15 at 13:43
• Yes I see your point, but the who's to say we can't find a number analogous to the derivative in the continuos case? (Even if in some cases like your function it won't be useful ) – Ant Nov 11 '15 at 14:45
• @Ant We can (I changed my answer to reflect this). It's more the question of what functions and what statements about them you have. There is special term for which I don't know English word (don't even know if it exists), $\omega(f,E) = \sup_{x_1,x_2 \in E}|f(x_1)-f(x_2)|$. Condition ${\omega(f,[a,b]) \over (b-a)} \le C$ can replace $|f'(x)|<C$ in most cases, but functions for which such condition holds yet no derivative exists are "pathologic" and unlikely to appear in any actual computations. – Abstraction Nov 11 '15 at 14:56
• @Abstraction The English term is "modulus of continuity". – Ian Nov 11 '15 at 21:07