Bivariate Lagrange interpolation at the Padua points: the ideal theory approach

The Padua points are a family of points on the square [−1, 1]² given by explicit formulas that admits unique Lagrange interpolation by bivariate polynomials. Interpolation polynomials and cubature formulas based on the Padua points are studied from an ideal theoretic point of view, which leads to the discovery of a compact formula for the interpolation polynomials. The L ^p convergence of the interpolation polynomials is also studied. S. De Marchi and M. Vianello were supported by the “ex-60%” funds of the University of Padua and by the INdAM GNCS (Italian National Group for Scientific Computing). Y. Xu was partially supported by NSF Grant DMS-0604056.     

On the Gibbs phenomenon V: recovering exponential accuracy from collocation point values of a piecewise analytic function

Summary. This paper presents a method to recover exponential accuracy at all points (including at the discontinuities themselves), from the knowledge of an approximation to the interpolation polynomial (or trigonometrical polynomial). We show that if we are given the collocation point values (or a highly accurate approximation) at the Gauss or Gauss-Lobatto points, we can reconstruct an uniform exponentially convergent approximation to the function in any sub-interval of analyticity. The proof covers the cases of Fourier, Chebyshev, Legendre, and more general Gegenbauer collocation methods. A numerical example is also provided. Received July 17, 1994 / Revised version received December 12, 1994     

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.     

The multipoint Padé table and general recurrences for rational interpolation

We first review briefly the Newton-Padé approximation problem and the analogous problem with additional interpolation conditions at infinity, which we call multipoint Padé approximation problem. General recurrence formulas for the Newton-Padé table combine either two pairs of Newton-Padé forms or one such pair and a pair of multipoint Padé forms. We show that, likewise, certain general recurrences for the multipoint Padé table compose two pairs of multipoint Padé forms to get a new pair of multipoint Padé forms. We also discuss the possibility of superfast, i.e.,O(n log² n) algorithms for certain rational interpolation problems.     

Fourier Series with Linear Splines on an Interval

We construct orthonormal bases of linear splines on a finite interval [a, b] and then we study the Fourier series associated to these orthonormal bases. For continuous functions defined on [a, b], we prove that the associated Fourier series converges pointwisely on (a, b) and also uniformly on [a, b], if it convergences pointwisely at a and b.     

Integral error formulæ for the scale of mean value interpolations which includes Kergin and Hakopian interpolation

Summary. In this paper, we provide an integral error formula for a certain scale of mean value interpolations which includes the multivariate polynomial interpolation schemes of Kergin and Hakopian. This formula involves only derivatives of order one higher than the degree of the interpolating polynomial space, and from it we can obtain sharp -estimates. These -estimates are precisely those that numerical analysts want, to guarantee that a scheme based on such an interpolation has the maximum possible order. Received July 11, 1994 / Revised version received February 12, 1996     

Pseudospectra of Matrix Polynomials that Are Expressed in Alternative Bases

Spectra and pseudospectra of matrix polynomials are of interest in geometric intersection problems, vibration problems, and analysis of dynamical systems. In this note we consider the effect of the choice of polynomial basis on the pseudospectrum and on the conditioning of the spectrum of regular matrix polynomials. In particular, we consider the direct use of the Lagrange basis on distinct interpolation nodes, and give a geometric characterization of “good” nodes. We also give some tools for computation of roots at infinity via a new, natural, reversal. The principal achievement of the paper is to connect pseudospectra to the well-established theory of Lebesgue functions and Lebesgue constants, by separating the influence of the scalar basis from the natural scale of the matrix polynomial, which allows many results from interpolation theory to be applied. This work was partially funded by the Natural Sciences and Engineering Research Council of Canada, and by the MITACS Network of Centres of Excellence.     

Multipoint Taylor formulæ

Summary. The main result of this paper is an abstract version of the Kowalewski–Ciarlet–Wagschal multipoint Taylor formula for representing the pointwise error in multivariate Lagrange interpolation. Several applications of this result are given in the paper. The most important of these is the construction of a multipoint Taylor error formula for a general finite element, together with the corresponding –error bounds. Another application is the construction of a family of error formul? for linear interpolation (indexed by real measures of unit mass) which includes some recently obtained formul?. It is also shown how the problem of constructing an error formula for Lagrange interpolation from a D–invariant space of polynomials with the property that it involves only derivatives which annihilate the interpolating space can be reduced to the problem of finding such a formula for a ‘simpler’ one–point interpolation map. Received March 29, 1996 / Revised version received November 22, 1996     

Limit problems for interpolation by analytic radial basis functions

Interpolation problems for analytic radial basis functions like the Gaussian and inverse multiquadrics can degenerate in two ways: the radial basis functions can be scaled to become increasingly flat, or the data points coalesce in the limit while the radial basis functions stay fixed. Both cases call for a careful regularization, which, if carried out explicitly, yields a preconditioning technique for the degenerating linear systems behind these interpolation problems. This paper deals with both cases. For the increasingly flat limit, we recover results by Larsson and Fornberg together with Lee, Yoon, and Yoon concerning convergence of interpolants towards polynomials. With slight modifications, the same technique can also handle scenarios with coalescing data points for fixed radial basis functions. The results show that the degenerating local Lagrange interpolation problems converge towards certain Hermite–Birkhoff problems. This is an important prerequisite for dealing with approximation by radial basis functions adaptively, using freely varying data sites.     

Quadrature formulas on the unit circle with prescribed nodes and maximal domain of validity

In this paper we investigate the Szeg?-Radau and Szeg?-Lobatto quadrature formulas on the unit circle. These are (n+m)-point formulas for which m nodes are fixed in advance, with m=1 and m=2 respectively, and which have a maximal domain of validity in the space of Laurent polynomials. This means that the free parameters (free nodes and positive weights) are chosen such that the quadrature formula is exact for all powers z^j, −p≤j≤p, with p=p(n,m) as large as possible.     

Hermite-Fejer type interpolation of higher order

The paper introduces Hermite-Fejér type (Hermite type) interpolation of higher order denoted by S _mn(f)(S* _mm(f)), and gives some basic properties including expression formulas, convergence relationship between S _mn(f) and H _mn(f) (Hermite-Fejér interpolation of higher order), and the saturation of S _mn(f). Supported by the Science Foundation of Shanxi Province for Returned Scholars.     

Approximation in L p (R d ) from a space spanned by the scattered shifts of a radial basis function

A new multivariate approximation scheme on R ^d using scattered translates of the “shifted” surface spline function is developed. The scheme is shown to provide spectral L _p -approximation orders with 1 ≤ p ≤ ∞, i.e., approximation orders that depend on the smoothness of the approximands. In addition, it applies to noisy data as well as noiseless data. A numerical example is presented with a comparison between the new scheme and the surface spline interpolation method.     

Stability results for approximation by positive definite functions on SO(3)

We consider interpolation methods defined by positive definite functions on a locally compact group G. Estimates for the smallest and largest eigenvalue of the interpolation matrix in terms of the localization of the positive definite function on G are presented, and we provide a method to get positive definite functions explicitly on compact semisimple Lie groups. Finally, we apply our results to construct well-localized positive definite basis functions having nice stability properties on the rotation group SO(3).     

Convergence of subdivision schemes in L p spaces

Abstract. In this paper it is proved that Lp solutions of a refinement equation exist if and only ifthe corresponding subdivision scheme with suitable initial function converges in Lp without anyassumption on the stability of the solutions of the refinement equation. A characterization forconvergence of subdivision scheme is also given in terms of the refinement mask. Thus a com-plete answer to the relation between the existence of Lp solutions of the refinement equation andthe convergence of the corresponding subdivision schemes is given.     

Nonlinear Methods of Approximation

Abstract. Our main interest in this paper is nonlinear approximation. The basic idea behind nonlinear approximation is that the elements used in the approximation do not come from a fixed linear space but are allowed to depend on the function being approximated. While the scope of this paper is mostly theoretical, we should note that this form of approximation appears in many numerical applications such as adaptive PDE solvers, compression of images and signals, statistical classification, and so on. The standard problem in this regard is the problem of m -term approximation where one fixes a basis and looks to approximate a target function by a linear combination of m terms of the basis. When the basis is a wavelet basis or a basis of other waveforms, then this type of approximation is the starting point for compression algorithms. We are interested in the quantitative aspects of this type of approximation. Namely, we want to understand the properties (usually smoothness) of the function which govern its rate of approximation in some given norm (or metric). We are also interested in stable algorithms for finding good or near best approximations using m terms. Some of our earlier work has introduced and analyzed such algorithms. More recently, there has emerged another more complicated form of nonlinear approximation which we call highly nonlinear approximation. It takes many forms but has the basic ingredient that a basis is replaced by a larger system of functions that is usually redundant. Some types of approximation that fall into this general category are mathematical frames, adaptive pursuit (or greedy algorithms), and adaptive basis selection. Redundancy on the one hand offers much promise for greater efficiency in terms of approximation rate, but on the other hand gives rise to highly nontrivial theoretical and practical problems. With this motivation, our recent work and the current activity focuses on nonlinear approximation both in the classical form of m -term approximation (where several important problems remain unsolved) and in the form of highly nonlinear approximation where a theory is only now emerging.     

Numerical evaluation of finite Fourier integrals

A computationally efficient algorithm for evaluating Fourier integrals ∫¹_?1?(x)e^iωxdx using interpolatory quadrature formulas on any set of collocation points is presented. Examples are given to illustrate the performances of interpolatory formulas which are based on the applications of the Fejér, Clenshaw—Curtis, Basu and the Newton—Cotes points. Initially, the formulas for nonoscillatory integrals are generated and then generalizations to finite Fourier integrals are made. Extensions of this algorithm to some other weighted integrals are also considered.     

Nonseparable Radial Frame Multiresolution Analysis in Multidimensions

Abstract

In this article we present a nonseparable multiresolution structure based on frames which is defined by radial frame scaling functions. The Fourier transform of these functions is the indicator (characteristic) function of a measurable set. We also construct the resulting frame multiwavelets, which can be isotropic as well. Our construction can be carried out in any number of dimensions and for a big variety of dilation matrices.     

WeightedL p approximation by modified hermite interpolation of higher order

The authors establish necessary and sufficient conditions for the weightedL ^p convergence at given rates of Hermite interpolation of higher order based on Jacobi zeros plus the endpoints ±1. Theorems on simultaneous approximation are also proved.This material is based upon work supported by the Ministero della Università e della Ricerca Scientifica e Tecnologica (the first two authors), by the National Research Council (the second author) and by Hungarian National Foundation Grant No. 1910 (the third author).     

General interpolation on the lattice h{\Bbb Z}^s: Compactly supported fundamental solutions

Summary. In this paper we combine an earlier method developed with K. Jetter on general cardinal interpolation with constructions of compactly supported solutions for cardinal interpolation to gain compactly supported fundamental solutions for the general interpolation problem. The general interpolation problem admits the interpolation of the functional and derivative values under very weak restrictions on the derivatives to be interpolated. In the univariate case, some known general constructions of compactly supported fundamental solutions for cardinal interpolation are discussed together with algorithms for their construction that make use of MAPLE. Another construction based on finite decomposition and reconstruction for spline spaces is also provided. Ideas used in the latter construction are lifted to provide a general construction of compactly supported fundamental solutions for cardinal interpolation in the multivariate case. Examples are provided, several in the context of some general interpolation problem to illustrate how easy is the transition from cardinal interpolation to general interpolation. Received May 11, 1993 / Revised version received August 16, 1994