Lagrange Interpolation on Arbitrarily Distributed Data in Banach Spaces

The Lagrange interpolation problem in Banach spaces is approached by cardinal basis interpolation. Some error estimates are given and the results of several numerical tests are reported in order to show the approximation performances of the proposed interpolants. A comparison between some examples of interpolants is presented in the noteworthy case of Hilbert spaces, with some considerations about the possible localization of the formulas. Finally, some remarks about the cardinal basis interpolation framework are made from the application point of view.     

Cardinal interpolation with general multiquadrics: convergence rates

This article pertains to interpolation of Sobolev functions at shrinking lattices \(h\mathbb {Z}^{d}\) from L _p shift-invariant spaces associated with cardinal functions related to general multiquadrics, ? _{α, c} (x) := (|x|² + c ²) ^α . The relation between the shift-invariant spaces generated by the cardinal functions and those generated by the multiquadrics themselves is considered. Additionally, L _p error estimates in terms of the dilation h are considered for the associated cardinal interpolation scheme. This analysis expands the range of α values which were previously known to give such convergence rates (i.e. O(h ^k ) for functions with derivatives of order up to k in L _p , \(1<p<\infty \)). Additionally, the analysis here demonstrates that some known best approximation rates for multiquadric approximation are obtained by their cardinal interpolants.     

Lower complexity bounds for interpolation algorithms

We introduce and discuss a new computational model for the Hermite-Lagrange interpolation with nonlinear classes of polynomial interpolants. We distinguish between an interpolation problem and an algorithm that solves it. Our model includes also coalescence phenomena and captures a large variety of known Hermite-Lagrange interpolation problems and algorithms. Like in traditional Hermite-Lagrange interpolation, our model is based on the execution of arithmetic operations (including divisions) in the field where the data (nodes and values) are interpreted and arithmetic operations are counted at unit cost. This leads us to a new view of rational functions and maps defined on arbitrary constructible subsets of complex affine spaces. For this purpose we have to develop new tools in algebraic geometry which themselves are mainly based on Zariski’s Main Theorem and the theory of places (or equivalently: valuations). We finish this paper by exhibiting two examples of Lagrange interpolation problems with nonlinear classes of interpolants, which do not admit efficient interpolation algorithms (one of these interpolation problems requires even an exponential quantity of arithmetic operations in terms of the number of the given nodes in order to represent some of the interpolants).In other words, classic Lagrange interpolation algorithms are asymptotically optimal for the solution of these selected interpolation problems and nothing is gained by allowing interpolation algorithms and classes of interpolants to be nonlinear. We show also that classic Lagrange interpolation algorithms are almost optimal for generic nodes and values. This generic data cannot be substantially compressed by using nonlinear techniques.We finish this paper highlighting the close connection of our complexity results in Hermite-Lagrange interpolation with a modern trend in software engineering: architecture tradeoff analysis methods (ATAM).     

On minimax cardinal spline interpolation

Statistical Inference for Stochastic Processes - It is shown that in the problem of cardinal interpolation, spline interpolants of various degrees are R-minimax, with respect to corresponding...     

Multivariate Bernoulli splines and the periodic interpolation problem

Periodic spline interpolation in Euclidian spaceR d is studied using translates of multivariate Bernoulli splines introduced in [25]. The interpolating polynomial spline functions are characterized by a minimal norm property among all interpolants in a Hilbert space of Sobolev type. The results follow from a relation between multivariate Bernoulli splines and the reproducing kernel of this Hilbert space. They apply to scattered data interpolation as well as to interpolation on a uniform grid. For bivariate three-directional Bernoulli splines the approximation order of the interpolants on a refined uniform mesh is computed.     

Approximation by radial basis functions with finitely many centers

Interpolation by translates of “radial” basis functions Φ is optimal in the sense that it minimizes the pointwise error functional among all comparable quasiinterpolants on a certain “native” space of functions $\mathcal{F}_\Phi $ . Since these spaces are rather small for cases where Φ is smooth, we study the behavior of interpolants on larger spaces of the form $\mathcal{F}_{\Phi _0 } $ for less smooth functions Φ₀. It turns out that interpolation by translates of Φ to mollifications of functionsf from $\mathcal{F}_{\Phi _0 } $ yields approximations tof that attain the same asymptotic error bounds as (optimal) interpolation off by translates of Φ₀ on $\mathcal{F}_{\Phi _0 } $ .     

ON AN EXTENSION OF ABEL-GONTSCHAROFF''''S EXPANSION FORMULA

We present a constructive generalization of Abel-Gontscharoff's series expansion to higher dimensions. A constructive application to a problem of multivariate interpolation is also investigated. In addition, two algorithms for constructing the basis functions of the interpolants are given.     

Weak descartes systems in generalized spline spaces

A class of generalized spline spaces is introduced for which a basis of functions with local support is constructed by using a recursion relation. It is shown that this basis forms a weak Descartes system. Moreover, an interpolation property is given.     

An elementary algebraic representation of polynomial spline interpolants for equidistant lattices and its condition

Summary A customary representation formula for periodic spline interpolants contains redundance which, however, can be eliminated by a transcendent method. We use an elementary indentity for the generalized Euler-Frobenius-polynomials, which seems to be unknown until now, in order to derive the theory by purely algebraic arguments. The general cardinal spline interpolation theory can be obtained from the periodic case by a simple approach to the limit. Our representation has minimum condition for odd/even degree if the interpolation points are the lattice (mid-)points. We evaluate the corresponding condition numbers and give an asymptotic representation for them.     

Multivariate interpolation with increasingly flat radial basis functions of finite smoothness

In this paper, we consider multivariate interpolation with radial basis functions of finite smoothness. In particular, we show that interpolants by radial basis functions in ℝ ^d with finite smoothness of even order converge to a polyharmonic spline interpolant as the scale parameter of the radial basis functions goes to zero, i.e., the radial basis functions become increasingly flat.     

Fundamental Sets of Fractal Functions

Fractal interpolants constructed through iterated function systems prove more general than classical interpolants. In this paper, we assign a family of fractal functions to several classes of real mappings like, for instance, maps defined on sets that are not intervals, maps integrable but not continuous and may be defined on unbounded domains. In particular, based on fractal interpolation functions, we construct fractal Müntz polynomials that successfully generalize classical Müntz polynomials. The parameters of the fractal Müntz system enable the control and modification of the properties of original functions. Furthermore, we deduce fractal versions of classical Müntz theorems. In this way, the fractal methodology generalizes the fundamental sets of the classical approximation theory and we construct complete systems of fractal functions in spaces of continuous and p-integrable mappings on bounded domains. This work is supported by the project No: SB 2005-0199, Spain.     

Improved stability estimates and a characterization of the native space for matrix-valued RBFs

In this paper we derive several new results involving matrix-valued radial basis functions (RBFs). We begin by introducing a class of matrix-valued RBFs which can be used to construct interpolants that are curl-free. Next, we offer a characterization of the native space for divergence-free and curl-free kernels based on the Fourier transform. Finally, we investigate the stability of the interpolation matrix for both the divergence-free and curl-free cases, and when the kernel has finite smoothness we obtain sharp estimates. An erratum to this article can be found at     

Best mean approximation by splines satisfying generalized convexity constraints

A characterization of the best L₁-approximation to a continuous function by classes of fixed-knot polynomial splines which satisfy generalized convexity constraints is presented and uniqueness is shown. Included is the possibility of specifying the positivity, monotonicity, or convexity of the class. The proof of uniqueness uses recently developed results for Hermite-Birkhoff interpolation by splines.     

Error estimates for interpolation of rough data using the scattered shifts of a radial basis function

The error between appropriately smooth functions and their radial basis function interpolants, as the interpolation points fill out a bounded domain in R^d, is a well studied artifact. In all of these cases, the analysis takes place in a natural function space dictated by the choice of radial basis function – the native space. The native space contains functions possessing a certain amount of smoothness. This paper establishes error estimates when the function being interpolated is conspicuously rough. AMS subject classification 41A05, 41A25, 41A30, 41A63R.A. Brownlee: Supported by a studentship from the Engineering and Physical Sciences Research Council.     

A recursive method for computing interpolants

In this paper, we describe a recursive method for computing interpolants defined in a space spanned by a finite number of continuous functions in R^d${\mathbb{R}}^d$. We apply this method to construct several interpolants such as spline interpolants, tensor product interpolants and multivariate polynomial interpolants. We also give a simple algorithm for solving a multivariate polynomial interpolation problem and constructing the minimal interpolation space for a given finite set of interpolation points.     

On cubic Hermite coalescence hidden variable fractal interpolation functions

Hermite interpolation is a very important tool in approximation theory and numerical analysis, and provides a popular method for modeling in the area of computer aided geometric design. However, the classical Hermite interpolant is unique for a prescribed data set,and hence lacks freedom for the choice of an interpolating curve, which is a crucial requirement in design environment. Even though there is a rather well developed fractal theory for Hermite interpolation that offers a large flexibility in the choice of interpolants, it also has the shortcoming that the functions that can be well approximated are highly restricted to the class of self-affine functions. The primary objective of this paper is to suggest a C1-cubic Hermite interpolation scheme using a fractal methodology, namely, the coalescence hidden variable fractal interpolation, which works equally well for the approximation of a self-affine and non-self-affine data generating functions. The uniform error bound for the proposed fractal interpolant is established to demonstrate that the convergence properties are similar to that of the classical Hermite interpolant. For the Hermite interpolation problem, if the derivative values are not actually prescribed at the knots, then we assign these values so that the interpolant gains global C2-continuity. Consequently, the procedure culminates with the construction of cubic spline coalescence hidden variable fractal interpolants. Thus, the present article also provides an alternative to the construction of cubic spline coalescence hidden variable fractal interpolation functions through moments proposed by Chand and Kapoor [Fractals, 15(1)(2007), pp. 41-53].     

A construction of interpolating wavelets on invariant sets

We introduce the concept of a refinable set relative to a family of contractive mappings on a metric space, and demonstrate how such sets are useful to recursively construct interpolants which have a multiscale structure. The notion of a refinable set parallels that of a refinable function, which is the basis of wavelet construction. The interpolation points we recursively generate from a refinable set by a set-theoretic multiresolution are analogous to multiresolution for functions used in wavelet construction. We then use this recursive structure for the points to construct multiscale interpolants. Several concrete examples of refinable sets which can be used for generating interpolatory wavelets are included.

     

ON AN EXTENSION OF ABEL-GONTSCHAROFF＇S EXPANSION FORMULA

We present a constructive generalization of Abel-Gontscharoff＇s series expansion to higher dimensions. A constructive application to a problem of multivariate interpolation is also investigated. In addition, two algorithms for constructing the basis functions of the interpolants are given.     

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