6
$\begingroup$

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

$\endgroup$
0

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Why is $2/n$ the best you could hope to get? $\endgroup$
    – Igor Rivin
    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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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