![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
A randomized trapezoidal quadrature rule is proposed for continuous functions which enjoy less regularity than commonly required. Indeed, we consider functions in some fractional Sobolev space. Various error bounds for the randomized rule are established while an error bound for classical trapezoidal quadrature is obtained for comparison. The randomized trapezoidal quadrature rule is shown to improve the order of convergence by half.
1. Introduction
It is well known that the trapezoidal quadrature in classical numerical analysis is a technique for approximating -valued definite integral when the integrand is at least twice differentiable. It has been well-studied by Goodwin [Citation7], Schwartz [Citation9] and Stenger [Citation10]. The case of a rough integrand was investigated in [Citation3]. More recently, a stochastic version of the trapezoidal quadrature was proposed for approximating the Itô integral where the integrator is a Brownian motion [Citation5].
Without loss of generality, we consider the time interval and let
to be the integrand of interest, where
is the space of
-valued continuous functions that have continuous first two derivatives, endowed with the uniform norm topology. The trapezoidal quadrature is proven to achieve a order of convergence as high as 2 for evaluating the integral
with finite many point evaluations [Citation4]. To implement this, we first partition the interval
into N equidistant intervals with stepsize
, i.e.
(1)
(1) where the subscription N is suppressed in h for the sake of notational simplicity but assumed implicitly in all of the quantities introduced involving h. Define
(2)
(2) When g has less regularity, the trapezoidal quadrature shows a slower convergence with a sharp bound [Citation3]. To accelerate the convergence when g is ‘rougher’, we consider a randomized trapezoidal quadrature, which is inspired by the randomized version of mid-point Runge–Kutta quadrature rule [Citation8] and stochastic version of trapezoidal quadrature for Itô integral [Citation5]. In this paper, the
-valued integrand g is assumed to be in fractional Sobolev space
under Sobolev–Slobodeckij norm:
(3)
(3) for
and
. We may write
as
for short. Let us define a randomized trapezoidal quadrature as follows:
(4)
(4) where
is a sequence of independent and identically (i.i.d.) uniformly distributed random variables on a probability space
,
and
. The main result, Theorem 3.2, shows that the convergence rate can be improved to
compared to
achieved by the classical trapezoidal quadrature (Theorem 3.1) when
.
The paper is organized as follows. In Section 2, we present some prerequisites from probability theory. In Section 3, we give the error estimates for both the classical trapezoidal quadrature and the randomized trapezoidal quadrature. In addition, we also investigate the error estimate in almost sure sense for the randomized trapezoidal quadrature in Theorem 3.3, which is proven still superior to the classical one. In the last section, we verify the results through several numerical experiments.
2. Preliminaries
This section is devoted to a brief review of essential probability results for audience who are not familiar with probability theory. Most of the contents are repeated material from Section 2 in [Citation8]. One may refer to [Citation2] for a more detailed introduction.
Recall that a probability space consists of a measurable space
endowed with a finite measure
satisfying
. A random variable
is called integrable if
. Then, the expectation of X is defined as
where
is distribution of X on its image space. We write
with
if
, where
is a Banach space endowed with the norm
We will write
as
for short.
We say that a family of -valued random variables
is a discrete-time stochastic process if we interpret the index m as a time parameter. A crucial concept in our main proof is martingales, which is a special case of the discrete-time stochastic process with many nice properties. If
is an independent family of integrable random variables satisfying
for each
, then the stochastic process defined by the partial sums
is a discrete-time martingale. One of the most important inequalities for martingales is the Burkholder–Davis–Gundy inequality. In this paper, we need its discrete-time version.
Theorem 2.1
Burkholder–Davis–Gundy
For each there exist positive constants
and
such that for every discrete time martingale
and for every
we have
where
denotes the quadratic variation of
up to n.
3. Trapezoidal quadratures for a rougher integrand
This section investigates the errors from trapezoidal rules for approximating integral of . The error bound from the classical trapezoidal rule is obtained in Section 3.1 and the ones from the randomized trapezoidal rule is in Section 3.2.
3.1. Classical trapezoidal quadrature for ![](//:0)
![](//:0)
Theorem 3.1
If for
, then we have
(5)
(5) where C is a constant that only depends on p.
Proof.
To show Equation (Equation5(5)
(5) ), we follow [Citation5] to rewrite
(6)
(6) where
. Then, the LHS of Equation (Equation5
(5)
(5) ) can be rewritten as
where
(7)
(7) and
(8)
(8) Regarding
, first note that
Then, we can rewrite
as
(9)
(9) Thus evaluating
under
norm gives
(10)
(10) where the second line is deduced by applying Hölder's inequality twice, and
. For the case
and any
, we may directly apply the discrete Hölder's inequality to the last term above:
For the case
and any
, we may first make use of the definition of
and then apply the discrete Hölder's inequality:
For term
, we can follow a similar argument in [Citation5] to show that
(11)
(11) Indeed, note that
If defining a new process
then Equation (Equation11
(11)
(11) ) can be obtained through the fact that
Thus applying a similar argument as for
, we can show that
(12)
(12) Finally, we can conclude that
For the classical trapezoidal quadrature (CTQ), Theorem 3.1 claims that its order of convergence would be the same as the regularity of the integrand. For the boundary case, when , the order is 1.
3.2. Randomized trapezoidal rules for ![](//:0)
![](//:0)
For the randomized trapezoidal quadrature (Equation4(4)
(4) ), the proof follows a similar argument as in Theorem 4.2 [Citation8].
Theorem 3.2
Define for
for
with
and
. Then
and is an unbiased estimator of
, i.e.
. Moreover, it holds true that
(13)
(13) where
is a constant that depends only on p.
Proof.
First, due to we have
. Recall that
for each
. Then, it follows that
Hence
for
. To show
is unbiased, we need to examine each term in RHS of Equation (Equation4
(4)
(4) ) through spelling out the expectation and changing variable, i.e.
and
Summing these terms up gives that
is unbiased for
. Furthermore, if define the error term like
(14)
(14) then each summand is a mean-zero random variable, i.e.
Note that the summands are mutually independent due to the independence of
. In addition, it is easy to show
. Therefore,
is a
-martingale. Then applying the discrete version of the Burkholder–Davis–Gundy inequality leads to
(15)
(15) where in the second line we substitute the quadratic variation
. Due to symmetric property, it is easy to see we only need to handle the first term on the RHS of Equation (Equation15
(15)
(15) ). Note that
(16)
(16) Then we have that
When p = 2, the term on the right-hand side above can be directly bounded by
(17)
(17) where
. For p>2, we may apply discrete Hölder inequality and get
(18)
(18) Now, we have shown Bound (Equation13
(13)
(13) ) when
. For Bound (Equation13
(13)
(13) ) under
, we first note that Equation (Equation6
(6)
(6) ) remains true if replacing
by
and
by
, i.e.
(19)
(19) Thus, the second line of Equation (Equation15
(15)
(15) ) can be further split as the follows:
Similar as in the proof of Theorem 3.1, we introduce
defined in Equation (Equation7
(7)
(7) ) and
(20)
(20) As in the proof of Theorem 3.1,
can be handled through the equivalent form Equation (Equation9
(9)
(9) ) and
can be treated in a similar way as Equation (Equation11
(11)
(11) ) by replacing
by
and
by
in the inner integral of Equation (Equation11
(11)
(11) ), i.e.
(21)
(21) Thus
where the first term on the right-hand side from Equation (Equation9
(9)
(9) ) and the second term is due to Equation (Equation21
(21)
(21) ). Let us now deal with the first term, the second term can be handled in the same way. Following a similar argument in (Equation16
(16)
(16) ), we have that
where we apply Hölder's inequality in Line 4 and 5. Similarly as in (Equation17
(17)
(17) ), for p = 2 we have that
Applying discrete Hölder inequality for p>2 as in (Equation18
(18)
(18) ), we have that
Altogether we have achieved Bound (Equation13
(13)
(13) ).
For a fixed integrand, the randomized quadrature rule (RTQ) improves the order of convergence by through incorporating randomness compared to Theorem 3.1. One may also be interested in the almost sure convergence of RTQ. Indeed, the argument from [Citation8, Theorem 3.2] can be directly adapted here:
Theorem 3.3
Almost sure convergence
Assume that conditions from Theorem 3.2 are satisfied. Let be an arbitrary sequence of step sizes with
. Then, there exists a nonnegative random variable
and a measurable set
with
such that for all
and
, then for every
there exist a nonnegative random variable
and a measurable set
with
such that such that for all
and
we have
(22)
(22) where
, i.e. the integer part of
.
Theorem 3.3 ensures that RTQ can achieve a slightly better order of pathwise convergence in the almost sure sense compared to CTQ when stepsize is adequately small.
4. Numerical experiments
In this section, we assessed the proposed method via different experiments. For simplicity, we fix T = 1.
4.1. Example 1
Consider the function:
(23)
(23) where
,
, for all
(Sobolev's inequality in [Citation1]). The curves of
with different values in γ can be found in Figure . The true solution was easily obtained as
. The numerical approximations were calculated for both kinds of trapezoidal quadrature with step sizes
and then compared to the true solution for errors. For RTQ, we computed errors in
norm via Monte Carlo method and also computed pathwise error, i.e.error from one realization.
The results of our simulations are shown in Figure and Table . Across all different values of γ, RTQ gave the higher order of convergence compared to CTQ. When γ increased from to
, the order of convergence for RTQ increased eventually to a number very close to 2.5. Note that the order of convergence for CTQ are not beyond 2 for all γ values. All the performances were superior to theoretical order of convergences shown in Theorems 3.1 and 3.2. We also examined the computational efficiency of both methods (lower right in Figure ). Though incorporating randomness increased computational expense, RTQ quickly offsetted its cost with its higher accuracy.
Figure 2. Error plots for approximating via variants of trapezoidal rule under different choices for γ (upper left:
; upper right:
; lower left:
) and time cost plot for
(lower right).
![Figure 2. Error plots for approximating I[gγ] via variants of trapezoidal rule under different choices for γ (upper left: γ=54; upper right: γ=32; lower left: γ=74) and time cost plot for γ=32 (lower right).](/cms/asset/15e148d4-40b0-4bbb-b91f-473b9d502f55/gcom_a_1929194_f0002_oc.jpg)
Table 1. Order of convergences for simulating .
4.2. Example 2
Consider the function:
(24)
(24) where
is a realization of standard Brownian motion (BM) (cf. Section 3.1 in [Citation6]). It is well known that
for arbitrary small
, therefore
for p>1. Figure illustrates how one BM path looks like and the curve of its
.We are interested in approximating
.
Due to the nature of BM, it is not easy to obtain the exact value of . To approximating terms
, one simply applies the Euler method, i.e.
For CTQ, for a fixed stepsize
we have that
For RTQ, define the corresponding i.i.d. uniform distributed sequence is
, we have a similar expression:
(25)
(25) where the last term can be further expanded as
Note that to deduce the third line of Equation (Equation25
(25)
(25) ), we make use of CTQ rather than the Euler method. The reason for this is that using the Euler method will result in the same expression as
. It is easy to see the difference between expressions for CTQ and RTQ lies in the last two terms of the equation above.
To compute the reference solution, we first sampled a BM path with a small stepsize . Then, we generated an i.i.d. standard uniformly distributed sequence
, and sampled
, which is determined by property of Brownian bridge (cf. Section 3.1 in [Citation6]), i.e.
where
is normal distribution with mean μ and variance
, and
for all j. The reference solution was thus computed via CTQ on grid points consisting of
as well as these intermediate
.
The reason for including randomness at this early stage is that this allows an easier sampling procedure for on coarser grids of stepsize h. For instance, if
and consider interval
, then
and
are in the same interval. Thus
can be determined from
where
is the indicator function,
, i.e. a discrete uniform distribution on the integers 0 and 1.
The numerical approximations were calculated for both trapezoidal quadratures with larger step sizes and then compared to the reference solution for errors. The results of our simulations are shown in Figure . RTQ gave the higher order of pathwise convergence compared to CTQ and gained a minor advantage in absolute error. Both the performances are consistent with the theoretical order of convergences shown in Theorems 3.1 and 3.3. We, in the meantime, examined the computational efficiency of both methods. Due to additional terms involved for RTQ in Equation (Equation25
(25)
(25) ), its time cost roughly doubled that of CTQ at the same stepsize. In this case, unfortunately, the slight odds of RTQ in accuracy did not offset its cost.
Disclosure statement
No potential conflict of interest was reported by the author(s).
Additional information
Funding
References
- R.A. Adams and J.J. Fournier, Sobolev Spaces, Elsevier, Amsterdam, 2003.
- R.B. Ash and C.A. Doleans-Dade, Probability and Measure Theory, Academic Press, Burlington, MA, 2000.
- D. Cruz-Uribe and C.J. Neugebauer, Sharp error bounds for the trapezoidal rule and Simpson's rule, J. Inequal. Pure Appl. Math. 3(4) (2002), pp. 1–222.
- P.J. Davis and P. Rabinowitz, Methods of Numerical Integration, Courier Corporation, Mineola, NY, 2007.
- M. Eisenmann and R. Kruse, Two quadrature rules for stochastic Ito-integrals with fractional Sobolev regularity, Commun. Math. Sci. 16(8) (2018), pp. 2125–2146.
- P. Glasserman, Monte Carlo Methods in Financial Engineering, Springer Science & Business Media, New York, 2013.
- E.T. Goodwin, The evaluation of integrals of the form ∫−∞∞f(x)exp(−x)dx, Proc. Camb. Phil. Soc. 45 (1949), pp. 241–245.
- R. Kruse and Y. Wu, Error analysis of randomized Runge–Kutta methods for differential equations with time-irregular coefficients, Comput. Methods Appl. Math. 17(3) (2017), pp. 479–498.
- C. Schwartz, Numerical integration of analytic functions, J. Comput. Phys. 4(1) (1969), pp. 19–29.
- F. Stenger, Integration formulae based on the trapezoidal formula, IMA J. Appl. Math. 12(1) (1973), pp. 103–114.