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.     

Interpolation lattices in several variables

Principal lattices are classical simplicial configurations of nodes suitable for multivariate polynomial interpolation in n dimensions. A principal lattice can be described as the set of intersection points of n + 1 pencils of parallel hyperplanes. Using a projective point of view, Lee and Phillips extended this situation to n + 1 linear pencils of hyperplanes. In two recent papers, two of us have introduced generalized principal lattices in the plane using cubic pencils. In this paper we analyze the problem in n dimensions, considering polynomial, exponential and trigonometric pencils, which can be combined in different ways to obtain generalized principal lattices.We also consider the case of coincident pencils. An error formula for generalized principal lattices is discussed. Partially supported by the Spanish Research Grant BFM2003-03510, by Gobierno de Aragón and Fondo Social Europeo.     

A reliable modification of the cross rule for rational Hermite interpolation

Claessens' cross rule [8] enables simple computation of the values of the rational interpolation table if the table is normal, i.e. if the denominators in the cross rule are non-zero. In the exceptional case of a vanishing denominator a singular block is detected having certain structural properties so that some values are known without further computations. Nevertheless there remain entries which cannot be determined using only the cross rule.In this note we introduce a simple recursive algorithm for computation of the values of neighbours of the singular block. This allows to compute entries in the rational interpolation table along antidiagonals even in the presence of singular blocks. Moreover, in the case of non-square singular blocks, we discuss a facility to monitor the stability.Dedicated to Professor G. Mühlbach on the occasion of his 50th birthday     

The general Neville-Aitken-algorithm and some applications

Summary In this note we will present the most general linear form of a Neville-Aitken-algorithm for interpolation of functions by linear combinations of functions forming a ebyev-system. Some applications are given. Expecially we will give simple new proofs of the recurrence formula for generalized divided differences [5] and of the author's generalization of the classical Neville-Aitkena-algorithm[8]applying to complete ebyev-systems. Another application of the general Neville-Aitken-algorithm deals with systems of linear equations. Also a numerical example is given.     

Lagrange interpolation for continuous piecewise smooth functions

This note is devoted to Lagrange interpolation for continuous piecewise smooth functions. A new family of interpolatory functions with explicit approximation error bounds is obtained. We apply the theory to the classical Lagrange interpolation.     

Lösung von Differentialgleichungen mit Splinefunktionen. Eine Störungstheorie

Summary In this paper non-linear splines (depending onn+1 parameters) are used to patch up the solution of an initial value problem in intervals of stepsizeh. The elements of the solution are fixed byq smoothness conditions andd conditions derived from the differential equation in an appropriate setup. The feasibility of the method can be connected to that of the polynomial spline method by a perturbation type argument. Thus the question of convergence forh0 is closely connected to the linear (polynomial) case.A new elementary prove is given for divergence of the polynomial splines ifq is larger thand+1, as was done by Mülthei [4] with other techniques.A byproduct is an extention of the famous result for polynomial interpolation by Runge on equidistant grids that interpolation of a given function by splines of too high smoothness can cause divergence forh0.

Diese Arbeit ist mit Unterstützung des von der Deutschen Forschungsgemeinschaft getragenen Sonderforschungsbereiches 72 entstanden     

A summability method for the arithmetic Fourier transform

The Arithmetic Fourier Transform (AFT) is an algorithm for the computation of Fourier coefficients, which is suitable for parallel processing and in which there are no multiplications by complex exponentials. This is accomplished by the use of the Möbius function and Möbius inversion. However, the algorithm does require the evaluation of the function at an array of irregularly spaced points. In the case that the function has been sampled at regularly spaced points, interpolation is used at the intermediate points of the array. Generally theAFT is most effective when used to calculate the Fourier cosine coefficients of an even function.In this paper a summability method is used to derive a modification of theAFT algorithm. The proof of the modification is quite independent of theAFT itself and involves a summation by primes. One advantage of the new algorithm is that with a suitable sampling scheme low order Fourier coefficients may be calculated without interpolation.     

Two interpolation operators on irregularly distributed data in inner product spaces

Two interpolation operators in inner product spaces for irregularly distributed data are compared. The first is a well-known polynomial operator, which in a certain sense generalizes the classical Lagrange interpolation polynomial. The second can be obtained by modifying the first so as to get a partition-of-unity interpolant. Numerical tests and considerations on errors show that the two operators have very different approximation performances, and that by suitable modifications both can provide acceptable results, working in particular from R^m to Rⁿ and from C[−π,π] to R.     

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.     

On local Hermitian and skew-Hermitian splitting iteration methods for generalized saddle point problems

In this paper, we first present a local Hermitian and skew-Hermitian splitting (LHSS) iteration method for solving a class of generalized saddle point problems. The new method converges to the solution under suitable restrictions on the preconditioning matrix. Then we give a modified LHSS (MLHSS) iteration method, and further extend it to the generalized saddle point problems, obtaining the so-called generalized MLHSS (GMLHSS) iteration method. Numerical experiments for a model Navier-Stokes problem are given, and the results show that the new methods outperform the classical Uzawa method and the inexact parameterized Uzawa method.     

Lagrange's formula for tangential interpolation with application to structured matrices

Lagrange's interpolation formula is generalized to tangential interpolation. This includes interpolation by vector polynomials and by rational vector functions with prescribed pole characteristics. The formula is applied to obtain representations of the inverses of Cauchy-Vandermonde matrices generalizing former results.     

A Lie-theoretic setting for the classical interpolation theories

The three classical interpolation theories — Newton-Lagrange, Thiele and Pick-Nevanlinna — are developed within a common Lie-theoretic framework. They essentially involve a recursive process, each step geometrically providing an analytic map from a Riemann surface to a Grassmann manifold. The operation which passes from the (n−1)st to the nth involves the action of what the physicists call a group of gauge transformations. There is also a first-order difference operator which maps the set of solutions of the nth order interpolation to the (n−1)st: This difference operator is, in each case, covariant with respect to the action of the Lie groups involved. For Newton-Lagrange interpolation, this Lie group is the group of affine transformations of the complex plane; for Thiele interpolation the group SL(2, C) of projective transformations; and for Pick-Nevanlinna interpolation the subgroup SU(1, 1) of SL(2, C) which leaves invariant the disk in the complex plane. National Research Council Senior Research Associate at the Ames Research Center (NASA)}.     

OnG 2 continuous cubic spline interpolation

In this paper the interpolation byG ² continuous planar cubic Bézier spline curves is studied. The interpolation is based upon the underlying curve points and the end tangent directions only, and could be viewed as an extension of the cubic spline interpolation to the curve case. Two boundary, and two interior points are interpolated per each spline section. It is shown that under certain conditions the interpolation problem is asymptotically solvable, and for a smooth curvef the optimal approximation order is achieved. The practical experiments demonstrate the interpolation to be very satisfactory. Supported in prat by the Ministry of Science and Technology of Slovenjia, and in part by the NSF and SF of National Educational Committee of China.     

On general Hermite trigonometric interpolation

Summary A sequence of general Hermite trigonometric interpolation polynomials with equidistant interpolation points is given. Integrating these interpolation formulae a sequence of quadrature formulae for the integration of periodic functions is obtained. Derivative-free remainders are stated for these interpolation and quadrature formulae.This work was done at the Max-Planck-Institut für Physik und Astrophysik, München.     

A new non‐polynomial univariate interpolation formula of Hermite type

A new C ^∞ interpolant is presented for the univariate Hermite interpolation problem. It differs from the classical solution in that the interpolant is of non‐polynomial nature. Its basis functions are a set of simple, compact support, transcendental functions. The interpolant can be regarded as a truncated Multipoint Taylor series. It has essential singularities at the sample points, but is well behaved over the real axis and satisfies the given functional data. The interpolant converges to the underlying real‐analytic function when (i) the number of derivatives at each point tends to infinity and the number of sample points remains finite, and when (ii) the spacing between sample points tends to zero and the number of specified derivatives at each sample point remains finite. A comparison is made between the numerical results achieved with the new method and those obtained with polynomial Hermite interpolation. In contrast with the classical polynomial solution, the new interpolant does not suffer from any ill conditioning, so it is always numerically stable. In addition, it is a much more computationally efficient method than the polynomial approach. This revised version was published online in June 2006 with corrections to the Cover Date.     

Multivariate polynomial interpolation under projectivities part I: lagrange and newton interpolation formulas

In this note interpolation by real polynomials of several real variables is treated. Existence and unicity of the interpolant for knot systems being the perspective images of certain regular knot systems is discussed. Moreover, for such systems a Newton interpolation formula is derived allowing a recursive computation of the interpolant via multivariate divided differences. A numerical example is given.Partially supported by CICYT Res. Grant PS 87/0060 and by a Europe Travel Grant CAI-CONAI, Spain, 1988.     

Newton interpolation at Leja points

The Newton form is a convenient representation for interpolation polynomials. Its sensitivity to perturbations depends on the distribution and ordering of the interpolation points. The present paper bounds the growth of the condition number of the Newton form when the interpolation points are Leja points for fairly general compact sets K in the complex plane. Because the Leja points are defined recursively, they are attractive to use with the Newton form. If K is an interval, then the Leja points are distributed roughly like Chebyshev points. Our investigation of the Newton form defined by interpolation at Leja points suggests an ordering scheme for arbitrary interpolation points.Research supported in part by NSF under Grant DMS-8704196 and by U.S. Air Force Grant AFSOR-87-0102.On leave from University of Kentucky, Department of Mathematics, Lexington, KY 40506, U.S.A.     

On the Nevanlinna-Pick interpolation problem for generalized stieltjes functions

The solutions of the Nevanlinna-Pick interpolation problem for generalized Stieltjes matrix functions are parametrized via a fractional linear transformation over a subset of the class of classical Stieltjes functions. The fractional linear transformation of some of these functions may have a pole in one or more of the interpolation points, hence not all Stieltjes functions can serve as a parameter. The set of excluded parameters is characterized in terms of the two related Pick matrices.Dedicated to the memory of M. G. Kreîn     

A parallel method for fast and practical high-order newton interpolation

We present parallel algorithms for the computation and evaluation of interpolating polynomials. The algorithms use parallel prefix techniques for the calculation of divided differences in the Newton representation of the interpolating polynomial. Forn+1 given input pairs, the proposed interpolation algorithm requires only 2 [log(n+1)]+2 parallel arithmetic steps and circuit sizeO(n ²), reducing the best known circuit size for parallel interpolation by a factor of logn. The algorithm for the computation of the divided differences is shown to be numerically stable and does not require equidistant points, precomputation, or the fast Fourier transform. We report on numerical experiments comparing this with other serial and parallel algorithms. The experiments indicate that the method can be very useful for very high-order interpolation, which is made possible for special sets of interpolation nodes.Supported in part by the National Science Foundation under Grant No. NSF DCR-8603722.Supported by the National Science Foundation under Grants No. US NSF MIP-8410110, US NSF DCR85-09970, and US NSF CCR-8717942 and AT&T under Grant AT&T AFFL67Sameh.     

Fast computation of determinants of Bézout matrices and application to curve implicitization

When using bivariate polynomial interpolation for computing the implicit equation of a rational plane algebraic curve given by its parametric equations, the generation of the interpolation data is the most costly of the two stages of the process. In this work a new way of generating those interpolation data with less computational cost is presented. The method is based on an efficient computation of the determinants of certain constant Bézout matrices.