Monotone and Convex C 1 Hermite Interpolants Generated by a Subdivision Scheme

   Abstract. We propose C ¹ Hermite interpolants generated by the general subdivision scheme introduced by Merrien [17] and satisfying monotonicity or convexity constraints. For arbitrary values and slopes of a given function f at the end-points of a bounded interval, which are compatible with the contraints, the given algorithms construct shape-preserving interpolants. Moreover, these algorithms are quite simple and fast as well as adapted to CAGD. We also give error estimates in the case of interpolation of smooth functions.     

Unified Representations of Nonlinear Splines

Golomb and Jerome's framework is modified and extended. The new framework is more general since it also handles interpolants which are not allowed to “slide” at the nodes. The space of interpolants of variable length is shown to be a smooth manifold. If the length is fixed, and there are no nodes, then the space of interpolants is a manifold. When there is at least one node, and at least one node is not on the line segment between the endpoints, then the space of interpolants of fixed length is a smooth manifold. Sufficient conditions are given which ensure the space of interpolants continues to be a smooth manifold in the presence of additional constraints such as clamping and pinning. A new fundamental finite-dimensional equation is derived. When it is solved it yields all nonlinear splines, and every nonlinear spline appears in this way. An important feature is that the same symbolic equation is used for all possible combinations of the constraints considered. It is shown how to take the solutions of the fundamental equation and use them to express the corresponding nonlinear splines in terms of a pair of elliptic functions. An inequality is derived that specifies which elliptic function appears along each section of the spline. The nonlinear splines are in a unified way shown to beC²for all possible combinations of the constraints considered.     

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.     

S-convex,monotone, and positive interpolation with rational bicubic splines of C2-continuity

In this paper we deal with shape preserving interpolation of data sets given on rectangular grids. The aim is to show that there exist spline interpolants of the continuity classC ² which areS-convex, monotone, or positive if the data sets have these properties. This is done by using particular rational bicubic splines defined on the grids introduced by the data. Interpolants of the desired type can be constructed by a simple search procedure.     

Superconvergent interpolants for collocation methods applied to Volterra integro-differential equations with delay

Standard software based on the collocation method for differential equations delivers a continuous approximation (called the collocation solution) which augments the high order discrete approximate solution that is provided at mesh points. This continuous approximation is less accurate than the discrete approximation. For ‘non-standard’ Volterra integro-differential equations with constant delay, that often arise in modeling predator-prey systems in Ecology, the collocation solution is C ⁰ continuous. The accuracy is O(h ^s+1) at off-mesh points and O(h ^2s ) at mesh points where s is the number of Gauss points used per subinterval and h refers to the stepsize. We will show how to construct C ¹ interpolants with an accuracy at off-mesh points and mesh points of the same order (2s). This implies that even for coarse mesh selections we achieve an accurate and smooth approximate solution. Specific schemes are presented for s=2, 3, and numerical results demonstrate the effectiveness of the new interpolants.     

Monotone and Convex C 1 Hermite Interpolants Generated by a Subdivision Scheme

Abstract. We propose C ¹ Hermite interpolants generated by the general subdivision scheme introduced by Merrien [17] and satisfying monotonicity or convexity constraints. For arbitrary values and slopes of a given function f at the end-points of a bounded interval, which are compatible with the contraints, the given algorithms construct shape-preserving interpolants. Moreover, these algorithms are quite simple and fast as well as adapted to CAGD. We also give error estimates in the case of interpolation of smooth functions.     

Constructing C3 shape preserving interpolating space curves

We present a method for constructing shape-preserving C ³ interpolants in R ³. The resulting curve is obtained by adding a polynomial perturbation of high degree to a curve which is shape-preserving but not sufficiently smooth. The degree of the perturbed curve is selected in order to maintain the shape properties of the basic curve.     

Bernstein-Type Bases and Corner Cutting Algorithms for C 1 Merrien's Curves

Bernstein bases, control polygons and corner-cutting algorithms are defined for C ¹ Merrien's curves introduced in [7]. The convergence of these algorithms is proved for two specific families of curves. Results on monotone and convex interpolants which have been proved in [8] by Merrien and the author are also recovered.     

Two shape preserving lagrangeC 2-interpolants

Summary We present a LagrangeC ²-interpolant to scattered convex data which preserves convexity. We also present a LagrangeC ²-interpolant to uniformly spaced monotone data sites which preserves monotonicity. In both cases no further conditions are required on the data values. These interpolants are explicitely described and local. Error isO(h ³) when the function to be interpolated isC ³.     

Fair upper bounds for the curvature in univariate convex interpolation

In convex interpolation the curvature of the interpolants should be as small as possible. We attack this problem by treating interpolation subject to bounds on the curvature. In view of the concexity the lower bound is equal to zero while the upper bound is assumed to be piecewise constant. The upper bounds are called fair with respect to a function class if the interpolation problem becomes solvable for all data sets in strictly convex position. We derive fair a priori bounds for classes of quadraticC ¹, cubicC ², and quarticC ³ splines on refined grids.     

Admissible slopes for monotone and convex interpolation

Summary In many applications, interpolation of experimental data exhibiting some geometric property such as nonnegativity, monotonicity or convexity is unacceptable unless the interpolant reflects these characteristics. This paper identifies admissible slopes at data points of variousC ¹ interpolants which ensure a desirable shape. We discuss this question, in turn for the following function classes commonly used for shape preserving interpolations: monotone polynomials,C ¹ monotone piecewise polynomials, convex polynomials, parametric cubic curves and rational functions.     

First order hermite interpolation with spherical Pythagorean-hodograph curves

The general stereographic projection which maps a point on a sphere with arbitrary radius to a point on a plane stereographically and its inverse projection have the Pythagorean-hodograph (PH) preserving property in the sense that they map a PH curve to another PH curve. Upon this fact, for given spatialC ¹ Hermite data, we construct a spatial PH curve on a sphere that is aC ¹ Hermite interpolant of the given data as follows: First, we solveC ¹ Hermite interpolation problem for the stereographically projected planar data of the given data in ?³ with planar PH curves expressed in the complex representation. Second, we construct spherical PH curves which are interpolants for the given data in ?³ using the inverse general stereographic projection.     

Variational Principles and Sobolev-Type Estimates for Generalized Interpolation on a Riemannian Manifold

The purpose of this paper is to study certain variational principles and Sobolev-type estimates for the approximation order resulting from using strictly positive definite kernels to do generalized Hermite interpolation on a closed (i.e., no boundary), compact, connected, orientable, m -dimensional C ^∞ Riemannian manifold , with C ^∞ metric g _ij . The rate of approximation can be more fully analyzed with rates of approximation given in terms of Sobolev norms. Estimates on the rate of convergence for generalized Hermite and other distributional interpolants can be obtained in certain circumstances and, finally, the constants appearing in the approximation order inequalities are explicit. Our focus in this paper will be on approximation rates in the cases of the circle, other tori, and the 2 -sphere. April 10, 1996. Dates revised: March 26, 1997; August 26, 1997. Date accepted: September 12, 1997. Communicated by Ronald A. DeVore.     

Refined Error Estimates for Radial Basis Function Interpolation

We discuss new and refined error estimates for radial-function scattered-data interpolants and their derivatives. These estimates hold on R ^d , the d-torus, and the 2-sphere. We employ a new technique, involving norming sets, that enables us to obtain error estimates, which in many cases give bounds orders of magnitude smaller than those previously known.     

The Problem of Topologies of Grothendieck and the Class of Fréchet T-Spaces

We examine the interpolation with periodic polynomial splines of degree d and defect r (d ≦ r) on equidistant partitions of the real axis and generalize known results for r = 0. We prove necessary and sufficient conditions for the existence and a certain L²-stability of the interpolants as well as their approximation properties in the scale of the periodic SOBOLEV spaces.     

Cubic Splines with Minimal Norm

Natural cubic interpolatory splines are known to have a minimal L ₂-norm of its second derivative on the C ² (or W ₂ ² ) class of interpolants. We consider cubic splines which minimize some other norms (or functionals) on the class of interpolatory cubic splines only. The cases of classical cubic splines with defect one (interpolation of function values) and of Hermite C ¹ splines (interpolation of function values and first derivatives) with spline knots different from the points of interpolation are discussed.     

The compass (star) identity for vector-valued rational interpolants

The compass identity (Wynn's five point star identity) for Padé approximants connects neighbouring elements called N, S, E, W and C in the Padé table. Its form has been extended to the cases of rational interpolation of ordinary (scalar) data and interpolation of vector-valued data. In this paper, full specifications of the associated five point identity for the scalar denominator polynomials and the vector numerator polynomials of the vector-valued rational interpolants on real data points are given, as well as the related generalisations of Frobenius' identities. Unique minimal forms of the polynomials constituting the interpolants and results about unattainable points correspond closely to their counterparts in the scalar case. This revised version was published online in June 2006 with corrections to the Cover Date.     

Piecewise linear interpolants to Lagrange and Hermite convex scattered data

This paper concerns two fundamental interpolants to convex bivariate scattered data. The first,u, is the supremum over all convex Lagrange interpolants and is piecewise linear on a triangulation. The other,l, is the infimum over all convex Hermite interpolants and is piecewise linear on a tessellation. We discuss the existence, uniqueness, and numerical computation ofu andl and the associated triangulation and tessellation. We also describe how to generate convex Hermite data from convex Lagrange data.Research partially supported by the EU Project FAIRSHAPE, CHRX-CT94-0522. The first author was also partially supported by DGICYT PB93-0310 Research Grant.     

Continued fractions associated with the Newton-Padé table

Summary We discuss first the block structure of the Newton-Padé table (or, rational interpolation table) corresponding to the double sequence of rational interpolants for the data{(z _k, h(z_k)} _k =0. (The (m, n)-entry of this table is the rational function of type (m,n) solving the linearized rational interpolation problem on the firstm+n+1 data.) We then construct continued fractions that are associated with either a diagonal or two adjacent diagonals of this Newton-Padé table in such a way that the convergents of the continued fractions are equal to the distinct entries on this diagonal or this pair of diagonals, respectively. The resulting continued fractions are generalizations of Thiele fractions and of Magnus'sP-fractions. A discussion of an some new results on related algorithms of Werner and Graves-Morris and Hopkins are also given.Dedicated to the memory of Helmut Werner (1931–1985)     

Tautologies with a unique craig interpolant,uniform vs. nonuniform complexity

If S?{0,1};^* and S′ = {0,1}^*\sbS are both recognized within a certain nondeterministic time bound T then, in not much more time, one can write down tautologies A_n→A′_n with unique interpolants I_n that define S∩{0,1}ⁿ; hence, if one can rapidly find unique interpolants, then one can recognize S within deterministic time T^p for some fixed p\s>0. In general, complexity measures for the problem of finding unique interpolants in sentential logic yield new relations between circuit depth and nondeterministic Turing time, as well as between proof length and the complexity of decision procedures of logical theories.