On the Randomization of Frolov's Algorithm for Multivariate Integration

MaRDI QIDQ6271481zbMATH OpenFDO

Authors David Krieg

Publication date 15 March 2016

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Numerical integration (65D30) Complexity and performance of numerical algorithms (65Y20) Analysis of algorithms and problem complexity (68Q25)

Abstract: We are concerned with the numerical integration of functions from the Sobolev space $H^{r,extmix}([0,1{]}^d)$ of dominating mixed smoothness $rinmathbbN$ over the $d$-dimensional unit cube. In 1976, K. K. Frolov introduced a deterministic quadrature rule whose worst case error has the order $n^{-r},(logn{)}^{(d-1)/2}$ with respect to the number $n$ of function evaluations. This is known to be optimal. 39 years later, Erich Novak and me introduced a randomized version of this algorithm using $d$ random dilations. We showed that its error is bounded above by a constant multiple of $n^{-r-1/2},(logn{)}^{(d-1)/2}$ in expectation and by $n^{-r},(logn{)}^{(d-1)/2}$ almost surely. The main term $n^{-r-1/2}$ is again optimal and it turns out that the very same algorithm is also optimal for the isotropic Sobolev space $H^s([0,1{]}^d)$ of smoothness $s>d/2$. We also added a random shift to this algorithm to make it unbiased. Just recently, Mario Ullrich proved that the expected error of the resulting algorithm on $H^{r,extmix}([0,1{]}^d)$ is even bounded above by $n^{-r-1/2}$. This thesis is a review of the mentioned upper bounds and their proofs.

This page was built for publication: On the Randomization of Frolov's Algorithm for Multivariate Integration

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6271481)