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     

Matrix-valued Nevanlinna-Pick interpolation with complexity constraint: an optimization approach

Over the last several years, a new theory of Nevanlinna-Pick interpolation with complexity constraint has been developed for scalar interpolants. In this paper we generalize this theory to the matrix-valued case, also allowing for multiple interpolation points. We parameterize a class of interpolants consisting of "most interpolants" of no higher degree than the central solution in terms of spectral zeros. This is a complete parameterization, and for each choice of interpolant we provide a convex optimization problem for determining it. This is derived in the context of duality theory of mathematical programming. To solve the convex optimization problem, we employ a homotopy continuation technique previously developed for the scalar case. These results can be applied to many classes of engineering problems, and, to illustrate this, we provide some examples. In particular, we apply our method to a benchmark problem in multivariate robust control. By constructing a controller satisfying all design specifications but having only half the McMillan degree of conventional H/sup /spl infin// controllers, we demonstrate the advantage of the proposed method.     

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.      

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.     

State space realizations of rational interpolants with prescribed poles

We give a generic algorithm for computing rational interpolants with prescribed poles. The resulting rational function is expressed in the so-called Newton form. State space realizations for this expression of rational functions are given. Our main tool for finding state space realizations is Fuhrmann's shift realization theory from which we obtain concrete realizations by introducing suitable bases of the state space and expressing the abstract operators with respect to these bases in matrix form.     

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.     

二元向量有理插值的NEVILLE计算公式

１．引 言 在机械振动的数据分析等方面，向量值函数的有理插值与逼近有着广泛的应用．Ｇｒａｖｅｓ－Ｍｏｒｒｉｓ系统地研究了一元向量值函数的有理插值问题［１－３］．朱功勤等自 １９９０年开始将一元的结果成功地推广到了二元的情形［４－７］．设由平面上相异点组成的点集为其对应的有限向量集为［５］给出了其中满足向量值函数的有理插值问题与下述向量的逆密切相关，其中ｆ＝（ｆ１，ｆ１，…，ｆｄ）Ｒｄ并且对于（１．４）的特殊情况，约定称ｄ维向量值多项式的次数为ｎ且记为｛Ｎ（ｘ，ｙ）｝＝ｎ，如果对任意ｊ＝１，２，…，…     

Analytic approach to intersection of all piecewise parametric rational cubic curves

Elimination theory is applied to develop an analytic approach to the intersection of any two piecewise parametric rational cubic curves. By splitting the general intersection problem into several simple cases, this algorithm reduces the intersection problem to the problem of finding the roots of a single polynomial in one variable of minimal degree. This technique is fast, automatic, efficient and robust.     

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.     

Hermite interpolation: The barycentric approach

The barycentric formulas for polynomial and rational Hermite interpolation are derived; an efficient algorithm for the computation of these interpolants is developed. Some new interpolation principles based on rational interpolation are discussed.     

Rational hodographs

An equation for the hodograph control points for a rational degree n Bézier curve is derived. If, for a rational Bézier curve with positive weights, all weights are set to one, then the hodograph for this integral Bézier curve will bound the tangent directions of the rational curve.     

Using linear algebra in decomposition of Farkas interpolants

The use of propositional logic and systems of linear inequalities over reals is a common means to model software for formal verification. Craig interpolants constitute a central building block in this setting for over-approximating reachable states, e.g. as candidates for inductive loop invariants. Interpolants for a linear system can be efficiently computed from a Simplex refutation by applying the Farkas’ lemma. However, these interpolants do not always suit the verification task—in the worst case, they can even prevent the verification algorithm from converging. This work introduces the decomposed interpolants, a fundamental extension of the Farkas interpolants, obtained by identifying and separating independent components from the interpolant structure, using methods from linear algebra. We also present an efficient polynomial algorithm to compute decomposed interpolants and analyse its properties. We experimentally show that the use of decomposed interpolants in model checking results in immediate convergence on instances where state-of-the-art approaches diverge. Moreover, since being based on the efficient Simplex method, the approach is very competitive in general.

     

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.     

Efficient Craig interpolation for linear Diophantine (dis)equations and linear modular equations

The use of Craig interpolants has enabled the development of powerful hardware and software model checking techniques. Efficient algorithms are known for computing interpolants in rational and real linear arithmetic. We focus on subsets of integer linear arithmetic. Our main results are polynomial time algorithms for obtaining interpolants for conjunctions of linear Diophantine equations, linear modular equations (linear congruences), and linear Diophantine disequations. We also present an interpolation result for conjunctions of mixed integer linear equations. We show the utility of the proposed interpolation algorithms for discovering modular/divisibility predicates in a counterexample guided abstraction refinement (CEGAR) framework. This has enabled verification of simple programs that cannot be checked using existing CEGAR based model checkers. This paper is an extended version of [14]. This research was sponsored by the Gigascale Systems Research Center (GSRC), Semiconductor Research Corporation (SRC), the National Science Foundation (NSF), the Office of Naval Research (ONR), the Naval Research Laboratory (NRL), the Defense Advanced Research Projects Agency (DARPA), the Army Research Office (ARO), and the General Motors Collaborative Research Lab at CMU. The views and conclusions contained in this document are those of the author and should not be interpreted as representing the official policies, either expressed or implied, of GSRC, SRC, NSF, ONR, NRL, DARPA, ARO, GM, or the U.S. government.     

Blended Hermite interpolants

In (Röschel, l997) B-spline technique was used for blending of Lagrange interpolants. In this paper we generalize this idea replacing Lagrange by Hermite interpolants. The generated subspline b(t) interpolates the Hermite input data consisting of parameter values t_i and corresponding derivatives a_i,j, j=0,…,_i−1, and is called blended Hermite interpolant (BHI). It has local control, is connected in affinely invariant way with the input and consists of integral (polynomial) segments of degree 2·k−1, where k−1max{_i}−1 denotes the degree of the B-spline basis functions used for the blending. This method automatically generates one of the possible interpolating subsplines of class C^k−1 with the advantage that no additional input data is necessary.     

Positive interpolation with rational quadratic splines

A necessary and sufficient criterion is presented under which the property of positivity carry over from the data set to rational quadratic spline interpolants. The criterion can always be satisfied if the occuring parameters are properly chosen.     

A Probabilistic Algorithm to Test Local Algebraic Observability in Polynomial Time

The following questions are often encountered in system and control theory. Given an algebraic model of a physical process, which variables can be, in theory, deduced from the input–output behaviour of an experiment? How many of the remaining variables should we assume to be known in order to determine all the others? These questions are parts of thelocal algebraic observability problem which is concerned with the existence of a non-trivial Lie subalgebra of model’s symmetries letting the inputs and the outputs be invariant.We present a probabilistic seminumerical algorithm that proposes a solution to this problem in polynomial time. A bound for the necessary number of arithmetic operations on the rational field is presented. This bound is polynomial in the complexity of evaluation of the model and in the number of variables. Furthermore, we show that the size of the integers involved in the computations is polynomial in the number of variables and in the degree of the system. Last, we estimate the probability of success of our algorithm.     

Improvement of the Degree Setting in Gosper's Algorithm

A detailed study of the degree setting for Gosper's algorithm for indefinite hypergeometric summation is presented. In particular, we discriminate between rational and proper hypergeometric input. As a result, the critical degree bound can be improved in the former case.     

Computing Contour Trees for 2D Piecewise Polynomial Functions

Contour trees are extensively used in scalar field analysis. The contour tree is a data structure that tracks the evolution of level set topology in a scalar field. Scalar fields are typically available as samples at vertices of a mesh and are linearly interpolated within each cell of the mesh. A more suitable way of representing scalar fields, especially when a smoother function needs to be modeled, is via higher order interpolants. We propose an algorithm to compute the contour tree for such functions. The algorithm computes a local structure by connecting critical points using a numerically stable monotone path tracing procedure. Such structures are computed for each cell and are stitched together to obtain the contour tree of the function. The algorithm is scalable to higher degree interpolants whereas previous methods were restricted to quadratic or linear interpolants. The algorithm is intrinsically parallelizable and has potential applications to isosurface extraction.     

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.