I suspect this is a homework question somewhere, but I've not seen it elsewhere and it seems like it should be easy: let $f(x)$ be a concave function from $[0,1]$ to the reals such that $f(0) = f(1) = 0$. Consider the obvious upper bound for $\int_0^1 f(x) dx$ obtained by dividing $[0,1]$ into $n$ sub-intervals of the same length and measuring the area of the rectangles whose heights are given by the maximum value of $f(x)$ along that sub-interval. What's the maximum relative error that this can introduce, as a function of $n$? (I'm guessing $2/n$?)
1 Answer
Since $f$ is concave, it is continuous in $(0,1)$. I will assume that it is continuous in $[0,1]$. The graph of $f$ is above the secants, so that $f(x)\ge 0$. Let $M$ be the maximum of $f$. If $M=0$ there is nothing to prove, so that we we may assume that $M > 0$ (and hence $f(x) > 0$ for $0 < x < 1$.) Assume by now that the maximum is achieved at a unique point $x_M\in(0,1)$. Given $n\ge 1$, let $k$ be the smallest integer such that $x_M\in(k/n,(k+1)/n)$ (the case $x_M=k/n$ is treated similarly.) Let $A_i=\int_{x_i}^{x_{i+1}}f(x)dx$. Then, because of the concavity $$ \frac{1}{2n}(f(\frac{i}{n})+f(\frac{i+1}{n}))\le A_i \le \frac{1}{n}f(\frac{i+1}{n}) $$ for $0\le i < k$, so that $$ 0\le\sum_{i=0}^{k-1}f(\frac{i+1}{n})-\int_{0}^{x_{k}}f(x)dx\le \frac{1}{2n}f(\frac{k}{n})\le\frac{M}{2n}. $$ Similarly, we get $$ 0\le\sum_{i=k+1}^{n-1}f(\frac{i}{n})-\int_{x_{k+1}}^{1}f(x)dx\le \frac{1}{2n}f(\frac{k+1}{n})\le\frac{M}{2n}. $$ Finally, it is easily seen that $$ 0\le \frac{M}{n}-A_k\le\frac{M}{2n}-\frac{1}{2}(f(\frac{k}{n})(x_M-\frac{k}{n})+f(\frac{k+1}{n})(\frac{k+1}{n}-x_M))\le \frac{M}{2}. $$ Thus, the total error is at most $3M/2n$. On the other hand, $\int_0^1f(x)dx$ is larger than the area of the triangle with vertices at $(0,0)$, $(1,0)$ and $(x_M,M)$, which is $M/2$. Thus, the relative error is at most $3/n$.
Using the fact that $f(k/n)$ converges to $M$, you can probably get all the way down to $(2+\epsilon)/n$ for any $\epsilon>0$ provided $n$ is sufficiently large.
The case in which the maximum is achieved on an interval is treated in a similar way.
-
$\begingroup$ Why is $2/n$ the best you could hope to get? $\endgroup$ Feb 25, 2011 at 4:44
-
$\begingroup$ @Igor: consider the "tent" function $f(x)=M(1-|2x-1|)$. Then the relative error is exactly $2/n$. $\endgroup$ Feb 25, 2011 at 13:27