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.     

Zur Existenz optimaler Quadraturformeln mit freien Knoten bei Integration analytischer Funktionen

Summary In the present paper we discuss the optimal quadrature rules for integration with positive continuous weight function in Hardy space H₂ of functions analytic in a circle of the complex plane. The new representations of the optimal weights and the norm of the error functional as functions of the nodes are obtained. On this basis we give an elementary proof for the existence of the optimal quadrature formula with free nodes.     

The best quadrature formula based on Hermite information for the class <Emphasis Type="Italic">KW</Emphasis><Superscript>2</Superscript> [<Emphasis Type="Italic">a,b</Emphasis>]

The best quadrature formula has been found in the following sense: for a function whose norm of the second derivative is bounded by a given constant and the best quadrature formula for the approximate evaluation of integration of that function can minimize the worst possible error if the values of the function and its derivative at certain nodes are known. The best interpolation formula used to get the quadrature formula above is also found. Moreover, we compare the best quadrature formula with the open compound corrected trapezoidal formula by theoretical analysis and stochastic experiments.     

Computing the Approximation Error for Neural Networks with Weights Varying on Fixed Directions

We obtain a sharp lower bound estimate for the approximation error of a continuous function by single hidden layer neural networks with a continuous activation function and weights varying on two fixed directions. We show that for a certain class of activation functions this lower bound estimate turns into equality. The obtained result provides us with a method for direct computation of the approximation error. As an application, we give a formula, which can be used to compute instantly the approximation error for a class of functions having second order partial derivatives.     

The error and guaranteed accuracy of cubature formulas in multidimensional periodic Sobolev spaces

We give an upper bound for the deviation of the norm of a perturbed error from the norm of the original error of a cubature formula in a multidimensional bounded domain. The deviation arises as a result of the joint influence on the computations of small variations of the weights of a cubature formula and rounding in the subsequent calculations of the cubature sum in the given standards (formats) of approximation to real numbers. We estimate the practical error of a cubature formula acting on an arbitrary function from the unit ball of a normed space of integrands. The resulting estimates are applied to studying the practical error of cubature formulas in the case of integrands in Sobolev spaces on a multidimensional cube. The norm of the error in the dual space of the Sobolev class is represented as a positive definite quadratic form in the weights of the cubature formula. We estimate the practical error for cubature formulas constructed as the direct product of quadrature formulas of rectangles along the edges of the unit cube. The weights of this direct product are positive.     

On the optimal approximation of bounded linear functionals in Hilbert spaces with inner product invariant in rotation or translation

Optimal numerical approximation of bounded linear functionals by weighted sums in Hilbert spaces of functions defined in a domain B ? $\text{C}$ or B ? $\text{R}$^m, invariant in rotation or translation (e.g. circle, circular annulus, ball, spherical shell, strip of the complex plane) and equipped with inner product invariant in rotation or translation are considered. The weights and error functional norms for optimal approximate rules based on nodes located angle-equidistant on concentric spheres or circles of B, for B invariant in rotation, and on nodes located equispaced on in B lying line, for B invariant in translation, are explicitly given in terms of the kernel function of the Hilbert space. A number of concrete Hilbert spaces satisfying the required conditions are listed.     

A fast algorithm for Gaussian type quadrature formulae with mixed boundary conditions and some lumped mass spectral approximations

After studying Gaussian type quadrature formulae with mixed boundary conditions, we suggest a fast algorithm for computing their nodes and weights. It is shown that the latter are computed in the same manner as in the theory of the classical Gauss quadrature formulae. In fact, all nodes and weights are again computed as eigenvalues and eigenvectors of a real symmetric tridiagonal matrix. Hence, we can adapt existing procedures for generating such quadrature formulae. Comparative results with various methods now in use are given. In the second part of this paper, new algorithms for spectral approximations for second-order elliptic problems are derived. The key to the efficiency of our algorithms is to find an appropriate spectral approximation by using the most accurate quadrature formula, which takes the boundary conditions into account in such a way that the resulting discrete system has a diagonal mass matrix. Hence, our algorithms can be used to introduce explicit resolutions for the time-dependent problems. This is the so-called lumped mass method. The performance of the approach is illustrated with several numerical examples in one and two space dimensions.

     

Optimal cubature formulas in a reflexive Banach space

Sequences of cubature formulas with a joint countable set of nodes are studied. Each cubature formula under consideration has only a finite number of nonzero weights. We call a sequence of such kind a multicubature formula. For a given reflexive Banach space it is shown that there is a unique optimal multicubature formula and the sequence of the norm of optimal error functionals is monotonically decreasing to 0 as the number of the formula nodes tends to infinity.     

Asymptotic properties of minimum norm and optimal quadratures

Summary This paper contains three types of asymptotic results for certain quadratures applied to a Hilbert space of analytic functions. These results concern the following: bounds on the norm of a certain error functional; the convergence of the weights and nodes of a minimum norm quadrature to the weights and nodes of the corresponding Gaussian quadrature; and the convergence of optimal quadratures.The research reported in this document was supported by the Office of Naval Research, Contract Nonr 562(36) to Brown University and by the National Science Foundation, Grant GP 5906 to the University of Utah.On leave during the 1966–67 academic year at the Division of Applied Mathematics, Brown University, Providence, Rhode Island.     

Almost sure exponential behaviour for a parabolic SPDE on a manifold

We derive an upper bound on the large-time exponential behavior of the solution to a stochastic partial differential equation on a compact manifold with multiplicative noise potential. The potential is a random field that is white-noise in time, and Hölder-continuous in space. The stochastic PDE is interpreted in its evolution (semigroup) sense. A Feynman–Kac formula is derived for the solution, which is an expectation of an exponential functional of Brownian paths on the manifold. The main analytic technique is to discretize the Brownian paths, replacing them by piecewise-constant paths. The error committed by this replacement is controlled using Gaussian regularity estimates; these are also invoked to calculate the exponential rate of increase for the discretized Feynman–Kac formula. The error is proved to be negligible if the diffusion coefficient in the stochastic PDE is small enough. The main result extends a bound of Carmona and Viens (Stochast. Stochast. Rep. 62 (3–4) (1998) 251) beyond flat space to the case of a manifold.     

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.     

Efficient sample sizes in stochastic nonlinear programming

We consider a class of stochastic nonlinear programs for which an approximation to a locally optimal solution is specified in terms of a fractional reduction of the initial cost error. We show that such an approximate solution can be found by approximately solving a sequence of sample average approximations. The key issue in this approach is the determination of the required sequence of sample average approximations as well as the number of iterations to be carried out on each sample average approximation in this sequence. We show that one can express this requirement as an idealized optimization problem whose cost function is the computing work required to obtain the required error reduction. The specification of this idealized optimization problem requires the exact knowledge of a few problems and algorithm parameters. Since the exact values of these parameters are not known, we use estimates, which can be updated as the computation progresses. We illustrate our approach using two numerical examples from structural engineering design.     

Polynomial approximation on the sphere using scattered data

We consider the problem of approximately reconstructing a function f defined on the surface of the unit sphere in the Euclidean space ℝ^{q +1} by using samples of f at scattered sites. A central role is played by the construction of a new operator for polynomial approximation, which is a uniformly bounded quasi‐projection in the de la Vallée Poussin style, i.e. it reproduces spherical polynomials up to a certain degree and has uniformly bounded L^p operator norm for 1 ≤ p ≤ ∞. Using certain positive quadrature rules for scattered sites due to Mhaskar, Narcowich and Ward, we discretize this operator obtaining a polynomial approximation of the target function which can be computed from scattered data and provides the same approximation degree of the best polynomial approximation. To establish the error estimates we use Marcinkiewicz–Zygmund inequalities, which we derive from our continuous approximating operator. We give concrete bounds for all constants in the Marcinkiewicz–Zygmund inequalities as well as in the error estimates. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Multivariate approximation in the worst case setting over reproducing kernel Hilbert spaces

We study the worst case setting for approximation of d variate functions from a general reproducing kernel Hilbert space with the error measured in the L_∞ norm. We mainly consider algorithms that use n arbitrary continuous linear functionals. We look for algorithms with the minimal worst case errors and for their rates of convergence as n goes to infinity. Algorithms using n function values will be analyzed in a forthcoming paper.We show that the L_∞ approximation problem in the worst case setting is related to the weighted L₂ approximation problem in the average case setting with respect to a zero-mean Gaussian stochastic process whose covariance function is the same as the reproducing kernel of the Hilbert space. This relation enables us to find optimal algorithms and their rates of convergence for the weighted Korobov space with an arbitrary smoothness parameter α>1, and for the weighted Sobolev space whose reproducing kernel corresponds to the Wiener sheet measure. The optimal convergence rates are n^-(α-1)/2 and n^-1/2, respectively.We also study tractability of L_∞ approximation for the absolute and normalized error criteria, i.e., how the minimal worst case errors depend on the number of variables, d, especially when d is arbitrarily large. We provide necessary and sufficient conditions on tractability of L_∞ approximation in terms of tractability conditions of the weighted L₂ approximation in the average case setting. In particular, tractability holds in weighted Korobov and Sobolev spaces only for weights tending sufficiently fast to zero and does not hold for the classical unweighted spaces.     

The error norm of Gauss-Lobatto quadrature formulae for weight functions of Bernstein-Szegö type

Summary In certain spaces of analytic functions the error term of the Gauss-Lobatto quadrature formula relative to a (nonnegative) weight function is a continuous linear functional. Here we compute the norm of the error functional for the Bernstein-Szegö weight functions consisting of any of the four Chebyshev weights divided by an arbitrary quadratic polynomial that remains positive on [–1, 1]. The norm can subsequently be used to derive bounds for the error functional. The efficiency of these bounds is illustrated with some numerical examples.Work supported in part by a grant from the Research Council of the Graduate School, University of Missouri-Columbia.     

COMPUTATIONAL COMPLEXITY IN WORST,STOCHASTIC AND AVERAGE CASE SETTING ON FUNCTIONAL APPROXIMATION PROBLEM OF MULTIVARIATE

The order of computational complexity of all bounded linear functional ap proximation problem is determined for the generalized Sobolev class W_p~(?)(Id), Nikolskii class H|∞~k(Id) in the worst (deterministic), stochastic and average case setting, from which it is concluded that the bounded linear functional approximation problem for the classes W_p~(?)(Id) and H_∞~k(Id) is intractable in worst case setting, but is tractable with respect to stochastic and average case setting.     

The exponential integrator scheme for stochastic partial differential equations: Pathwise error bounds

We present an error analysis for the pathwise approximation of a general semilinear stochastic evolution equation in d dimensions. We discretise in space by a Galerkin method and in time by using a stochastic exponential integrator. We show that for spatially regular (smooth) noise the number of nodes needed for the noise can be reduced and that the rate of convergence degrades as the regularity of the noise reduces (and the noise becomes rougher).     

An infinite horizon stochastic maximum principle for discounted control problem with Lipschitz coefficients

In the present work, a stochastic maximum principle for discounted control of a certain class of degenerate diffusion processes with global Lipschitz coefficient is investigated. The value function is given by a discounted performance functional, leading to a stochastic maximum principle of semi-couple forward–backward stochastic differential equation with non-smooth coefficients. The proof is based on the approximation of the Lipschitz coefficients by smooth ones and the approximation of the infinite horizon adjoint process.     

Approximation in rough native spaces by shifts of smooth kernels on spheres

Within the conventional framework of a native space structure, a smooth kernel generates a small native space, and “radial basis functions” stemming from the smooth kernel are intended to approximate only functions from this small native space. Therefore their approximation power is quite limited. Recently, Narcowich et al. (J. Approx. Theory 114 (2002) 70), and Narcowich and Ward (SIAM J. Math. Anal., to appear), respectively, have studied two approaches that have led to the empowerment of smooth radial basis functions in a larger native space. In the approach of [NW], the radial basis function interpolates the target function at some scattered (prescribed) points. In both approaches, approximation power of the smooth radial basis functions is achieved by utilizing spherical polynomials of a (possibly) large degree to form an intermediate approximation between the radial basis approximation and the target function. In this paper, we take a new approach. We embed the smooth radial basis functions in a larger native space generated by a less smooth kernel, and use them to approximate functions from the larger native space. Among other results, we characterize the best approximant with respect to the metric of the larger native space to be the radial basis function that interpolates the target function on a set of finite scattered points after the action of a certain multiplier operator. We also establish the error bounds between the best approximant and the target function.     

Weak convergence of finite element approximations of linear stochastic evolution equations with additive noise II. Fully discrete schemes

We present an abstract framework for analyzing the weak error of fully discrete approximation schemes for linear evolution equations driven by additive Gaussian noise. First, an abstract representation formula is derived for sufficiently smooth test functions. The formula is then applied to the wave equation, where the spatial approximation is done via the standard continuous finite element method and the time discretization via an I-stable rational approximation to the exponential function. It is found that the rate of weak convergence is twice that of strong convergence. Furthermore, in contrast to the parabolic case, higher order schemes in time, such as the Crank-Nicolson scheme, are worthwhile to use if the solution is not very regular. Finally we apply the theory to parabolic equations and detail a weak error estimate for the linearized Cahn-Hilliard-Cook equation as well as comment on the stochastic heat equation.