Category Archives: Programming

August 21, 2008 · 4:48 am

What do We Have to Know About a Function in Order to Compute its Definite Integral?

Suppose that f is a continuous function from \lbrack 0,1\rbrack to \lbrack 0,1\rbrack and that we have a program which computes it. (Ignore for now exactly what it means to “compute” a real-valued function of the reals. Suffice it to say that almost every natural continuous function you come across is computable). If we want to compute \int_{0}^1 f(x)\,dx, say to within an accuracy of 0.001, how would we do it, and would we need any further information about f in order to do it?

The obvious thing to do is to compute a Riemann sum R(f,n)=\sum_{i=0}^{n-1} (1/n)\cdot f(i/n) for some large n. However, this could be arbitrarily far from the true value of \int_0^1 f(x)\,dx. For example, f(i/n) might be 0 for all 0 \leq i \leq n-1, but f might curve sharply up in between each i/n and (i+1)/n so that its definite integral is arbitrarily close to 1.

However, since f is continuous on \lbrack 0,1\rbrack, it is uniformly continuous. This means that for all \epsilon > 0 there is a \delta > 0 such that whenever |x - y| < \delta, |f(x) - f(y)| < \epsilon. If we could compute a function \delta(\epsilon) such for all \epsilon > 0, whenever |x - y| < \delta(\epsilon), |f(x) - f(y)| < \epsilon, then we could compute the definite integral of f with arbitrary accuracy: If we want to know \int_0^1 f(x)\, dx to within 0.001, then choose n so that 1/n < \delta(0.001) and we can take R(f,n), since |R(f,n) - \int_0^1 f(x)\,dx| < 0.001.

So, one answer to the question “What extra information do we need in order to compute \int_0^1 f(x)\,dx?” is: a function \delta(\epsilon) witnessing f‘s uniform continuity.

In 1998, Alex Simpson showed, building on ideas of Ulrich Berger and others, that another answer is: Nothing!
Continue reading →

5 Comments

Filed under Programming