The tent transformation can improve the convergence rate of quasi-Monte Carlo algorithms using digital nets
The authors investigate the worst-case error of the multivariate integration in reproducing kernel Sobolev spaces. These spaces are composed of functions whose second partial derivatives are square integrable. For an approximation of the \(s\)-dimensional integrals of the functions of these spaces a quasi-Monte Carlo (QMC) algorithm is used. For a deterministically chosen point set in \([0,1)^{s}\) two component-by-component transformations are used. The first one is a digital shift with a random vector in \([0,1)^{s}\) and the second one is a fold with tent transformation. The well-known digital \((t,m,s)\)-nets over \({\mathbb Z}_{2}\) and nets, constructed by polynomial lattice rules are used in the paper. In section 2 some preliminary definitions and results are presented. In section 3 the notions: a worst-case error of a QMC algorithm of the integration in reproducing kernel Hilbert space, a mean square worst-case error for the integration, a digitally shifted and folded kernel are reminded. Theorem 1 represents the relation beween the mean square worst-case error of the integration in a reproducing kernel Hilbert space, generated by an ordinary kernel and the worst-case error of the integration in a reproducing kernel Hilbert space, generated by a digitally shifted and then folded initial kernel. Theorem 2 gives a formula for the digitally shifted and then folded kernel in the terms of the Walsh functions in base 2. Theorem 3 gives a formula for the mean square worst-case error of the integration using an arbitrary \(s\)-dimensional net and the form of this formula in the case when the net is chosen to be a digital \((t,m,s)\)-net over \({\mathbb Z}_{2}.\) In Theorem 4 the formula for the mean square worst-case error of the integration using an arbitrary \(s\)-dimensional net in the terms of the Walsh functions in base 2 is shown. In the cases when the net is chosen to be a digital \((t,m,s)\)-net over \({\mathbb Z}_{2}\) and a net, constructed by polynomial lattice rules, the corresponding formulae for the mean square worst-case error are also given in Theorem 4. In section 4 the details of the Sobolev space \(H_{s, \gamma}\) are presented. The reproducing kernel of this space is based on using the first, second and fourth Bernoulli polynomials. Theorem 5 and 6, respectively, state that there exist a digital \((t,m,s)\)-net \(P_{2^{m}}\) over \({\mathbb Z}_{2}\) and a net \(P({\mathbf g},f)\) with \(f \in {\mathbb Z}_{2}[x]\) an irreducible polynomial and a vector \({\mathbf g}\) such that for any \({1 \over 4} < \lambda \leq 1\) the quadrate of the mean square worst-case error has an order \({\mathcal O}(2^{-{m \over \lambda}}).\) An algorithm for a construction of the nets of the form \(P({\mathbf g},f)\) from Theorem 6 is exposed. The obtained results show that there exists a randomly digitally shifted and then folded by using the tent transformation digital net which achieves a convergence order of \({\mathcal O}(2^{m(-2 + \epsilon)})\) for any \(\epsilon > 0\) of the mean square worst-case error. Theorem 8 states the existence of nets constructed by Korobov polynomial lattice rules such that for any \({1 \over 4} < \lambda \leq 1\) the quadrate of the mean square worst-case error has an order \({\mathcal O}(2^{-{ m \over \lambda}}).\) An algorithm for obtaining the polynomial \(g^{*}\) for which the order \({\mathcal O}(2^{-{ m \over \lambda}})\) is achieved, is exposed.
scientific article; zbMATH DE number 5119708
scientific article