Stability-Preserving Rational Approximation Subject to Interpolation Constraints

A quite comprehensive theory of analytic interpolation with degree constraint, dealing with rational analytic interpolants with an a priori bound, has been developed in recent years. In this paper, we consider the limit case when this bound is removed, and only stable interpolants with a prescribed maximum degree are sought. This leads to weighted $H_2$ minimization, where the interpolants are parameterized by the weights. The inverse problem of determining the weight given a desired interpolant profile is considered, and a rational approximation procedure based on the theory is proposed. This provides a tool for tuning the solution to specifications. The basic idea could also be applied to the case with bounded analytic interpolants.      

The Inverse Problem of Analytic Interpolation With Degree Constraint and Weight Selection for Control Synthesis

The minimizers of certain weighted entropy functionals are the solutions to an analytic interpolation problem with a degree constraint, and all solutions to this interpolation problem arise in this way by a suitable choice of weights. Selecting appropriate weights is pertinent to feedback control synthesis, where interpolants represent closed-loop transfer functions. In this paper we consider the correspondence between weights and interpolants in order to systematize feedback control synthesis with a constraint on the degree. There are two basic issues that we address: we first characterize admissible shapes of minimizers by studying the corresponding inverse problem, and then we develop effective ways of shaping minimizers via suitable choices of weights. This leads to a new procedure for feedback control synthesis.      

A new algorithm for a recursive construction of the minimal interpolation space

In this work, we introduce a new interpolation algorithm, based on a recursive method for computing Lagrange interpolants. This algorithm allows to construct recursively the minimal interpolation space (see [1]) with respect to a finite set of points. We also extend this recursive method to the osculatory interpolation problem.     

A new algorithm for a recursive construction of the minimal interpolation space

In this work, we introduce a new interpolation algorithm, based on a recursive method for computing Lagrange interpolants. This algorithm allows to construct recursively the minimal interpolation space (see [1]) with respect to a finite set of points. We also extend this recursive method to the osculatory interpolation problem.     

A one-pass algorithm for shape-preserving quadratic spline interpolation

Schumaker (1983) and McAllister and Roulier (1981) have proposed algorithms for shape-preserving interpolation using quadratic splines. The former requires the user to provide and perhaps to adjust estimates of the slope at the data points. Here we show that, for a particular slope estimation technique, the two methods are identical, and that in this case the Schumaker algorithm automatically generates shape-preserving interpolants. Furthermore, in case of convex data the slopes are improved iteratively to produce more visually pleasing curves.     

Weight Selection in Feedback Design With Degree Constraints

We present an approach for feedback design which is based on recent developments in analytic interpolation with a degree constraint. Performance is cast as an interpolation problem with bounded analytic functions. Minimizers of a certain weighted-entropy functional provide interpolants having degree less than the number of constraints. The choice of weight parameterizes all such bounded degree solutions. However, the relationship between the weights and the shape of corresponding transfer functions is not direct. Thus, in this paper we develop a formalism that guides weight selection.     

A generalized entropy criterion for Nevanlinna-Pick interpolationwith degree constraint

We present a generalized entropy criterion for solving the rational Nevanlinna-Pick problem for n+1 interpolating conditions and the degree of interpolants bounded by n. The primal problem of maximizing this entropy gain has a very well-behaved dual problem. This dual is a convex optimization problem in a finite-dimensional space and gives rise to an algorithm for finding all interpolants which are positive real and rational of degree at most n. The criterion requires a selection of a monic Schur polynomial of degree n. It follows that this class of monic polynomials completely parameterizes all such rational interpolants, and it therefore provides a set of design parameters for specifying such interpolants. The algorithm is implemented in a state-space form and applied to several illustrative problems in systems and control, namely sensitivity minimization, maximal power transfer and spectral estimation     

Boolesche zweidimensionale Lagrange-Interpolation

In this paper the Boolean method for approximation of multivariate functions developed by Gordon [4], [5] is systematically applied to bivariate Lagrange interpolation. Interpolation methods are considered whose interpolation projectors can be characterized by K-times (K ∈ ?) Boolean sums of tensor product Lagrange interpolation projectors. Using certain properties of Boolean Lagrange interpolation projectors we derive explicit representation formulas for the interpolants. After showing that the classical Biermann interpolation on a triangular mesh is a special case of Boolean Lagrange interpolation a method for the construction of Serendipity elements of arbitrary order is presented. This method provides a systematic generalization of the construction of special Serendipity elements proposed by Gordon-Hall [6]. Furthermore, we derive an explicit remainder representation formula for Boolean Lagrange interpolation. Finally, a list of generalized Serendipity elements of order N-1 (2≦N≦8) is presented.     

On the solutions of the rational covariance extension problem corresponding to pseudopolynomials having boundary zeros

In this note, we study the rational covariance extension problem with degree bound when the chosen pseudopolynomial of degree at most n has zeros on the boundary of the unit circle and derive some new theoretical results for this special case. In particular, a necessary and sufficient condition for a solution to be bounded (i.e., has no poles on the unit circle) is established. Our approach is based on convex optimization, similar in spirit to the recent development of a theory of generalized interpolation with a complexity constraint. However, the two treatments do not proceed in the same way and there are important differences between them which we discuss herein. An implication of our results is that bounded solutions can be computed via methods that have been developed for pseudopolynomials which are free of zeros on the boundary, extending the utility of those methods. Numerical examples are provided for illustration.     

Shape preservation of scientific data through rational fractal splines

Fractal interpolation is a modern technique in approximation theory to fit and analyze scientific data. We develop a new class of $\mathcal C ^1$ - rational cubic fractal interpolation functions, where the associated iterated function system uses rational functions of the form $\frac{p_i(x)}{q_i(x)},$ where $p_i(x)$ and $q_i(x)$ are cubic polynomials involving two shape parameters. The rational cubic iterated function system scheme provides an additional freedom over the classical rational cubic interpolants due to the presence of the scaling factors and shape parameters. The classical rational cubic functions are obtained as a special case of the developed fractal interpolants. An upper bound of the uniform error of the rational cubic fractal interpolation function with an original function in $\mathcal C ^2$ is deduced for the convergence results. The rational fractal scheme is computationally economical, very much local, moderately local or global depending on the scaling factors and shape parameters. Appropriate restrictions on the scaling factors and shape parameters give sufficient conditions for a shape preserving rational cubic fractal interpolation function so that it is monotonic, positive, and convex if the data set is monotonic, positive, and convex, respectively. A visual illustration of the shape preserving fractal curves is provided to support our theoretical results.     

Runge-Kutta-Nyström interpolants for the numerical integration of special second-order periodic initial-value problems

The theory of the phase-lag analysis for Runge-Kutta-Nyström methods and Runge-Kutta-Nyström interpolants is developed in this paper. Also a new Runge-Kutta-Nyström method with interpolation properties is developed to integrate second-order differential equations of the formu″(t)=f(t,u) when they possess an oscillatory solution.     

A recursive method for solving unconstrained tangentialinterpolation problems

An efficient recursive solution is presented for the one-sided unconstrained tangential interpolation problem. The method relies on the triangular factorization of a certain structured matrix that is implicitly defined by the interpolation data. The recursive procedure admits a physical interpretation in terms of discretized transmission lines. In this framework the generating system is constructed as a cascade of first-order sections. Singular steps occur only when the input data is contradictory, i.e., only when the interpolation problem does not have a solution. Various pivoting schemes can be used to improve numerical accuracy or to impose additional constraints on the interpolants. The algorithm also provides coprime factorizations for all rational interpolants and can be used to solve polynomial interpolation problems such as the general Hermite matrix interpolation problem. A recursive method is proposed to compute a column-reduced generating system that can be used to solve the minimal tangential interpolation problem     

Unit interpolation in H∞: Bounds of norm and degree of interpolants

This paper studies the problem of unit interpolation in H_∞. Specifically, bounds of the norm and degree of interpolants are obtained using the Nevanlinna-Pick interpolation theory. Also simpler bounds are given using the Poincaré metric. These results indicate that strong stabilization and simultaneous stabilization need a cautious approach if the system is ‘ill-conditioned’. In fact, it is demonstrated that the degree of stable compensator is not bounded for the class of plants with fixed degree. Also an example shows that there is a class of plants for which the sensitivity can be made small only if unstable compensators are used.     

An operator-theoretic approach to the mixed-sensitivity minimization problem

We consider the mixed-sensitivity minimization problem (scalar case). It gives rise to the so-called two-block problem on the algebra H^∞; we analyze this problem from an operator point of view, using Krein space theory. We obtain a necessary and sufficient condition for the uniqueness of the solution and a parameterization of all solutions in the non-uniqueness case. Moreover, an interpolation interpretation is given for the finite-dimensional case.     

Geometric interpolants with different degrees of smoothness

Geometric interpolation is a basic task in geometric modelling. In this paper, the geometric interpolant with different degrees of smoothness is introduced. The method provides the lower degree, flexile interpolation curves and construction is simple. Moreover, convexity, regularity and the construction of some special geometric interpolants are also discussed.     

Craig Interpolation with Clausal First-Order Tableaux

We develop foundations for computing Craig-Lyndon interpolants of two given formulas with first-order theorem provers that construct clausal tableaux. Provers that can be understood in this way include efficient machine-oriented systems based on calculi of two families: goal-oriented such as model elimination and the connection method, and bottom-up such as the hypertableau calculus. We present the first interpolation method for first-order proofs represented by closed tableaux that proceeds in two stages, similar to known interpolation methods for resolution proofs. The first stage is an induction on the tableau structure, which is sufficient to compute propositional interpolants. We show that this can linearly simulate different prominent propositional interpolation methods that operate by an induction on a resolution deduction tree. In the second stage, interpolant lifting, quantified variables that replace certain terms (constants and compound terms) by variables are introduced. We justify the correctness of interpolant lifting (for the case without built-in equality) abstractly on the basis of Herbrand’s theorem and for a different characterization of the formulas to be lifted than in the literature. In addition, we discuss various subtle aspects that are relevant for the investigation and practical realization of first-order interpolation based on clausal tableaux.

     

A unified, integral construction for coordinates over closed curves

We propose a simple generalization of Shephard's interpolation to piecewise smooth, convex closed curves that yields a family of boundary interpolants with linear precision. Two instances of this family reduce to previously known interpolants: one based on a generalization of Wachspress coordinates to smooth curves and the other an integral version of mean value coordinates for smooth curves. A third instance of this family yields a previously unknown generalization of discrete harmonic coordinates to smooth curves. For closed, piecewise linear curves, we prove that our interpolant reproduces a general family of barycentric coordinates considered by Floater, Hormann and Kós that includes Wachspress coordinates, mean value coordinates and discrete harmonic coordinates.     

New results on the rational covariance extension problem with degree constraint

A new theory for the rational covariance extension problem (with degree constraint), or simply the RCEP, has recently emerged with applications in high-resolution spectral estimation, speech synthesis and possibly new applications in time series analysis and system identification. This paper establishes some new theoretical results on the RCEP via an alternative analysis. In one result we show the bijective correspondence between denominator polynomials of non-strictly-positive solutions of the RCEP and the minimizers of a class of (strictly) convex functionals, associated with non-strictly-positive pseudopolynomials, defined on a subset of a finite dimensional space. This result leads to an alternative constructive proof of a theorem of Georgiou on complete parametrization of all solutions of the RCEP and a new geometric proof, with an extension to non-real interpolators, of a homeomorphism derived previously by Blomqvist, Fanizza and Nagamune. We then generalize this homeomorphism to also allow for variation in the covariance data. Our contribution in the generalization is allowing for non-strictly-positive pseudopolynomials. For the special case of strictly positive pseudopolynomials, a stronger property of diffeomorphism (in the context of the Nevanlinna–Pick interpolation with degree constraint) has been shown earlier by Byrnes and Lindquist. The results of this paper have direct analogues to Nevanlinna–Pick interpolation with degree constraint which is of interest to the robust control community.     

An Interpolating Sequent Calculus for Quantifier-Free Presburger Arithmetic

Craig interpolation has become a versatile tool in formal verification, used for instance to generate program assertions that serve as candidates for loop invariants. In this paper, we consider Craig interpolation for quantifier-free Presburger arithmetic (QFPA). Until recently, quantifier elimination was the only available interpolation method for this theory, which is, however, known to be potentially costly and inflexible. We introduce an interpolation approach based on a sequent calculus for QFPA that determines interpolants by annotating the steps of an unsatisfiability proof with partial interpolants. We prove our calculus to be sound and complete. We have extended the Princess theorem prover to generate interpolating proofs, and applied it to a large number of publicly available Presburger arithmetic benchmarks. The results document the robustness and efficiency of our interpolation procedure. Finally, we compare the procedure against alternative interpolation methods, both for QFPA and linear rational arithmetic.     

Cardinal interpolation with differences of tempered functions

In this paper, we investigate the existence and uniqueness of cardinal interpolants associated with functions arising from the k^th order iterated discrete Laplacian ^k applied to certain radial basis functions. In particular, we concentrate on determining, for a given radial function Φ, which functions ^kΦ give rise to cardinal interpolation operators which are both bounded and invertible ℓ₂ (Z³). In addition to solving the cardinal interpolation problem (CIP) associated with such functions ^kΦ, our approach provides a unified framework and simpler proofs for the CIP associated with polyharmonic splines and Hardy multiquadrics.