---
abstract: 'We consider the problem of integration of $d$-variate analytic functions defined on the unit cube with directional derivatives of all orders bounded by 1.  We prove that the Clenshaw Curtis Smolyak algorithm leads to weak tractability of the problem.  This seems to be the first positive tractability result for the Smolyak algorithm for a normalized and unweighted problem.  The space of integrands is not a tensor product space and therefore we have to develop a different proof technique.  We use the polynomial exactness of the algorithm as well as an explicit bound on the operator norm of the algorithm.' 
author:
- |
    Aicke Hinrichs\
    Institut für Mathematik, Universität Rostock\
    Ulmenstraße 69, Haus 3, 18051 Rostock, Germany\
    email: aicke.hinrichs@uni-rostock.de\
    \
    Erich Novak[^1], Mario Ullrich[^2]\
    Mathematisches Institut, Universität Jena\
    Ernst-Abbe-Platz 2, 07743 Jena, Germany\
    email: erich.novak@uni-jena.de, ullrich.mario@gmail.com
title: 'On Weak Tractability of the Clenshaw–Curtis Smolyak Algorithm'
---

Introduction and Result {#sec1}
=======================

We prove that the Clenshaw Curtis Smolyak algorithm is weakly tractable for a class of analytic functions.  Weak tractability of the integration problem for this class was recently shown in [@HNUW13].  In \[12\] high derivatives are approximated by finite differences.  This approximation is very unstable, it does not give a practical algorithm.  In this paper we show with different proof techniques that the Smolyak algorithm can be used with essentially the same error bounds.  Therefore we are now able to give a constructive algorithm, while the result from [@HNUW13] was only a complexity result. 

To explain our result in detail, we say a few words about this algorithm, about recent tractability results, and about our proof technique. 

The CCS algorithm
-----------------

We want to compute $$S_d(f) = \int_{[0,1]^d} f(x) \, {\rm d} x$$ and use the Smolyak algorithm [@Sm63] in combination with the Clenshaw Curtis algorithm as in Novak, Ritter [@NR96; @NR97; @NR99], see also Gerstner, Griebel [@GG98] and Petras [@Pe00].  We describe the resulting CCS algorithm. 

For $f\colon[0,1]\to{\mathbb{R}}$ define the sequence of (one-dimensional) quadrature rules $$\label{eq:U}
U^\ell(f) \;=\; \sum_{j=1}^{m_\ell} a_j^\ell\, f(x_j^\ell), \quad \ell\in{\mathbb{N}},$$ with $$m_\ell \;=\; \begin{cases}
1, & \ell=1 \\
2^{\ell-1}+1, & \ell\ge2 .  
\end{cases}$$ For $\ell=1$ there is only one node $x_1^1=1/2$ with weight $a_1^1=1$. For $\ell > 1$ we have the nodes $$x_j^\ell \;=\; \frac12 \left(1-\cos\Bigl(\pi\frac{j-1}{m_\ell-1}\Bigr)\right), 
\qquad j=1,\dots,m_\ell$$ and weights $$\label{eq:a}
a_j^\ell \;=\; \begin{cases} 
\frac{1}{2m_\ell(m_\ell-2)}, & j=1,m_\ell\\
\frac{1}{m_\ell-1} \left( 1 - \frac{\cos (j-1)\pi}{(m_\ell-1)^2-1}  
                - 2\sum\limits_{k=1}^{\frac{m_\ell-3}{2}} 
\frac{\cos \frac{2k(j-1)\pi}{m_\ell-1}}{4 k^2 -1}\right), & j=2,\dots m_\ell-1. 
\end{cases}$$ These rules are called Clenshaw-Curtis (CC) quadrature rules.  It is well known that the CC-rules are positive rules, that is $a_j^\ell>0$ for all $j$ and $\ell$, see [@BP11]. 

Observe that the nodes of the $U^\ell$ are nested, since $$x_{2j-1}^{\ell+1} = x_j^{\ell}  \qquad \mbox{for }\  j=1,2,\dots m_\ell.$$

Additionally, we define $$\label{eq:Delta}
\Delta^1 \,=\, U^1 \quad \text{ and } \quad \Delta^\ell \,=\, U^\ell-U^{\ell-1}, 
\quad \ell\ge2.$$ Note that, for $f\colon[0,1]\to{\mathbb{R}}$, $$\Delta^\ell(f) \;=\; \sum_{j=1}^{m_\ell} b_j^\ell\, f(x_j^\ell), \quad \ell\in{\mathbb{N}},$$ with $$b_{j}^\ell \;=\; \begin{cases}
a_j^\ell & \text{ for even } j \\ 
a_j^\ell - a_{\frac{j+1}{2}}^{\ell-1}  & \text{ for odd } j. 
\end{cases}$$ These weights, except for $\ell=1$, sum up to zero. 

Then the Smolyak algorithm (based on the CC rule $U^\ell$) is defined by $$A(q,d) \;=\; \sum_{i\in{\mathbb{N}}_0^d\colon |i|\le q-d} 
    \Delta^{i_1+1} \otimes\dots\otimes \Delta^{i_d+1}.$$ Here, the $d$-fold tensor product of the functionals $\Delta^\ell$ is given by $$(\Delta^{\ell_1} \otimes\ldots\otimes \Delta^{\ell_d})(f) 
\;=\; \sum_{j_1=1}^{m_{\ell_1}}\ldots \sum_{j_d=1}^{m_{\ell_d}}\,
    b_{j_1}^{\ell_1}\cdot\ldots\cdot b_{j_d}^{\ell_d}\; 
    f(x_{j_1}^{\ell_1},\ldots,x_{j_d}^{\ell_d})$$ for $f\colon[0,1]^d\to{\mathbb{R}}$. Note that we can write this CCS algorithm $A(q,d)$, for $q=d+k$, as $$A(d+k,d) \;=\; \sum_{\ell=1}^{k+1} A(d+k-\ell,d-1) \otimes \Delta^\ell.$$ The Smolyak algorithm can also be written as $$A(q,d) = 
\sum_{q-d+1 \le |i| \le q} (-1)^{q-|i|} \cdot 
\binom{d-1}{q-|i| } \cdot
(U^{i_1} \otimes \dots \otimes U^{i_d}) ,$$ see Wasilkowski and Woźniakowski [@WW95 Lemma 1].  Clearly $A(q,d)$ is a linear functional, and $A(q,d)(f)$ depends on $f$ only through function values at a finite number of points.  To describe these points let $$X^i = \{ x_1^i, \dots, x^i_{m_i} \} \subset [0,1]$$ denote the set of nodes of $U^i$. The tensor product algorithm $U^{i_1} \otimes \dots \otimes U^{i_d}$ is based on the grid $X^{i_1} \times \dots \times X^{i_d}$, and therefore $A(q,d)(f)$ depends (at most) on the values of $f$ at points in the union $$H(q,d) = \bigcup_{q-d+1 \leq |i| \leq q} 
(X^{i_1} \times \dots \times X^{i_d}) \subset [0,1]^d$$ of grids.  Nested sets $X^i \subset X^{i+1}$ yield $H(q,d) \subset H(q+1,d)$ and $$H(q,d) = \bigcup_{|i| = q} 
(X^{i_1} \times \dots \times X^{i_d}).$$ Therefore nested sets seem to be the most economical choice.  The points $x \in H(q,d)$ are called hyperbolic cross points and $H(q,d)$ is also called a sparse grid. 

In what follows we will bound the number of function values that are sufficient for the CCS algorithm to achieve a certain error.  For this we define $$N_d(k) \;:=\; \bigl|H(d+k,d)\bigr|$$ as the number of points used by $A(d+k,d)$.

Some known properties of the CCS algorithm
------------------------------------------

Error bounds for the Smolyak algorithm were proved by Smolyak [@Sm63], Wasilkowski and Woźniakowski [@WW95] and many others, see also [@BG04; @Gr06; @SU06; @SU11].  In this paper we always consider the worst case error with respect to the unit ball for some norm, and therefore properties of various norms are very relevant. 

Most of the known error bounds are for tensor product spaces, i.e., one takes norms with $$\label{prop-tens} 
\Vert f_1 \otimes f_2 \otimes \dots \otimes f_d \Vert = 
\prod_{i=1}^d \Vert f_i \Vert,$$ where $$(f_1 \otimes f_2 \otimes \dots \otimes f_d)(x) = 
\prod_{i=1}^d  f_i(x_i) .$$ We stress that in this paper we do *not* use tensor product norms since we use the norm $$\label{norm} 
\sup_{k \in {\mathbb{N}}_0}  \sup_{\theta\in S^{d-1}}\, 
\|D^k_\theta f\|_\infty ,$$ where $D_\theta f$ denotes the directional derivative of $f$ in direction $\theta$. Therefore we cannot use the property and error bounds based on it.  We want to illustrate this a bit further.  For $f_1(x) = x$ on $[0,1]$ clearly all partial derivatives of $f_1 \otimes f_1 \otimes \dots \otimes 
f_1$ are bounded by 1.  Some directional derivatives are larger than 1 and hence, for the norm , $$\Vert f_1 \otimes f_1 \Vert > \Vert f_1 \Vert \cdot \Vert f_1 \Vert.$$ This property makes the unit ball with respect to the norm *smaller* than the unit ball of a tensor product space. 

Consider now $C^r([0,1]^d)$ with the standard norm $$\label{standard} 
\Vert f \Vert = \max_{|\alpha| \le r} \Vert D^\alpha f \Vert_\infty,$$ where $\alpha = ({\alpha}_1, \dots , {\alpha}_d) \in {\mathbb{N}}_0^d$ is used to denote a partial derivative of order $|\alpha | = {\alpha}_1 + \dots + {\alpha}_d$. Then, for $r=1$ and $f_2(x)=x^2$ on $[0,1]$, $$2 = \Vert f_2 \otimes f_2 \Vert < \Vert f_2 \Vert \cdot \Vert f_2 \Vert = 4.$$ This property makes the unit balls of $C^k([0,1]^d)$ *larger* than the unit balls of tensor product spaces.  We present a result from [@NR97] for the CCS algorithm for the order of convergence and the standard norm , hence the unit ball is $$C^r_d = \{ f: [0,1]^d \to {\mathbb{R}}\mid 
\max_ {|\alpha| \leq r} \Vert D^\alpha  f \Vert_\infty \le 1 \}.$$

\[prop1\] For $d, r \in {\mathbb{N}}$ there exists $c_{r,d}>0$ such that $$e(A(q,d),C^r_d) = \sup_{f \in C^r_d} | A(q,d)(f) - S_d(f) | 
\leq  c_{r,d} \cdot N^{-r/d} \cdot(\log N)^{(d-1) \cdot (r/d +1)},$$ where $N=N_d(q-d)$ is the number of function values used by the CCS algorithm. 

We describe the proof since in this paper we use a similar technique, but with a different emphasis.  Observe that Proposition \[prop1\] contains unknown constants $c_{r,d}$ and hence the error bound makes sense only for given $r$ and $d$ and very large $N$ or small error ${\varepsilon}$. For the proof we need three facts. 

First we need an estimate of the number $N_d(k)$ of knots that are used by $A(d+k,d)$. We use $\approx$ to denote the strong equivalence of sequences, i.e., $v_n \approx w_n$ iff $\lim_{n\to \infty }v_n/w_n=1$. Then, for $k \to \infty$ and fixed $d$, $$\label{TMG} 
N_d(k) \approx \frac{1}{(d-1)!  \cdot 2^{d-1}} 
\cdot 2^k \, k^{d-1},$$ see Müller-Gronbach [@MG Lemma 1]. 

Smolyak’s construction leads to cubature formulas with negative weights, even if positive weights are used in the univariate case.  However, the weights are relatively small in absolute value.  Hence, secondly, we need a bound for ${\left\Vert A(q,d) \right\Vert}$, where ${\left\Vert A(q,d) \right\Vert}$ denotes the sum of the absolute values of the weights of $A(q,d)$. We use $c_d$ and $c_{r,d}$ to denote different positive constants depending on $d$ or on $r$ and $d$, respectively.  There exists a constant $c_d>0$ such that $$\label{norm von CCS} 
{\left\Vert A(d+k,d) \right\Vert} \leq c_d \cdot  \Big(\log \big( N_d(k)\big)\Big)^{d-1} .$$

For a proof observe that $$\# \big\{ i \in {\mathbb{N}}^d \,\big|\, |i| = \ell \big\} = 
\binom{\ell - 1}{d-1}.$$ Since the Clenshaw-Curtis formulas have positive weights, we conclude $$\label{norm2} 
{\left\Vert A(d+k,d) \right\Vert}
\leq c_d \cdot \! \!   \sum_{\ell=k+1}^{d+k} \binom{\ell - 1}{d-1} \leq
c_d \cdot \binom{d+k - 1}{d-1} \leq c_d \cdot (d+k)^{d-1},$$ where we can take $c_d = 2^d$. Then follows from $$\log N_d(k) \geq c_d \cdot (d+k).$$

The third fact that we need is that $A(d+k,d)$ is exact for all polynomials of total degree at most $2k+1$, see [@NR96; @NR99]. 

We add in passing that the estimates , and are not suitable for tractability studies.  In particular we cannot use estimates that contain unknown or exponentially large constants $c_d$.

The curse of dimensionality
---------------------------

We study multivariate integration for different classes $F_d$ of smooth functions $f \colon [0,1]^d \to {\mathbb{R}}$. Our emphasis is on large values of $d\in{\mathbb{N}}$. We want to approximate $$\label{int} 
S_d(f) = \int_{D_d} f(x) \, {{\rm d}}x \quad \mbox{for} \quad  
f\in F_d$$ up to some error ${\varepsilon}>0$.

We consider (deterministic) algorithms that use only function values, and classes $F_d$ of functions bounded in absolute value by 1 and containing all constant functions $f(x)\equiv c$ with $|c|\le 1$. An algorithm that uses no function value at all must be a constant, $A_0(f)\equiv b$, and its error is at least $$\max_{f\in F_d}|S_d(f)|=1.$$ We call this the initial error of the problem, it does not depend on $d$. Hence multivariate integration is well scaled and that is why we consider ${\varepsilon}<1$.

Let $n({\varepsilon},F_d)$ denote the minimal number of function values needed for this task in the worst case setting.  By the *curse of dimensionality* we mean that $n({\varepsilon},F_d)$ is exponentially large in $d$. That is, there are positive numbers $c$, ${\varepsilon}_0$ and $\gamma$ such that $$\label{curse} 
n({\varepsilon},F_d) \ge c \, (1+\gamma)^d \quad  
\mbox{for all} \quad {\varepsilon}\le {\varepsilon}_0  \quad  
\mbox{and infinitely many} \quad d\in {\mathbb{N}}.$$ For many natural classes $F_d$ the bound in  will hold for all $d\in{\mathbb{N}}$. There are many classes $F_d$ for which the curse of dimensionality has been proved, see [@NW08; @NW10] for such examples. 

The classes $C^r_d$ were already studied in 1959 by Bakhvalov [@Ba59], see also [@No88].  He proved that there are two positive numbers $c_{r,d}$ and $\tilde c_{r,d}$ such that $$\label{bak1959} 
c_{r,d}\,{\varepsilon}^{-d/r}\le n({\varepsilon}, C^r_d )\le 
\tilde c_{r,d} \,{\varepsilon}^{-d/r} \quad 
\text{for all}  \ d\in{\mathbb{N}}\ \text{and} \ {\varepsilon}\in(0,1).$$ This means that for a fixed $d$ and for ${\varepsilon}$ tending to zero, we know that $n({\varepsilon}, C^r_d )$ is of order ${\varepsilon}^{-d/r}$ and the exponent of ${\varepsilon}^{-1}$ grows linearly in $d$. If we compare this with Proposition \[prop1\] we may say that the CCS algorithm is “almost optimal” for each class $C^r_d$. In this sense the algorithm is “universal”. 

Bakhvalov’s result does not allow us to conclude whether the curse of dimensionality holds for the classes $C^r_d$. In fact, if we reverse the roles of $d$ and ${\varepsilon}$, and consider a fixed ${\varepsilon}$ and $d$ tending to infinity, the bound  on $n({\varepsilon}, C^r_d )$ is useless.  The curse of dimensionality for the classes $C^r_d$ was only recently proved in Hinrichs, Novak, Ullrich and Woźniakowski [@HNUW12]. 

\[cor:Lip\] The curse of dimensionality holds for the classes $C^r_d$ with the *super-exponential* lower bound $$n({\varepsilon},C^r_d ) \ge c_r\,(1-{\varepsilon}) \, d^{\,d /(2r+3)}$$ for all $d\in{\mathbb{N}}$ and ${\varepsilon}\in(0,1)$, where $c_r\in(0,1]$ depends only on $r$.

One may say that the classes $C^r_d$ are too large and therefore we obtain the curse of dimensionality.  Therefore it is natural to study smaller classes such as the unit balls $F_d$ with respect to the norm .  In Hinrichs, Novak, Ullrich and Woźniakowski [@HNUW13] we prove

\[weak\] The curse of dimensionality does not hold for the classes $F_d$ since the problem is weakly tractable, i.e., $$\lim_{d+{\varepsilon}^{-1} \to \infty} 
\frac{\log (n({\varepsilon}, F_d ))}{d+{\varepsilon}^{-1}} = 0.$$

This means that, for a fixed ${\varepsilon}$, the complexity of integration is sub-exponential in the dimension.  Unfortunately, the proof of Proposition \[weak\] in [@HNUW13] is rather theoretical, we use a very unstable algorithm which is based on the approximation of high derivatives by function values via finite differences, see also Vybíral [@Vyb13].  This algorithm could not be implemented because of huge rounding errors.  The aim of this paper is to give a much more constructive proof of Proposition \[weak\] by means of the CCS algorithm, see Theorem \[thm:main\]. 

Main result
-----------

Let $$\label{eq:class}
F_d = \Bigl\{ f\in C^\infty([0,1]^d) \mid 
\sup_{k \in {\mathbb{N}}_0}  \sup_{\theta\in S^{d-1}}\, 
    \|D^k_\theta f\|_\infty\le 1 \Bigr\},$$ where $D_\theta f$ denotes the directional derivative of $f$ in direction $\theta$.

\[thm:main\] For each $d\in{\mathbb{N}}$ and ${\varepsilon}\in(0,1]$ define $$            k_{{\varepsilon},d} \;:=\; 
\biggl\lceil\max\Bigl\{3\,d^{2/3},\; \ln(1/{\varepsilon})\Bigr\} \biggr\rceil .$$ Then, $$e(k_{{\varepsilon},d}, d) \;:=\; 
\sup_{f\in F_d} {\left\vert A\bigl(d+k_{{\varepsilon},d},d\bigr)(f) \,-\,  S_d(f) \right\vert} \;\le\; {\varepsilon}$$ and the number of function values $N_d(k_{{\varepsilon},d})$ used by the CCS algorithm $A(d+k_{{\varepsilon},d},d)$ satisfies $$N_d(k_{{\varepsilon},d}) \;\le\; 2\,\exp\Bigl\{k_{{\varepsilon},d}\, 
    \Bigl( 2 + \ln\Bigl( 1- d/\ln({\varepsilon}) \Bigr) \Bigr)\Bigr\}.$$

This shows, in particular, that the problem of integration for $F_d$ is weakly tractable and that the CCS algorithm is weakly tractable for these classes. 

One may argue that also the CCS algorithm is “mildly unstable” and one would prefer an algorithm with small operator norm, such as a cubature formula with positive weights that add up to 1.  Indeed, we prove an analogue of Theorem \[thm:main\] with a better dependence of the number of nodes. 

\[thm:qmc\] For each $d\in{\mathbb{N}}$ and ${\varepsilon}\in(0,1]$ define $$k^*_{{\varepsilon},d} \;:=\; 
\biggl\lceil\max\Bigl\{4\,d^{1/2},\; \ln(1/{\varepsilon})\Bigr\} \biggr\rceil .$$ Then there exists a cubature rule $Q\bigl(k^*_{{\varepsilon},d},d\bigr)$ with positive weights that add up to 1 with error $$e(k^*_{{\varepsilon},d}, d) \;:=\; 
\sup_{f\in F_d} {\left\vert Q\bigl(k^*_{{\varepsilon},d},d\bigr)(f) \,-\,  S_d(f) \right\vert} \;\le\; {\varepsilon}$$ and the number of function values $N^*_d(k^*_{{\varepsilon},d})$ used by $Q\bigl(k^*_{{\varepsilon},d},d\bigr)$ satisfies $$N^*_d(k^*_{{\varepsilon},d}) \;\le\; \exp\Bigl\{k^*_{{\varepsilon},d}\, 
    \Bigl( 1 + \ln\Bigl( 1- d/\ln({\varepsilon}) \Bigr) \Bigr)\Bigr\}.$$

The proof is based on a constructive version of Tchakalov’s Theorem due to Davis, see [@Dav67].  However, to construct these cubature formulas, one has to solve exponentially (in $d$) many linear systems of equations, each having exponentially many unknowns.  So these methods can be applied only for small $d$. In contrast, the CCS Smolyak algorithm can be easily implemented. 

Related results and open problems
---------------------------------

-   Considering the above remarks about the relation of Theorems \[thm:main\] and \[thm:qmc\], a natural question is whether the weak tractability of integration for $F_d$ can be proved with a positive cubature formula which can be efficiently constructed.  Additionally, we pose the same question for QMC algorithms, i.e. positive cubature formulas with equal weights.  For recent surveys on QMC algorithms see [@DKS; @DP]. 

-   The classes $$F^d = 
    \{ f: [0,1]^d \to {\mathbb{R}}\mid 
    \Vert D^\alpha f \Vert_\infty \le 1 \ \hbox{for all} \ 
    \alpha \in {\mathbb{N}}_0^d   \}$$ were studied several times in the literature, also for the $L_p$ approximation problem, see [@HNUW12; @HNUW13; @HZ07; @NW08; @NW09b; @NW10; @Wei; @Woj03].  Here we only mention that $F_d$ from this paper is smaller than $F^d$ and it is still *not* known whether integration is weakly tractable for the classes $F^d$.

-   We do not know whether integration for the classes $F_d$ from is uniformly weakly tractable.  See Siedlecki [@Sied12] for this stronger notion of tractability. 

-   There is an algorithm for the approximation problem that uses the same sparse grid $H(q,d)$ as well as interpolation by polynomials, see [@BNR98].  This algorithm is often applied, see, e.g., [@BNT] and one may ask about tractability properties of this algorithm.  We do not know whether the $L_p$ approximation problem for the classes $F_d$ from is weakly tractable and, in particular, whether the weak tractability follows from properties of the Smolyak algorithm. 

-   The Smolyak algorithm was generalized to the weighted tensor product algorithm by Wasilkowski and Woźniakowski [@WWW1; @WWW2] and these authors also proved tractability results for weighted tensor product problems; see also [@NW10]. 

The proof
=========

We start with computing the norms of $\Delta^\ell$ and note that a similar (slightly weaker) result was already proved by Petras [@Pe00]. 

\[lemma:Delta\] For $\Delta^\ell$ from we have $$\|\Delta^1\|=1, \quad \|\Delta^2\|=\frac23\quad \text{ and }\quad 
\|\Delta^\ell\|=1+\frac1{4^{\ell-1}+1}$$ for $\ell\ge3$.

Recall that the norm of a quadrature rule is given by the sum of the absolute values of the used weights.  Obviously, $\Delta^1$ has only one weight equal to 1, so $\| \Delta^1 \|=1$. For $\Delta^2$ it is an easy computation to check that there are three nodes with weights $b_1^2 = \frac16, b_2^2 = -\frac13, b_3^2=\frac16$, which gives $$\| \Delta^2 \| \;=\; \sum_{j=1}^3 |b_j^1| \;=\; \frac23.$$ We now treat the case $\ell>2$. Since we want to sum up the absolute values of the weights $b_j^\ell$ we first consider their signs.  Clearly, $b_{j}^\ell=a_j^\ell>0$ for even $j$.

For odd $j$ we now show that $b_{j}^\ell<0$ for all $\ell\ge3$ and $j\le m_\ell$. That is, we show that $$a_{2j-1}^{\ell+1} < a_j^{\ell}$$ for $\ell\ge2$ and (not necessarily odd) $j=1,\dots,m_{\ell}$. For $j=1,m_{\ell}$, noting that $m_{\ell+1}=2 m_{\ell}-1$, this follows immediately from the formulas for the weights.  So assume that $2\le j \le m_{\ell}-1$.

For $\ell=2$, there is only the case $j=2$ left.  Direct computation shows $$a_3^3=\frac25 < \frac23 = a_2^2.$$

For $\ell\ge 3$, we use the absolutely convergent Fourier series $$u(x) \;:=\; \frac{\pi}{2} |\sin \pi x| \;=\; 
1 - 2 \sum_{k=1}^\infty \frac{\cos 2kx\pi}{4k^2-1} .$$ Using this for $x=\frac{j-1}{m_\ell-1}$ and the weight formula and abbreviating $u=u(x)$ we obtain $$\begin{split}
(m_\ell-1) a_j^\ell - u \;&=\;  
- \frac{\cos (j-1)\pi}{(m_\ell-1)^2-1}  + 2\sum_{k=\frac{m_\ell-1}{2}}^{\infty}  
    \frac{ \cos \frac{2k(j-1) \pi}{m_\ell-1}}{4 k^2 - 1} \\
\;&=\;
\frac{\cos (j-1)\pi}{(m_\ell-1)^2-1}  + 2\sum_{k=\frac{m_\ell+1}{2}}^{\infty}  \frac{ \cos \frac{2k(j-1) \pi}{m_\ell-1}}{4 k^2 - 1.} 
\end{split}$$ Note that $${\left\vert 2\, \sum_{k=\frac{m_\ell+1}{2}}^{\infty} 
                    \frac{ \cos 2k \pi x}{4 k^2 - 1} \right\vert}
\;\le\; \sum_{k=\frac{m_\ell+1}{2}}^{\infty} \frac{2}{4 k^2 - 1}
\;=\; \sum_{k=\frac{m_\ell+1}{2}}^{\infty} \Bigl(\frac{1}{2k - 1}
                    - \frac{1}{2k + 1} \Bigr)
\;=\; \frac{1}{m_\ell}$$ for all $x\in{\mathbb{R}}$. This implies $${\left\vert (m_\ell-1)\, a_j^\ell - u \right\vert} 
\;<\; \frac{1}{(m_\ell-1)^2-1} + \frac{1}{m_\ell}
\;=\; \frac{m_\ell-1}{m_\ell(m_\ell - 2)}  
\;<\; \frac{1}{m_\ell - 2}$$ and thus $$\label{eq:aju}
(m_\ell-1)\, a_j^\ell \;>\; u - \frac{1}{m_\ell-2}.$$ Similarly, noting that $x=\frac{j-1}{m_\ell-1}=\frac{2j-2}{m_{\ell+1}-1}$, we obtain that $$\label{eq:a2ju}
2 (m_\ell-1)\, a_{2j-1}^{\ell+1}
\;=\; (m_{\ell+1}-1)\, a_{2j-1}^{\ell+1} 
 \;<\; u + \frac{1}{m_{\ell+1}-2} 
 \;=\; u + \frac{1}{2 m_\ell-3} 
 \;<\; u + \frac{1}{2 (m_\ell-2)} .$$ Recall that our aim is to show that $a_{2j-1}^{\ell+1} < a_j^{\ell}$ which, thanks to and , is certainly satisfied if $$u  \;>\; \frac{5}{2(m_\ell-2)}.$$ Using $m_\ell\ge 5$ and $\sin x \ge \frac{2\sqrt{2}x}{\pi}$ for $x \in[0,\pi/4]$, we can conclude this from $$u \;=\; \frac{\pi}{2} \left|\sin \frac{(j-1)\pi}{m_\ell-1} \right| 
\;\ge\; \frac{\pi}{2} \sin \frac{\pi}{m_\ell-1} 
\;\ge\; \frac{\pi\sqrt{2}}{m_\ell-1}
\;>\; \frac{5}{m_\ell-1}
\;>\; \frac{5}{2(m_\ell-2)}.$$

This finally shows $a_{2j-1}^{\ell+1} < a_j^{\ell}$ for all $\ell\ge2$ and $j=1,\dots,m_\ell$ and, consequently, that $b_{j}^{\ell}<0$ for all $\ell\ge3$ and all odd $j$.

Now we can compute the norm $$\| \Delta^\ell \| \;=\; \sum_{j=1}^{m_\ell} |b_j^{\ell}| 
\;=\; \sum_{j=1}^{\frac{m_\ell-1}{2}} a_{2j}^{\ell} 
        - \sum_{j=1}^{\frac{m_\ell+1}{2}} a_{2j-1}^{\ell} 
        + \sum_{j=1}^{m_{\ell-1}} a_{j}^{\ell-1} .$$ Using twice that the weights of one CC-rule add up to 1 we obtain $$\| \Delta^\ell \| = 2 \sum_{j=1}^{\frac{m_\ell-1}{2}} a_{2j}^{\ell} = 
2  \sum_{j=1}^{2^{\ell-2}}  \frac{1}{2^{\ell-1}} 
\left( 1 + \frac{1}{4^{\ell-1}-1}  - 
2\sum_{k=1}^{2^{\ell-2}-1} \frac{ \cos \frac{2k(2j-1) 
\pi}{2^{\ell-1}}}{4 k^2 - 1}\right).$$ Simplifying and changing the order of summation yields $$\| \Delta^\ell \| =  1 + \frac{1}{4^{\ell-1}-1} 
+ \frac{1}{2^{\ell-3}} \sum_{k=1}^{2^{\ell-2}-1} \frac{1}{4 k^2 - 1} 
\sum_{j=1}^{2^{\ell-2}}  \cos \frac{k(2j-1) \pi}{2^{\ell-2}}.$$ Since the inner sum is always zero, we finally arrive at $$\| \Delta^\ell \| =  1 + \frac{1}{4^{\ell-1}-1.}$$

Now we are able to prove our explicit bound on the norm of the Smolyak algorithm. 

\[prop:norm\] For every $k\in{\mathbb{N}}_0$ and $d\in{\mathbb{N}}$ we have $${\left\Vert A(d+k,d) \right\Vert} \;\le\; \binom{d+k}{d} \;\le\; e^k\,\Bigl(1+\frac{d}{k}\Bigr)^k.$$

The second inequality is proven by $$\binom{d+k}{d} \;\le\; \frac{(d+k)^k}{k!}  \;\le\; \left(\frac{e(d+k)}{k}\right)^k,$$ where we used Stirling’s approximation of the factorial. 

To prove the first inequality, we show that $$M(k,d) \;:=\; \max_{0\le\ell\le k}\, {\left\Vert A(d+\ell,d) \right\Vert} \;\le\; \binom{d+k}{d}$$ by induction on $d$. For $d=1$ we obviously have $$M(k,1) \;:=\; {\left\Vert A(1+k,1) \right\Vert} ={\left\Vert U^{k+1} \right\Vert} = 1 \le  \binom{1+k}{1}$$ for every $k\in{\mathbb{N}}_0$. For $d\ge1$ let us now assume $M(k,d) \le \binom{d+k}{d}$ for all $k\in{\mathbb{N}}_0$ and recall that, for $d,k\in{\mathbb{N}}_0$, we have $$\sum_{\ell=0}^k\binom{d+\ell}{d}=\binom{d+k+1}{d+1}.$$ Then we obtain by Lemma \[lemma:Delta\] that $$\begin{split}
\|A(d+1+k,d+1)\|
\;&\le\; \sum_{\ell=1}^{k+1}\, \|A(d+1+k-\ell,d)\| \cdot \|\Delta^\ell\| \\
\;&\le\; \sum_{\ell=1}^{k+1}\, M(k+1-\ell,d)\, \|\Delta^\ell\|\\
        \;&=\; M(k,d) \,+\, \frac23\, M(k-1,d) 
    + \sum_{\ell=3}^{k+1}\, 
    \frac{4^{\ell-1}}{4^{\ell-1}-1}\; M(k+1-\ell,d) \\
\;&=\;  \sum_{\ell=1}^{k+1}\, M(k+1-\ell,d)
                            \,-\, \frac13 M(k-1,d) \\
    &\qquad\qquad\qquad + \sum_{\ell=3}^{k+1}\, 
    \frac{1}{4^{\ell-1}-1}\; M(k+1-\ell,d) \\
\;&\le\;  \sum_{\ell=0}^{k}\, M(\ell,d)
\,-\, M(k-1,d)\, \left(\frac13 - \sum_{\ell=3}^{k+1}\, 
\frac{1}{4^{\ell-1}-1}\right), \\
\end{split}$$ where we have used that $M(k+1-\ell,d)\le M(k-1,d)$ for $k=3,\dots,k+1$. Noting that $$\sum_{\ell=3}^{k+1} \frac{1}{4^{\ell-1}-1} 
= \sum_{\ell=0}^{k-2} \frac{1}{4^{\ell+2}-1} 
\le \sum_{\ell=0}^{k-2} \frac{1}{4^{\ell+1}} \le \frac13,$$ we finally obtain $$\begin{split}
\|A(d+1+k,d+1)\| \;&\le\; \sum_{\ell=0}^{k}\, M(\ell,d) 
\;\le\; \sum_{\ell=0}^{k}\, \binom{d+\ell}{d} \;=\; \binom{d+1+k}{d+1}  .  
\end{split}$$ Writing this inequality down with $k$ replaced by $\ell$ and taking the maximum over $\ell=0,1\dots,k$ on both sides leads to $$M(k,d+1) \le \max_{0\le \ell\le k} \binom{d+1+\ell}{d+1} = \binom{d+1+k}{d+1}$$ and concludes the induction step and the proof.\

Note that Proposition 1 holds also for the Smolyak algorithm that is based on other one-dimensional quadrature rules as long as $$\|\Delta^1\| \;\le\; 1 \quad\text{ and }\quad 
\sum_{\ell=2}^\infty(\|\Delta^\ell\|-1) \;\le\; 0.$$

To conclude our main result, Theorem \[thm:main\], we additionally need a bound on the error of approximation by polynomials.  We prove that $d$-dimensional $C^\infty$ functions with directional derivatives of all orders bounded by one can be arbitrarily well approximated by polynomials of total degree of order $\sqrt{d}$. This result was already proven by the authors and H. Woźniakowski in [@HNUW13], but we state the proof here again for completeness.  Let $\mathcal{P}_k$ be the space of polynomials of degree $k$.

\[prop:poly\] Let $f\in F_d$ and $k\in{\mathbb{N}}$. Then $$\inf_{p\in\mathcal{P}_{k-1}}\|f-p\|_\infty 
\;\le\; \sqrt{\frac{1}{2\pi k}}\; \biggl( \frac{e \sqrt{d}}{2 k} \biggr)^k.$$

Consider the Taylor polynomial for $f\in F_d$ of order $k-1$ about the point $x^*=(1/2,\dots,1/2)$ which can be written as $$T_{k-1}(x)=\sum_{\ell=0}^{k-1} \frac{f^{(\ell)}(x^*)(x-x^*)^\ell}{\ell!} 
\ \ \ \ \mbox{for all}\ \ \ \ x\in [0,1]^d.$$ Here we use the standard notation $A(x^\ell)=A(x,\dots,x)$ for the evaluation of an $\ell$-linear map on the diagonal.  Note that we consider here $f^{(\ell)}(x^*)$ as an $\ell$-linear map.  It is well-known that the error of the approximation of $f$ by $T_{k-1}$ can be written as $$f(x)-T_{k-1}(x)\;=\; k\,\int_0^1(1-t)^{k-1}\,
\frac{ f^{(k)} \big(x^*+t(x-x^*)\big)(x-x^*)^{k}}{k!} {{ \rm d}}t,$$ which implies $$\begin{split}
\left| f(x)-T_{k-1}(x) \right| \;&\le\;  \frac{1}{(k-1)!}\, 
    \int_0^1(1-t)^{k-1}\, {{\rm d}}t \, 
    \Bigl(\max_{\theta\in S^{d-1}}\,\|D^k_\theta f\|_\infty\Bigr)\, 
    {\left\Vert x-x^* \right\Vert}_2^{k} \\
&\le\; \frac{1}{2^k\, k!}\, d^{k/2}. 
\end{split}$$ An application of Stirling’s formula proves the result since $T_{k-1}\in\mathcal{P}_{k-1}$.\

We combine Propositions \[prop:norm\] and \[prop:poly\] to obtain the first part of our main result.  To ease the calculations we use the trivial bound $\inf_{p\in\mathcal{P}_{2k+1}}\|f-p\|_\infty\le 
\inf_{p\in\mathcal{P}_{2k-1}}\|f-p\|_\infty$. Recall that $$e(k,d) \;:=\; 
\sup_{f\in F_d} {\left\vert A\bigl(d+k,d\bigr)(f) \,-\,  S_d(f) \right\vert} .$$ Using that $A(d+k,d)$ is exact for all polynomials of total degree at most $2k+1$, see [@NR96; @NR99], we have $$\begin{split}
e(k,d) \;&\le\; \sup_{f\in F_d} \inf_{p\in\mathcal{P}_{2k+1}}\|f-p\|_\infty\, 
\Bigl(1+\|A(d+k,d)\|\Bigr)\\
&\le\; \sqrt{\frac{1}{4\pi k}}\; 
                \biggl( \frac{e \sqrt{d}}{4k} \biggr)^{2k}\; 
                \biggl(1+e^k\,\Bigl(1+\frac{d}{k}\Bigr)^k \biggr) 
\;\le\; \sqrt{\frac{1}{\pi k}}\; 
\biggl( \frac{e \sqrt{d}}{4k} \biggr)^{2k}\; 
                e^k\,\Bigl(1+\frac{d}{k}\Bigr)^k  \\
&\le\; \frac{1}{\sqrt{\pi k}}\; \biggl( \frac{e^3}{16}\biggr)^k\;
                \biggl( \frac{d}{k^2} 
                \,+\, \frac{d^{2}}{k^3}\biggr)^k 
\;\le\; \frac{1}{\sqrt{\pi k}}\; \biggl( \frac{e^3 d}{8 k^2}\; 
                \max\Bigl\{ 1, \frac{d}{k} \Bigr\}\biggl)^k  .  
\end{split}$$

This shows that with $$k_{{\varepsilon},d} \;:=\; \biggl\lceil\max\Bigl\{3\,d^{2/3},\; \ln(1/{\varepsilon})\Bigr\} \biggr\rceil$$ we have $e(k_{{\varepsilon},d},d)\le{\varepsilon}$, which is the first part of Theorem \[thm:main\]. 

It remains to prove the bound on the number of function values $N_d(k_{{\varepsilon},d})$ that are used by the Smolyak algorithm $A(d+k_{{\varepsilon},d},d)$. For this we use the following bound of Wasilkowski and Woźniakowski. 

\[lemma:number\] The number of function values used by the Smolyak algorithm $A(d+k,d)$ that is based on the one-dimensional quadrature rules from satisfies $$N_d(k) \;\le\; 2 (2e)^k \Bigl( 1+ \frac{d}{k} \Bigr)^k$$ for all $k,d\in{\mathbb{N}}$, and thus $$\ln\bigl(N_d(k)\bigr) \;\le\; \ln2 \,+\, k\,\Bigr(\ln(2e) 
+ \ln\bigl( 1+ d/k \bigr)\Bigr).$$

Since our $m_\ell$’s satisfy $m_\ell\le2^\ell -1$ and the used nodes are nested, we use equation (43) of [@WW95] with $F_0=1$, $F=2$ and $q=d+k$. This gives $$N_d(k) \;\le\; 2^{k+1} \binom{d+k-1}{d-1} 
\;\le\; 2 (2e)^k \Bigl( 1+ \frac{d}{k} \Bigr)^k$$ by Stirling’s formula.\

From this we obtain $$\begin{split}
\ln\bigl(N_d(k_{{\varepsilon},d})\bigr) \;&\le\; \ln 2 +  k_{{\varepsilon},d}\, 
    \biggl( \ln(2e) \\
    &\qquad+ \min\Bigl\{ \ln\bigl( 1+(1/3)\, d^{1/3} \bigr),\, 
        \ln\bigl( 1+ d \ln(1/{\varepsilon})^{-1} \bigr) \Bigr\} \biggr) \\
\;&\le\; \ln 2 + k_{{\varepsilon},d}\, 
    \biggl( 2 + \ln\biggl( 1- \frac{d}{\ln({\varepsilon})} \biggr) \biggr),
\end{split}$$ which is the second part of Theorem \[thm:main\]. 

The proof of Theorem \[thm:qmc\] proceeds similarly, so we only sketch the necessary modifications.  It follows from [@Dav67] that for all $k,d\in{\mathbb{N}}$ there exists a cubature formula $Q(k,d)$ with positive weights, exactness $k$ and such that the number of function values $N^*_d(k)$ satisfies the Tchakalov bound $$\label{eq:Tschakk}
 N^*_d(k) \le \binom{d+k}{d} \;\le\;  e^k \Bigl( 1+ \frac{d}{k} \Bigr)^k.$$ This implies that ${\left\Vert Q(k,d) \right\Vert}=1$ which can now be used instead of Proposition \[prop:norm\].  So, we obtain for the error $$e(k,d) \;\le\; \sup_{f\in F_d} \inf_{p\in\mathcal{P}_{k}}\|f-p\|_\infty\, 
\Bigl(1+\|Q(k,d)\|\Bigr)
\le\; \sqrt{\frac{2}{\pi k}}\; \biggl( \frac{e \sqrt{d}}{2 k} \biggr)^k,$$ which is smaller than ${\varepsilon}$ for $k=k^*_{{\varepsilon},d}$ as in Theorem \[thm:qmc\].  Finally, the bound on $N^*_d(k^*_{{\varepsilon},d})$ in Theorem \[thm:qmc\] now follows from . 

[99]{}

I. Babuška, F. Nobile and R. Tempone, A stochastic collocation method for elliptic partial differential equations with random input data, *SIAM Rev.* [**52**]{}, 317–355, 2010. 

N. S. Bakhvalov, On approximate computation of integrals, *Vestnik MGU, Ser.  Math.  Mech.  Astron.  Phys.  Chem.* [** 4**]{}, 3–18, 1959, in Russian. 

V. Barthelmann, E. Novak and K. Ritter, High dimensional polynomial interpolation on sparse grids, *Adv.  in Comput.  Math.* [** 12**]{}, 273–288, 1999. 

H. Brass and K. Petras, *Quadrature Theory*, American Math.  Soc.,  Providence, 2011. 

H.-J. Bungartz and M. Griebel, Sparse grids, *Acta Numerica* [**13**]{}, 147–269, 2004. 

P. J. Davis, A construction of nonnegative approximate quadratures, [*Math.  Comp.  *]{}[**21**]{}, 578–582, 1967. 

J. Dick, F. Y. Kuo and I. H. Sloan, High-dimensional integration: The quasi-Monte Carlo way, *Acta Numerica* [**22**]{}, 133–288, 2013. 

J. Dick and F. Pillichshammer, Discrepancy theory and quasi-Monte Carlo integration, in: W. W. L. Chen, A. Srivastav, G. Travaglini, A Panorama of Discrepancy Theory, Lecture Notes in Mathematics, Vol.  2107, Springer Verlag, 2014. 

Th.  Gerstner and M. Griebel, Numerical integration using sparse grids, *Num.  Algorithms* [**18**]{}, 209–232, 1998. 

M. Griebel, Sparse grids and related approximation schemes for higher dimensional problems, in: *Foundations of Computational Mathematics*, Santander 2005, L. M. Pardo et al. ( eds.),  106–161, London Math.  Soc.,  Lecture Note Series 331, Cambridge University Press, 2006. 

A. Hinrichs, E. Novak, M. Ullrich, H. Woźniakowski, The curse of dimensionality for numerical integration of smooth functions, *Math.  Comp.*,  to appear. 

A. Hinrichs, E. Novak, M. Ullrich, H. Woźniakowski, The curse of dimensionality for numerical integration of smooth functions II, [*J. Complexity *]{}[**30**]{}, 117–143, 2014. 

F. L. Huang and S. Zhang, Approximation of infinitely differentiable multivariate functions is not strongly tractable, [*J. Complexity *]{}[**23**]{}, 73–81, 2007. 

Th.  Müller-Gronbach, Hyperbolic cross designs for approximation of random fields, *J. Statistical Planning and Inference* [**66**]{}, 321–344, 1998. 

E. Novak, *Deterministic and Stochastic Error Bounds in Numerical Analysis*, LNiM [**1349**]{}, Springer Verlag, Berlin, 1988. 

E. Novak and K. Ritter, High dimensional integration of smooth functions over cubes, [*Numer.  Math.  *]{}[**75**]{}, 79–97, 1996. 

E. Novak and K. Ritter, The curse of dimension and a universal method for numerical integration, in: *Multivariate Approximation and Splines*, G. Nürnberger, J. W. Schmidt and G. Walz, eds.,  ISNM [**125**]{}, Birkhäuser, Basel, 177–188, 1997. 

E. Novak and K. Ritter, Simple cubature formulas with high polynomial exactness, [*Constr.  Approx.  *]{}[**15**]{}, 499–522, 1999. 

E. Novak and H. Woźniakowski, *Tractability of Multivariate Problems*, Volume 1, Linear Information, European Math.  Soc.,  Zürich, 2008. 

E. Novak and H. Woźniakowski, Approximation of infinitely differentiable multivariate functions is intractable, [*J. Complexity *]{}[**25**]{}, 398–404, 2009. 

E. Novak and H. Woźniakowski, *Tractability of Multivariate Problems*, Volume II: Standard Information for Functionals, European Math.  Soc.  Publ.  House, Zürich, 2010. 

K. Petras, On the Smolyak cubature error for analytic functions, *Adv.  in Comput.  Math.* [** 12**]{}, 71–93, 2000. 

W. Sickel and T. Ullrich, Smolyak’s algorithm, sampling on sparse grids and function spaces of dominating mixed smoothness, *East J. on Approx.* [** 13**]{}, 387–425, 2007. 

W. Sickel and T. Ullrich, Spline interpolation on sparse grids, *Applicable Analysis* [**90**]{}, 337–383, 2011. 

P. Siedlecki, Uniform weak tractability, *J. Complexity* [**29**]{}, 438–453, 2013. 

S. A. Smolyak, Quadrature and interpolation formulas for tensor products of certain classes of functions, *Dokl.  Akad.  Nauk SSSR* [**4**]{}, 240–243, 1963. 

J. Vybíral, Weak and quasi-polynomial tractability of approximation of infinitely differentiable functions, *J. Complexity* [**30**]{}, 48–55, 2014. 

G. W. Wasilkowski and H. Woźniakowski, Explicit cost bounds of algorithms for multivariate tensor product problems, [*J. Complexity *]{}[**11**]{}, 1–56, 1995. 

G. W. Wasilkowski and H. Woźniakowski, Weighted tensor-product algorithms for linear multivariate problems, [*J. Complexity *]{}[**15**]{}, 402–447, 1999. 

G. W. Wasilkowski and H. Woźniakowski, Polynomial-time algorithms for multivariate linear problems with finite-order weights; worst case setting, [*Found.  Comput.  Math.  *]{}[**5**]{}, 451–491, 2005. 

M. Weimar, Tractability results for weighted Banach spaces of smooth functions, [*J. Complexity *]{}[**28**]{}, 59–75, 2012. 

J. O. Wojtaszczyk, Multivariate integration in $C^{\infty}([0,1]^d)$ is not strongly tractable, [*J. Complexity *]{}[**19**]{}, 638–643, 2003. 

[^1]: This author was partially supported by the DFG-Priority Program 1324. 

[^2]: This author was partially supported by DFG GRK 1523.