Integration and

www.oeaw.ac.at

Integration and

approximation in cosine spaces of smooth functions

C. Irrgeher, P. Kritzer, F. Pillichshammer

RICAM-Report 2015-42

Integration and approximation in cosine spaces of smooth functions

Christian Irrgeher

^∗

, Peter Kritzer

^†

, Friedrich Pillichshammer

^‡

Abstract

We study multivariate integration and approximation for functions belonging to a weighted reproducing kernel Hilbert space based on half-period cosine functions in the worst-case setting. The weights in the norm of the function space depend on two sequences of real numbers and decay exponentially. As a consequence the functions are infinitely often differentiable, and therefore it is natural to expect exponential convergence of the worst-case error. We give conditions on the weight sequences under which we have exponential convergence for the integration as well as the approximation problem. Furthermore, we investigate the dependence of the errors on the dimension by considering various notions of tractability. We prove sufficient and necessary conditions to achieve these tractability notions.

Keywords: numerical integration, function approximation, cosine space, worst-case er- ror, exponential convergence, tractability

2010 MSC: 41A63, 41A25, 65C05, 65D30, 65Y20

1 Introduction

In this paper we study two instances of multivariate linear problems. We are interested in approximating linear operators Ss : Hs → Gs, where Hs is a certain Hilbert space of s-variate functions defined on [0,1]^s and where Gs is a normed space, namely:

• Numerical integration of functions f ∈ H_s: In this case, we have G_s=R and Ss(f) = INTs(f) =

Z

[0,1]^sf(x) dx, or

• L2-approximation of functions f ∈ Hs: In this case, we have Gs =L2([0,1]^s) and Ss(f) = APPs(f) = f.

∗C. Irrgeher is supported by the Austrian Science Fund (FWF): Project F5509-N26, which is a part of the Special Research Program "Quasi-Monte Carlo Methods: Theory and Applications".

†P. Kritzer is supported by the Austrian Science Fund (FWF): Project F5506-N26, which is a part of the Special Research Program "Quasi-Monte Carlo Methods: Theory and Applications".

‡F. Pillichshammer is partially supported by the Austrian Science Fund (FWF): Project F5509-N26, which is a part of the Special Research Program "Quasi-Monte Carlo Methods: Theory and Applications".

Without loss of generality, see, e.g., [15] or [12, Section 4], we approximateSs by a linear algorithm An,s usingn information evaluations which are given by linear functionals from the class Λ∈ {Λ^all,Λ^std}. More precisely, we approximateSs by algorithms of the form

An,s(f) =

Xn j=1

αjLj(f) for all f ∈ Hs,

where L_j ∈ Λ andα_j ∈ G_s for all j = 1,2, . . . , n. For Λ = Λ^all we have L_j ∈ H^∗_s whereas for Λ = Λ^std we have Lj(f) = f(xj) for allf ∈ Hs, and for some xj ∈[0,1]^s. Obviously, for multivariate integration only the class Λ^std makes sense. Furthermore, we remark that in this paper we consider only function spaces for which Λ^std ⊂Λ^all.

We measure the error of an algorithm An,s in terms of the worst-case error, which is defined as

e(An,s, Ss) := sup

f∈Hs

kfkHs≤1

kSs(f)−An,s(f)k_Gs,

wherek·k_Hs,k·k_Gs denote the norms inHs andGs, respectively. The nth minimal (worst- case) error is given by

e(n, Ss) := inf

An,s

e(An,s, Ss),

where the infimum is taken over all admissible algorithms An,s. When we want to em- phasize that thenth minimal error is taken with respect to algorithms using information from the class Λ ∈ {Λ^all,Λ^std}, we write e(n, Ss; Λ). For n = 0, we consider algorithms that do not use information evaluations and therefore we use A0,s ≡0. The error of A0,s

is called the initial (worst-case) error and is given by e(0, Ss) := sup

f∈Hs

kfkHs≤1

kSs(f)k_Gs =kSsk.

Since we will study a class of weighted reproducing kernel Hilbert spaces with expo- nentially decaying weights, which will be introduced in Section1.2, we are concerned with spaces Hs of smooth functions. We remark that reproducing kernel Hilbert spaces of a similar flavor were previously considered in [2, 3, 5, 6, 7, 8, 9]. In this case it is natu- ral to expect that, by using suitable algorithms, we should be able to obtain errors that converge to zero very quickly as n increases, namely exponentially fast. By exponential convergence (EXP) for the worst-case error we mean that there exist a numberq ∈(0,1) and functions p, C, M :N→(0,∞) such that

e(n, S_s)≤C(s)q^(n/M(s))p(s) for all s, n∈N. (1) If the function p in (1) can be taken as a constant function, i.e., p(s) = p > 0 for all s ∈ N, we say that we achieve uniform exponential convergence (UEXP) for e(n, Ss).

Furthermore, we denote by p^∗(s) and p^∗ the largest possible rates p(s) and p such that EXP and UEXP holds, respectively.

When studying algorithmsAn,s, we do not only want to control how their errors depend on n, but also how they depend on the dimension s. This is of particular importance

for high-dimensional problems. To this end, we define, for ε ∈ (0,1) and s ∈ N, the information complexity by

n(ε, Ss) := min{n : e(n, Ss)≤ε e(0, Ss)}

as the minimal number of information evaluations needed to reduce the initial error by a factor ofε. Exponential convergence implies that asymptotically, with respect toεtending to zero, we need O(log^1/p(s)ε⁻¹) information evaluations to compute anε-approximation.

However, it is not clear how long we have to wait to see this nice asymptotic behavior especially for large s. This, of course, depends on how C(s), M(s) and p(s) depend on s, and this is the subject of tractability. Thus, we intend to study how the information complexity depends on logε⁻¹ and s by considering the following tractability notions, which were already considered in [2, 3, 5,6, 8]. The nomenclature was introduced in [9].

We say that we have Exponential Convergence-Weak Tractability (EC-WT) if

s+loglimε⁻¹→∞

log n(ε, Ss) s+ log ε⁻¹ = 0

with the convention log 0 = 0, i.e., we rule out the cases for which n(ε, s) depends exponentially on s and log ε⁻¹. If there exist numbers c, τ, σ >0 such that

n(ε, Ss)≤c s^σ(1 + log ε⁻¹)^τ for all s∈N, ε∈(0,1), (2) we say thatExponential Convergence-Polynomial Tractability (EC-PT)holds. This means that the information complexity depends at most polynomially on s and log ε⁻¹. If the upper bound is independent of the dimension s, i.e., (2) holds with σ = 0, then we say that we have Exponential Convergence-Strong Polynomial Tractability (EC-SPT).

Furthermore, the infimum of all τ for which EC-SPT holds is called the exponent of EC-SPT and it is denoted by τ^∗.

For further general remarks on exponential convergence and these tractability notions we refer to [2, 3, 5, 6, 8, 9]. Moreover, we remark that in many papers tractability is studied for problems where we do not have exponential, but usually polynomial, error convergence. For this kind of problems, tractability is concerned with the question how the information complexity depends on s and ε⁻¹, rather than logε⁻¹, (for a detailed survey of such results, we refer to [12, 13, 14]).

1.1 Relations between multivariate integration and approxima- tion

It is well known that multivariate approximation using information from Λ^stdis not easier than multivariate integration, see, e.g., [11]. More precisely, for any algorithm An,s(f) =

P_n

k=1αkf(xk) for multivariate approximation using the nodes x₁, . . . ,x_n ∈ [0,1)^s and αk ∈L2([0,1]^s), define βk :=^R_[0,1]sαk(x) dx and the algorithm

A^int_n,s(f) =

Xn k=1

βkf(xk)

for multivariate integration. Then it can easily be checked that e(A^int_n,s,INTs)≤e(An,s,APPs).

Since this holds for all algorithms An,s we conclude that e(n,INT_s)≤e(n,APP_s; Λ^std).

If the initial errors of integration and approximation are equal, these observations imply that for ε∈(0,1) ands ∈Nwe have

n(ε,INTs)≤n(ε,APPs; Λ^std). (3)

1.2 The half-period cosine spaces with infinite smoothness

We now introduce the function spaces for which we will consider multivariate integration and approximation. First, we choose two weight sequences of real positive numbers, a ={aj} and b={bj} such that

0< a∗ :=a1 ≤a2 ≤. . . and b∗ := inf

j bj >0.

Moreover, we fix a parameter ω ∈(0,1) and define for any k= (k1, . . . , ks)∈N^s

0, ωk :=ω^Psj=1ajkbjj =

Ys j=1

ω^ajkbjj .

The half-period cosine space with infinite smoothness is a reproducing kernel Hilbert space H(K_s,a,b,ω^cos ) of (half-period) cosine series with reproducing kernel

K_s,a,b,ω^cos (x,y) := ^X

k∈Ns 0

ωk2^|

k|∗

2 2^|

k|∗

2

Ys j=1

cos(πkjxj) cos(πkjyj), forx,y∈[0,1]^s, (4) where we define |k|∗ :=|{j ∈[s] : kj 6= 0}| to be the number of nonzero components in k= (k1, . . . , ks)∈N^s

0, and [s] := {1, . . . , s}. The inner product in H(K_s,a,b,ω^cos ) is given by hf, gi_K^cos_s,a,b,ω = ^X

k∈N^s

0

ω⁻¹_k f^e(k)g(k),e

where the kth cosine coefficient for a function f : [0,1]^s→R is given by fe(k) :=

Z

[0,1]^sf(x) 2^|k2|∗

Ys j=1

cos(πk_jx_j) dx.

The corresponding norm is defined by kfkK_s,^cos_a,b,ω =^qhf, fiK_s,^cos_a,b,ω, in particular, kfk²_K^cos

s,a,b,ω = ^X

k∈Ns 0

|f(k)|^{e 2} ωk

= ^X

h∈Zs

2^−|h|∗|f(|h|)|^{e 2} ωh

, (5)

where |h|= (|h1|, . . . ,|hs|). Furthermore, we can write f ∈ H(K_s,a,b,ω^cos ) as f(x) = ^X

k∈N^s

0

f(k)e



2^|

k|∗

2

Ys j=1

cos(πk_jx_j)



,

and the sequence {ek}k∈N^s

0 with ek(x) =



2^|

k|∗

2

Ys j=1

cos(πkjxj)



ω_k¹² is an orthonormal basis of H(K_s,a,b,ω^cos ).

From (5) we see that the functions in H(K_s,a,b,ω^cos ) are characterized by the decay rate of their cosine coefficients, which is regulated by the weights ωk. Since {ωk} decreases exponentially as k grows, the cosine coefficients of the functions in H(K_s,a,b,ω^cos ) also de- crease exponentially fast, which influences the smoothness of the functions. Indeed, it can be shown that f ∈ H(K_s,a,b,ω^cos ) belongs to the Gevrey class with index 1/b∗ and so it follows that for the case b∗ ≥ 1 the functions of H(K_s,a,b,ω^cos ) are analytic. Note that the half-period cosine space with infinite smoothness fits into the general setting which is discussed in [6]. Furthermore we refer to the recent paper [4] in which the integration problem is discussed in a half-period cosine space with weights of polynomial decay.

Finally, we remark that we can assume a∗ ≥ 1 without loss of generality, because we always can modify ω such that a∗ ≥1.

2 Integration in half-period cosine spaces

Let INTs :H(K_s,a,b,ω^cos )→Rwith INTs(f) =^R_[0,1]sf(x) dx. In order to approximate INTs

with respect to the absolute value | · |we use linear algorithms An,s, which are algorithms based on n function evaluations of the form

An,s(f) =

Xn k=1

αkf(xk) for f ∈ H(K_s,a,b,ω^cos ), where each αk∈R and x_k ∈[0,1]^s for k = 1,2, . . . , n.

The worst-case error of an algorithm An,s is defined as e(An,s,INTs) := sup

f∈H(K^cos_s,a,b,ω) kfk_Kcos

s,a,b,ω≤1

|INTs(f)−An,s(f)|.

The nth minimal worst-case error is denoted by e(n,INTs) = inf

An,s

e(An,s,INTs),

where the infimum is taken over all linear algorithms An,s of the above given form. With [1, Proposition 2.11] it is easy to check the initial error ise(0,INT_s) = 1.

2.1 Upper and lower error bounds

An n-point midpoint rule is a linear integration rule of the form Tn(f) = 1

n

n−1X

j=0

f

2j+ 1 2n

.

The following lemma on midpoint rules applied to cosine functions has a simple proof which we omit for the sake of brevity.

Lemma 1. We have

1 n

n−1X

j=0

cos

πl2j+ 1 2n

=





1 if l= 2tn for t∈Z, 0 otherwise.

For integration in the multivariate case, we use the cartesian product of one-dimensional midpoint rules. Let n1, . . . , ns ∈ N and let n = n1n2· · ·ns. For j = 1,2, . . . , s let T_n^(j)_j (f) = _n¹

j

Pnj−1

i=0 f²ⁱ⁺¹_2n

j

be one-dimensional nj-point midpoint rules. Then we apply the s-dimensional Cartesian product ruleTn,s =Tn1 ⊗ · · · ⊗Tns, i.e.,

Tn,s(f) = 1 n

nX1−1 i1=0

. . .

nXs−1 is=0

f²ⁱ_2n¹⁺¹₁ , . . . ,²ⁱ_2n^s+1_s for f ∈ H(K_s,a,b,ω^cos ). (6) Proposition 1. Let Tn,s be the s-dimensional Cartesian product of nj-point midpoint rules given by (6) and let n =n₁n₂· · ·n_s. Then we have

e²(Tn,s,INTs)≤ −1 +

Ys j=1

1 +ω^aj(2nj)bjC(a∗, b∗)

with C(a∗, b∗) := 2ω^−a∗P∞_l=1ω^a∗lb∗ <∞.

Proof. With [1, Proposition 2.11] and (4) we get for the worst-case error of Tn,s in H(K_s,a,b,ω^cos ),

e²(Tn,s,INTs) = ^X

l∈Ns 0\{0}

ωl2^|l|0



 1 n1

nX1−1 j1=0

. . . 1 ns

nXs−1 js=0

cos

πl1

2j1 + 1 2n1

· · ·cos

πls

2js+ 1 2ns





2

=−1 +

Ys i=1



1 + 2

X∞ l=1

ω^ailbi



 1 ni

nXi−1 j=0

cos

πl2j+ 1 2ni





2

.

Now it follows from Lemma 1that e²(Tn,s,INTs)≤ −1 +

Ys j=1

1 + 2

X∞ l=1

ω^aj(2lnj)bj

!

≤ −1 +

Ys j=1

1 + 2ω^aj(2nj)bjω^−a∗

X∞ l=1

ω^a∗lb∗

!

.

The following proposition states a lower bound on the nth minimal worst-case error which will be useful to derive the necessary conditions in Theorem 1.

Proposition 2. Let t₁, . . . , t_s∈N. Then the nth minimal worst-case error satisfies e(n,INTs)≥ω^{Psj=1aj(2tj)bj}

Ys j=1

(5(1 +tj))⁻¹ for any 1≤n≤^Qs_j=1(1 +tj).

Proof. The lower bound can be shown in the same way as [8, Lemma 1] or [5, Theorem 2].

2.2 The main results for integration

The following theorem gives necessary and sufficient conditions on the weight sequences a and b for EXP, UEXP, and the notions of EC-WT, EC-PT, and EC-SPT.

Theorem 1. Consider integration defined over H(K_s,a,b,ω^cos ) with weight sequences a and b.

1. EXP holds for all a and b considered, and p^∗(s) = _B(s)¹ with B(s) :=^Ps_j=1b¹

j. 2. The following assertions are equivalent:

(i) The sequence {b⁻¹_j }j≥1 is summable, i.e., B :=^P∞_{j=1 b}¹

j <∞;

(ii) we have UEXP;

(iii) we have EC-PT;

(iv) we have EC-SPT.

If one of the assertions holds then p^∗ = 1/B and the exponent τ^∗ of EC-SPT is B. 3. EC-WT implies that limj→∞aj2^bj =∞.

4. A sufficient condition for EC-WT is that limj→∞aj =∞.

Proof. Proof of Point 1: We first show that we always have EXP. For ε∈(0,1), define

m = max

j=1,2,...,s









1 aj

logC(a∗, b∗)_log(1+ε^s 2)

log ω⁻¹





B(s)





with C(a∗, b∗) = 2ω^−a∗P∞_k=1ω^a∗kb∗. Now let n1, n2, . . . , ns be given by nj :=^jm^1/(B(s)bj)k for j = 1,2, . . . , s and set n=n1n2· · ·ns. Since ⌊x⌋ ≥x/2 for all x≥1, we have

aj(2nj)^bj ≥ajm^1/B(s) for every j = 1,2, . . . , s. Then we obtain with Proposition 1,

e²(Tn,s,INTs)≤ −1 +

Ys j=1

1 +ω^ajm1/B(s)C(a∗, b∗).

From the definition of m we have for allj = 1,2, . . . , s, ω^ajm1/B(s)C(a∗, b∗)≤ log(1 +ε²)

s .

This proves

e(Tn,s,INTs)≤ −1 + 1 + log(1 +ε²) s

!_s!1/2

≤−1 + exp(log(1 +ε²))^1/2 =ε. (7)

Furthermore, note that n =

Ys j=1

nj =

Ys j=1

jm^1/(B(s)bj)k≤m^{B(s)1 Psj=11/bj} =m =Olog^B(s)1 +ε⁻¹, (8)

with the factor in the O notation independent of ε⁻¹ but dependent on s. From (7) and (8) it follows directly that we always have EXP with p^∗(s)≥1/B(s).

It remains to show that we have indeed p^∗(s) = 1/B(s) for the largest possible rate of EXP. To this end, assume that EXP holds. Let t = (t₁, . . . , t_s) ∈ N^s and choose n =−1 +^Qs_j=1(1 +tj). Then Proposition 2implies

C(s)q^(n/M(s))p(s) ≥ω^{Psj=1aj(2tj)bj}

Ys j=1

(5(1 +tj))⁻¹, which implies

P_s

j=1a_j(2t_j)^bj

Q_s

j=1(1 +tj)^p(s) + logC(s) +^Ps_j=1log(5(1 +t_j))

Q_s

j=1(1 +tj)^p(s)logω⁻¹ ≥

≥ 1− 1

Q_s

j=1(1 +tj)

!p(s)

logq⁻¹

logω⁻¹M(s)^−p(s). (9) For fixed s, when ktk_s,∞ = max1≤j≤stj → ∞, then the second term of the left hand side of (9) goes to zero, and it follows that

lim inf

ktk_s,∞→∞

P_s

j=1aj(2tj)^bj

Q_s

j=1(1 +tj)^p(s) ≥ logq⁻¹

logω⁻¹M(s)^−p(s) >0.

For a positive number t take now

tj :=^lt^1/bjm for all j = 1,2, . . . , s.

Clearly, limt→∞

lt^1/bjm/t^1/bj = 1. Then we have

P_s

j=1aj(2tj)^bj

Q_s

j=1(1 +tj)^p(s) =t^{1−p(s)Psj=1b−1j}

P_s

j=1a_j(2^lt^1/bjm/t^1/bj)^bj

Q_s

j=1(^lt^1/bjm/t^1/bj+t^−1/bj)^p(s). (10) Now if t → ∞, then

P_s

j=1aj(2^lt^1/bjm/t^1/bj)^bj

Q_s

j=1(^lt^1/bjm/t^1/bj+t^−1/bj)^p(s) −→

Xs j=1

a_j2^bj.

However, the expression (10) must be positive when t tends to infinity, so we must have p(s)^Ps_j=1b⁻¹_j ≤1 or, equivalently, p(s)≤1/B(s). Thus, altogether p(s) = 1/B(s).

Proof of Point 2: Obviously, EC-SPT implies EC-PT. In [8] it is shown that EC-PT implies UEXP. Now we assume that UEXP holds, then we can show in exactly the same way as above that

lim inf

ktk_s,∞→∞

P_s

j=1aj(2tj)^bj

Q_s

j=1(1 +t_j)^p ≥ logq⁻¹

logω⁻¹M(s)^−p >0.

From this, it is then shown analogously to the proof of the first point thatp^Ps_j=1b⁻¹_j ≤1.

Since this holds for alls, we conclude, forstending to infinity, thatp^P∞_j=11/bj =pB ≤1.

Furthermore, if we assume that B <∞, and if we replace B(s) by B in the proof of Point 1, we see that UEXP holds with p≥1/B. Thus we have thatp^∗ = 1/B.

It remains to show thatB <∞implies EC-SPT. So assume that B =^P∞_j=11/bj <∞ and let n1, . . . , ns be given by

nj =









logC(a∗, b∗)^π₆² _log(1+ε^j2 2)

aj2^bj logω⁻¹





1/bj





with C(a∗, b∗) = 2ω^−a∗P∞_k=1ω^a∗kb∗. Note that nj is defined such that ω^aj(2nj)bjC(a∗, b∗)≤ 6

π²

log(1 +ε²) j² . Therefore

e²(Tn,s,INTs)≤ −1 +

Ys j=1

1 + 6 π²

log(1 +ε²) j²

!

≤ −1 + exp



 6

π² log(1 +ε²)

Xs j=1

j⁻²





≤ −1 + explog(1 +ε²)=ε².

We now estimate nj and then n = ^Qs_j=1nj. Clearly, nj ≥ 1 for all j ∈ N. We prove that nj = 1 for large j. Indeed,nj = 1 if

a_j2^bjlogω⁻¹ ≥log C(a∗, b∗)π² 6

j² log(1 +ε²)

!

. (11)

Let δ > 0. From ^P_{j b}¹

j < ∞ it follows with the Cauchy condensation test that also

P

j 2^j

b₂j <∞ and hence lim_j2^j/b₂^j = 0. Hence, we find that b⁻¹₂j ≤ ₂j+1^δ for j large enough.

For large enough k with 2^j ≤k ≤2^j+1 we then obtain 1

bk

≤ 1

b₂^j ≤ δ 2^j+1 ≤ δ

k

or, equivalently, 2^bk ≥2^k/δ. Hence, there exists a positive β₁ such that a_k2^bk ≥β₁2^k/δ for all k ∈N.

Then the inequality (11) holds for all j ≥j^∗, where j^∗ is the smallest positive integer for which

j^∗ ≥ δ

log 2 log 1

β1logω⁻¹ log C(a∗, b∗)π² 6

[j^∗]² log(1 +ε²)

!!

.

Clearly,

j^∗ = δ

log 2 log log ε⁻¹+O(1) as ε→0.

Without loss of generality we can restrict ourselves to ε ≤e^−e, where e = exp(1), so that log log ε⁻¹ ≥1. Then there exists a number C0 ≥1, independent of ε and s, such that

n_j = 1 for all j >

$

C₀+ δ

log 2 log log ε⁻¹

%

.

We now estimate n_j for j ≤^jC₀+_{log 2}^δ log log ε^−1k. Note that

log 2

1−ω π²

6

j² log(1 +ε²)

!

= log C(a∗, b∗) π² 6 log(1 +ε²)

!

+ log(j²).

Then aj2^bj ≥2^j/δ also implies that

K(a,b) := sup

j∈N

log(j²) aj2^bj <∞.

Furthermore, there exists a number C1 ≥1, independent of ε and s such that log C(a∗, b∗) π²

6 log(1 +ε²)

!

≤C₁+ 2 log1

ε for all ε∈(0,1).

This yields

n_j ≤1 + K(a,b) +C₁+ 2 logε⁻¹ logω⁻¹

!_1/bj

for all j ≤

$

C₀+ δ

log 2 log log1 ε

%

.

Let

k= min s,

$

C0+ δ

log 2 log log1 ε

%!

.

Then for C = max (K(a,b) +C1,−2e + logω⁻¹) we have max 1,K(a,b) +C1+ 2 logε⁻¹

logω⁻¹

!

≤ C+ 2 logε⁻¹ logω⁻¹ and

n=

Ys j=1

nj =

Yk j=1

nj ≤

Yk j=1



1 + C+ 2 logε⁻¹ logω⁻¹

!_1/bj



= C+ 2 logε⁻¹ logω⁻¹

!P^k

j=11/bj Yk j=1



1 + logω⁻¹ C+ 2 logε⁻¹

!1/bj



≤ C+ 2 logε⁻¹ logω⁻¹

!B

2^k. Note that

2^k≤2^C0 exp

δlog log1 ε

= 2^C0 log^δ 1 ε.

Therefore for any positive δ there is a positive number Cδ independent of ε⁻¹ and s such that

n(ε, s)≤n ≤Cδ log^B+δ

1 + 1 ε

for all ε∈(0,1), s∈N. This means that we have EC-SPT with τ^∗ at mostB.

Proof of Point 3: Assume that EC-WT holds and that (aj2^bj)j≥0 is bounded, say aj2^bj ≤A < ∞ for all j ∈ N. From setting t1 = t2 =· · · = 1 in Proposition 2 it follows that for all n <2^s we have

e(n,INTs)≥10^−sω^Psj=1aj2bj ≥10^−sω^As =η^s,

where η := ω^A/10 ∈ (0,1). Hence, for ε = η^s/2 we have e(n,INTs) > ε for all n < 2^s. This implies that n(ε,INT_s)≥2^s and

logn(ε,INTs)

s+ logε⁻¹ ≥ slog 2

s+ log 2 +slogη⁻¹ −→ log 2

1 + logη⁻¹ >0 as s→ ∞, but this contradicts EC-WT. Therefore, it must hold that limj→∞aj2^bj =∞.

Proof of Point 4: By Point 3 of Theorem 2, the condition limj→∞aj = ∞ implies EC-WT for the approximation problem with Λ^std, which, by (3), also implies EC-WT for the integration problem.

3 L

2

-approximation in half-period cosine spaces

Let APPs :H(K_s,a,b,ω^cos )→ L2([0,1]^s) with APPs(f) = f. In order to approximate APPs

with respect to the norm inL2([0,1]^s) we use linear algorithmsAn,s, which are algorithms based on n information evaluations of the form

An,s(f) =

Xn k=1

αkLk(f) for f ∈ H(K_s,a,b,ω^cos ),

where each α_k is a function from L₂([0,1]^s) and each L_k is a continuous linear functional defined on H(K_s,a,b,ω^cos ) from a permissible class Λ of information.

The worst-case error of an algorithm An,s is defined as e(A_n,s,APP_s) := sup

f∈H(K_s,^cosa,b,ω) kfk_Kcos

s,a,b,ω≤1

kf −A_n,s(f)k_L2([0,1]s).

The nth minimal worst-case error for the information class Λ∈ {Λ^std,Λ^all}is denoted by e(n,APP_s; Λ) = inf

An,s

e(A_n,s,APP_s),

where the infimum is taken over all linear algorithms An,s using information from Λ. For n = 0, we simply approximatef by zero, and the initial error is e(0,APP_s; Λ) = 1.

3.1 Some auxiliary results

We proceed in a similar way to [2] and [7]. For M >1 we define the setA(s, M) = {h∈ N^s

0 : ω_h⁻¹ < M} and we will study approximating f ∈ H(K_s,a,b,ω^cos ) by algorithms of the form

An,s,M(f)(x) = ^X

h∈A(s,M)



1 n

Xn k=1

f(xk)2^|

h|∗

2

Ys j=1

cos(πhjxk,j)



2^|

h|∗

2

Ys j=1

cos(πhjxj), (12) where x= (x1, . . . , xs) ∈ [0,1]^s. The choice of M and x_k = (xk,1, . . . , xk,s) ∈ [0,1)^s will be given later.

We first show upper bounds on the worst-case error of An,s,M. The following analysis is similar to that in [7, 10]. Using Parseval’s identity we obtain

kf−A_n,s,M(f)k²_L2([0,1]s) =

= ^X

h/∈A(s,M)

|f^e(h)|²+ ^X

h∈A(s,M)

fe(h)− 1 n

Xn k=1

f(xk)2^|h2|∗

Ys j=1

cos(πhjxk,j)

2

. (13) The first term can be estimated by

X

h∈A(s,M)/

|f(h)|^{e 2} = ^X

h∈A(s,M)/

|f(h)|^{e 2}ωhω⁻¹_h ≤ 1

Mkfk²_K^cos

s,a,b,ω. (14)

We now consider the second term in (13). Leth ∈N^s

0. Forf ∈ H(K_s,a,b,ω^cos ) we define fh(x) := f(x)2^|h|∗/2Qs_j=1cos(πhjxj). So we get

fe(h)− 1 n

Xn k=1

f(xk)2^|h|∗/2

Ys j=1

cos(πhjxk,j)

2

=

Z

[0,1]^sfh(x) dx− 1 n

Xn k=1

fh(xk)

2

. As for the integration problem, we choose the pointsx₁, . . . ,x_n used in the algorithm An,s,M according to a centered regular grid Gn,s with different mesh-sizes n1, . . . , ns ∈ N for successive variables, i.e.,

Gn,s =

( 2k1+ 1 2n1

, . . . , 2ks+ 1 2ns

!

: kj = 0,1, . . . , nj −1 for all j = 1,2, . . . , s

)

,

where n=^Qs_j=1nj is the cardinality of Gn,s. By G_n,s^⊥ we denote the set G_n,s^⊥ ={h∈N^s

0 : hj ≡0 (mod 2nj) for all j = 1,2, . . . , s}.

Since fh can be represented by a pointwise convergent cosine series, we have that

Z

[0,1]^sfh(x) dx− 1 n

Xn k=1

fh(xk)

≤

X

l∈N^s

0\{0}

ffh(l)2^|

l|∗

2

Ys j=1



 1 nj

n_j

X

kj=1

cos πlj

2kj + 1 2nj

!



≤ ^X

l∈G_n,s^⊥ \{0}

|f^fh(l)|2^|l2|∗.