Suppose that $f$ is a twice-differentiable concave function from $R^2$ to $R$ that's negative outside of some bounded set (e.g. $f(x,y)=1-x^2-y^2$) and let $F=$max$(f,0)$. Let $S_n$ be the Riemann sum for the integral of $F$ over $R^2$ obtained by summing the values of $F$ at all points in the lattice $(Z/n)^2$ and dividing by $n^2$. What sort of bounds can be given for the difference between $S_n$ and the integral of $F$ over $R^2$? Is it $O(1/n)$ or $O(1/n^2)$ or what? This is a more focussed version of the question error estimates for multi-dimensional Riemann sums .
$\begingroup$
$\endgroup$
1
asked Aug 18, 2011 at 12:36
-
$\begingroup$ Oy! Mr. Propp, are you going to accept or comment at mathoverflow.net/questions/71432/…? (Also, I answered your comment at (mathoverflow.net/questions/71344/…) $\endgroup$– user5810Commented Aug 18, 2011 at 19:04
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
It looks like the error is in $O(1/n^2)$, with a precise and optimal bound $C/n^2$ if you have a fixed bound on (1) the second derivative of the function (2) the radius of the region where it is non-negative.
As the question is stated there are two sources for the error term:
the error in each square, centered at a point of the lattice, on which the function is strictly positive. This terms is controled by the second derivative of the function (it clearly vanishes for a linear function) at it is bounded by $O(1/n^4)$, since the number of squares is $O(n^2)$ the estimate on this whole term is $O(1/n^2)$,
the error term in the boundary squares, those on which the function takes both a $>0$ and a zero value. On those squares the error is $O(1/n^3)$ and the number or such boundary squares is $O(n)$ so we get again a bound $O(1/n^2)$.
(Note that a complete argument has to be more precise because the function $f$ could have zero derivative at the points where it vanishes, then the number of boundary squares is $O(n^2)$ but I think the result does not change).
To check that this estimate is optimal you can think of a function which is invariant under a rotation of angle $\pi/2$ and equal to say $N-x$ on $y>0, -y+u\leq x\leq y-u$ for some small $u>0$. Then the first error term can be made smaller than the second, while the second "boundary" error term is indeed of the order of $1/n^2$ (the boundary errors all sum up).
answered Aug 18, 2011 at 14:23
-
1$\begingroup$ The errors in each cell tend to compensate. If instead of having a compactly supported function with limited regularity, we have a functin $F$ in the Schwartz class, then the total error is $O(n^{-k})$ for every $k>0$. This is a consequence of the Poisson summation formula and the fact that the Fourier transform of $F$ is of Schwartz class too. Therefore the question is really about the effect of the limited regularity of $F$, and whether the concavity helps. $\endgroup$ Commented Aug 18, 2011 at 16:14
-
$\begingroup$ I agree but as stated the main error term comes from the boundary squares. In some cases at least no compensation occurs, as in the example I tried to described, where all centers of boundary squares are at points where $f=0$ so that all those boundary terms are positive. $\endgroup$ Commented Aug 18, 2011 at 17:48