The number of lattice rules

A lattice rule is a quadrature rule for integration over ans-dimensional hypercube that employsN abscissas located on a lattice, chosen to conform to certain specifications. In this paper we determine the numberv _s(N) of distinctN-points-dimensional lattice rules. We show that, in general,

Computational aspects of Boolean cubature

Boolean methods of interpolation [1,4] have been applied to construct multivariate quadrature rules for periodic functions of Korobov classes which are comparable with lattice rules of numerical integration [6,7]. In particular, we introducedd-variate Boolean trapezoidal rules [3,4] andd-variate Boolean midpoint rules [2,4]. The basic tools for constructing Boolean midpoint rules are Boolean midpoint sums. It is the purpose of this paper to use a modification of these Boolean midpoint sums to compute Boolean trapezoidal rules in an efficient way.     

Moderate Degree Symmetric Quadrature Rules for the Triangle

A variant formulation of the moment fitting equations for theconstruction of D₃ (triangularly symmetric) quadrature rulesfor the triangle is derived. These equations are solved to produceweights and abscissas for quadrature rules of polynomial degreeup to 11 for the triangle, some of which require fewer functionevaluations than any presently available rule of the same polynomialdegree. Cytolic rules of degrees up to 9 are also derived.     

Higher-order Newton–Cotes rules with end corrections

We present higher-order quadrature rules with end corrections for general Newton–Cotes quadrature rules. The construction is based on the Euler–Maclaurin formula for the trapezoidal rule. We present examples with 6 well-known Newton–Cotes quadrature rules. We analyze modified end corrected quadrature rules, which consist on a simple modification of the Newton–Cotes quadratures with end corrections. Numerical tests and stability estimates show the superiority of the corrected rules based on the trapezoidal and the midpoint rules.     

Nonlinear Periodic Optimal Control: A Pseudospectral Fourier Approach

Abstract

A pseudospectral method for generating optimal trajectories of the class of periodic optimal control problems is proposed. The method consists of representing the solution of the periodic optimal control problem by an mth degree trigonometric interpolating polynomial, using Fourier nodes as grid points, and then discretizing the problem using the trapezoidal rule as the quadrature formula for smoothly differentiable periodic functions. The periodic optimal control problem is thereby transformed into an algebraic nonlinear programming problem. Due to its dynamic nature, the pseudospectral Fourier approach avoids many of the numerical difficulties typically encountered in solving standard periodic optimal control problems. An illustrative example is provided to demonstrate the applicability of the proposed method.     

Integral operators with Green's function type kernel

A variant of the Nyström method based on Simpson's rule is presented. This is designed to deal with integral operators with kernels k(s, t) that are not continuous along the diagonal s = t. A complete analysis is carried out, generalizations for other interpolatory quadrature rules are proposed; also a variant using Gaussian quadrature is considered and examples are given.     

Quadrature rules for integrals of fuzzy-number-valued functions

In this paper, we introduce some quadrature rules for the Henstock integral of fuzzy-number-valued mappings by giving error bounds for mappings of bounded variation and of Lipschitz type. We also consider generalizations of classical quadrature rules, such as midpoint-type, trapezoidal and three-point-type quadrature. Finally, we study δ-fine quadrature rules and we present some numerical applications.     

Determination of the rank of an integration lattice

The continuing and widespread use of lattice rules for high-dimensional numerical quadrature is driving the development of a rich and detailed theory. Part of this theory is devoted to computer searches for rules, appropriate to particular situations. In some applications, one is interested in obtaining the (lattice) rank of a lattice rule Q(Λ) directly from the elements of a generator matrix B (possibly in upper triangular lattice form) of the corresponding dual lattice Λ^⊥. We treat this problem in detail, demonstrating the connections between this (lattice) rank and the conventional matrix rank deficiency of modulo p versions of B. AMS subject classification (2000) 65D30     

Numerical integration using sparse grids

We present new and review existing algorithms for the numerical integration of multivariate functions defined over d-dimensional cubes using several variants of the sparse grid method first introduced by Smolyak [49]. In this approach, multivariate quadrature formulas are constructed using combinations of tensor products of suitable one-dimensional formulas. The computing cost is almost independent of the dimension of the problem if the function under consideration has bounded mixed derivatives. We suggest the usage of extended Gauss (Patterson) quadrature formulas as the one‐dimensional basis of the construction and show their superiority in comparison to previously used sparse grid approaches based on the trapezoidal, Clenshaw–Curtis and Gauss rules in several numerical experiments and applications. For the computation of path integrals further improvements can be obtained by combining generalized Smolyak quadrature with the Brownian bridge construction. This revised version was published online in August 2006 with corrections to the Cover Date.     

On the Accuracy of Quadrature Laplace Transform Inversion and the Solution of State Space Equations

A quadrature formula is shown to be an approximation of thepower-series method of inverting Laplace transforms. This togetherwith the properties of the constants derived from a power-seriesexpansion of the Pad? approximation to exp (s) yield an importantupper limit on t which is quite sharp in determining the breakdownpoint up to and after which the approximation is accurate andinaccurate respectively. The solution of state space equationsusing the quadrature inversion formula is also discussed.     

Cubature formulas for function spaces with moderate smoothness

We construct simple algorithms for high-dimensional numerical integration of function classes with moderate smoothness. These classes consist of square-integrable functions over the d-dimensional unit cube whose coefficients with respect to certain multiwavelet expansions decay rapidly. Such a class contains discontinuous functions on the one hand and, for the right choice of parameters, the quite natural d-fold tensor product of a Sobolev space H^s[0,1] on the other hand.The algorithms are based on one-dimensional quadrature rules appropriate for the integration of the particular wavelets under consideration and on Smolyak's construction. We provide upper bounds for the worst-case error of our cubature rule in terms of the number of function calls. We additionally prove lower bounds showing that our method is optimal in dimension d=1 and almost optimal (up to logarithmic factors) in higher dimensions. We perform numerical tests which allow the comparison with other cubature methods.     

Randomized Smolyak algorithms based on digital sequences for multivariate integration

Gunther Leobacher ^{In this paper, we consider Smolyak algorithms based on quasi-MonteCarlo rules for high-dimensional numerical integration. Thequasi-Monte Carlo rules employed here use digital (t, , ß,, d)-sequences as quadrature points. We consider the worst-caseerror for multivariate integration in certain Sobolev spacesand show that our quadrature rules achieve the optimal rateof convergence. By randomizing the underlying digital sequences,we can also obtain a randomized Smolyak algorithm. The boundon the worst-case error holds also for the randomized algorithmin a statistical sense. Further, we also show that the randomizedalgorithm is unbiased and that the integration error can beapproximated as well.}     

On Free Planes in Lattice Ball Packings

This note, by studying the relations between the length of theshortest lattice vectors and the covering minima of a lattice,proves that for every d-dimensional packing lattice of ballsone can find a four-dimensional plane, parallel to a latticeplane, such that the plane meets none of the balls of the packing,provided that the dimension d is large enough. Nevertheless,for certain ball packing lattices, the highest dimension ofsuch ‘free planes’ is far from d.     

Component-by-Component Construction of Good Lattice Rules with a Composite Number of Points

We develop algorithms to construct rank-1 lattice rules in weighted Korobov spaces of periodic functions and shifted rank-1 lattice rules in weighted Sobolev spaces of non-periodic functions. Analyses are given which show that the rules so constructed achieve strong QMC tractability error bounds. Unlike earlier analyses, there is no assumption that n, the number of quadrature points, be a prime number. However, we do assume that there is an upper bound on the number of distinct prime factors of n. The generating vectors and shifts characterizing the rules are constructed ‘component-by-component,’ that is, the (d+1)th components of the generating vectors and shifts are obtained using one-dimensional searches, with the previous d components kept unchanged.     

Product Integration Rules at Clenshaw-Curtis and Related Points: A Robust Implementation

Product integration rules generalizing the Fej?r, Clenshaw-Curtis,and Filippi quadrature rules respectively are derived for integralswith trigonometric and hyperbolic weight factors. The Chebyshevmoments of the weight functions are found to be given by well-conditionedexpressions, in terms of hypergeometric functions ₀F₁. An a priori error estimator is discussed which is shown bothto avoid wasteful invocation of the integration rule and toincrease significantly the robustness of the automatic quadratureprocedure. Then, specializing to extended Clenshaw-Curtis (ECC) rules,three types of a posteriori error estimates are considered andthe existence of a great risk of their failure is demonstratedby large scale validation tests. An empirical error estimator,superseding them for slowly varying integrands, is found toresult in a spectacular increase in the output reliability. Finally, enhancements in the control of the interval subdivisionstrategy aiming at increasing code robustness is discussed.Comparison with the code DQAWO of QUADPACK, with about a hundredthousand solved integrals, is illustrative of the increasedrobustness and error estimate reliability of our computer codeimplementation of the ECC rules.     

Error bounds for rank 1 lattice quadrature rules modulo composites

Improved estimates are established regarding the accuracy which can be achieved by a suitable choice of generator in a single-generator lattice quadrature rule (as used in the method of good lattice points) in the general case wherem, the number of quadrature points, is not necessarily prime. The result obtained for the general case is asymptotically the same as the best currently-known result for the prime case. However, it is also shown that when these rules are applied to some customary test functions the mean error (over different rules with the same number of points) can be arbitrarily large compared to the corresponding mean value for rules with a comparable but prime value ofm. These mean values are of interest in relation to computerised searches for good generators.     

A nodal spline interpolant for the Gregory rule of even order

Summary The Gregory rule is a well-known example in numerical quadrature of a trapezoidal rule with endpoint corrections of a given order. In the literature, the methods of constructing the Gregory rule have, in contrast to Newton-Cotes quadrature,not been based on the integration of an interpolant. In this paper, after first characterizing an even-order Gregory interpolant by means of a generalized Lagrange interpolation operator, we proceed to explicitly construct such an interpolant by employing results from nodal spline interpolation, as established in recent work by the author and C.H. Rohwer. Nonoptimal order error estimates for the Gregory rule of even order are then easily obtained.     

The Superconvergence of the Composite Trapezoidal Rule for Hadamard Finite Part Integrals

The composite trapezoidal rule has been well studied and widely applied for numerical integrations and numerical solution of integral equations with smooth or weakly singular kernels. However, this quadrature rule has been less employed for Hadamard finite part integrals due to the fact that its global convergence rate for Hadamard finite part integrals with (p+1)-order singularity is p-order lower than that for the Riemann integrals in general. In this paper, we study the superconvergence of the composite trapezoidal rule for Hadamard finite part integrals with the second-order and the third-order singularity, respectively. We obtain superconvergence estimates at some special points and prove the uniqueness of the superconvergence points. Numerical experiments confirm our theoretical analysis and show that the composite trapezoidal rule is efficient for Hadamard finite part integrals by noting the superconvergence phenomenon. The work of this author was partially supported by the National Natural Science Foundation of China(No.10271019), a grant from the Research Grants Council of the Hong Kong Special Administractive Region, China (Project No. City 102204) and a grant from the Laboratory of Computational Physics The work of this author was supported in part by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. CityU 102204).     

Error expansions for multidimensional trapezoidal rules with Sidi transformations

In 1993, Sidi introduced a set of trigonometric transformations x = ψ(t) that improve the effectiveness of the one-dimensional trapezoidal quadrature rule for a finite interval. In this paper, we extend Sidi's approach to product multidimensional quadrature over [0,1] ^N . We establish the Euler–Maclaurin expansion for this rule, both in the case of a regular integrand function f(x) and in the cases when f(x) has homogeneous singularities confined to vertices. This revised version was published online in August 2006 with corrections to the Cover Date.