Classical integration rules and Wiener measure

Amarjit S. Budhiraja  Andrew J. Sommese

Abstract

In this paper precise calculations are made of the square of the error of classical integration rules averaged over spaces of differentiable functions. Precisely, let C_{0}^{N} denote the space of N-times continuously differentiable functions on [0, 1] with f^{(j)}(0) = 0 for j ≤ N. Let μ_{N} denote the measure induced by the N-times integrated Wiener process on C_{0}^{N}. For a given set of nodes 0 = x_{0} < x_{1} < ⋯ < x_{K} = 1 and weights w := (w_{ij}; i = 0, ⋯ K; j = 0, ⋯, N)

define the integration rule f → A_{w}(f) := ∑_{i,j} w_{i,j}f^{(j)}(x_{i}), to approximate I(f) := ∫_{0}^{1} f(x)dx.

A study is made of the average square error ∫_{C_{0}^{N}} |I(f) − A_{w}(f)|^{2}dμ_{N}(f); for what weights

w the minimum is achieved; for what sets of nodes this minimum is minimized; and what the minimum is in this case. AMS Subject Classification. 65D30, 60G15. Keywords. integration rules, trapezoidal rule, Newton-Cotes rules, Wiener measure, integrated Wiener process, Hermite interpolation.

Contents

1 Introduction 1

2 Background Material 3 2.1 Function Spaces and Measures Derived from Wiener Measure . . . . . . . . . . . . 3 2.2 Measures on C^{N} := C^{N}[0, 1] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.3 Change of Variables Formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

3 Integration Rules on C_{0} 6 3.1 Reduction from a Composite Rule to a Simple Rule . . . . . . . . . . . . . . . . . 7 3.2 Some Specific Calculations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

3.2.1 The trapezoidal rule and Simpson’s rule . . . . . . . . . . . . . . . . . . . . 8 3.2.2 Newton-Cotes’ rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3.3 The Optimal Integration Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

4 Integration Rules and Measures on Spaces of Differentiable Functions 12 4.1 Optimal Integration Rule on C_{0}^{N} and Hermite Interpolation . . . . . . . . . . . . . 12 4.2 The Average Square Error for the Optimal Rule . . . . . . . . . . . . . . . . . . . 17

1 Introduction

For a classical integration rule of order n−1 applied to a sufficiently differentiable function, there is an estimate for the error of the approximation to the actual integral in terms of the n-th derivative of the function. For example, given a twice continuously differentiable function f on the interval [0, 1], and using the composite trapezoidal rule [StoB93],

|∫_{0}^{1} f(x)dx − (\frac{f(0) + ∑_{i=1}^{K−1} 2f (\frac{i}{K} ) + f(1)}{2})| ≤ \frac{max_{[0,1]} |f^{(2)}|}{12K^{2}}.

For merely continuous functions, there are no strong error estimates that are true for each individual function. In this article, we study the L^{2}-error of the integration method for differentiable functions averaged with respect to a natural measure on the space of such functions. For example, using Wiener measure [Wie23, KarShr91] μ on C, the continuous real valued functions on [0, 1], we have

∫_{C} |∫_{0}^{1} f(x)dx − (\frac{f(0) + ∑_{i=1}^{K−1} 2f (\frac{i}{K} ) + f(1)}{2})|^{2} dμ(f) = \frac{1}{12K^{2}} .

More precisely, given a partition x_{0} = 0 < x_{1} ⋯ x_{K−1} < x_{K} = 1 of the interval [0, 1] ⊂ ℝ, and an integer N ≥ 0, we ask what integration method minimizes the L^{2}-error under the assumption that we know the first N derivatives of the function at the points, x_{0}, …, x_{K}. We further ask what is this error explicitly; and for a given K and N, which choice of K − 1 points in the open interval (a, b) minimize this error. More generally we are interested in these same questions where the underlying assumption is that we know possibly different numbers of derivatives at nodes on the interval.

The study of such errors averaged over an appropriate function space measure seems to have been begun by Sul’din [Su59, Su60]. Since then there have been a number of papers touching on different aspects of this study, cf., Smale [Sm85], Gao [G89, G91], and Choi [C94].

There are a number of issues that immediately come up as to what spaces of functions, measures, and norms should be used. The use of measures built out of a Wiener process is very natural. From Donsker’s invariance principle [Bill68, Theorem 2.10.1], a path space analogue of the classical central limit theorem, Brownian motion and Wiener measure are the limiting stochastic process and measure when the uncertainties in the physical problem under consideration arise as a net result of many small and not strongly dependent random effects. This partially accounts for the pervasive use of Wiener measure as the basis for many useful applied real world models, e.g., prices of securities in financial markets. Thus our results say something about the average of a given integration method applied to a random sample of functions, e.g., of price histories securities in a fixed time interval.

Moreover, Wiener measure has many canonical properties, which effectively means that many different set of assumptions lead to it, e.g., [Str93, Chapter IV]. We use L^{2} norms since the orthogonal increment property of the Wiener process and its simple covariance structure enable us to carry out many calculations explicitly.

For spaces of functions we use the space C^{N}[0, 1] of N times continuously differentiable functions on the interval [0, 1]. We will denote C^{0}[0, 1], also by C[0, 1]. A natural measure on the subset of C^{N}[0, 1] consisting of functions with f^{(j)}(0) = 0 for j ≤ N is the measure associated to N times integrated Brownian motion. There are choices involved in extending the measure to all of C^{N}[0, 1], but for the case of main interest, N less than or equal to the order of the method, the natural choices lead to the same L^{2}-norm for error, see, §2.2.

Let us give a more detailed description of the results of this paper.

In §2, we summarize some facts about the function space measures we use in the rest of the paper.

In §3 we work only with continuous functions, because the combinatorics are such that we can give a very complete picture. We consider an integration rule A(f) := ∑_{i=0}^{n} w_{i}f(x_{i}) for f ∈ C[0, 1] with 0 ≤ x_{0}, …, x_{n} ≤ 1 a strictly increasing sequence of points and w_{i} ∈ ℝ. We let

A_{m}(f) := ∑_{j=1}^{m} [∑_{i=0}^{n} w_{i}f (a + \frac{(b − a)}{m}(j − 1 + x_{i}))] \frac{(b − a)}{m}

be the associated m-fold composite rule on [a, b]. We show in Corollary 3.5 that if A is of order N ≥ 2, i.e., if A(p) = ∫_{0}^{1} p(t)dt for all polynomials p(t) of degree ≤ N ≥ 2, then with the Wiener measure, μ on C[a, b],

∫_{C[a,b]} |∫_{a}^{b} f(x)dx − A_{m}(f)|^{2} dμ(f) = \frac{(b − a)^{3}}{m^{2}} (∫_{C[0,1]} A(f)^{2}dμ(f) − \frac{1}{3}) .

There is also a slightly more complicated formula in the case when the order N = 1. Using this formula it is easy to compute the exact average square error for classical rules such as the Newton-Cotes rules. We carry out the calculations of this average square error, and show that it equals

\frac{1}{12K^{2}} in the case of the composite trapezoidal rule and \frac{1}{9K^{2}} in the case of the composite Simpson’s rule, where K := nm is one less than the number of points where the function f is evaluated. In Table 1, we list the average square errors for the Newton-Cotes rules with n ≤ 10.

We next show in Theorem 3.8 that for a given set of node points for the rule 0 ≤ x_{0} < ⋯ < x_{K} ≤ 1 the smallest average square error occurs for the composite trapezoidal rule, and moreover once the trapezoidal rule is fixed then varying over the sets of node points 0 ≤ x_{0} ≤ ⋯ ≤ x_{K} ≤ 1,

the smallest average error is obtained when the nodes are equidistant, i.e, x_{i} = a + \frac{(b − a)i}{K}.

In §4 we study the average error on C^{N}[0, 1] assuming that the values of the function and some of its first N derivatives are known at the node points. We show in Theorem 4.2 that the least L^{2}(μ_{N}) error, where μ_{N} is the measure induced by the N times integrated Wiener process, is obtained when the integration rule is given by the integration of a piecewise polynomial function. In Corollary 4.3, we show that if the values of the function f and its first N derivatives are known at the node points, then the least L^{2}(μ_{N}) error is achieved when the integration rule is given by the integration between any two node points x_{i}, x_{i+1} of the unique interpolating polynomial p(x) of degree 2N + 1, with p^{(j)}(x_{i}) := f^{(j)}(x_{i}), p^{(j)}(x_{i+1}) := f^{(j)}(x_{i+1}), for j ≤ N, i.e.,

A(f) := ∑_{i=0}^{K−1} ∫_{x_{i}}^{x_{i+1}} H_{i}(f)(y)dy

= ∑_{i=0}^{K−1} ∑_{j=0}^{N}(−1)^{j} \frac{\binom{2N+1−j}{N+1}}{\binom{2N+2}{N+1}(j + 1)!} [f^{(j)}(x_{i+1}) + (−1)^{j}f^{(j)}(x_{i})] (x_{i+1} − x_{i})^{j+1}. (1)

We then turn to what the minimum L^{2}(μ_{N}) error is in this case. We show that for N = 1, the

minimum L^{2}(μ_{N}) error is \frac{1}{720K^{4}} with equality only for the rule given in equation 1, and the node points, x_{i} := i/K for i = 0, …, K. We also give a precise conjecture 4.5 for the minimum for all

N, i.e., \frac{1}{2(2N + 3)!\binom{2N+1}{N}K^{2N+2}} , with equality only for the rule given in equation 1, and the node

points, x_{i} := i/K for i = 0, …, K.

The first author would like to thank National Science Foundation (NSF-DMI-9812857) and the University of Notre Dame Faculty Research Program for their support. The second author would like to thank the Duncan Chair of the University of Notre Dame and the Mathematical Sciences Research Institute in Berkeley for their support.

2 Background Material

In this section we collect some background material.

2.1 Function Spaces and Measures Derived from Wiener Measure

Let C[0, ∞) be the space of continuous functions from [0, ∞) to IR. Let B(C[0, ∞)) denote the Borel σ- field for this space with the usual topology of uniform convergence on compacts. Let μ_{∞} be the standard Wiener measure on (C[0, ∞), B(C[0, ∞))). Let 0 ≤ a ≤ b < ∞ be fixed and define: π_{a,b} : C[0, ∞) → C[a, b] as follows. For f ∈ C[0, ∞):

(π_{a,b}f)(x) := f(x); a ≤ x ≤ b.

Let μ_{a,b} be the push forward measure: μ_{∞}oπ_{a,b}^{−1} on (C[a, b], B(C[a, b])), where B(C[a, b]) is the Borel σ field on C[a, b]. We will write μ_{0,1} as μ. The rest of §2.1 is not needed for §3.

Let C^{N}[a, b] denote the space of N-times continuously differentiable functions on [a, b] and let C[a, b] be the space of continuous functions on [a, b]. We will sometimes denote C^{N}[0, 1] by C^{N} and C^{0} by C. Also, let C_{0}^{N} be the space of N times continuously differentiable functions f on [0, 1] such that f^{(j)}(0) = 0 for j ≤ N. Recall that C_{0} is the space of continuous functions f on [0, 1] such that f(0) = 0.

Let μ, as before be the standard Wiener measure on C_{0}. For N ∈ IN, define the map ϕ_{N}:

ϕ_{N} : C_{0} → C_{0}^{N},

as follows. For t_{N} ∈ [0, 1] and f ∈ C_{0},

(ϕ_{N}f)(t_{N}) := ∫_{0}^{t_{N}} (∫_{0}^{t_{N−1}} ⋯ (∫_{0}^{t_{1}} f(t_{0})dt_{0}) ⋯) dt_{N−1}.

Denote by μ_{N} the push forward measure μoΦ_{N}^{−1} on (C_{0}^{N}, B(C_{0}^{N})), where B(C_{0}^{N}) denotes the Borel σ-field on C_{0}^{N} corresponding to the uniform norm on the function value and its first N derivatives. Also let μ_{0} := μ.

2.2 Measures on C^{N} := C^{N}[0, 1]

In this article we restrict attention to C_{0}^{N}, the space of N times continuously differentiable functions f on [0, 1] such that f^{(j)}(0) = 0 for j ≤ N. In this subsection we will show that, for natural extensions of the measures to C^{N} := C^{N}[0, 1], we get the same results. Let P^{N} := P^{N}[0, 1] denote the polynomials of degree ≤ N on [0, 1]. Every function h ∈ C^{N} can be written uniquely h(x) = t_{N}(x) + f(x), where t_{N}(x) ∈ P^{N} is the Taylor polynomial of h of degree N expanded around 0, and f(x) ∈ C_{0}^{N}. Now let G := C_{0}^{N} × P^{N} and endow G with the usual product σ-field denoted by G. Let ν_{N} be a probability measure on (G, G) satisfying

ν_{N}(A × P^{N}) = μ_{N}(A),  (2)

for all A ∈ B(C_{0}^{N}). Define θ : G → C^{N} as θ(f, p) := f + p; (f, p) ∈ C_{0}^{N} × P^{N}. Finally, let μ̃_{N} := ν_{N}oθ^{−1}.

Lemma 2.1 Let A be any integration rule of order ≥ N on functions f ∈ C^{N}, i.e., A(p) =

∫_{0}^{1} p(x)dx for p ∈ P^{N}. Let μ̃_{N} be a probability measure on (C^{N}, B(C^{N})) as constructed above.

Then:

∫_{C^{N}} |A(h) − ∫_{0}^{1} h(x)dx|^{2} dμ̃_{N}(h) = ∫_{C_{0}^{N}} |A(f) − ∫_{0}^{1} f(x)dx|^{2} dμ_{N}(f).

Proof. Since A(p) = ∫_{0}^{1} p(x)dx for p ∈ P^{N}, we have

∫_{C^{N}} |A(h) − ∫_{0}^{1} h(x)dx|^{2} dμ̃_{N}(h) = ∫_{C_{0}^{N} ×P^{N}} |A(f + p) − ∫_{0}^{1}(f(x) + p(x))dx|^{2} dν_{N}(f, p)

= ∫_{C_{0}^{N} ×P^{N}} |A(f) − ∫_{0}^{1} f(x)dx|^{2} dν_{N}(f, p)

= ∫_{C_{0}^{N}} |A(f) − ∫_{0}^{1} f(x)dx|^{2} dμ_{N}(f),

where the last step follows from (2). □

It is important to note, that when we talk about an integration rule of order ≥ N on f ∈ C_{0}^{N}

of the form ∑_{i=0}^{K} ∑_{j=0}^{N} w_{ij}f^{(j)}(x_{i}) for the set of nodepoints x_{0} = 0 < x_{1} < ⋯ < x_{K} = 1, the

weights w_{0k} for k ≤ N are determined by the other weights. Indeed we have that \frac{1}{k+1} = A(x^{k}) = w_{0k}k! + ∑_{i=1}^{K} ∑_{j=k}^{N} w_{ij}\binom{j}{k}k!x_{i}^{j−k}, i.e.,

w_{0k} = \frac{1}{(k + 1)!} − ∑_{i=1}^{K} ∑_{j=k}^{N} w_{ij}\binom{j}{k}x_{i}^{j−k}.

for k = 0, …, N. This observation is implicit in the proofs of the uniqueness statements of Theorem 3.8, Lemma 3.9, Corollary 4.3, Conjecture 4.5, and Theorem 4.6.

2.3 Change of Variables Formula

In §3 we are interested in studying the L^{2} error, with respect to the measure μ_{a,b}, for a given integration rule on C[a, b]. The following change of variables formula will allow us to study this L^{2} error for a given integration rule on C[a, b] in terms of a related integration rule on C_{0} := {f ∈ C[0, 1]|f(0) = 0}. Henceforth for f ∈ C[a, b], we write ∫_{a}^{b} f(x)dx as I_{a}^{b}(f). We will usually abbreviate I_{0}^{1}(f) to I(f).

Theorem 2.2 Let a = x_{0} < x_{1} < ⋯ < x_{K} = b be a fixed partition of [a, b]. Let {w_{j}}_{0≤j≤k} be a given set of weights. Let A(·) be an integration rule of order N ≥ 0, on C[a, b], defined as follows. For f ∈ C[a, b]

A(f) := ∑_{j=0}^{K} w_{j}f(x_{j}).

Then

∫_{C[a,b]}[I_{a}^{b}(f) − A(f)]^{2}dμ_{a,b}(f) = (b − a)^{3} ∫_{C_{0}}[I(f) − Ã(f)]^{2}dμ(f),

where for f ∈ C_{0}

Ã(f) := ∑_{j=0}^{k} w̃_{j}f(y_{j});

w̃_{j} = \frac{w_{j}}{b−a} and y_{j} = \frac{x_{j} − a}{b − a}; j = 0, ⋯, K.

CLASSICAL INTEGRATION RULES AND WIENER MEASURE 6 Proof. Let {W (t)}_{0≤t<∞} be a standard Wiener process on some probability space. Then

∫_{C[a,b]}[I_{a}^{b}(f) − A(f)]^{2}dμ_{a,b}(f) = 𝔼 [∫_{a}^{b} W (s)ds − ∑_{j=0}^{K} w_{j}W (x_{j})]^{2}
= 𝔼 [∫_{a}^{b}(W (s) − W (a))ds + W (a)(b − a)
− ∑_{j=0}^{K} w_{j}(W (x_{j}) − W (a)) − W (a) ∑_{j=0}^{K} w_{j}]^{2}
= 𝔼 [∫_{a}^{b}(W (s) − W (a))ds − ∑_{j=0}^{K} w_{j}(W (x_{j}) − W (a))]^{2} ,

where the last equality follows on noticing that ∑_{j=0}^{K} w_{j} = b − a. Next note that

∫_{a}^{b}(W (s) − W (a))ds = (b − a) ∫_{0}^{1}[W (a + s(b − a)) − W (a)]ds.

Furthermore

∑_{j=0}^{K} w_{j}(W (x_{j}) − W (a)) = ∑_{j=0}^{k} w_{j}(W (a + y_{j}(b − a)) − W (a)).

Define, for s ∈ [0, 1]

W̃(s) := \frac{W (a + s(b − a)) − W (a)}{\sqrt{b − a}}.

With this notation

∫_{C[a,b]}[I_{a}^{b}(f) − A(f)]^{2}dμ_{a,b}(f) = (b − a)^{3}𝔼 [∫_{0}^{1} W̃(s)ds − ∑_{j=0}^{K} w̃_{j}W̃(y_{j})]^{2}
= (b − a)^{3}𝔼 [∫_{0}^{1} W (s)ds − ∑_{j=0}^{K} w̃_{j}W (y_{j})]^{2}
= (b − a)^{3} ∫_{C_{0}}[I(f) − Ã(f)]^{2}dμ(f),

where the next to last equality above follows on observing that the probability law of the family {W̃(s); 0 ≤ s ≤ 1} is same as that of the family {W (s); 0 ≤ s ≤ 1}. □

3 Integration Rules on C_{0}

We recall that μ is the standard Wiener measure on

C_{0} := {f ∈ C[0, 1]|f(0) = 0}

and for f ∈ C_{0}, I(f) := ∫_{0}^{1} f(x)dx. Let A(f) := ∑_{i=0}^{n} w_{i}f(x_{i}), where 1. the x_{i} are a strictly increasing sequence of real numbers with x_{0} ≥ 0 and x_{n} ≤ 1; and

2. the w_{i} are real numbers.

Given a rule f → A(f) := ∑_{i=0}^{n} w_{i}f(x_{i}) as above and m ∈ IN_{0}, define the m-times composite rule

A_{m}(f) := ∑_{j=1}^{m} A_{j}(f) = ∑_{j=1}^{m} [∑_{i=0}^{n} \frac{w_{i}}{m} f (\frac{j − 1 + x_{i}}{m} )] .

Note that for m = 1, A_{1} = A. Moreover if A is of order N, then so is A_{m} for any m. The

composite rule associated to A(f) = \frac{f(0) + f(1)}{2} is the usual composite trapezoidal rule analyzed

in §3.2.1, and the composite rule associated to A(f) = \frac{f(0) + 4f(\frac{1}{2}) + f(1)}{6} is the usual composite Simpson’s rule analyzed in §3.2.2.

The goal of this section is to compute

∫_{C_{0}} |I(f) − A_{m}(f)|^{2}dμ(f)  (3)

3.1 Reduction from a Composite Rule to a Simple Rule

In this section we make calculations with few assumptions on the weights and nodes. In particular we give Theorem 3.4 which reduces calculations for a composite method based on a given simple rule to that for the simple rule. Let A(·) be an integration rule as above. Then

∫_{C_{0}} |I(f) − A(f)|^{2}dμ(f) = ∫_{C_{0}} I(f)^{2}dμ(f) − 2 ∫_{C_{0}} I(f)A(f)dμ(f) + ∫_{C_{0}} A(f)^{2}dμ(f) (4)
= 2 ∫_{0}^{1} ∫_{0}^{y} xdxdy − 2A(x) + A(x^{2}) + ∫_{C_{0}} A(f)^{2}dμ(f)  (5)
= \frac{1}{3} − 2A(x) + A(x^{2}) + ∫_{C_{0}} A(f)^{2}dμ(f).  (6)

An immediate consequence of this calculation is:

Lemma 3.1 If A is an integration rule of order N ≥ 1, then

∫_{C_{0}} |I(f) − A(f)|^{2}dμ(f) = \frac{1}{3} − 2A(x) + A(x^{2}) + ∫_{C_{0}} A(f)^{2}dμ(f).

Furthermore, if N ≥ 2, then

∫_{C_{0}} |I(f) − A(f)|^{2}dμ(f) = ∫_{C_{0}} A(f)^{2}dμ(f) − \frac{1}{3}.

The above lemma shows that the computation of ∫_{C_{0}} |I(f) − A(f)|^{2}dμ(f) comes down to the

computation of ∫_{C_{0}} A(f)^{2}dμ(f).

Example 3.2 Let A be the trapezoid rule, A(f) := \frac{f(0) + f(1)}{2}. Then ∫_{C_{0}} A(f)^{2}dμ(f) = \frac{1}{4}, and

thus,

∫_{C_{0}} |I(f) − A(f)|^{2}dμ(f) = \frac{1}{3} − 2A(x) + A(x^{2}) + ∫_{C_{0}} A(f)^{2}dμ(f) = \frac{1}{3} − 1 + \frac{1}{2} + \frac{1}{4} = \frac{1}{12}.

CLASSICAL INTEGRATION RULES AND WIENER MEASURE 8 Example 3.3 Let A be Simpson’s rule, A(f) := \frac{f(0) + 4f (\frac{1}{2}) + f(1)}{6}. Then

∫_{C_{0}} A(f)^{2}dμ(f) = [\frac{4}{6}]^{2} [\frac{1}{2}] + 2 [\frac{4}{6}] [\frac{1}{6}] [\frac{1}{2}] + [\frac{1}{6}]^{2} = \frac{13}{36},

and thus,

∫_{C_{0}} |I(f) − A(f)|^{2}dμ(f) = \frac{1}{3} − 2A(x) + A(x^{2}) + ∫_{C_{0}} A(f)^{2}dμ(f) = \frac{1}{3} − 1 + \frac{1}{3} + \frac{13}{36} = \frac{1}{36}.

We now show how to reduce the computation of ∫_{C_{0}} A_{m}(f)^{2}dμ(f) for a composite rule to the computations for the rule. Theorem 3.4 Let A be an integration rule of order N ≥ 1 and let A_{m} be the m-fold composite rule constructed from A. Then

∫_{C_{0}} A_{m}(f)^{2}dμ(f) = \frac{1}{m^{2}} ∫_{C_{0}} A(f)^{2}dμ(f) − \frac{1}{3m^{2}} + \frac{1}{3}.

Proof. Note that if j < k then

∫_{C_{0}} A_{j}(f)A_{k}(f)dμ(f) = \frac{1}{m} ∑_{i=1}^{n} \frac{w_{i}}{m} (\frac{j − 1 + x_{i}}{m} ) = \frac{1}{m^{3}} (j − 1 + \frac{1}{2}) = \frac{1}{m^{3}} (j − \frac{1}{2})

Thus ∫_{C_{0}} A_{m}(f)^{2}dμ(f)

= ∑_{j=1}^{m} ∫_{C_{0}} A_{j}^{2}dμ(f) + 2 ∑_{j=1}^{m} [\frac{1}{m^{3}} (j − \frac{1}{2})] (m − j)
= ∑_{j=1}^{m} ∫_{C_{0}} A_{j}^{2}dμ(f) − \frac{1}{2m} + \frac{1}{6m^{2}} + \frac{1}{3}
= ∑_{j=1}^{m} [∑_{i=1}^{n} \frac{w_{i}^{2}}{m^{2}} (\frac{j − 1 + x_{i}}{m} ) + 2 ∑_{1≤i<k≤n} \frac{w_{i}w_{k}}{m^{2}} (\frac{j − 1 + x_{i}}{m} )] − \frac{1}{2m} + \frac{1}{6m^{2}} + \frac{1}{3}
= [∑_{i=1}^{n} \frac{w_{i}^{2}}{m^{2}} (\frac{m − 1}{2} + x_{i}) + 2 ∑_{1≤i<k≤n} \frac{w_{i}w_{k}}{m^{2}} (\frac{m − 1}{2} + x_{i})] − \frac{1}{2m} + \frac{1}{6m^{2}} + \frac{1}{3}
= \frac{m − 1}{2} [∑_{i=1}^{n} \frac{w_{i}}{m} ]^{2} + \frac{1}{m^{2}} ∫_{C_{0}} A(f)^{2}dμ(f) − \frac{1}{2m} + \frac{1}{6m^{2}} + \frac{1}{3}
= \frac{m − 1}{2} \frac{1}{m^{2}} + \frac{1}{m^{2}} ∫_{C_{0}} A(f)^{2}dμ(f) − \frac{1}{2m} + \frac{1}{6m^{2}} + \frac{1}{3}
= \frac{1}{m^{2}} ∫_{C_{0}} A(f)^{2}dμ(f) − \frac{1}{3m^{2}} + \frac{1}{3}.
□

Combining Theorem 3.4 with Lemma 3.1 we get the following corollary.

Corollary 3.5 Let A be an integration rule of order N ≥ 1 and let A_{m} be the m-fold composite rule constructed from A. Then

∫_{C_{0}} |I(f) − A_{m}(f)|^{2}dμ(f) = −\frac{1}{3} + A_{m}(x^{2}) + \frac{1}{m^{2}} ∫_{C_{0}} A(f)^{2}dμ(f) − \frac{1}{3m^{2}} .

If N ≥ 2 then

∫_{C_{0}} |I(f) − A_{m}(f)|^{2}dμ(f) = \frac{1}{m^{2}} ∫_{C_{0}} A(f)^{2}dμ(f) − \frac{1}{3m^{2}} .

3.2 Some Specific Calculations

In this section we compute the L^{2} errors with respect to the Wiener measure for a few specific methods.

3.2.1 The trapezoidal rule and Simpson’s rule

Example 3.6 (Composite Trapezoid Rule) Let A_{m} denote the m-fold composite trapezoidal

rule. Noting that A_{m}(x^{2}) = \frac{1}{3} + \frac{1}{6m^{2}} , it follows from Corollary 3.5 and Example 3.2 that

∫_{C_{0}} |I(f) − A_{m}(f)|^{2}dμ(f) = −\frac{1}{3} + \frac{1}{3} + \frac{1}{6m^{2}} + \frac{1}{m^{2}} ∫_{C_{0}} A(f)^{2}dμ(f) − \frac{1}{3m^{2}}
= \frac{1}{6m^{2}} + \frac{1}{m^{2}} ∫_{C_{0}} A(f)^{2}dμ(f) − \frac{1}{3m^{2}}
= \frac{1}{6m^{2}} + \frac{1}{4m^{2}} − \frac{1}{3m^{2}}
= \frac{1}{12m^{2}} .

Note that the m-fold composite trapezoidal rule has K + 1 nodes with K = m. Thus we have

∫_{C_{0}} |I(f) − A_{m}(f)|^{2}dμ(f) = \frac{1}{12K^{2}} .

Example 3.7 (Composite Simpson Rule) Let A_{m} denote the m-fold composite Simpson rule.

Using Corollary 3.5 and Example 3.3, we have ∫_{C_{0}} |I(f) − A_{m}(f)|^{2}dμ(f) = \frac{13}{36m^{2}} − \frac{1}{3m^{2}} = \frac{1}{36m^{2}} .

Note that the m-fold composite Simpson rule has K + 1 nodes with K = 2m. Thus we have

∫_{C_{0}} |I(f) − A_{m}(f)|^{2}dμ(f) = \frac{1}{9K^{2}} .

3.2.2 Newton-Cotes’ rules

Calculations for other Newton-Cotes’ rules are carried out similarly. Table 1 has the values for the first ten Newton-Cotes’ rules using Maple. We have n equal to the number of nodes minus one. The third column is the value multiplied by n^{2}.

Note that the weights in Newton-Cotes are positive for n ≤ 7 and n = 9. It is probably true that n = 9 is the last Newton-Cotes formula with all weights positive. The last column grows quite fast. Generally, the values for odd n are increasing and the values for even n are increasing, though the series for odd n is less than that for the preceding even n. For n = 20, the value in the last column is ≈ 177,908.

Table 1: Average Square Error for Newton-Cotes Formulae

n ∫_{C_{0}} |I(f) − A(f)|^{2}dμ(f) n^{2} (∫_{C_{0}} |I(f) − A(f)|^{2}dμ(f))
1  \frac{1}{12}  \frac{1}{12}  ≈  0.083
2  \frac{1}{36}  \frac{1}{9}  ≈  0.111
3  \frac{1}{96}  \frac{3}{32}  ≈  0.094
4  \frac{13}{1620}  \frac{52}{405}  ≈  0.128
5  \frac{169}{41472}  \frac{4225}{41472}  ≈  0.102
6  \frac{293}{50400}  \frac{293}{1400}  ≈  0.209
7  \frac{21211}{8294400}  \frac{1039339}{8294400}  ≈  0.125
8  \frac{2670323}{267907500}  \frac{42725168}{66976875} ≈  0.638
9  \frac{33233407}{12042240000}  \frac{897301989}{4014080000} ≈  0.224
10  \frac{554021687}{16295634432}  \frac{13850542175}{4073908608} ≈  3.400

3.3 The Optimal Integration Rule

In this subsection we show that in the class of integration rules with K + 1 nodes, composite trapezoidal rule gives the least L^{2} error.

Theorem 3.8 Let a = x_{0} < x_{1} < ⋯ < x_{K} = b be a fixed partition of [a, b]. For a given set of weights w := (w_{0}, w_{1}, ⋯, w_{K}) define the integration rule A_{w} on C[a, b] as follows. For f ∈ C[a, b]:

A_{w}(f) := ∑_{j=0}^{K} w_{j}f(x_{j}).

Then

inf_{w} ∫_{C[a,b]}[I_{a}^{b}(f) − A_{w}(f)]^{2}dμ_{a,b}(f) = ∫_{C[a,b]}[I_{a}^{b}(f) − A(f)]^{2}dμ_{a,b}(f);

if and only if

A(f) = ∑_{j=0}^{K} \frac{Δ_{j}}{2} (f(x_{j+1}) + f(x_{j})),

where

Δ_{j} = x_{j+1} − x_{j}.

Moreover

∫_{C[a,b]}[I_{a}^{b}(f) − A_{w}(f)]^{2}dμ_{a,b}(f) ≥ \frac{(b − a)^{3}}{12K^{2}} ,

with equality if and only if x_{j} = a+ \frac{(b − a)j}{K} for j = 0, … K, and A_{w}(f) is the composite trapezoidal rule, i.e.,

A_{w}(f) := (f(x_{0}) + ∑_{j=1}^{K−1} 2f(x_{j}) + f(x_{K})) \frac{(b − a)}{2K}.

As an immediate consequence of Theorem 2.2 we are reduced to showing the following lemma.

Lemma 3.9 Let 0 = x_{0} < x_{1} < ⋯ < x_{K} = 1 be a given partition of [0, 1]. For a given set of weights: w := (w_{0}, w_{1}, ⋯, w_{K}) define the integration rule on C_{0} as follows. For f ∈ C_{0}

A_{w}(f) := ∑_{j=0}^{K} w_{j}f(x_{j}).

Then

inf_{w} ∫_{C_{0}}[I(f) − A_{w}(f)]^{2}dμ(f) = ∫_{C_{0}}[I(f) − A(f)]^{2}dμ(f),

where

A(f) = ∑_{j=0}^{K} \frac{Δ_{j}}{2} [f(x_{j+1}) + f(x_{j})],

and Δ_{j} := x_{j+1} − x_{j}. Moreover

∫_{C_{0}}[I(f) − A_{w}(f)]^{2}dμ(f) ≥ \frac{1}{12K^{2}} ,

with equality if and only if A_{w}(f) is the composite trapezoidal rule, i.e.,

A_{w}(f) := (f(0) + ∑_{j=1}^{K−1} 2f (\frac{j}{K} ) + f(1)) \frac{1}{2K} .

Proof. In order to prove the first conclusion of the lemma it suffices to show that

𝔼_{μ} [I(f) | f(x_{0}), ⋯, f(x_{K})] = A(f),

where 𝔼_{μ} denotes the expected value corresponding to the measure μ. Observe that

𝔼_{μ}[I(f) | f(x_{0}), ⋯, f(x_{K})] = ∑_{j=0}^{K−1} 𝔼_{μ}[∫_{x_{j}}^{x_{j+1}} f(x)dx | f(x_{0}), ⋯, f(x_{K})]

= ∑_{j=0}^{K−1} ∫_{x_{j}}^{x_{j+1}} 𝔼_{μ}[f(x) | f(x_{0}), ⋯, f(x_{K})] dx.

Next note that for x ∈ [x_{j}, x_{j+1}), 𝔼_{μ}[f(x) | f(x_{0}), ⋯, f(x_{K})]

= f(x_{j}) + 𝔼_{μ}[f(x) − f(x_{j}) | f(x_{0}), ⋯, f(x_{K})]
= f(x_{j}) + 𝔼_{μ}[f(x) − f(x_{j}) | f(x_{0}), f(x_{1}) − f(x_{0}), ⋯, f(x_{K}) − f(x_{K−1})]
= f(x_{j}) + 𝔼_{μ}[f(x) − f(x_{j}) | f(x_{j+1}) − f(x_{j})]
= f(x_{j}) + \frac{x − x_{j}}{Δ_{j}} (f(x_{j+1}) − f(x_{j})),

where the third equality follows from the independent increment property of the Wiener process. Hence

𝔼_{μ}[I(f) | f(x_{0}), ⋯, f(x_{K})] = ∑_{j=0}^{K−1} ∫_{x_{j}}^{x_{j+1}} (f(x_{j}) + \frac{x − x_{j}}{Δ_{j}} (f(x_{j+1}) − f(x_{j}))) dx

= ∑_{j=0}^{K−1} (Δ_{j}f(x_{j}) + \frac{Δ_{j}}{2} (f(x_{j+1}) − f(x_{j})))

= ∑_{j=0}^{K−1} \frac{Δ_{j}}{2} (f(x_{j+1}) + f(x_{j})).

This proves the conclusion of the theorem for arbitrary node points x_{i}.

The final assertion is a minimization statement about the explicit function:

F_{K}(x_{1}, …, x_{K−1}) := ∫_{C_{0}} (∫_{0}^{1} f(x)dx − ∑_{j=0}^{K−1} \frac{x_{j+1} − x_{j}}{2} (f(x_{j+1}) + f(x_{j})))^{2} dμ(f).

By Example 3.2.1, F_{K} (\frac{1}{K} , …, \frac{K − 1}{K}) = \frac{1}{12K^{2}} . Therefore it suffices to show that there is a

unique minimum of F_{K}(x_{1}, …, x_{K−1}) on the region 0 ≤ x_{1} ≤ ⋯ ≤ x_{K−1} ≤ 1, and it occurs at (x_{1}, …, x_{K−1}) = (\frac{1}{K} , …, \frac{K−1}{K}). First note that

F_{K}(x_{1}, …, x_{K−1}) = \frac{1}{3} − ∑_{j=0}^{K−1} (x_{j} + x_{j+1} − \frac{x_{j}^{2}}{2} − \frac{x_{j+1}^{2}}{2} ) (x_{j+1} − x_{j})

+ ∑_{j=0}^{K−1}(3x_{j} + x_{j+1}) (\frac{x_{j+1} − x_{j}}{2} )^{2}

+ ∑_{j=0}^{K−1}(x_{j} + x_{j+1})(x_{j+1} − x_{j})(1 − x_{j+1})

Noting that F_{K} with two variables equal, e.g., x_{i} = x_{i+1} is simply the F_{K−1} with one of the variables omitted, we are reduced by induction to checking the local minima of F_{K} in the region x_{1} < ⋯ < x_{K−1}. To this end note that

\frac{∂F_{K}(x_{1}, …, x_{K−1})}{∂x_{j}} = \frac{1}{4}(x_{j−1} − x_{j+1})(x_{j−1} − 2x_{j} + x_{j+1}).

In the region x_{1} < ⋯ < x_{K−1}, we conclude that any relative minima satisfies x_{j−1}−2x_{j} +x_{j+1} = 0 for j = 0, …, K − 1. This system of linear equations has the unique solution (x_{1}, …, x_{K−1}) = (\frac{1}{K} , …, \frac{K−1}{K}). To see this, note that (x_{1}, …, x_{K−1}) = (\frac{1}{K} , …, \frac{K−1}{K}) is a solution, and further, with the tridiagonal (K − 1) × (K − 1)-matrix T with −2 along the diagonal, and 1 on the off diagonals, e.g., for K ≥ 7,

T := ( \begin{matrix}−2 & 1 & 0 & 0 & ⋯ & 0 \\ 1 & −2 & 1 & 0 & ⋯ & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & ⋯ & 0 & 1 & −2 & 1 \\ 0 & ⋯ & 0 & 0 & 1 & −2 \end{matrix} ) ,

it follows by using difference equations applied to the expansion by minors that det T = (−1)^{K−1}K ≠

0. That it is a relative minima follows from the fact that by induction, F_{K} ≥ \frac{1}{12(K − 1)^{2}} on the

boundary of the region. □

4 Integration Rules and Measures on Spaces of Differentiable Functions

We will consider in this section integration rules on C_{0}^{N} and the L^{2}(μ_{N}) errors associated with such rules. We follow the notation of §2.1.

4.1 Optimal Integration Rule on C_{0}^{N} and Hermite Interpolation

Suppose that:

0 = x_{0} < x_{1} < x_{2} ⋯ < x_{K} = 1

is a given partition on [0, 1]. We will like to find the integration rule on C_{0}^{N} which minimizes the L^{2}(μ_{N}) error and which is based on

{f^{(j)}(x_{i}); i, j ∈ IN_{0}; i ≤ K; j ≤ N} ,

where f is an arbitrary element of C_{0}^{N}.

Let W (·) be a standard Brownian motion on [0, 1], and for j ∈ {1, ⋯, N} let X^{(j)}(·) be a stochastic process defined inductively as

X^{(j)}(t) := ∫_{0}^{t} X^{(j−1)}(s)ds,

where X^{(0)}(·) := W (·). Clearly, μ_{N} is the law of X^{(j)}(·), i.e. for any continuous bounded real valued function G on C_{0}^{N}

∫_{C_{0}^{N}} G(f)dμ_{N}(f) = 𝔼 (G (X^{(N)}(·))) .

We let

R^{(N)}(u, v) := 𝔼 (X^{(N)}(u)X^{(N)}(v)) .

Lemma 4.1 With the above notation we have that for n ∈ IN_{0}

R^{(n)}(u, v) = \{ \begin{matrix}\frac{(−1)^{n}}{(2n+1)!} [∑_{k=0}^{n} \binom{2n+1}{k}u^{2n+1−k}(−v)^{k}] for u ≤ v \\ \frac{(−1)^{n}}{(2n+1)!} [∑_{k=0}^{n} \binom{2n+1}{k}(−u)^{k}v^{2n+1−k}] for v ≤ u \end{matrix}

Proof. The proof is via an inductive argument. The result is clearly true when n = 0. Next suppose that the result is true for n − 1 for some n ∈ IN. Then for u ≤ v, 𝔼[X^{(n)}(u)X^{(n)}(v)]

= ∫_{0}^{v} (∫_{0}^{u} 𝔼[X^{(n−1)}(s)X^{(n−1)}(t)]ds) dt
= 2 ∫_{0}^{u} (∫_{0}^{t} 𝔼[X^{(n−1)}(s)X^{(n−1)}(t)]ds) dt + ∫_{u}^{v} (∫_{0}^{u} 𝔼[X^{(n−1)}(s)X^{(n−1)}(t)]ds) dt.

Thus

R^{(n)}(u, v) = 2 ∫_{0}^{u} (∫_{0}^{t} \frac{(−1)^{n−1}}{(2n − 1)!} [∑_{k=0}^{n−1} \binom{2n − 1}{k}s^{2n−1−k}(−t)^{k}] ds) dt

+ ∫_{u}^{v} (∫_{0}^{u} \frac{(−1)^{n−1}}{(2n − 1)!} [∑_{k=0}^{n−1} \binom{2n − 1}{k}s^{2n−1−k}(−t)^{k}] ds) dt

= \frac{(−1)^{n−1}}{(2n − 1)!} ∑_{k=0}^{n−1} \binom{2n − 1}{k}(−1)^{k} \frac{2u^{2n+1}}{(2n − k)(2n + 1)}
+ \frac{(−1)^{n−1}}{(2n − 1)!} ∑_{k=0}^{n−1} \binom{2n − 1}{k}(−1)^{k} \frac{u^{2n−k}[v^{k+1} − u^{k+1}]}{(2n − k)(k + 1)}.

Rearranging the terms above we have that

R^{(n)}(u, v) = \frac{(−1)^{n−1}}{(2n − 1)!} ∑_{k=0}^{n−1} \binom{2n − 1}{k}(−1)^{k} \frac{u^{2n+1}}{(2n − k)} [\frac{2}{2n + 1} − \frac{1}{k + 1}]
+ \frac{(−1)^{n−1}}{(2n − 1)!} ∑_{k=0}^{n−1} \binom{2n − 1}{k}(−1)^{k} \frac{u^{2n−k}v^{k+1}}{(2n − k)(k + 1)}
= \frac{(−1)^{n−1}}{(2n − 1)!}u^{2n+1} [∑_{k=0}^{n−1} \binom{2n − 1}{k}(−1)^{k} \frac{2k + 1 − 2n}{(2n − k)(2n + 1)(k + 1)}]  (7)
+ \frac{(−1)^{n}}{(2n + 1)!} ∑_{k=1}^{n} \binom{2n + 1}{k}(−1)^{k}u^{2n+1−k}v^{k}.  (8)

Finally, the expression in (7) can be written as:

\frac{(−1)^{n−1}}{(2n − 1)!}u^{2n+1} [− ∑_{k=0}^{n−1} \binom{2n − 1}{k}\frac{(−1)^{k}}{(2n + 1)(k + 1)} + ∑_{k=0}^{n−1} \binom{2n − 1}{k}\frac{(−1)^{k}}{(2n − k)(2n + 1)}]

= \frac{(−1)^{n−1}}{(2n − 1)!}u^{2n+1} [\frac{−1}{2n(2n + 1)} ∑_{k=0}^{n−1}(−1)^{k}\binom{2n}{k + 1} + \frac{1}{2n(2n + 1)} ∑_{k=0}^{n−1}(−1)^{k}\binom{2n}{k}]
= \frac{(−1)^{n}}{(2n + 1)!}u^{2n+1} [1 − 2 ∑_{k=0}^{n−1}(−1)^{k}\binom{2n}{k} − (−1)^{n}\binom{2n}{n}]
= \frac{(−1)^{n}}{(2n + 1)!}u^{2n+1} [1 + (−1)^{n}2\binom{2n − 1}{n − 1} − (−1)^{n}\binom{2n}{n}]
= \frac{(−1)^{n}}{(2n + 1)!}u^{2n+1}.

Using the above observation in (7) we have the result. □

We now show that the optimal L^{2}(μ_{N}) estimate is obtained by using an interpolating polynomial. More precisely, Theorem 4.2 Let 0 = x_{0} < x_{1} < ⋯ < x_{K} = 1 be a given partition of [0, 1]. Let

S ⊂ {0, 1, ⋯, K} × {0, 1, ⋯, N}

be given. For a given set of weights w := (w_{ij}; (i, j) ∈ S) define the integration rule

A_{w}(f) := ∑_{(i,j)∈S} w_{ij} (\frac{d}{dx})^{j} f(x_{i});

where f is an arbitrary element of C_{0}^{N}. Then

inf_{w} ∫_{C_{0}^{N}} [I(f) − A_{w}(f)]^{2}dμ_{N}(f) = ∫_{C_{0}^{N}} [I(f) − A(f)]^{2}dμ_{N}(f),

where

A(f) := ∑_{k=0}^{K−1} ∫_{x_{k}}^{x_{k+1}} P_{k}(f)(y)dy,

and P_{k}(f)(y); y ∈ [x_{k}, x_{k+1}] is a polynomial of degree at most 2N +1. Furthermore, P_{k}(f) satisfies

\frac{d^{j}}{dx^{j}} P_{k}(f)(x_{k}) = f^{(j)}(x_{k}); ∀j s.t. (k, j) ∈ S

and

\frac{d^{j}}{dx^{j}} P_{k}(f)(x_{k+1}) = f^{(j)}(x_{k+1}); ∀j s.t. (k + 1, j) ∈ S.

Proof. Note that

∫_{C_{0}^{N}} [I(f) − A_{w}(f)]^{2}dμ_{N}(f) = 𝔼 [∫_{0}^{1} X^{(N)}(s)ds − A_{w}(X^{(N)})]^{2} .

Furthermore

inf_{w} 𝔼 [∫_{0}^{1} X^{(N)}(s)ds − A_{w}(X^{(N)})]^{2} = 𝔼 [∫_{0}^{1} X^{(N)}(s)ds − ζ]^{2} ,

where

ζ = 𝔼 [∫_{0}^{1} X^{(N)}(s)ds | X^{(j)}(x_{i}); (i, N − j) ∈ S]

= ∑_{k=0}^{K−1} 𝔼 [∫_{x_{k}}^{x_{k+1}} X^{(N)}(s)ds | X^{(j)}(x_{i}); (i, N − j) ∈ S]

= ∑_{k=0}^{K−1} ∫_{x_{k}}^{x_{k+1}} 𝔼 [X^{(N)}(s) | X^{(j)}(x_{i}); (i, N − j) ∈ S] ds.

Thus it suffices to show that for all k ∈ {0, 1, ⋯, K − 1} and s ∈ [x_{k}, x_{k+1}]

𝔼 [X^{(N)}(s) | X^{(j)}(x_{i}); (i, j) ∈ S̃] = P_{k}(X^{(N)})(s),  (9)

where

S̃ := {(i, j) : (i, N − j) ∈ S}.

Since (X^{(N)}(s), X^{(j)}(x_{i}); (i, j) ∈ S̃) is a Gaussian family for all s ∈ [0, 1] we have that the conditional expectation in (9) equals u_{S}(x)A_{S}^{−1}v_{S}, where A_{S} is a |S| × |S| matrix with a typical entry being 𝔼[X^{(j)}(x_{i})X^{(j′)}(x_{i′})]; (i, j), (i′, j′) ∈ S̃, v_{S} is a |S| × 1 matrix with a typical entry equal to X^{(j)}(x_{i}) and finally u_{S}(x) is a 1 × |S| matrix with a typical entry equal to 𝔼[X^{(N)}(s)X^{(j)}(x_{i})]; (i, j) ∈ S̃. We will now show that for s ∈ [x_{k}, x_{k+1}] all the entries of the row vector u_{S}(x) are polynomials with degree at most 2N + 1. Note that for j ∈ {0, 1, ⋯, N}

X^{(N)}(s) = ∑_{l=0}^{N−j} X^{(N−l)}(x_{k})\frac{(s − x_{k})^{l}}{l!}

+ ∫_{x_{k}}^{s} (∫_{x_{k}}^{t_{N−1}} ⋯ (∫_{x_{k}}^{t_{j+1}}(X^{(j)}(t_{j}) − X^{(j)}(x_{k}))dt_{j}) ⋯) dt_{N−1}.

Thus 𝔼(X^{(N)}(s)X^{(j)}(x_{i}))

= ∑_{l=0}^{N−j} 𝔼 (X^{(N−l)}(x_{k})X^{(j)}(x_{i})) \frac{(s − x_{k})^{l}}{l!}

+ ∫_{x_{k}}^{s} (∫_{x_{k}}^{t_{N−1}} ⋯ (∫_{x_{k}}^{t_{j+1}} (𝔼(X^{(j)}(t_{j})X^{(j)}(x_{i})) − 𝔼(X^{(j)}(x_{k})X^{(j)}(x_{i}))) dt_{j}) ⋯) dt_{N−1}.

(10)

Now observe that 𝔼(X^{(j)}(t_{j})X^{(j)}(x_{i})) = R^{(j)}(x_{i}, t_{j}) and also that either t_{j} ≤ x_{i} or t_{j} ≥ x_{i} for all t_{j} ∈ [x_{k}, x_{k+1}]. Thus from Lemma 4.1 we have that for all t_{j} ∈ [x_{k}, x_{k+1}], 𝔼(X^{(j)}(t_{j})X^{(j)}(x_{i})) is a polynomial in t_{j} of degree 2j + 1. This yields that the expression in (10) is a polynomial, for s ∈ [x_{k}, x_{k+1}], of degree at most:

2j + 1 + N − j ≤ 2N + 1.

This establishes that P_{k}(X^{(N)}(s)) is a polynomial of degree at most 2N + 1 for s ∈ [x_{k}, x_{k+1}] and k ∈ {0, 1, ⋯, K − 1}. Finally note that for fixed k ∈ {0, 1, ⋯, K − 1} and j such that (k, j) ∈ S

\frac{d^{j}}{dx^{j}} P_{k}(X^{(N)})(x_{k}) = 𝔼 (X^{(N−j)}(x_{k}) | X^{(j)}(x_{i}); (i, j) ∈ S̃)
= X^{(N−j)}(x_{k}).

Similarly for j such that (k + 1, j) ∈ S

\frac{d^{j}}{dx^{j}} P_{k}(X^{(N)})(x_{k+1}) = X^{(N−j)}(x_{k+1}).

□

Given f ∈ C_{0}^{N} and i ∈ {0, ⋯, K − 1} let H_{i}(f) be the unique polynomial of degree 2N + 1 on [x_{i}, x_{i+1}] such that

(\frac{d^{j}}{dx^{j}} H_{i}(f)) (x_{i}) = f^{(j)}(x_{i})

and

(\frac{d^{j}}{dx^{j}} H_{i}(f)) (x_{i+1}) = f^{(j)}(x_{i+1}),

where j ∈ {0, ⋯, N}. Thus H_{i}(f) is the Hermite interpolating polynomial over the interval [x_{i}, x_{i+1}].

Corollary 4.3 Let

0 = x_{0} < x_{1} < x_{2} ⋯ < x_{K} = 1

be a given partition of [0, 1]. For a given set of weights w := (w_{ij}; i = 0, ⋯ K; j = 0, ⋯, N) define the integration rule

A_{w}(f) := ∑_{i,j} w_{i,j}f^{(j)}(x_{i}),

where f is an arbitrary element of C_{0}^{N}. Then

inf_{w} ∫_{C_{0}^{N}} [I(f) − A_{w}(f)]^{2}dμ_{N}(f) = ∫_{C_{0}^{N}} [I(f) − A(f)]^{2}dμ_{N}(f),

where A(f) :=

∑_{k=0}^{K−1} ∫_{x_{k}}^{x_{k+1}} H_{k}(f)(y)dy = ∑_{i=0}^{K−1} ∑_{j=0}^{N}(−1)^{j} \frac{\binom{2N+1−j}{N+1}}{\binom{2N+2}{N+1}(j + 1)!} [f^{(j)}(x_{i+1}) + (−1)^{j}f^{(j)}(x_{i})] (x_{i+1} − x_{i})^{j+1}.

Proof. All that remains to be shown is the second equality in the description of A(f). This follows from the following Lemma.

Lemma 4.4 Let p(y) be a polynomial of degree 2N + 1 on an interval [a, b]. Then

∫_{a}^{b} p(y)dy = ∑_{j=0}^{N}(−1)^{j} \frac{\binom{2N+1−j}{N+1}}{\binom{2N+2}{N+1}(j + 1)!} [p^{(j)}(b) + (−1)^{j}p^{(j)}(a)] (b − a)^{j+1}.

To prove the Lemma is suffices by changing variables to prove the lemma on the interval [0, 1]. Any polynomial can be written as a sum of degree 2N +1 polynomials p(y) = q(y)+r(y) where for j ≤ N: q^{(j)}(0) = 0 = r^{(j)}(1); q^{(j)}(1) = p^{(j)}(1); and r^{(j)}(0) = p^{(j)}(0). Thus, it suffices to prove the result for polynomials of the form q(y). We are therefore reduced to showing that for polynomials of degree 2N + 1 satisfying p^{(j)}(0) = 0 for j ≤ N, we have

∫_{0}^{1} p(y)dy = ∑_{j=0}^{N}(−1)^{j} \frac{\binom{2N+1−j}{N+1}}{\binom{2N+2}{N+1}(j + 1)!}p^{(j)}(1).

Since p(y) = y^{N+1} ∑_{k=0}^{N} c_{k}(y − 1)^{k}, we have

∑_{k=0}^{N} c_{k}(y − 1)^{k} = (\frac{1}{1 + (y − 1)})^{N+1} ( ∑_{j=0}^{2N+1} \frac{p^{(j)}(1)}{j!}(y − 1)^{j}) .

Expanding (\frac{1}{1 + (y − 1)})^{N+1} in a power series around 1, we get explicit expressions for the

coefficients c_{k}, i.e.,

c_{k} := ∑_{j=0}^{k}(−1)^{k−j}\binom{N + k − j}{N}\frac{p^{(j)}(1)}{j!}.

Integrating y^{N+1} ∑_{k=0}^{N} c_{k}(y − 1)^{k} from 0 to 1 yields

∑_{k=0}^{N}(−1)^{k} \frac{1}{(N + k + 2)\binom{N+k+1}{k}} (∑_{j=0}^{k}(−1)^{k−j}\binom{N + k − j}{N}\frac{p^{(j)}(1)}{j!}) .

Changing the order of summation we obtain

∑_{j=0}^{N}(−1)^{j} (∑_{k=j}^{N} \frac{\binom{N+k−j}{N}}{(N + k + 2)\binom{N+k+1}{k}j!}) p^{(j)}(1).

Summing the middle sum gives the desired expression. □

4.2 The Average Square Error for the Optimal Rule

Using Corollary 4.3 for any particular N and K, the computation of the infimum that is achieved with the optimal integration rule is completely straightforward using a symbolic processing program such as Maple. Unfortunately, increasingly complicated combinatorics make the study of the average square error difficult for arbitrary N and K. We have the following conjecture.

Conjecture 4.5 Let 0 = x_{0} < x_{1} < x_{2} ⋯ < x_{K} = 1 be a given partition of [0, 1]. For a given set of weights w := (w_{ij}; i = 0, ⋯ K; j = 0, ⋯, N) define the integration rule

A_{w}(f) := ∑_{i,j} w_{i,j} (\frac{d}{dx})^{j} f(x_{i}),

where f is an arbitrary element of C_{0}^{N}. Then

∫_{C_{0}^{N}} [I(f) − A_{w}(f)]^{2}dμ_{N}(f) ≥ \frac{1}{2(2N + 3)!\binom{2N+1}{N}K^{2N+2}} ,

with equality only if A_{w}(f) is as given in Corollary 4.3 with x_{i} := \frac{i}{K} for i = 0, …, K.

All that needs to be done to prove the conjecture is analyze the average square distance in Corollary 4.3 for general N and K. The above conjecture is based on many calculations for a variety of N and K

Theorem 3.8 proves the conjecture when N = 0. Here we give a proof of the conjecture when N = 1.

Theorem 4.6 Let

0 = x_{0} < x_{1} < x_{2} ⋯ < x_{K} = 1

be a given partition of [0, 1]. For a given set of weights w := (w_{ij}; i = 0, ⋯ K; j = 0, ⋯, N) define the integration rule

A_{w}(f) := ∑_{i,j} w_{i,j} (\frac{d}{dx})^{j} f(x_{i}),

where f is an arbitrary element of C_{0}^{N}. Then

∫_{C_{0}^{N}} [I(f) − A_{w}(f)]^{2}dμ_{N}(f) ≥ \frac{1}{720K^{4}} ,

with equality only if

A_{w}(f) := [ ∑_{i=0}^{K−1}(f(x_{i}) + f(x_{i+1}))\frac{(x_{i+1} − x_{i})}{2}] − [ ∑_{i=0}^{K−1}(f′(x_{i+1}) − f′(x_{i}))\frac{(x_{i+1} − x_{i})^{2}}{12} ] ,

and x_{i} := \frac{i}{K}.

Proof. The calculation follows exactly the lines of the proof of Lemma 3.9. We leave the reader to check that

F_{K}(x_{1}, …, x_{K−1}) := ∫_{C_{0}^{N}} [I(f)−A_{w}(f)]^{2}dμ_{N}(f) = \frac{1}{720}−\frac{1}{144} ∑_{i=0}^{K−1} x_{i}x_{i+1}(x_{i+1}^{2}−x_{i}x_{i+1}+x_{i}^{2})(x_{i+1}−x_{i})

Thus for i = 1 to i = K − 1, we have

\frac{∂F_{K}}{∂x_{i}} = \frac{−1}{144}(x_{i+1} − x_{i−1})(x_{i−1} − 2x_{i} + x_{i+1})[(x_{i+1} − x_{i})^{2} + (x_{i} − x_{i−1})^{2}].

This allows us by induction to conclude the smallest value occurs when x_{i−1} − 2x_{i} + x_{i+1} = 0 for each i from 1 to K − 1. Thus for the minimum, we have x_{i} = \frac{i}{K}. The rest of the calculation is straightforward. □

References

[Bill68] P. Billingsley, Convergence of Probability Measures, (1968), John Wiley & Sons. Inc.

[C94] S.H. Choi, Probabilistic analysis of Simpson’s quadrature, J. Complexity 10 (1994), 384–410.

[G89] F. Gao, A probabilistic theory of error estimation for automatic integration algorithms, NumerṀath. 56 (1989), 309–329.

[G91] F. Gao, Probabilistic analysis of numerical integration algorithms, J. Complexity 7 (1991), 58–69.

[KarShr91] I. Karatzas and S. Shreve, Brownian motion and Stochastic Calculus, (1991), Springer-Verlag.

[Sm85] S. Smale, On the efficiency of algorithms of analysis, Bull. Amer. Math. Soc. 13 (1985), 87–121.

[StoB93] J. Stoer and R. Bullirsch, Introduction to Numerical Analysis, 2nd Ed. (1993), Springer-Verlag, New York.

[Str93] D.W. Stroock, Probability Theory, An Analytic View, (1993), Cambridge University Press, Cambridge.

[Su59] A.V. Sul’din, Wiener measure and its application to approximation methods (Russian) Izv. Vysš. Učebn. Zaved. Matematika (1959) no. 6 (13), 145–158.

[Su60] A.V. Sul’din, Wiener measure and its applications to approximation methods. II. (Russian) Izv. Vysš. Učebn. Zaved. Matematika (1960) no. 5 (18), 165–179.

[Wie23] N. Wiener, Differential Space, J. Math. Phys. 3, 127–146.

Amarjit S. Budhiraja budhiraja.1@nd.edu Andrew J. Sommese sommese@nd.edu

 URL: www.nd.edu/∼sommese

Department of Mathematics University of Notre Dame Notre Dame, Indiana 46556, U.S.A. fax: U.S.A. + 219–631-6579