Romberg integration as a problem in interpolation theory

A complete derivation of Romberg integration for an arbitrary sequence of integration steplenghts, using classical interpolation theory only, is given. An explicit expression for the error is derived using Lagrange interpolation. From the general theory developed, several previous known results may be derived as special cases.     

Error bounds for Romberg quadrature

Denote by the error of a Romberg quadrature rule applied to the function f. We determine approximately the constants in the bounds of the types and for all classical Romberg rules. By a comparison with the corresponding constants of the Gaussian rule we give the statement “The Gaussian quadrature rule is better than the Romberg method” a precise meaning. Received September 10, 1997 / Revised version received February 16, 1998     

Extended product integration rules

In this paper we introduce a class of extended product quadrature rules to associate with the corresponding standard product rules, and present an algorithm for their construction. A general discussion on the convergence of such formulas is then given. Finally some examples and applications are considered.Work sponsored by the Ministero della Pubblica Istruzione of Italy.     

On rates of acceleration of extrapolation methods for oscillatory infinite integrals

The purpose of this work is to complement and expand our knowledge of the convergence theory of some extrapolation methods for the accurate computation of oscillatory infinite integrals. Specifically, we analyze in detail the convergence properties of theW- and -transformations of the author as they are applied to three integrals, all with totally different behavior at infinity. The results of the analysis suggest different convergence and acceleration of convergence behavior for the above mentioned transformations on the different integrals, and they improve considerably those that can be obtained from the existing convergence theories.     

On forming the Romberg table

Romberg-type extrapolation is commonly used in many areas of numerical computation. An algorithm is presented for forming the Romberg table for general step-length sequence and general powers in the asymptotic expansion. It is then shown that parameters of the algorithm can be used to gain an a priori bound on propagation of rounding errors in the table.     

Adaptive integration for multi-factor portfolio credit loss models

We propose algorithms of adaptive integration for calculation of the tail probability in multi-factor credit portfolio loss models. We first modify the classical Genz-Malik rule, a deterministic multiple integration rule suitable for portfolio credit models with number of factors less than 8. Later on we arrive at the adaptive Monte Carlo integration, which essentially replaces the deterministic integration rule by antithetic random numbers. The latter can not only handle higher-dimensional models but is also able to provide reliable probabilistic error bounds. Both algorithms are asymptotic convergent and consistently outperform the plain Monte Carlo method.     

An asymptotic expansion in wavelet analysis and its application to accurate numerical wavelet decomposition

We consider a dilation operatorT admitting a scaling function with compact support as fixed point. It is shown that the adjoint operatorT*admits a sequence of polynomial eigenfunctions and that a smooth functionf admits an expansion in these eigenfunctions, which reveals the asymptotic behavior ofT* forn.Due to this asymptotic expansion, an extrapolation technique can be applied for the accurate numerical computation of the integrals appearing in the wavelet decomposition of a smooth function. This extrapolation technique fits well in a multiresolution scheme.     

Quasi-monte carlo methods for numerical integration of multivariate Haar series

In the present paper we study quasi-Monte Carlo methods to integrate functions representable by generalized Haar series in high dimensions. Using (t, m, s)-nets to calculate the quasi-Monte Carlo approximation, we get best possible estimates of the integration error for practically relevant classes of functions. The local structure of the Haar functions yields interesting new aspects in proofs and results. The results are supplemented by concrete computer calculations. Research supported by the Austrian Science Foundation (FWF), project no. P11143-MAT.     

Quasi-Monte Carlo methods for numerical integration of multivariate Haar series II

The present paper contains a comparison of different classes of multivariate Haar series that have been studied with respect to numerical integration, new properties ofE _s ^α -classes and numerical results. Research supported by the Austrian Science Foundation (FWF), project no. P11143-MAT.     

Romberg quadrature using the Bulirsch sequence

Summary. In this note, we prove a conjecture of Bulirsch concerning the definiteness of the Romberg quadrature rules using the Bulirsch sequence. We compare these rules with the classical Romberg scheme and the Gaussian rules. Received May 16, 2000 / Published online May 30, 2001     

Remarks on a unified theory for classical and generalized interpolation and extrapolation

A unified theory for generalized interpolation, as developed by Mühlbach, and classical polynomial interpolation is discussed. A fundamental theorem for generalized linear iterative interpolation is given and used to derive generalizations of the classical formulae due to Neville, Aitken and Lagrange. Using Mühlbach's definition of generalized divided differences, Newton's generalized interpolation formula, including an expression for the error term, is derived as a pure identity.     

Fast inversion of vandermonde-like matrices involving orthogonal polynomials

Let {q} _j ^=0n–1 be a family of polynomials that satisfy a three-term recurrence relation and let {t _k } _k ⁼¹ⁿ be a set of distinct nodes. Define the Vandermonde-like matrixW _n =[w _jk ] _k,j ⁼¹ⁿ ,w _jk =q _j–1(t _k ). We describe a fast algorithm for computing the elements of the inverse ofW _n inO(n ²) arithmetic operations. Our algorithm generalizes a scheme presented by Traub [22] for fast inversion of Vandermonde matrices. Numerical examples show that our scheme often yields higher accuracy than the LINPACK subroutine SGEDI for inverting a general matrix. SGEDI uses Gaussian elimination with partial pivoting and requiresO(n ³) arithmetic operations.Dedicated to Gene H. Golub on his 60th birthdayResearch supported by NSF grant DMS-9002884.     

Fully symmetric integration rules for the 4-cube

In this paper we discuss fully symmetric integration rules of degree 7 and 9 for the 4-cube. In particular we are interested in good rules. (i.e. rules with all the evaluation points inside the cube and all the weights positive).This work was supported by the Norwegian Research Council for Sciences and Humanities.     

On integrating vertex singularities using extrapolation

A new approach to the integration of vertex singularities is described. This approach is based on a non-uniform subdivision of the region of integration and the technique fits well to the subdivision strategy used in many adaptive algorithms. A nice feature with this approach is that it can be used in any dimension and on any region of integration which can be subdivided into subregions of the same form. The strategy can be applied both to vertex singularities and internal point singularities. In the latter case this can be done without an initial subdivision of the region in order to put the singular point in a vertex. It turns out that the technique has excellent numerical stability properties.Dedicated to Carl-Erik Fröberg on the occasion of his 75th birthday.This work was supported by The Norwegian Research Council for Science and the Humanities.     

An extension of trapezoidal type product integration rules

In the present paper, we use a generalization of the Euler-Maclaurin summation formula for integrals of the form where F₀(x) (the weight) is a continuous and positive function and g(x) is twice continuously differentiable function in the interval [a,b]. Numerical examples are given to show the effectiveness of the method.     

Ein kurze Anmerkung zur Romberg-Integration

Summary Subject to rather mild assumptions on the integrand, the Romberg table (theT-table) and the modified Romberg table (theU-table) yield asymptotically upper and lower bounds for the value of the integral, and the convergence of the columns of the two tables is asymptotically monotone. This is verified for arbitrary sequences of step sizes satisfying the usual condition of convergence for Romberg integration.

     

Adaption allows efficient integration of functions with unknown singularities

We study numerical integration for functions f with singularities. Nonadaptive methods are inefficient in this case, and we show that the problem can be efficiently solved by adaptive quadratures at cost similar to that for functions with no singularities. Consider first a class of functions whose derivatives of order up to r are continuous and uniformly bounded for any but one singular point. We propose adaptive quadratures Q*_n, each using at most n function values, whose worst case errors are proportional to n^−r. On the other hand, the worst case error of nonadaptive methods does not converge faster than n⁻¹. These worst case results do not extend to the case of functions with two or more singularities; however, adaption shows its power even for such functions in the asymptotic setting. That is, let F^∞_r be the class of r-smooth functions with arbitrary (but finite) number of singularities. Then a generalization of Q*_n yields adaptive quadratures Q**_n such that |I(f)−Q**_n(f)|=O(n^−r) for any f ∈ F^∞_r. In addition, we show that for any sequence of nonadaptive methods there are `many' functions in F^∞_r for which the errors converge no faster than n⁻¹. Results of numerical experiments are also presented. The authors were partially supported, respectively, by the State Committee for Scientific Research of Poland under Project 1 P03A 03928 and by the National Science Foundation under Grant CCR-0095709.     

An algorithm for numerical integration based on quasi-interpolating splines

In this paper product quadratures based on quasi-interpolating splines are proposed for the numerical evaluation of integrals with anL ₁-kernel and of Cauchy Principal Value integrals.Work sponsored by Ministero dell'Università e Ricerca Scientifica of Italy.