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

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 .

share|improve this question
    
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/…) –  Ricky Demer Aug 18 '11 at 19:04
add comment

1 Answer

up vote 1 down vote accepted

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).

share|improve this answer
1  
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. –  Denis Serre Aug 18 '11 at 16:14
    
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. –  Jean-Marc Schlenker Aug 18 '11 at 17:48
add comment

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.