Commuting extensions and cubature formulae

Based on a novel point of view on 1-dimensional Gaussian quadrature, we present a new approach to d-dimensional cubature formulae. It is well known that the nodes of 1-dimensional Gaussian quadrature can be computed as eigenvalues of the so-called Jacobi matrix. The d-dimensional analog is that cubature nodes can be obtained from the eigenvalues of certain mutually commuting matrices. These are obtained by extending (adding rows and columns to) certain noncommuting matrices A₁,...,A_d, related to the coordinate operators x₁,...,x_d, in R^d. We prove a correspondence between cubature formulae and “commuting extensions” of A₁,...,A_d, satisfying a compatibility condition which, in appropriate coordinates, constrains certain blocks in the extended matrices to be zero. Thus, the problem of finding cubature formulae can be transformed to the problem of computing (and then simultaneously diagonalizing) commuting extensions. We give a general discussion of existence and of the expected size of commuting extensions and briefly describe our attempts at computing them.     

Quadrature Formulas for the Wiener Measure

We present a new method for the approximation of Wiener integrals and provide an explicit error bound for a class of smooth integrands. The purely deterministic algorithm is a sequence of quadrature formulas for the Wiener measure, where the knots are piecewise linear functions. It uses ideas of Smolyak, as well as the multiscale decomposition of the Wiener measure due to Lévy and Ciesielski. For the class we obtain n()max(1, 2⁻⁴), where n() is the number of integrand evaluations needed to guarantee an error at most for f .     

Construction of cubature formulae with preassigned nodes§

In this article, a technique for developing cubature rules with preassigned nodes is presented to avoid wasting of information in scientific computation. The corresponding constructive method of the cubature rule is also given. As an application of the rules, a cubature formula on disk, which was derived via the method of reproducing kernel in (Xu, Y., 2000, Constructing cubature formulae by the method of reproducing kernel. Numerische Mathematik, 85, 155–173), is reconstructed by using our technique. When the preassigned nodes are selected as the nodes of a cubature formula of lower degree, an embedded cubature formula can be easily obtained by the presented method. Furthermore, some examples are included in the article.     

Simple Fourth-Degree Cubature Formulae with Few Nodes over General Product Regions

A simple method is proposed for constructing fourth-degree cubature formulae over general product regions with no symmetric assumptions. The cubature formulae that are constructed contain at most $n^2+7n+3$ nodes and they are likely the first kind of fourth-degree cubature formulae with roughly $n^2$ nodes for non-symmetric integrations. Moreover, two special cases are given to reduce the number of nodes further. A theoretical upper bound for minimal number of cubature nodes is also obtained.     

Fast calculation of coefficients in the Smolyak algorithm

For many numerical problems involving smooth multivariate functions on d-cubes, the so-called Smolyak algorithm (or Boolean method, sparse grid method, etc.) has proved to be very useful. The final form of the algorithm (see equation (12) below) requires functional evaluation as well as the computation of coefficients. The latter can be done in different ways that may have considerable influence on the total cost of the algorithm. In this paper, we try to diminish this influence as far as possible. For example, we present an algorithm for the integration problem that reduces the time for the calculation and exposition of the coefficients in such a way that for increasing dimension, this time is small compared to dn, where n is the number of involved function values.     

Optimal addition of knots to cubature formulae for planar regions

Summary A method is described to add knots to a cubature formula of degree 2k–1 for an integral over a symmetric region, to obtain a cubature formula of degree 2k+1. This method is used to construct cubature formulae for the square, the circle, the hexagon and the entire plane.     

On the Smolyak cubature error for analytic functions

We consider Smolyak's construction for the numerical integration over the d‐dimensional unit cube. The underlying class of integrands is a tensor product space consisting of functions that are analytic in the Cartesian product of ellipses. The Kronrod–Patterson quadrature formulae are proposed as the corresponding basic sequence and this choice is compared with Clenshaw–Curtis quadrature formulae. First, error bounds are derived for the one‐dimensional case, which lead by a recursion formula to error bounds for higher dimensional integration. The applicability of these bounds is shown by examples from frequently used test packages. Finally, numerical experiments are reported. This revised version was published online in June 2006 with corrections to the Cover Date.     

Errors, condition numbers, and guaranteed accuracy of higher-dimensional spherical cubatures

We give upper bounds for the deviation of the norm of a perturbed error functional from the norm of the original error of a higher-dimensional spherical cubature formula. The deviation arises as a result of the combined influence on the computation of small variations of the weights of the cubature formula and rounding for the subsequent calculation of the cubature sum in the given standards of approximation to real numbers. We estimate the practical error of the cubature formula for its action on an arbitrary function in the unit ball of the normed space of integrands. The resulting estimates are applied to studying the practical error of spherical cubature formulas in the case of integrands in Sobolev-type spaces on the higher-dimensional unit sphere. We represent the norm of the error functional in the dual space of the Sobolev class as a positive definite quadratic form in the weights of the cubature formula. We estimate the practical error for spherical cubature formulas, each of which is constructed as the direct product of Gauss’s quadrature formula along the meridian of the sphere and of the rectangle quadrature formula along the equator. The weights of this direct product with 2m ² nodes are positive. The formula itself is exact at all spherical harmonics up to order 2m ? 1.     

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.     

On rational cuspidal curves

Let be a rational curve of degree d which has only one analytic branch at each point. Denote by m the maximal multiplicity of singularities of C. It is proven in [MS] that . We show that where is the square of the “golden section”. We also construct examples which show that this estimate is asymptotically sharp. When , we show that and this estimate is sharp. The main tool used here, is the logarithmic version of the Bogomolov-Miyaoka-Yau inequality. For curves as above we give an interpretation of this inequality in terms of the number of parameters describing curves of a given degree and the number of conditions imposed by singularity types. Received: 11 February 2000 / Published online: 8 November 2002 RID="*" ID="*" Partially supported by Grants RFFI-96-01-01218 and DGICYT SAB95-0502     

Orthogonal polynomials and cubature formulae on balls,simplices, and spheres

We report on recent developments on orthogonal polynomials and cubature formulae on the unit ball B^d, the standard simplex T^d, and the unit sphere S^d. The main result shows that orthogonal structures and cubature formulae for these three regions are closely related. This provides a way to study the structure of orthogonal polynomials; for example, it allows us to use the theory of h-harmonics to study orthogonal polynomials on B^d and on T^d. It also provides a way to construct new cubature formulae on these regions.     

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.     

Error estimates for interpolatory quadrature formulae

Summary In this paper we study the remainder of interpolatory quadrature formulae. For this purpose we develop a simple but quite general comparison technique for linear functionals. Applied to quadrature formulae it allows to eliminate one of the nodes and to estimate the remainder of the old formula in terms of the new one. By repeated application we may compare with quadrature formulae having only a few nodes left or even no nodes at all. With the help of this method we obtain asymptotically best possible error bounds for the Clenshaw-Curtis quadrature and other Pólya type formulae.Our comparison technique can also be applied to the problem of definiteness, i.e. the question whether the remainderR[f] of a formula of orderm can be represented asc·f ^(m)(). By successive elimination of nodes we obtain a sequence of sufficient criteria for definiteness including all the criteria known to us as special cases.Finally we ask for good and worst quadrature formulae within certain classes. We shall see that amongst all quadrature formulae with positive coefficients and fixed orderm the Gauss type formulae are worst. Interpreted in terms of Peano kernels our theorem yields results on monosplines which may be of interest in themselves.     

Spherical cubature formulas in Sobolev spaces

We study sequences of cubature formulas on the unit sphere in a multidimensional Euclidean space. The grids for the cubature formulas under consideration embed in each other consecutively, forming in the limit a dense subset on the initial sphere. As the domain of cubature formulas, i.e. as the class of integrands, we take spherical Sobolev spaces. These spaces may have fractional smoothness. We prove that, among all possible spherical cubature formulas with given grid, there exists and is unique a formula with the least norm of the error, an optimal formula. The weights of the optimal cubature formula are shown to be solutions to a special nondegenerate system of linear equations. We prove that the errors of cubature formulas tend to zero as the number of nodes grows indefinitely.     

On cubature formulae of degree 4k+1 attaining Möller's lower bound for integrals with circular symmetry

Summary The structure of cubature formulae of degree 4k+1 whose number of nodes is equal to Möller's lower bound is investigated for integrals with circular symmetry. A simple criterion is derived for the existence of such formulae. It shows that fork=1 Möller's lower bound can always be attained with Radon's formulae. It also allows to prove that for several integrals with circular symmetry and several values ofk>1, Möller's lower bound cannot be attained.     

Expansions over a Simplex of Real Functions by Means of Bernoulli Polynomials

In [1] there is an expansion in Bernoulli polynomials for sufficiently smooth real functions in an interval [a,b]R that has useful applications to numerical analysis. An analogous result in a 2-dimensional context is derived in [2] in the case of rectangle. In this note we generalize the above-mentioned one-dimensional expansion to the case of C ^m -functions on a 2-dimensional simplex; a method to generalize the expansion on an N-dimensional simplex is also discussed. This new expansion is applied to find new cubature formulas for 2-dimensional simplex.     

Cubature Formula and Interpolation on the Cubic Domain

Several cubature formulas on the cubic domains are derived using the dis-crete Fourier analysis associated with lattice tiling, as developed in [10]. The main results consist of a new derivation of the Gaussian type cubature for the product Cheby-shev weight functions and associated interpolation polynomials on [-1,1]2, as well as new results on [-1,1]3. In particular, compact formulas for the fundamental interpo-lation polynomials are derived, based on n3/4 + (n2) nodes of a cubature formula on [-1,1]3.     

Lower semicontinuity of quasi-convex integrals in BV

Some boundedness properties for an extension operator are proved and used together with techniques of Maly [24], Meyers [29], Fonseca and Müller [13] and Fonseca and Marcellini [12] to obtain lower semicontinuity results in BV for quasiconvex integrals of super-linear growth. Received January 25, 1997 / Accepted October 3, 1997     

Edgewise Subdivision of a Simplex

In this paper we introduce the abacus model of a simplex and use it to subdivide a d -simplex into k ^d d -simplices all of the same volume and shape characteristics. The construction is an extension of the subdivision method of Freudenthal [3] and has been used by Goodman and Peters [4] to design smooth manifolds. Received June 24, 1999, and in revised form January 13, 2000. Online publication August\/ 11, 2000.     

Integral formulae on hypersurfaces in Riemannian manifolds

The coefficients of the complete set of n fundamental forms of a hypersuface V_n−1 imbedded in an n-dimensional Riemannian space V_n, as recently introduced[(5)], are used to construct certain tensor fields over V_n−1 which display some remarkable features. In particular, the divergences of these tensor fields can be expressed very simply in terms of polynomials involving the curvature tensor of V_n, the coefficients of the n fundamental forms, and the r^th curvatures of V_n−1. As the result of an application of the generalized divergence theorem of Gauss to these relations a set of integral formulae on V_n−1 is obtained. The integrands of these integral formulae can be expressed very simply in terms of the n fundamental forms of V_n−1. By successive specialization it is indicated how known integral theorems([2], [3], [6], [7], [8]) can be derived as particular cases, which is possible partly as a result of the fact that the polynomial referred to above vanishes identically whenever V_n is a space of constant curvature. This research was supported by the National Research Council of Canada. Entrata in Redazione il 21 agosto 1970.