2
$\begingroup$

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 .

$\endgroup$
1

1 Answer 1

1
$\begingroup$

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

$\endgroup$
2
  • 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$ 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$ Aug 18, 2011 at 17:48

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.