Optimal quadrature for weighted function spaces on multivariate domains

Jiansong Li, Heping Wang · 2024

Read Optimal quadrature for weighted function spaces on multivariate domains by Jiansong Li, Heping Wang (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-17546.txt.

Introduction

Jiansong Li and Heping Wang find best rules for numeric area sums on round domains in a 2024 math paper. The task is quadrature: guess an integral by a weighted sum of point values. Their stage is the unit sphere, with weights that bend the measure. Two classes of smooth functions face the test, in set and random rule forms.

For the first class the pair nail the best error rate in both forms. For the second they build rules from weighted fits and coin-flip sampling that hit the best rate in set cases. Random rules can beat set rules in speed of shrink when a key index tops one. Like results hold on the unit ball and the standard simplex. The work guides codes that must sum over balls and spheres with care.

Catalog record

CREATORJiansong Li, Heping Wang
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE119 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-17546

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Optimal quadrature for weighted function spaces on multivariate domains Thanks: The research was supported by the National Natural Science Foundation of China (Project no. 12371098). Jiansong Li, Heping Wang Abstract Abstract: Consider the numerical integration {\rm Int}_{\mathbb{S}^{d},w}(f)=\int_{\mathbb{S}^{d}}f({\bf x})w({\bf x}){\rm d}\sigma({\bf x}) for weighted Sobolev classes BW_{p,w}^{r}(\mathbb{S}^{d}) with a Dunkl weight w and weighted Besov classes BB_{\gamma}^{\Theta}(L_{p,w}(\mathbb{S}^{d})) with the generalized smoothness index \Theta and a doubling weight w on the unit sphere \mathbb{S}^{d} of the Euclidean space \mathbb{R}^{d+1} in the deterministic and randomized case settings. For BW_{p,w}^{r}(\mathbb{S}^{d}) we obtain the optimal quadrature errors in both settings. For BB_{\gamma}^{\Theta}(L_{p,w}(\mathbb{S}^{d})) we use the weighted least \ell_{p} approximation and the standard Monte Carlo algorithm to obtain upper estimates of the quadrature errors which are optimal if w is an A_{\infty} weight in the deterministic case setting or if w is a product weight in the randomized case setting. Our results show that randomized algorithms can provide a faster convergence rate than that of the deterministic ones when p>1 . Similar results are also established on the unit ball and the standard simplex of \mathbb{R}^{d} . Keywords: Numerical integration; Weighted Sobolev classes; Weighted Besov classes of generalized smoothness; Deterministic and randomized case settings; Weighted least \ell_{p} approximation MSC(2000) subject classification: 65D30; 65D32; 41A55; 65C05; 33C50; 33C52. 1 Introduction A critical problem in applied mathematics and data sciences is to calculate the numerical integration {\rm Int}_{\Omega^{d},w}(f)=\int_{\Omega^{d}}f({\bf x})w({\bf x}){\rm d}\mathsf{m}({\bf x}), (1.1) for a function f belonging to a class F_{d} of continuous functions on \Omega^{d} , where \Omega^{d} is a compact subset of the Euclidean space equipped with a measure w({\bf x}){\rm d}\mathsf{m}({\bf x}) . For most cases, we could not compute this integration utilizing the fundamental theorem of the calculus since there is no closed form expression of the antiderivatives. Therefore, we have to approximate such integration numerically. Meanwhile, in the applications we only know function values on finite points on \Omega^{d} which are called standard information . Hence, we have to use algorithms based on these finite function values. One type of algorithms is the deterministic algorithm of the form A_{n}(f):=\varphi_{n}\left[f({\bf x}_{1}),f({\bf x}_{2}),\dots,f({\bf x}_{n})\right], where {\bf x}_{j}\in\Omega^{d} can be chosen adaptively and \varphi_{n}:\mathbb{R}^{n}\rightarrow\mathbb{R} is an arbitrary mapping. We denoted by \mathcal{A}_{n}^{\rm det} the class of all algorithms of this form. (Adaption means that the selection of {\bf x}_{j} may depend on the already computed values f({\bf x}_{1}),f({\bf x}_{2}),\dots,f({\bf x}_{j-1}) .) Then, for a positive integer n , we define • the deterministic case error of an algorithm A_{n} on F_{d} by e^{\rm det}({\rm Int}_{\Omega^{d},w};F_{d},\,A_{n}):=\sup\limits_{f\in F_{d}}\left|{\rm Int}_{\Omega^{d},w}(f)-A_{n}(f)\right|; • the n -th minimal (optimal) deterministic case error on F_{d} by e_{n}^{\rm det}({\rm Int}_{\Omega^{d},w};F_{d}):=\inf\limits_{A_{n}\in\mathcal{A}_{n}^{\rm det}}e^{\rm det}({\rm Int}_{\Omega^{d},w};F_{d},\,A_{n}). Usually we assume that the class F_{d} is convex and balanced. It follows from [ 3 ] that the n -th minimal deterministic case error e_{n}^{\rm det}({\rm Int}_{\Omega^{d},w};F_{d}) can be achieved by linear algorithms, i.e., the algorithms of the form A_{n}^{\rm lin}(f)=\sum_{j=1}^{n}{\lambda}_{j}f({\bf x}_{j}),\ {\lambda}_{j}\in\mathbb{R},\ j=1,\dots,n, which is also called a quadrature formula , and, moreover, it follows from [ 46 , Theorem 4.7] that e_{n}^{\rm det}({\rm Int}_{\Omega^{d},w};F_{d})=\inf_{\begin{subarray}{c}{\bf x}_{1},\dots,{\bf x}_{n}\in\Omega^{d}\end{subarray}}\sup_{\begin{subarray}{c}f\in F_{d}\\ f({\bf x}_{1})=\dots=f({\bf x}_{n})=0\end{subarray}}\int_{\Omega^{d}}f({\bf x})w({\bf x}){\rm d}\mathsf{m}({\bf x}). (1.2) We say that a quadrature formula A_{n}^{\rm lin} is positive if {\lambda}_{j}\geq 0,j=1,\dots,n , and is a quasi-Monte-Carlo (QMC) algorithm if {\lambda}_{j}=1/n,j=1,\dots,n . For usual smooth classes the integration problem in the deterministic setting suffers from the curse of dimensionality if the dimension d is large. It is well known that the standard Monte-Carlo algorithm overcomes the curse of dimensionality. In this paper we consider randomized algorithms (Monte-Carlo algorithms). Randomized algorithms (also called Monte-Carlo algorithms) are understood as \Sigma\otimes\mathcal{B}(F_{d}) measurable functions (A^{\omega})=(A^{\omega}(\cdot))_{{\omega}\in\mathcal{F}}:\mathcal{F}\times F_{d}\to\mathbb{R}, where \mathcal{B}(F_{d}) denotes the Borel \sigma -algebra of F_{d} , (\mathcal{F},\Sigma,\mathcal{P}) is a suitable probability space, and for any fixed {\omega}\in\mathcal{F} , A^{\omega} is a deterministic method with cardinality n(f,{\omega}) . The number n(f,{\omega}) may be randomized and adaptively depend on the input, and the cardinality of (A^{\omega}) is then defined by {\rm Card}(A^{\omega}):=\sup_{f\in F_{d}}\mathbb{E}_{\omega}\,n(f,{\omega}):=\sup\limits_{f\in F_{d}}\int_{\mathcal{F}}n(f,\omega){\rm d}\mathcal{P}(\omega). Denote by \mathcal{A}_{n}^{\rm ran} the class of all randomized algorithms with cardinality not exceeding n . Then, for a positive integer n , we define • the randomized case error of a randomized algorithm (A^{\omega}) on F_{d} by e^{\rm ran}({\rm Int}_{\Omega^{d},w};F_{d},(A^{\omega})):=\sup\limits_{f\in F_{d}}\mathbb{E}_{\omega}|{\rm Int}_{\Omega^{d},w}(f)-A^{\omega}(f)|; • the n -th minimal (optimal) randomized case error on F_{d} by e_{n}^{\rm ran}({\rm Int}_{\Omega^{d},w};F_{d}):=\inf\limits_{(A^{\omega})\in\mathcal{A}_{n}^{\rm ran}}e^{\rm ran}({\rm Int}_{\Omega^{d},w};F_{d},(A^{\omega})). Since a deterministic algorithm may be viewed as a randomized algorithm, it follows from definitions that e_{n}^{\rm ran}({\rm Int}_{\Omega^{d},w};F_{d})\leq e_{n}^{\rm det}({\rm Int}_{\Omega^{d},w};F_{d}). Numerous results indicate that the optimal randomized quadrature errors are generally less than optimal deterministic quadrature errors. Consequently, employing randomized algorithms proves to be an effective strategy for reducing errors in a variety of applications, particularly in dealing with high-dimensional scenarios. Researchers have shown significant interest in the integration problem described in ( 1.1 ) for Sobolev-type and Besov-type spaces. These function spaces are crucial in functional analysis, numerical analysis, approximation theory, and related fields (see, for example, [ 51 , 52 , 15 ] ). We can now review some previous findings in this area. There is a vast literature on this classical problem for various unweighted function classes, especially for Sobolev and Besov classes. For abbreviation, when w\equiv 1 , we write e_{n}^{\rm det}(F_{d})\equiv e_{n}^{\rm det}({\rm Int}_{\Omega^{d},w};F_{d}) and e_{n}^{\rm ran}(F_{d})\equiv e_{n}^{\rm ran}({\rm Int}_{\Omega^{d},w};F_{d}) . 1. Consider the classical Sobolev class BW_{p}^{r}([0,1]^{d}) , 1\leq p\leq\infty , r\in\mathbb{N} , defined by BW_{p}^{r}([0,1]^{d}):=\left\{f\in L_{p}([0,1]^{d}):\,\sum_{|\boldsymbol{\alpha}|_{1}\leq r}\|D^{\boldsymbol{\alpha}}f\|_{p}\leq 1\right\}, and the Hölder class C^{k,\gamma}([0,1]^{d}) , k\in\mathbb{N}_{0} , 0<{\gamma}\leq 1 , defined by C^{k,\gamma}([0,1]^{d}):=\left\{f\in C([0,1]^{d}):\,|D^{\boldsymbol{\alpha}}f({\bf x})-D^{\boldsymbol{{\alpha}}}f({\bf y})|\leq\max_{1\leq i\leq d}|x_{i}-y_{i}|^{\gamma},\,|\boldsymbol{\alpha}|=k\right\}, where \boldsymbol{\alpha}\in\mathbb{N}_{0}^{d},\ |\boldsymbol{\alpha}|:=\sum_{i=1}^{d}\alpha_{i} , and D^{\boldsymbol{\alpha}}f is the partial derivative of order \boldsymbol{\alpha} of f in the sense of distribution. Bakhvalov in [ 1 ] and [ 2 ] proved that 1 1 1 The notation A_{n}\asymp B_{n} means that A_{n}\lesssim B_{n} and A_{n}\gtrsim B_{n} , and A_{n}\lesssim B_{n} ( A_{n}\gtrsim B_{n} ) means that there exists a constant c>0 independent of n such that A_{n}\leq cB_{n} ( A_{n}\geq cB_{n} ). e_{n}^{\rm det}(C^{k,{\gamma}}([0,1]^{d}))\asymp n^{-\frac{k+{\gamma}}{d}}\quad{\rm and}\quad e_{n}^{\rm det}(BW_{\infty}^{r}([0,1]^{d}))\asymp n^{-\frac{r}{d}}. Novak extended the second equivalence result in [ 44 ] and [ 45 ] , and obtained, for 1\leq p<\infty and r>d/p , e_{n}^{\rm det}(BW_{p}^{r}([0,1]^{d}))\asymp n^{-\frac{r}{d}}. Meanwhile, Novak considered the randomized case errors of the above two classes in [ 44 ] and [ 45 ] , and proved that e_{n}^{\rm ran}(C^{k,{\alpha}}([0,1]^{d}))\asymp n^{-\frac{k+{\alpha}}{d}-\frac{1}{2}}, and for 1\leq p\leq\infty and r>d/p , e_{n}^{\rm ran}(BW_{p}^{r}([0,1]^{d}))\asymp n^{-\frac{r}{d}-\frac{1}{2}+(\frac{1}{p}-\frac{1}{2})_{+}}, where a_{+}=\max(a,0) . 2. Consider the anisotropic Sobolev class BW_{p}^{{\bf r}}([0,1]^{d}),\ 1\leq p\leq\infty,\ {\bf r}=(r_{1},\cdots,r_{d})\in\mathbb{N}^{d} , defined by BW_{p}^{{\bf r}}([0,1]^{d}):=\left\{f\in L_{p}([0,1]^{d}):\,\sum_{j=1}^{d}\left\|\frac{\partial^{r_{j}}f}{\partial x_{j}^{r_{j}}}\right\|_{p}\leq 1\right\}. Fang and Ye in [ 21 ] obtained for g({\bf r}):=\big(\sum_{j=1}^{d}r_{j}^{-1}\big)^{-1}>1/{p} , e_{n}^{\rm det}(BW_{p}^{{\bf r}}([0,1]^{d}))\asymp n^{-g({\bf r})}, and for g({\bf r})>1/{p} , e_{n}^{\rm ran}(BW_{p}^{{\bf r}}([0,1]^{d}))\asymp n^{-g({\bf r})-\frac{1}{2}+(\frac{1}{p}-\frac{1}{2})_{+}}. For the anisotropic Hölder-Nikolskii classes, Fang and Ye obtained the similar results in [ 21 ] . 3. Consider the Sobolev class with bounded mixed derivative BW_{p}^{r,\rm mix}([0,1]^{d}),\ r\in\mathbb{N},\ 1\leq p\leq\infty , defined by BW_{p}^{r,\rm mix}([0,1]^{d}):=\left\{f\in L_{p}([0,1]^{d}):\,\sum_{|\boldsymbol{\alpha}|_{\infty}\leq r}\|D^{\boldsymbol{\alpha}}f\|_{p}\leq 1\right\}, where |\boldsymbol{\alpha}|_{\infty}:=\max_{1\leq i\leq d}{\alpha}_{i} . The authors in [ 8 , 23 , 47 , 50 ] obtained for r>1/{p} and 1<p<\infty , e_{n}^{\rm det}(BW_{p}^{r,\rm mix}([0,1]^{d}))\asymp n^{-r}(\log n)^{\frac{d-1}{2}}. It was shown in [ 34 , 42 , 54 ] that for r>\max\{1/p,1/2\} and 1<p<\infty , e_{n}^{\rm ran}(BW_{p}^{r,\rm mix}([0,1]^{d}))\asymp n^{-r-\frac{1}{2}+(\frac{1}{p}-\frac{1}{2})_{+}}. 4. For the Sobolev class BW_{p}^{r}(\mathbb{S}^{d})

Read the complete text