{
  "id": "1603.04637",
  "version": "v1",
  "published": "2016-03-15T11:19:52.000Z",
  "updated": "2016-03-15T11:19:52.000Z",
  "title": "On the Randomization of Frolov's Algorithm for Multivariate Integration",
  "authors": [
    "David Krieg"
  ],
  "comment": "Master Thesis",
  "categories": [
    "math.NA"
  ],
  "abstract": "We are concerned with the numerical integration of functions from the Sobolev space $H^{r,\\text{mix}}([0,1]^d)$ of dominating mixed smoothness $r\\in\\mathbb{N}$ over the $d$-dimensional unit cube. K.\\,K.\\,Frolov introduced a deterministic quadrature rule whose worst case error has the order $n^{-r} \\, (\\log n)^{(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} \\, (\\log n)^{(d-1)/2}$ in expectation and by $n^{-r} \\, (\\log n)^{(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 in \\cite{ullrichneu} that the expected error of the resulting algorithm on $H^{r,\\text{mix}}([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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-03-15T11:19:52.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "65D30",
      "65C05",
      "65Y20",
      "68Q25"
    ],
    "keywords": [
      "multivariate integration",
      "frolovs algorithm",
      "randomization",
      "isotropic sobolev space",
      "deterministic quadrature rule"
    ],
    "tags": [
      "dissertation"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}