3
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ +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? :-) $\endgroup$ – Ant Nov 12 '15 at 13:36
  • $\begingroup$ @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$. $\endgroup$ – A.S. Nov 12 '15 at 14:45
  • $\begingroup$ Ah yeah, right.. Well thank you! :-) This is very nice :-) $\endgroup$ – Ant Nov 12 '15 at 14:46
  • $\begingroup$ Anyhow shouldn't it be $I_n = \frac tn \sum_{i=1}^n f(X_i)$? $\endgroup$ – Ant Dec 2 '15 at 17:43
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Ant Nov 11 '15 at 13:04
  • $\begingroup$ @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. $\endgroup$ – Abstraction Nov 11 '15 at 13:43
  • $\begingroup$ 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 ) $\endgroup$ – Ant Nov 11 '15 at 14:45
  • $\begingroup$ @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. $\endgroup$ – Abstraction Nov 11 '15 at 14:56
  • 1
    $\begingroup$ @Abstraction The English term is "modulus of continuity". $\endgroup$ – Ian Nov 11 '15 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.