2015/07/04 by Frances Kuo, Frances Y. Kuo, Kuo, Frances Y. +9 · 4 citations
Decision Sciences · Mathematics · #Probabilistic and Robust Engineering Design #Mathematical Approximation and Integration #Statistical Methods and Inference
paper · pdf · doi:10.1090/mcom/3207
In this paper we present a rigorous cost and error analysis of a multilevel estimator based on randomly shifted Quasi-Monte Carlo (QMC) lattice rules for lognormal diffusion problems. These problems are motivated by uncertainty quantification problems in subsurface flow. We extend the convergence analysis in [Graham et al., Numer. Math. 2014] to <italic>multilevel</italic> Quasi-Monte Carlo finite element discretisations and give a constructive proof of the dimension-independent convergence of the QMC rules. More precisely, we provide suitable parameters for the construction of such rules that yield the required variance reduction for the multilevel scheme to achieve an <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="epsilon"> <mml:semantics> <mml:mi> ε </mml:mi> <mml:annotation encoding="application/x-tex">ε</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -error with a cost of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper O left-parenthesis epsilon Superscript negative theta Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">O</mml:mi> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:msup> <mml:mi> ε </mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo> − </mml:mo> <mml:mi> θ </mml:mi> </mml:mrow> </mml:msup> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal O(ε -θ )</mml:annotation> </mml:semantics> </mml:math> </inline-formula> with <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="theta greater-than 2"> <mml:semantics> <mml:mrow> <mml:mi> θ </mml:mi> <mml:mo>></mml:mo> <mml:mn>2</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">θ > 2</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , and in practice even <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="theta almost-equals 1"> <mml:semantics> <mml:mrow> <mml:mi> θ </mml:mi> <mml:mo> ≈ </mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">θ ≈ 1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , for sufficiently fast decaying covariance kernels of the underlying Gaussian random field inputs. This confirms that the computational gains due to the application of multilevel sampling methods and the gains due to the application of QMC methods, both demonstrated in earlier works for the same model problem, are complementary. A series of numerical experiments confirms these gains. The results show that in practice the multilevel QMC method consistently outperforms both the multilevel MC method and the single-level variants even for nonsmooth problems.