Approximation of an integral of a concave function - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T06:47:12Z http://mathoverflow.net/feeds/question/56491 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/56491/approximation-of-an-integral-of-a-concave-function Approximation of an integral of a concave function Jennifer Gao 2011-02-24T06:25:10Z 2011-02-24T19:42:08Z <p>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$?)</p> http://mathoverflow.net/questions/56491/approximation-of-an-integral-of-a-concave-function/56556#56556 Answer by Julián Aguirre for Approximation of an integral of a concave function Julián Aguirre 2011-02-24T19:42:08Z 2011-02-24T19:42:08Z <p>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 &lt; x &lt; 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 &lt; 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$.</p> <p>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.</p> <p>The case in which the maximum is achieved on an interval is treated in a similar way.</p>