Let $f:\mathbb{T}^m \to \mathbb{R}$ is a function of bounded variation(BV). Let $D=\{\boldsymbol{p}_i,i=1,2,3\ldots\}$ be a countable dense subset of $(0,1)^m$. Let $E_n, n = 1,2,3\ldots$ be a sequence of sets defined as $E_n = \{\boldsymbol{p_i}/\boldsymbol{p_i}\in D, i = 1,2,3\ldots n\}$.

Define the mesh norm of the data points set $E_n$ over the domain $\Omega = (0,1)^m$ as \begin{equation}\label{mesh_norm} \zeta_n = \sup\limits_{\boldsymbol{x}\in\Omega}\inf\limits_{\boldsymbol{p}\in E_n}\|\boldsymbol{x}-\boldsymbol{p}\|_2 \end{equation}

As $D$ is dense we know that $$\lim\limits_{n\to\infty}\zeta_n = 0$$

Also as $f$ is BV, we have $$ \lim\limits_{n\to\infty}\left(\|f\|^2_{L^2(\mathbb{T}^m)}-\frac{1}{n}\sum\limits_{i=1}^n\left(f(\boldsymbol{p_i})\right)^2\right) = 0$$


I am looking for an estimate between the above two expressions for sufficiently large $n$. That is how does LHS of the above expression decay as $\zeta_n$ decays with $n$.

Something like, for sufficiently large $n$, $$\left(\|f\|^2_{L^2(\mathbb{T}^m)}-\frac{1}{n}\sum\limits_{i=1}^n\left(f(\boldsymbol{p_i})\right)^2\right) \le h(\zeta_n)$$

I want to find such a best possible $h$.

PS: Note $h$ should be such that $\lim\limits_{n\to\infty}h(\zeta_n) = 0$


1 Answer 1


Assume $m=1$ and $f$ is of bounded variation on $[0,1]$. The problem is to estimate $$ \|f\|^2_{2}-\frac{1}{n}\sum\limits_{i=1}^n\left(f({p_i})\right)^2=\int_{0}^{1}f^{2}(t)dt -\frac{1}{n}\sum\limits_{i=1}^n f^{2}({p_i}), $$ as the number of points grows. Setting $g=f^{2}$, which is also of bounded variation, the question is about the rate of convergence of the Riemann sums of $g$ to its integral.

For a regular mesh $\{1/n,2/n,\ldots,1\}$, one has $$ \left|\int_{0}^{1}g(t)dt-\frac1n\sum_{k=1}^{n}g(k/n)\right|\leq\int_{0}^{1/n}\sum_{k=1}^{n} |g(t+(k-1)/n)-g(k/n)|dt\leq\frac{V(g)}{n}, $$ where $V(g)$ denotes the variation of $g$.

More generally, consider a tagged mesh $T=\{\sigma_{k},[s_{k-1},s_{k}],~k=1,\ldots,n\}$ of $[0,1]$ such that $T\ll\delta$ meaning that $\max_{k}(s_{k}-s_{k-1})<\delta$, and set $$ g(T)=\sum_{k=1}^{n}g(\sigma_{k})(s_{k}-s_{k-1}),\qquad \psi_{\delta}(g)=\sup _{T \ll \delta}\left|g(T)-\int_{0}^{1} g(t) dt\right| $$ Then, the following holds, for any function $g$, $$ \sup _{\delta>0} \frac{\psi_{\delta}(g)}{\delta} \leq V(g) \leq 2\liminf _{\delta \to 0}\frac{\psi_{\delta}(g)}{\delta}, $$ see J.A. Alewine, Rates of uniform convergence for Riemann integrals. Missouri J. Math. Sci. 26 (2014), 48-56.

Hence, for a function of bounded variation, its Riemann sums converge to its integral at a rate of $O(\delta)$, and that rate cannot be improved.

For several variables, you may have a look here.

  • $\begingroup$ Thanks for the answer. I think its the same for $m>1$ too. $\endgroup$
    – user102868
    Nov 16, 2020 at 13:22
  • $\begingroup$ From the answer of Gerry Myerson, the answer seem to be $\sim \zeta_nV(f^2)$ or is it $$\sim \zeta_n^mV(f^2)$$ $\endgroup$
    – user102868
    Nov 20, 2020 at 16:34
  • 1
    $\begingroup$ only $\zeta_n$ I guess. $\endgroup$
    – user111
    Nov 20, 2020 at 18:01

Your Answer

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

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