On the optimal order of integration in Hermite spaces

www.oeaw.ac.at

On the optimal order of integration in Hermite spaces

with finite smoothness

J. Dick, C. Irrgeher, G. Leobacher, F.

Pillichshammer

RICAM-Report 2016-28

On the optimal order of integration in Hermite spaces with finite smoothness

Josef Dick

^∗

, Christian Irrgeher, Gunther Leobacher and Friedrich Pillichshammer

^†

August 1, 2016

Abstract

We study the numerical approximation of integrals with respect to the standard Gaussian measure for integrands which lie in certain Hermite spaces of functions.

The decay rate of the associated sequence is specified by a single parameter and determines the smoothness classes and for certain integer values of the parameter, the inner product can be expressed via L₂ norms of the derivatives of the function.

We map higher order digital nets from the unit cube to a suitable subcube ofR^s via a linear transformation and show that such rules achieve, apart from powers of logN, the optimal rate of convergence of the integration error. Numerical examples illustrate the performance of these quadrature rules and show their power compared to other quadrature rules.

Keywords: Numerical integration, worst-case error, higher order digital nets, Hermite polynomials

2010 MSC: 65D30, 65D32, 65Y20

1 Introduction

In this paper we study numerical integration of functions over thes-dimensional real space R^s of the form

I_s(f) =

Z

R^s

f(x)ϕ_s(x) dx, (1)

where ϕ_s denotes the density of the s-dimensional standard Gaussian measure, ϕ_s(x) = 1

(2π)^s/2 exp

−x·x 2

for x∈R^s.

∗This research was supported under Australian Research Council’s Discovery Projects funding scheme (project number DP150101770).

†The authors are supported by the Austrian Science Fund (FWF): Projects F5508-N26 (Leobacher), F5509-N26 (Irrgeher and Pillichshammer) and F5506-N26 (Irrgeher), respectively, which are parts of the Special Research Program “Quasi-Monte Carlo Methods: Theory and Applications”.

We assume that the integrands f belong to a certain reproducing kernel Hilbert space H_s,α of smoothness α whose construction is based on Hermite polynomials and which is therefore called a Hermite space of smoothness α. The exact definition of this space, which was introduced by Irrgeher and Leobacher [8], will be given in Section2.

In order to approximateI_s(f) we use linear algorithms of the form A_N,s(f) =

N

X

i=1

w_if(x_i),

which are based on nodes x₁, . . . ,x_N ∈ R^s and real weights w₁, . . . , w_N and study the worst-case absolute error e(A_N,s,Hs,α) ofAN,s over the unit ball of the Hermite space, i.e.

e(A_N,s,H_s,α) = sup

f∈Hs,α

kfks,α≤1

|I_s(f)−A_N,s(f)|.

The N-th minimal worst-case error e(N,H_s,α) is the infimum of e(A_N,s,H_s,α) over all linear algorithms A_N,s that useN function values.

For F, G : D ⊆ N → R we say F(N) . G(N) if there exists some c > 0 such that F(N) ≤ c G(N) for all N ∈ D. If the positive quantity c depends on some parameter, say s, then we may indicate this by writing .s. We may use the symbol also the other way round &with the obvious meaning.

Our main result states thate(N,H_s,α) is, up to some logN-factors, of the exact order of magnitude N^−α. More precisely, we show that

1

N^α .s,αe(N,H_s,α).s,α

(logN)^{s2α+34 −12}

N^α . (2)

For the upper bound we present an explicit algorithm.

The paper is organized as follows: In the next section we will introduce the function space setting under consideration. We recall the definition of Hermite polynomials, give the definition of Hermite spaces and discuss their smoothness properties. Section 3 is devoted to the numerical integration problem. After some further introductory words we will prove the lower bound from (2) in Subsection 3.1 (see Theorem 1). The upper bound from (2) will be presented in Subsections 3.2 (Theorem 2) and 3.3 (Corollary 1).

In Section 4 we numerically compute the worst-case error of the presented algorithm as well as of two other types of quadrature rules and compare their performances.

2 Hermite spaces of functions of finite smoothness

For k∈N0 the k-th Hermite polynomial is given by Hk(x) = (−1)^k

√k! exp(x²/2) d^k

dx^k exp(−x²/2),

which is sometimes also called normalized probabilistic Hermite polynomial, since

Z

R

Hk(x)²ϕ(x) dx= 1,

where ϕis the standard normal density, ϕ(x) = ^√1

2πexp(−x²/2). For example, H0(x) = 1, H₁(x) = x, H2(x) = ^√1

2(x²−1), H₃(x) = ^√1

6(x³−3x), . . . .

Here we follow the definition given in [1], but we remark that there are slightly different ways to introduce Hermite polynomials (see, e.g., [13]). Fors ≥2,k= (k₁, . . . , k_s)∈N^s0, and x= (x₁, . . . , x_s)∈R^s we defines-dimensional Hermite polynomials by

Hk(x) =

s

Y

j=1

Hkj(xj).

It is well-known (see [1]) that the sequence of Hermite polynomials{H_k(x)}k∈N^s0 forms an orthonormal basis of the function spaceL²(R^s, ϕ_s) of Gauss square-integrable functions.

We know that for all k∈N^s0 the bound

|H_k(x)^qϕs(x)| ≤1 for all x∈R^s (3) holds, which is a slightly weaker version of Cramer’s bound (c.f. Sansone [12]). The next lemma states a stronger bound on the Hermite polynomials.

Lemma 1. For all k∈N^s0 and for all x∈R^s we have

|Hk(x)^qϕs(x)| ≤

s

Y

j=1

min



1,

√π k_j^1/12



. (4)

The proof of this lemma will be deferred to the appendix. From this lemma it follows that

σ_s(k) := kH_k√

ϕ_sk∞ ≤min



1,

√π k^1/12_j



. (5)

For every square-integrable f :R^s →Rthe k-th Hermite coefficient of f is defined as fb(k) =^R

R^sf(x)H_k(x)ϕ_s(x) dx.

Definition 1. Lets∈N and let r:N^s0 →(0,∞) be a function satisfying

X

k∈N^s0

r(k)σ_s(k)² <∞.

Then the Hermite space corresponding to r is the Hilbert space H_r :=

f :R^s→R:f is continuous,

Z

R^s

f(x)²ϕ_s(x) dx<∞,kfk_r <∞

,

where kfk²_r :=^P_k∈N^s

0r(k)⁻¹f(k)^{b 2}. The inner product in H_r is thus given by hf, gi_r = ^X

k∈N^s0

1

r(k)f^b(k)bg(k).

This definition of a Hermite space is slightly more general than that given in [8]. There it was required ^P_k∈N^s

0r(k)<∞. From Lemma 1it follows that ^P_k∈N^s

0r(k)<∞ implies

P

k∈N^s0r(k)σ_s(k)² <∞.

To see that H_r is indeed closed under this norm one needs to show that for f ∈ H_r the Hermite series for f converges to a continuous function. But, applying the Cauchy- Schwarz inequality,

X

k∈N^s0

|f^b(k)H_k(x)ϕ_s(x)^1/2| ≤



 X

k∈N^s0

r(k)σ_s(k)²





1 2 

 X

k∈N^s0

r(k)⁻¹f(k)^{b 2}H_k(x)²ϕ_s(x) σ_s(k)²





1 2

≤



 X

k∈N^s₀

r(k)σ_s(k)²





1 2

kfk_s,α<∞.

Thus ^P_k∈N^s

0

fb(k)H_kϕ^1/2_s is a series of continuous functions which converges uniformly, so its limit is continuous. Therefore also ^P_k∈N^s

0

f(k)Hb _k =ϕ^−1/2_s ^P_k∈N^s

0

fb(k)H_kϕ^1/2_s is contin- uous.

We are now going to define the Hermite space of smoothnessα, which are characterized by a special choice of the r(k) for k∈N^s0. Let s, α∈N. For all k∈N^s0 we define

rs,α(k) =

s

Y

j=1

rα(kj) (6)

with

r_α(k) =







1 if k = 0

(^Pα_τ=0β_τ(k))⁻¹ if k ≥1 and for integers τ ≥1,

β_τ(k) =







k!

(k−τ)! if k ≥τ, 0 otherwise.

Note that we have r_α(k) =





min(α,k)

X

τ=0

k!

(k−τ)!





−1

≤ (k−min(α, k))!

k! =







1

k! if 1≤k ≤α,

(k−α)!

k! if k ≥α.

It is easily shown that limk→∞r_α(k)k^α = 1. Hence r_α(k)_α 1

k^α for k ∈N. Thus^P_k∈N^s

0r_s,α(k)σ_s(k)² <∞for allα∈N, and we may consider the associated Hermite space.

Definition 2. We call the Hermite space H_s,α corresponding to r_s,α as defined in (6) a Hermite space with smoothness α. We write k.k_s,α and h·,·i_s,α for the norm and inner product, respectively, of H_s,α.

The name Hermite space with smoothness α will be justified below. In the following we recall some commonly used conventions for operations with multiindices

• We denote the partial derivative by ∂xi := _∂x^∂

i for any i= 1, . . . , s.

• We denote the mixed partial derivatives with respect to x by

∂_x^τ := ∂^|τ|

∂x^τ = ∂^τ1· · ·∂^τs

∂x^τ₁¹· · ·∂x^τ_s^s

for any τ = (τ₁, . . . , τ_s)∈N^s0, where |τ|=τ₁+· · ·+τ_s.

• For vectors n= (n₁, . . . , n_s) andk= (k₁, . . . , k_s) we use the following notation:

n! =

s

Y

j=1

n_j!, n k

!

=

s

Y

j=1

nj

k_j

!

, |n|=

s

X

j=1

|n_j|, n·k=

s

X

j=1

n_jk_j.

Furthermore, n≥k means that n_j ≥k_j for all j ∈ {1,2, . . . , s}.

For f ∈ H_s,α we have the Hermite expansion, see [8], f(x) = ^X

k∈N^s0

f(k)Hb _k(x) for all x∈R^s and for any τ ∈N^s0 with τ ≤αwe have that

∂_x^τf ∼ ^X

k≥τ

fb(k)

s k!

(k−τ)!Hk−τ.

Using an analogous expression for g, we obtain using Parseval’s theorem that hf, gi_s,α = ^X

k∈N^s₀

1

rs,α(k)f(k)^b g(k)_b

= ^X

k∈N^s₀ s

Y

j=1 α

X

τ=0

β_τ(k_j)

!

fb(k)g(k)_b

= ^X

k∈N^s₀

X

τ∈{0,...,α}^s





s

Y

j=1

β_τj(k_j)



f(k)b g(k)_b

= ^X

τ∈{0,...,α}^s

X

k≥τ

k!

(k−τ)!f^b(k)g(k)_b

= ^X

τ∈{0,...,α}^s

Z

R^s

∂_x^τf(x)∂_x^τg(x)ϕ_s(x) dx.

Thus the inner product of H_s,α can also be written as hf, gi_s,α= ^X

τ∈{0,...,α}^s

Z

R^s

∂_x^τf(x)∂_x^τg(x)ϕ_s(x) dx.

In other words, for our special functionr_s,αthe corresponding Hermite space is a Sobolev- type space of functions on R^s with smoothness α.

Remark 1. Hermite spaces have already been introduced in [8] with the stronger re- quirement of summability of the corresponding sequence. The authors there consider the sequence ˜r_s,α(k) = k^−α, which asymptotically is same as the choice of r_s,α in this paper.

But due to the stronger (and unnecessary) requirement of summability in [8] there is the restriction of α >1, which is relaxed to α≥1 here.

Besides the case of polynomially decaying coefficients, Hermite spaces with with ex- ponentially decaying coefficients were also considered. Multivariate integration for such Hermite spaces has been analyzed in [7]. It is also shown there that the elements of those function spaces are analytic.

The results in [8] and [7] make heavy use of the facts that Hermite spaces are repro- ducing kernel Hilbert spaces with canonical kernel

K_s,α(x,y) = ^X

k∈N^s₀

r(k)H_k(x)H_k(y) for all x,y ∈R^s. (7) The eigenfunctions of the reproducing kernel are the Hermite polynomials and the eigen- values are precisely the numbers r(k).

It is a curious fact that we do not make direct use of this fact here.

3 Integration

We are interested in numerical approximation of the values of integrals Is(f) =

Z

R^s

f(x)ϕ_s(x) dx for f ∈ Hs,α.

Without loss of generality, see, e.g., [11, Section 4.2] or [14], we can restrict ourselves to approximating I_s(f) by means of linear algorithms of the form

A_N,s(f) =

N

X

i=1

w_if(x_i) for f ∈ H_s,α (8)

with integration nodes x₁, . . . ,x_N ∈ R^s and weights w₁, . . . , w_N ∈ R. An important subclass of linear algorithms are quasi Monte Carlo algorithms which are obtained by choosing the weights w_i = 1/N for all 1≤i≤N.

Forf ∈ H_s,α let

err(f) := I_s(f)−A_N,s(f).

The worst-case error of the algorithm AN,s is then defined as the worst performance of A_N,s over the unit ball of H_s,α, i.e.,

e(A_N,s,H_s,α) = sup

f∈Hs,α

kfks,α≤1

|err(f)|. (9)

Moreover, we define the N-th minimal worst-case error, e(N,H_s,α) = inf

AN,s

e(A_N,s,H_s,α)

where the infimum is taken over all linear algorithms using N function evaluations.

Numerical integration in the Hermite space has already been studied in [8]. There it has been shown that for every N ∈ N there exist points x₁, . . . ,x_N ∈ R^s such that the worst-case error of the quasi-Monte Carlo (QMC) algorithm Q_N,s(f) = _N^{1 PN}_i=1f(x_i) satisfies

e(Q_N,s,Hs,α).^s,α 1

√N.

This result, which is [8, Corollary 3.9], has been shown by means of an averaging argument.

The convergence rate however is very weak and does not depend on the smoothness α.

Even very large smoothness does not give information about an improved convergence rate. The aim of this paper is to improve this error estimate.

3.1 Lower bound on the worst-case error

First we prove a lower bound on the integration error.

Theorem 1. Let s, α ∈ N. Then for all N ∈ N the N-th minimal worst-case error for integration in the Hermite space H_s,α is bounded from below by

e(N,H_s,α)&s,α

1 N^α.

Proof. It is sufficient to prove the result for dimension s = 1, since higher dimensional integration is at least as hard as integration in one dimension. Let P ={x₁, x₂, . . . , x_N} denote the set of quadrature points used in algorithm AN = AN,1. (In the following we drop the index for the dimension to simplify the notation.) For m ∈ N we define Dm ={1,2, . . . ,2^m}. For i∈Dm let

h_i,m(x) =







(2^mx−i+ 1)^α(i−2^mx)^α for ⁱ⁻¹₂m ≤x < ₂ⁱm,

0 otherwise.

Let supp^◦(h_i,m) denote the open support of the function h_i,m and note that supp^◦(h_i,m)⊆

i−1 2^m , i

2^m

⊆[0,1]

for all i ∈ Dm, m ∈ N0. Note further that for fixed m the functions h_i,m for i ∈ Dm are orthogonal in L²(R, ϕ).

Lett∈N be such that 2^t−1 ≤2N <2^t. Define

h(x) = ^X

i∈Dt

P∩supp^◦(hi,t)=∅

h_i,t(x).

By definition we have h(x_i) = 0 for all i∈ {1,2, . . . , N} and hence also A_N(h) = 0.

Moreover,

Z

R

h_i,m(x)ϕ(x) dx=

Z ⁱ

2m i−1 2m

h_i,m(x)ϕ(x) dx

=

Z ⁱ

2m i−1 2m

(2^mx−i+ 1)^α(i−2^mx)^αϕ(x) dx

= 1 2^m

Z 1 0

z^α(1−z)^αϕ

z+i−1 2^m

dz

≥ 1 2^m

Z 1 0

z^α(1−z)^αϕ(1) dz

= 1 2^m

(α!)² (2α+ 1)!

√1 2πe,

where we used the value B(α+ 1, α+ 1) of the beta function. Thus we have

Z

R

h(x)ϕ(x) dx= ^X

i∈D^t P∩supp^◦(hi,t)=∅

Z

R

h_i,t(x)ϕ(x) dx

≥ ^X

i∈Dt

P∩supp^◦(hi,t)=∅

1 2^t

(α!)² (2α+ 1)!

√1 2πe

≥ 2^t−N 2^t

(α!)² (2α+ 1)!

√1 2πe

> 1 2

(α!)² (2α+ 1)!

√1

2πe, (10)

where we also used that P ∩supp^◦(h_i,m) is empty for at least 2^t−N many indices i∈Dt. It remains to estimate the norm of the functionhfrom above. Using orthogonality we have that

khk²_α =

α

X

τ=0

Z

R

h^(τ)(x)²ϕ(x) dx= ^X

i∈Dt

P∩supp^◦(hi,t)=∅

α

X

τ=0

Z

R

(h^(τ)_i,t (x))²ϕ(x) dx. (11)

In order to analyze the integrals in (11) we define g :R→R as g(x) =







x^α(1−x)^α for x∈(0,1),

0 otherwise.

Then

Z

R

(h^(τ)_i,t (x))²ϕ(x) dx=

Z ⁱ

2t i−1 2t

d^τ

dx^τg(2^tx−i+ 1)

!2

ϕ(x) dx

≤ 2^{2τ t}

√2π

Z ⁱ

2t i−1 2t

(g^(τ)(2^tx−i+ 1))²dx

= 2^{2τ t} 2^t√

2π

Z 1 0

(g^(τ)(z))²dz (note that ^R₀¹(g^(τ)(z))²dz <∞for all τ = 0,1, . . . , α) and further

α

X

τ=0

Z

R

(h^(τ)_i,t(x))²ϕ(x) dx≤c_α2^2αt−t,

where c_α=^q2/πmax_τ=0,...,α^R₀¹(g^(τ)(z))²dz <∞ depends only on α. Thus we have khk²_α .α

X

i∈Dt

P∩supp^◦(hi,t)=∅

2^2αt−t≤2^2αt. (12)

Combining (10), the fact thatAN(h) = 0 and (12) we finally obtain e(A_N,H_α)≥ |I(h)−A_N(h)|

khk_α &α

1 2^αt &α

1 N^α.

Remark 2. We conjecture that the lower estimate in Theorem 1 can be improved to N^−α(logN)^(s−1)/2.

3.2 A relation to integration in the ANOVA space

Definition 3. The ANOVA space of smoothness α defined over [0,1)^s (also known as unanchored Sobolev space) is given by

H_s,α^sob([0,1)^s) :=

s

O

j=1

ng : [0,1)→R : g^(r) absolutely continuous

for r ∈ {0. . . , α−1}, g^(α)∈L²[0,1)^o (13) with inner product

hg, hi_sob,s,α := ^X

u⊆{1,...,s}

X

τu∈{0,...,α−1}^|u|

×

Z

[0,1]^s−|u|

Z

[0,1]^|u|

∂_z^(τu,α−u)g(z) dz_u

! Z

[0,1]^|u|

∂_z^(τu,α−u)h(z) dz_u

!

dz−u

wherez_u denotes the|u|-dimensional vector with componentsz_j forj ∈uandz−u denotes the (s− |u|)-dimensional vector with the components z_j for j /∈ u. Moreover, (τ_u, α−u) denotes the s-dimensional vector for which the j-th component is α for j /∈ u and τ_j for j ∈u, whereτ_u = (τ_j)j∈u. The norm is k·k_sob,s,α =^qh·,·i_sob,s,α.

For short we write H^sob_s,α := H^sob_s,α([0,1)^s). Note that H^sob_s,α consists of functions with domain [0,1)^s instead of R^s.

Remark 3. Also the ANOVA space of smoothnessαis a reproducing kernel Hilbert space with kernel function

K_s,α^sob(x,y) =

s

Y

j=1

K_α^sob(x_j, y_j)

forx= (x₁, x₂, . . . , x_s)∈[0,1)^s and similarly fory, and where the one-dimensional kernel is given by

K_α^sob(x, y) =

α

X

r=0

Br(x)Br(y)

(r!)² + (−1)^α+1B2α(|x−y|) (2α)!

for x, y ∈[0,1), where B_r denotes the Bernoulli polynomial of degree r.

The worst-case absolute integration error of an algorithmA_N,s as in (8) is e(A_N,s,H^sob_s,α) = sup

g∈H^sob_s,α kgk_sob,s,α≤1

Z

[0,1]^s

g(x) dx−A_N,s(g)

.

Now we relate the integration problem in the Hermite space H_s,α to the integration problem in H^sob_s,α.

LetQN,s be a QMC-rule for integration in the ANOVA space H^sob_s,α which is based on a point set {z₁,z₂, . . . ,z_N} in [0,1)^s, i.e.,

Q_N,s(g) = 1 N

N

X

n=1

g(z_i) for g ∈ H^sob_s,α.

For any b = (b, . . . , b) ∈ (0,∞)^s we denote by B_b the mapping from [0,1]^s to [−b,b]

given by

Bb(z) = 2bz−b. (14)

Note that the mapping B_b is just a scaling and translation of the s-dimensional unit cube which is fully determined by the parameter b. The volume of the s-dimensional interval [−b,b] is then (2b)^s.

For integration in the Hermite spaceH_s,αwe consider integration rules of the following form: let {z₁,z₂, . . . ,z_N} ⊆ [0,1)^s be the point set used in Q_N,s. Then we use the integration rule

A_N,s(f) = (2b)^s N

N

X

i=1

f(B_b(z_i))ϕ_s(B_b(z_i)) for f ∈ H_s,α, (15) with b = 2√

αlogN for all i∈ {1,2, . . . , N}.

Theorem 2. Let α ∈ N and A_N,s be the quadrature rule defined in (15). Then for the worst-case error of AN,s in the Hermite space Hs,α we have

e(A_N,s,H_s,α).s,α(logN)^s2α+14 e(Q_N,s,H^sob_s,α) + 1 N^α.

For the proof of Theorem 2 we need some tools that will be provided in the next subsection. The proof will then be given in Subsection 3.2.2.

In Subsection 3.3 we provide a construction of point sets with low worst-case error e(Q_N,s,H^sob_s,α).

3.2.1 Auxiliary results

Lemma 2. Let f ∈ H_s,α with α∈N. Then |f(x)^qϕ_s(x)|.s,αkfk_s,α for all x∈R^s. Proof. For any f ∈ Hs,α we know that f(x) = ^P_k∈N^s

0

fb(k)H_k(x) for all x ∈ R^s. Using the Cauchy-Schwarz inequality and Lemma 1,

|f(x)^qϕ_s(x)| ≤ ^X

k∈N^s₀

|f^b(k)| |H_k(x)^qϕ_s(x)|r_s,α(k)^−1/2r_s,α(k)^1/2

≤



 X

k∈N^s0

1

r_s,α(k)|f^b(k)|²





1/2

 X

k∈N^s0

|H_k(x)^qϕ_s(x)|²r_s,α(k)





1/2

=kfk_s,απ^s/2 1 +

∞

X

k=1

1

k^1/6rα(k)

!s/2

.

We have

1 +

∞

X

k=1

1

k^1/6 r_α(k)≤1 +

α

X

k=1

1 k^1/6

1 k! +

∞

X

k=α+1

1 k^1/6

(k−α)!

k!

≤1 + e−1 +

∞

X

k=α+1

1 k^7/6

≤e +

Z ∞ α

dt

t^7/6 = e + 6 α^1/6 and hence the desired result follows.

Lemma 3. Let f ∈ H_s,α. For anyτ ={0, . . . , α}^s we have

∂_x^τ (f ·ϕ_s) (x) =ϕ_s(x)^X

j≤τ

(−1)^|τ−j| τ τ −j

! q

(τ −j)!H_τ−j(x)∂_x^jf(x). (16) Proof. We show this by induction on s. It is obvious that (16) holds for τ = 0. Now we denote by e_i the multiindex whose i-th entry is 1 with the remaining entries set to 0.

Then for any i= 1, . . . , swe have for τ =e_i that

∂_x^τ(f ·ϕ_s) (x) = ∂_xi(f(x)ϕ_s(x))

=∂xif(x)ϕ_s(x)−xif(x)ϕ_s(x)

= (H0(x)∂_x^eif(x)−Hei(x)f(x))ϕs(x).

Next we assume that (16) holds for some τ. Then for any i= 1, . . . , s we get that

∂_x^τ+ei(f(x)ϕ_s(x)) =

=∂_xi



 X

j≤τ

(−1)^|τ−j| τ τ −j

! q

(τ −j)!H_τ−j(x)∂_x^jf(x)ϕ_s(x)





= ^X

j≤τ

(−1)^|τ−j| τ τ −j

! q

(τ −j)!∂_xiH_τ−j(x)∂_x^jf(x)ϕ_s(x)

= ^X

j≤τ

(−1)^|τ−j| τ τ −j

! q

(τ −j)! (∂_x^eiHτ−j(x)−x_iH_τ−j(x))∂_x^jf(x)ϕ_s(x)

+^X

j≤τ

(−1)^|τ−j| τ τ −j

! q

(τ −j)!H_τ−j(x)∂^j+eif(x)ϕ_s(x)

= ^X

j≤τ

(−1)^|τ−j+ei| τ τ −j

! q

(τ −j+e_i)!H_τ−j+e_i(x)∂_x^jf(x)ϕ_s(x)

+ ^X

0<j≤τ+ei

(−1)^|τ−j+ei| τ τ −j +e_i

! q

(τ −j +e_i)!H_τ−j+e_i(x)∂_x^jf(x)ϕ_s(x).

If we use that for all j ≤τ and i= 1, . . . , s, τ

τ −j

!

+ τ

τ −j +e_i

!

= τ +ei

τ +e_i−j

!

,

we end up with

∂_x^τ+ei(f ·ϕ_s)(x) = ϕ_s(x) ^X

j≤τ+ei

(−1)^|τ−j+ei| τ +e_i τ +e_i−j

! q

(τ +e_i−j)!H_τ+ei−j(x)∂_x^τf(x).

3.2.2 Proof of Theorem 2

We will now prove the upper bound given in Theorem 2. To this end let f ∈ H_s,α. Then the absolute integration error can be estimated by using the triangle inequality, i.e.,

err(f) =

Z

R^s

f(x)ϕ_s(x) dx−(2b)^s N

N

X

i=1

f(x_i)ϕ_s(x_i)

≤

Z

R^s\[−b,b]f(x)ϕ_s(x) dx

+

Z

[−b,b]f(x)ϕ_s(x) dx− (2b)^s N

N

X

i=1

f(x_i)ϕ_s(x_i)

= err₁(f) + err₂(f), (17)

where

err₁(f) :=

Z

R^s\[−b,b]f(x)ϕ_s(x) dx

describes the error of approximating the integral outside of [−b,b] by zero and err₂(f) :=

Z

[−b,b]

f(x)ϕ_s(x) dx− (2b)^s N

N

X

i=1

f(x_i)ϕ_s(x_i)

is the integration error which results by applying the QMC rule to the function x 7→

f(x)ϕ_s(x) restricted to the interval [−b,b].

Estimate of err₁(f): With Lemma 2 we get err₁(f)≤

Z

R^s\[−b,b]

|f(x)ϕ_s(x)|dx

=

Z

R^s\[−b,b]|f(x)^qϕ_s(x)|^qϕ_s(x) dx .^s,αkfk_s,α

Z

R^s\[−b,b]

exp(−x·x/4) (2π)^s/2 dx .s,αkfk_s,α

Z

[0,∞)^s\[0,b]

exp(−x·x/4) π^s/2 dx.

Furthermore we have that

Z

[0,∞)^s\[0,b]

exp(−x·x/4) π^s/2 dx=

Z

[0,∞)^s

exp(−x·x/4) π^s/2 dx−

Z

[0,b]

exp(−x·x/4) π^s/2 dx

= 1

√π

Z ∞ 0

exp(−x²/4) dx

!s

− 1

√π

Z b 0

exp(−x²/4) dx

!s

= 1− 1

√π

Z b 0

exp(−x²/4) dx

!s

≤1−1−e^−b2/4s

≤s e^−b2/4

= s N^α,

where we used that b= 2√

αlogN. This shows that err₁(f).s,αkfk_s,α 1

N^α. (18)

Estimate of err₂(f): To estimate err₂(f) we will derive an upper bound which includes the worst-case error of integration in the ANOVA space H^sob_s,α. To this end we first trans- form the problem from [−b,b] to [0,1]^s, i.e.

err₂(f) =

Z

[−b,b]

f(x)ϕ_s(x) dx− (2b)^s N

N

X

i=1

f(x_i)ϕ_s(x_i)

= (2b)^s

Z

[0,1]^s

f(B_b(z))ϕ_s(B_b(z)) dz− 1 N

N

X

i=1

f(B_b(z_i))ϕ_s(B_b(z_i))

. (19)

Now we need the following lemma:

Lemma 4. Let f ∈ H_s,α and b > 0. Then the function g : [0,1)^s → R^s, given by g = (f·ϕ_s)◦ B_b with B_b as in (14), belongs to H^sob_s,α and furthermore,

kgk_sob,s,α .s,αb^s(α−1/2)kfk_s,α. (20)

Proof. Let f ∈ H_s,α. Using the Cauchy-Schwarz inequality we get kgk²_sob,s,α= ^X

u⊆{1,...,s}

X

τu∈{0,...,α−1}^|u|

Z

[0,1]^s−|u|

Z

[0,1]^|u|

∂_z^(τu,α−u)g(z) dz_u

!2

dz−u

≤ ^X

u⊆{1,...,s}

X

τu∈{0,...,α−1}^|u|

Z

[0,1]^s

∂_z^(τu,α−u)g(z)² dz

= ^X

τ∈{0,...,α}^s

Z

[0,1]^s

(∂_z^τg(z))² dz.

Since g = (f·ϕs)◦ Bb, we obtain kgk²_sob,s,α ≤ ^X

τ∈{0,...,α}^s

Z

[0,1]^s

(∂_z^τ(f·ϕs)(Bb(z)))² dz

= 1

(2b)^s

X

τ∈{0,...,α}^s

(2b)^2|τ|

Z

[−b,b]

(∂_x^τ(f ·ϕ_s)(x))² dx,