Empirically estimating error of integration by quasi-Monte Carlo method

The possibility of applying probability-theoretical methods to a deterministic procedure for estimating the error of evaluating multiple integrals by the quasi-Monte Carlo method is considered. The existing methods for estimating this error are nonconstructive. The well-known Koksma-Hlawka inequality contains the variations of the integrand as a constant. The problem of calculating these variations is more difficult than the initial one. Since the quasi-Monte Carlo method uses the arithmetic mean value of the integrand as an estimate of the integral, it is natural to expect that the distribution (in the number-theoretic sense) of the remainder in the approximate integration procedure obeys the normal law. However, there is an additional difficulty that, from the probability-theoretic point of view, quasi-random points are dependent, and numerically estimating the second moment of the remainder is thereby impeded. An approach to estimating the second moment of the error is proposed, which is based on the results of the theory of random cubature formulas obtained by the authors. Numerical examples are given, which show that the proposed error estimation method has great potential.     

Generalized von Neumann–Kakutani transformation and random-start scrambled Halton sequences

It is a well-known fact that the Halton sequence exhibits poor uniformity in high dimensions. Starting with Braaten and Weller in 1979, several researchers introduced permutations to scramble the digits of the van der Corput sequences that make up the Halton sequence, in order to improve the uniformity of the Halton sequence. These sequences are called scrambled Halton, or generalized Halton sequences. Another significant result on the Halton sequence was the fact that it could be represented as the orbit of the von Neumann–Kakutani transformation, as observed by Lambert in 1982. In this paper, I will show that a scrambled Halton sequence can be represented as the orbit of an appropriately generalized von Neumann–Kakutani transformation. A practical implication of this result is that it gives a new family of randomized quasi-Monte Carlo sequences: random-start scrambled Halton sequences. This work generalizes random-start Halton sequences of Wang and Hickernell. Numerical results show that random-start scrambled Halton sequences can improve on the sample variance of random-start Halton sequences by factors as high as 7000.     

Best cubature formulas for some classes of functions of many variables

The problem of minimizing the error in the cubature formula for a given class of functions is considered. For cubature formulas with a lattice arrangement of points this problems is solved exactly for a wide class of functions of m variables.Basic contents of this paper presented with proofs at the Seminar on Theory of Functions at Dnepropetrovsk State University, December, 1965.Translated from Matematicheskie Zametki, Vol. 3, No. 5, pp. 565–576, May, 1968.     

Interpolation and cubature approximations and analysis for a class of wideband integrals on the sphere

We propose, analyze, and implement interpolatory approximations and Filon-type cubature for efficient and accurate evaluation of a class of wideband generalized Fourier integrals on the sphere. The analysis includes derivation of (i) optimal order Sobolev norm error estimates for an explicit discrete Fourier transform type interpolatory approximation of spherical functions; and (ii) a wavenumber explicit error estimate of the order $\mathcal {O}(\kappa ^{-\ell } N^{-r_{\ell }})$ , for $\ell = 0, 1, 2$ , where $\kappa $ is the wavenumber, $2N^2$ is the number of interpolation/cubature points on the sphere and $r_{\ell }$ depends on the smoothness of the integrand. Consequently, the cubature is robust for wideband (from very low to very high) frequencies and very efficient for highly-oscillatory integrals because the quality of the high-order approximation (with respect to quadrature points) is further improved as the wavenumber increases. This property is a marked advantage compared to standard cubature that require at least ten points per wavelength per dimension and methods for which asymptotic convergence is known only with respect to the wavenumber subject to stable of computation of quadrature weights. Numerical results in this article demonstrate the optimal order accuracy of the interpolatory approximations and the wideband cubature.     

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.     

拟蒙特卡罗模拟方法在金融计算中的应用研究

在本文中我们展示了低差异序列的一些特点,利用拟蒙特卡罗模拟方法中的Halton、Faure、Sobol序列来对期权进行数值定价分析,数值实验结果表明:在低维数的条件下Hal- ton、Faure、Sobol序列比(伪)蒙特卡罗模拟方法好,在高维数的条件下,Halton序列比较敏感,Faure、Sobol序列比其它方法表现好.     

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 quadrature and cubature formulas for a class of multiple singular integrals

We consider the problem of conditions for the existence of multiple singular integrals of a certain class at inner and boundary points of a domain. We obtain the quadrature and cubature formulas for calculating multiple singular integrals and present the corresponding estimates for the formulas.     

Nontensorial Clenshaw–Curtis cubature

We extend Clenshaw–Curtis quadrature to the square in a nontensorial way, by using Sloan’s hyperinterpolation theory and two families of points recently studied in the framework of bivariate (hyper)interpolation, namely the Morrow–Patterson–Xu points and the Padua points. The construction is an application of a general approach to product-type cubature, where we prove also a relevant stability theorem. The resulting cubature formulas turn out to be competitive on nonentire integrands with tensor-product Clenshaw–Curtis and Gauss–Legendre formulas, and even with the few known minimal formulas.     

Banach空间中几乎渐近非扩张型映象的不动点的迭代逼近

在Banach空间中引入了一类新的几乎渐近非扩张型映象,概括了Banach空间中若干熟知的非线性的Lipschitz映象类与非Lipschitz映象类成特例;例如,熟知的非扩张映象类,渐近非扩张映象类与渐近非扩张型映象类.考虑了用于逼近几乎渐近非扩张型映象不动点的带误差的修改了的Ishikawa迭代序列的收敛性问题.关于Banach空间范数的S.S.Chang的不等式与H.K.Xu的不等式皆被用于做精确不动点与近似不动点间的误差估计.而且,张石生教授用于做带误差的修改了的Ishikawa迭代序列收敛性分析的方法(应用数学和力学,2001,22(1):23-31)被推广到几乎渐近非扩张型映象的情况.给出了用于求一致凸Banach空间中几乎渐近非扩张型映象不动点的带误差的修改了的Ishikawa迭代序列的新的收敛判据.并且,由该判据,立即得到了此类映象的带误差的修改了的Mann迭代序列的新的收敛判据.上述结果统一、改进与推广了张石生教授关于用带误差的修改了的Ishikawa与Mann迭代序列来逼近渐近非扩张型映象不动点方面的结果.     

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.     

Quasi-random Simulation of Linear Kinetic Equations

We study the improvement achieved by using quasi-random sequences in place of pseudo-random numbers for solving linear spatially homogeneous kinetic equations. Particles are sampled from the initial distribution. Time is discretized and quasi-random numbers are used to move the particles in the velocity space. Quasi-random points are not blindly used in place of pseudo-random numbers: at each time step, the number order of the particles is scrambled according to their velocities. Convergence of the method is proved. Numerical results are presented for a sample problem in dimensions 1, 2 and 3. We show that by using quasi-random sequences in place of pseudo-random points, we are able to obtain reduced errors for the same number of particles.     

拟蒙特卡罗法在亚洲期权定价中的应用

亚洲期权是场外交易中几种最受欢迎的新型期权之一,但它的价格却没有解析表达式,到目前为止,亚洲期权的定价仍是个公开问题.本文采用拟蒙特卡罗法中的Halton序列来估计它的价格,数值结果表明当观察点的个数N13时,它比蒙特卡罗法要好.本文还利用MATLAB程序生成了随机Halton序列,并将它与控制变量法结合起来估计亚洲期权的价格,估计值标准差的比较表明它在大多情况下比相应的蒙特卡罗法的估计效果要好.     

Boundary layer approximate approximations and cubature of potentials in domains

In this article we present a new approach to the computation of volume potentials over bounded domains, which is based on the quasi‐interpolation of the density by almost locally supported basis functions for which the corresponding volume potentials are known. The quasi‐interpolant is a linear combination of the basis function with shifted and scaled arguments and with coefficients explicitly given by the point values of the density. Thus, the approach results in semi‐analytic cubature formulae for volume potentials, which prove to be high order approximations of the integrals. It is based on multi‐resolution schemes for accurate approximations up to the boundary by applying approximate refinement equations of the basis functions and iterative approximations on finer grids. We obtain asymptotic error estimates for the quasi‐interpolation and corresponding cubature formulae and provide some numerical examples. This revised version was published online in June 2006 with corrections to the Cover Date.     

Functional a posteriori error estimates for incremental models in elasto-plasticity

We consider incremental problem arising in elasto-plastic models with isotropic hardening. Our goal is to derive computable and guaranteed bounds of the difference between the exact solution and any function in the admissible (energy) class of the problem considered. Such estimates are obtained by an advanced version of the variational approach earlier used for linear boundary-value problems and nonlinear variational problems with convex functionals [24, 30]. They do no contain mesh-dependent constants and are valid for any conforming approximations regardless of the method used for their derivation. It is shown that the structure of error majorant reflects properties of the exact solution so that the majorant vanishes only if an approximate solution coincides with the exact one. Moreover, it possesses necessary continuity properties, so that any sequence of approximations converging to the exact solution in the energy space generates a sequence of positive numbers (explicitly computable by the majorant functional) that tends to zero.      

Cubature rule associated with a discrete blending sum of quadratic spline quasi-interpolants

A new cubature rule for a parallelepiped domain is defined by integrating a discrete blending sum of C¹ quadratic spline quasi-interpolants in one and two variables. We give the weights and the nodes of this cubature rule and we study the associated error estimates for smooth functions. We compare our method with cubature rules based on the tensor products of spline quadratures and classical composite Simpson’s rules.     

Metrical results on the discrepancy of Halton–Kronecker sequences

By a Halton–Kronecker sequence we mean a sequence in the (s+t)-dimensional unit-cube which is the combination of an s-dimensional Halton-sequence and a t-dimensional Kronecker sequence. The distribution of such sequences was studied for the first time quite recently by Niederreiter. In this paper we obtain metrical results for the discrepancy of Halton–Kronecker sequences which are similar to results for the pure Kronecker sequences obtained by Khintchine and by W.M. Schmidt.     

On scrambled Halton sequences

Halton's low discrepancy sequence is still very popular in spite of its shortcomings with respect to the correlation between points of two-dimensional projections for large dimensions. As a remedy, several types of scrambling and/or randomization for this sequence have been proposed. We examine empirically some of these by calculating their L_∞- and L₂-discrepancies (D^* resp. T^*), and by performing integration tests.Most investigated sequence types give practically equivalent results for D^*, T^*, and the integration error, with two exceptions: random shift sequences are in some cases less efficient, and the shuffled Halton sequence is no more efficient than a pseudo-random one. However, the correlation mentioned above can only be broken with digit-scrambling methods, even though the average correlation of many randomized sequences tends to zero.     

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.     

Compound Poisson Approximation to Convolutions of Compound Negative Binomial Variables

In this paper, the problem of compound Poisson approximation to the convolution of compound negative binomial distributions, under total variation distance, is considered. First, we obtain an error bound using the method of exponents and it is compared with existing ones. It is known that Kerstan’s method is more powerful in compound approximation problems. We employ Kerstan’s method to obtain better estimates, using higher-order approximations. These bounds are of higher-order accuracy and improve upon some of the known results in the literature. Finally, an interesting application to risk theory is discussed.