Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$?)

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
Why is $2/n$ the best you could hope to get? –  Igor Rivin Feb 25 '11 at 4:44
    
@Igor: consider the "tent" function $f(x)=M(1-|2x-1|)$. Then the relative error is exactly $2/n$. –  Julián Aguirre Feb 25 '11 at 13:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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