Systolic computation of interpolating polynomials

Several time-optimal and spacetime-optimal systolic arrays are presented for computing a process dependence graph corresponding to the Aitken algorithm. It is shown that these arrays also can be used to compute the generalized divided differences, i.e., the coefficients of the Hermite interpolating polynomial. Multivariate generalized divided differences are shown to be efficiently computed on a 2-dimensional systolic array. The techniques also are applied to the Neville algorithm, producing similar results.     

On the complete instability of interval polynomials

In this paper, we study “complete instability” of interval polynomials, which is the counterpart of classical robust stability. That is, the objective is to check if all polynomials in the family are unstable. If not, a subsequent goal is to find a stable polynomial. To this end, we first propose a randomized algorithm which is based on a (recursive) necessary condition for Hurwitz stability. The second contribution of this paper is to provide a probability-one estimate of the volume of stable polynomials. These results are based on a combination of deterministic and randomized methods. Finally, we present two numerical examples and simulations showing the efficiency of the proposed methodology for small and medium-size problems.     

Some algorithms for interval interpolating polynomial

Some algorithms for the computation of an Interval Interpolating Polynomial have been proposed. The algorithms have been compared with the existing algorithms. One of the algorithms has been shown to be superior to all others.     

On a root distribution criterion for interval polynomials

H. Kokame and T. Mori (1991) and C.B. Soh (1990) derived conditions under which an interval polynomial has a given number of roots in the open left-half plane and the other roots in the open right-half plane. However, the one-shot-test approach using Sylvester's resultant matrices and Bezoutian matrices implies that the implemented conditions are only sufficient (not necessary) for an interval polynomial to have at least one root in the open left-half plane and open right-half plane. Alternative necessary and sufficient conditions, which only require the root locations of four polynomials to check the root distribution of an interval polynomial, are presented     

On interval polynomials with no zeros in the unit disc

We give a necessary condition for an interval polynomial to have no zeros in the closed unit disc. The condition is expressed in terms of the two first intervals     

On certain properties of Hurwitz determinants for interval polynomials

Consider the stable interval polynomialsF _n (z)=z ⁿ +a ₁ z ^n?1 +...+a _n?1 z+a _n wherea _i are real numbers, satisfying the inequalities α _i ≤a _i ≤β _i ,i=1,2, ...,n. In this paper we prove that mind _n (a) is the same foraεD andaεD ₁, whereD=[α₁, β₁]×[α₂, β₂]×...×[α _n , β _n ],D={(γ₁, γ₂,...γ _n )∈D:γ₁=α₁∨γ₁=β₁,... γ _n =α _n ∨γ _n =β _n }d _n (a)=detH, aεD, H—Hurwitz matrix for the polynomialF _n (z).     

State-space algorithm for the computation of superoptimal matrix interpolating functions

A state-space algorithm is studied which generates the (unique) superoptimal Nehari extension of a general rational matrix $. The procedure is to use a set of all-pass transformations to sequentially minimize each frequency-dependent singular value (of the interpolating function) in a dimension peeling algorithm. These all-pass transformations are determined by the maximal Schmidt pairs of a sequence of Hankel operators. The process terminates when the original problem is reduced to one of rank one; at this stage all the available degrees of freedom have been exhausted. The work is an extension of that by Young (1986) and gives a ‘concrete’ state-space implementation of his operator-theoretic arguments. In addition, bounds are given on the minimum achievable values for s₁ ^∞ (E) = sup_ωεRSi (E(jω)), i = 1, 2,..., rank (G₀), and also the McMillan degree of the final superoptimal extension. Here S_i.(.) denotes the ith singular value of a (frequency-dependent) matrix, and the numbering is taken to be in decreasing order of magnitude. The algorithm has the property that it may be stopped after minimizing s_i ^∞ (.),i = 1. 2,...,l< rank (G₀) if it continues further it is deemed ‘not worth it’ in some sense. A premature termination of the algorithm carries with it an expected saving in computational effort and a predictable reduction in the degree of the extension. A shortened version of the present work has already appeared in work by Limebeeref al, (1987).     

Convergence property of interval matrices and interval polynomials

In association with robust control-system design and analysis, the Hurwitz property of interval matrices and interval polynomials has recently been actively investigated. However, its discrete counterpart, the convergence property, has seemingly not been much discussed. In this paper, this property is studied in comparison with the Hurwitz counterpart. Some conditions under which interval matrices or interval polynomials are convergent are derived.     

Aperiodic property of interval polynomials

An examination is made of the aperiodic property of interval polynomials. The authors also characterize the zero locations of aperiodic interval polynomials. Examples are given that clarify the points made     

Schur stability of interval polynomials

A method for checking the Schur stability of interval polynomials is presented. The numbers of critical vertex and edge polynomials that are sufficient for inferring robust Schur stability are obtained. It is shown that the critical edges can be greatly reduced to the order of 2 n²     

Damping margins of interval polynomials

The zero locations of interval polynomials are examined. In particular, it is shown that a family of interval polynomials will have zeros only in the left sector if the real and imaginary parts of four specially constructed complex polynomials have an interlacing real zero property. This is significant for the analysis of uncertain systems, as the computation cost associated with checking the zero locations of interval polynomials will be greatly reduced. The results presented can be readily extended to more general stability regions where the real and imaginary parts of the polar plot are polynomial functions     

Schur stability of interval polynomials

In this note we consider real interval polynomials of degree n whose roots are required to lie in the unit disc. The main result of the paper is the following. There exists a finite partition

Equation pending

so that when w_i < w < w_i+l the set of vertices of the polynomial box generating the extreme points of the corresponding value set does not depend on w. The number of vertices is 2n. An algorithm that selects vertices generating extreme points of the value sets, and a formula for the number k, are provided.     

Projectors, solvents, interpolating polynomials and lambda matrices

This paper describes the relationships between projectors, solvents, interpolating polynomials and partial fraction expansions. Properties of the projections as well as the definition and properties of a set of interpolating polynomials are given and the application of the polynomials to partial fraction expansions is discussed.     

Effective computation of optimal stability polynomials

Abstract The construction of stable explicit multistage Runge-Kutta methods in 1950–1960 stumbled over a certain extremal problem for polynomials. The solution to this problem is known as the optimal stability polynomial and its computation is notoriously difficult. We propose a new method for the effective evaluation of optimal stability polynomials which is based on the explicit analytical representation of the solution. The main feature of the method is its independence of the computational complexity of the degree of the solution.     

On interval arithmetic range approximation methods of polynomials and rational functions

Interval arithmetics seems to offer a variety of simple numerical approximation methods well applicable in computational algorithms of curves and sculptured surfaces. In this work we analyse and compare several interval arithmetic methods to approximate the range of polynomials and rational functions.     

Robust Schur stability of interval polynomials

The investigation of Schur stability using a Kharitonov parameter box is discussed. The discrete counterpart of Kharitonov's theorem is obtained. The solution is based on the use of the Hollot-Bartlett-Huang theorem and the Hollott-Bartlett theorem. This made it possible to test for Schur stability only a subset of the edges. The Schur testing of the required edges of the cube is performed using three different methods, namely, the critical edge polynomial, edge stability as an eigenvalue problem, and edge stability using colinearity conditions. Comparison of these three methods is presented. It is believed that, with the Schur testing of the minimum number of edges and the use of the critical stability constraints, minimum computational effort can be achieved     

On some interval methods for algebraic,exponential and trigonometric polynomials

New inclusion methods for the simultaneous determination of the zeros of algebraic, exponential and trigonometric polynomials are presented. These methods are realized in real interval arithmetic and do not use any derivatives. Using Weierstrass' correction some modified methods with the increased convergence rate are constructed. Convergence analysis and numerical example are included.     

Comments on the computation of interval Routh approximants

In Bandyopadhyay et al. (1994, 1997), the Routh approximation method was extended to derive reduced-order interval models for linear interval systems. In this paper, the authors show that: 1) interval Routh approximants to a high-order interval transfer function depend on the implementation of interval Routh expansion and inversion algorithms; 2) interval Routh expansion algorithms cannot guarantee the success in generating a full interval Routh array; 3) some interval Routh approximants may not be robustly stable even if the original interval system is robustly stable; and 4) an interval Routh approximant is in general not useful for robust controller design because its dynamic uncertainties (in terms of robust frequency responses) do not cover those of the original interval system