Constructing lattice rules based on weighted degree of exactness and worst case error (Q2380808): Difference between revisions

The authors consider the approximation of a \(d\)-dimensional integral over the unit cube \([0,1]\) \[ I_{d}(f)=\displaystyle{\int_{[0,1]^d}f(x)dx}, \] by a special type of equal weight integration rules known as rank-1 lattice rules \[ Q_{n,d}(f)=\displaystyle{\frac{1}{n}\sum_{k=1}^n f\left(\left\{\frac{kz}{n}\right\}\right)}.\tag{1} \] Here the integration points \(\left\{\displaystyle\frac{kz}{n}\right\}\) are fully specified by one integer vector \(z\), referred to as the generating vector, and the braces around a vector indicate that every component of the vector is replaced by its fractional part in \([0,1)\). An integration rule is said to have a trigonometric degree of exactness \(m\) if it integrates exactly all trigonometric polynomials of degree \(\leq m\). If the integrand \(f\) has an absolutely convergent Fourier series representation \[ f(x)=\displaystyle{\sum_{h\in Z^d}\hat{f}(h)e^{2\pi i h\cdot x},}\text{ with }\hat{f}(h)=\displaystyle{\int_{[0,1]^d}f(x)e^{-2\pi i h\cdot x},} \] then the error of the rank-1 lattice rule applied to \(f\) is precisely \[ Q_{n,d}(f)-I_{d}(f)=\displaystyle{\sum_{h\in Z^{d}\setminus \{0\},\, hz\equiv0 \pmod n}\hat{f}(h).} \] This approach is usually restricted to low dimensions because the number of points \(n\) required for an integration rule to achieve a certain degree of exactness increases exponentially with the dimension \(d\). To avoid this problem, the authors introduce the notion of weighted degree of exactness which allows different emphasis on different dimension. If these weights decay sufficiently fast, then they show that the number of points \(n\) required no longer increases exponentially with \(d\). In this paper the authors present a component-by-component algorithm for the construction of a rank-1 lattice rule such that {\parindent6mm \begin{itemize}\item[(i)] it has a prescribed weighted degree of exactness, and \item[(ii)] its worst case error achieves the optimal rate of convergence in a weighted Korobov space. \end{itemize}} They introduce a modified, more practical, version of this algorithm which maximizes the weighted degree of exactness in each step of the construction. Both algorithms are illustrated by numerical results.