An exact order of discrepancy of the Smolyak grid and some general conclusions in the theory of numerical integration (Q434420)

Denote the discrepancy of a point set in \(\mathbb R^s\) by \[ \begin{multlined} D_s(\xi_1, \ldots, \xi_N) :\\ = \sup \biggl\{ | N^{-1} \sum_{k=1}^N \chi_J (\xi_k) - \int_{[0,1]^s} \chi_J(x) dx| : J = [a_1, b_1] \times \ldots \times [a_s, b_s] \subset [0,1]^s \biggr\},\end{multlined} \] and let the Smolyak grid be \[ \begin{aligned}\sigma^{(N)} = \biggl\{& ((2 \mu_1 - 1) 2^{-\nu_1}, (2 \mu_2 - 1) 2^{-\nu_2}, \ldots, (2\mu_{s-1} - 1) 2^{-\nu_{s-1}}, \mu_s 2^{-\nu_s}) :\\ & 1 \leq \mu_j \leq \max \{ 1, 2^{\nu_j-1}\},\\ & \nu_j \geq 0, j = 1,2,\ldots,s-1, 1 \leq \mu_s \leq 2^{\nu_s}, \sum_{j=1}^s \nu_j = q\biggr\}.\end{aligned} \] The main result of this paper is then that \(D_s(\sigma^{(N)}) \sim (\ln N)^{-1}\) if \(q \geq s\) and \(N = N_s(q) \sim 2^q q^{s-1}\). This result has some important consequences for \(s\)-dimensional numerical integration methods; e.g., quadature formulas based on Smolyak nodes can be expected to have much smaller errors than, e.g., quasi Monte Carlo methods based on these points if the weights of the former are properly chosen. Moreover, the result gives a starting point for investigating the relations between the degree of uniformity of the grids and proper choices of weights for efficient quadrature formulas.