Approximation numbers of Sobolev and Gevrey type embeddings on the sphere and on the ball -- Preasymptotics, asymptotics, and tractability

Abstract

In this paper, we investigate optimal linear approximations ($n$-approximation numbers ) of the embeddings from the Sobolev spaces $H^r(r>0)$ for various equivalent norms and the Gevrey type spaces $G^{\alpha ,\beta }(\alpha ,\beta >0)$ on the sphere ${\mathbb{S}}^d$ and on the ball ${\mathbb{B}}^d$, where the approximation error is measured in the $L_2$-norm. We obtain preasymptotics, asymptotics, and strong equivalences of the above approximation numbers as a function in $n$ and the dimension $d$. We emphasis that all equivalence constants in the above preasymptotics and asymptotics are independent of the dimension $d$ and $n$. As a consequence we obtain that for the absolute error criterion the approximation problems $I_d:H^r\to L_2$ are weakly tractable if and only if $r>1$, not uniformly weakly tractable, and do not suffer from the curse of dimensionality. We also prove that for any $\alpha ,\beta >0$, the approximation problems $I_d:G^{\alpha ,\beta }\to L_2$ are uniformly weakly tractable, not polynomially tractable, and quasi-polynomially tractable if and only if $\alpha \ge 1$.

26 pages