STRONG EQUIVALENCES OF APPROXIMATION NUMBERS AND TRACTABILIY OF WEGHED NSP SV M*

Jidong HAO (郝季冬) Heping WANG (汪和平)†

School of Mathematical Sciences, Capital Normal University, Beijing 100048, China E-mail : 1047695025@qq.com; wanghp@cnu.edu.cn

[1,10–12]),and Sobolev embeddings and Gevrey type embeddings on the sphere Sdand on the ball Bd(see[2]).In[25],Werschulz and Wo´zniakowski investigated the tractability of weighted isotropic Sobolev embeddings.The aim of this article is to generalize the above results to weighted anisotropic Sobolev embeddings.

We also consider the tractability of the approximation problemI={Id}of the weighted anisotropic Sobolev embeddings.We consider algorithms that use finitely many continuous linear functionals.The information complexityn(ε,Id)is defined as the minimal number of linear functionals which are needed to find an approximation to within an error thresholdε.There are two kinds of tractability:that based on polynomial convergence,and that based on exponential convergence.The classical tractability describes how the information complexity behaves as a function ofdandε−1,while the exponential convergence-tractability(EC-tractability)does as one ofdand(1+lnε−1).Nowadays,the study of tractability and EC-tractability has attracted much interest,and a great number of interesting results have been obtained(see[5,6,15–18,22]and the references therein).

Denote byH(Kd,a,2b)the analytic Korobov space which is a reproducing kernel Hilbert space with the reproducing kernelKd,a,2b,and whose definition will be given in Section 2.2.Such spacesH(Kd,a,2b)have been widely investigated in the study of tractability and ECtractability(see[4–8,13,14,23]).In particular,the articles[4,23]considered different notions of EC-tractability of the approximation problems APP={APPd}d∈N,and obtained the corresponding necessary and sufficient conditions,where

In this article,we establish the relationship of the information complexitiesn(ε,Id)andn(ε,APPd).On the basis of this relationship,we obtain the necessary and sufficient conditions for various notions of tractability of the approximation problemI={Id}d∈N.

The article is organized as follows:in Section 2 we introduce the weighted anisotropic Sobolev spaces,the analytic Korobov spaces,the properties of the approximation numbers,the tractability,and then state our main results.Section 3 is devoted to proving the strong equivalence of the approximation numbers of the weighted anisotropic embeddings.In Section 4 we prove the tractability of the weighted anisotropic embeddings.

2 Preliminaries and Main Results

2.1 Weighted anisotropic Sobolev spaces on[0,1]d

2.2 Analytic Korobov spaces

2.3 Approximation numbers

2.4 General notations of tractability

In both cases,e(0,Sd)=1.In other words,the normalized error criterion and the absolute error criterion coincide for the approximation problemsI={Id}and APP={APPd}.

Forε∈(0,1)andd∈N,letn(ε,Sd)be the information complexity defined by

We say thatS={Sd}d∈Nis

•Exponential convergence-strong polynomially tractable(EC-SPT)if and only if there exist non-negative numbersCandpsuch that,for alld∈N,ε∈(0,1),

2.5 Main results

3 Strong Equivalences of Approximation Numbers