Robust stability of discrete-time systems using delta operators

The robust stability of discrete-time systems formulated in terms of the delta (δ) operator is discussed. That is, given the nominal characteristic equation P(δ) of a discrete-time system, it is of interest to know how much the coefficients can be perturbed while preserving stability. A procedure to obtain the maximum intervals for a perturbed polynomial P(δ) to still be stable is presented     

Strict aperiodic property of polynomials with perturbedcoefficients

Let a family of polynomials be P(s)=t ₀sⁿ+t₁s ⁿ±¹ + . . . + t_n where 0<a_j⩽t_j⩽b _j. V.L. Kharitonov (1978) derived a necessary and sufficient condition for the above equation to have only zeros in the open left-half plane. The present authors derive some similar results for the equation to be strictly aperiodic (distinct real roots)     

Integral action in robust adaptive control

Conditions are studied under which integral action in robust adaptive control is soundly based. The method of analysis amounts to verifying that the key conditions needed for convergence are satisfied. A simple strategy is described for choosing the integral constant and global convergence is established for the resultant algorithm. This illustrates a proof paradigm which could be similarly applied to other problems. The principal assumptions used are that the plant, when augmented by an integrator, has a known degree of controllability and that an overbounding function is known for the unmodeled system response. The continuous-time case is treated, but the corresponding discrete-time results follow mutatis mutandis by simply replacing p =d/dt by δ=q-1/Δ, L ₂ by l₂, ∫ by Σ, and so on     

Robust stability under structured and unstructured perturbations

The problem of robust stability for linear time-invariant single-output control systems subject to both structured (parametric) and unstructured (H_∞) perturbations is studied. A generalization of the small gain theorem which yields necessary and sufficient conditions for robust stability of a linear time-invariant dynamic system under perturbations of mixed type is presented. The solution involves calculating the H_∞ -norm of a finite number of extremal plants. The problem of calculating the exact structured and unstructured stability margins is then constructively solved. A feedback control system containing a linear time-invariant plant which is subject to both structured and unstructured perturbations is considered. The case where the system to be controlled is interval is treated, and a nonconservative, easily verifiable necessary and sufficient condition for robust stability is given. The solution is based on the extremal of a finite number of line segments in the plant parameter property of a finite number of line segments in the plant parameter space along which the points closest to instability are encountered     

Efficient algorithms for system diagnosis with both processor andcomparator faults

For the comparison-based self-diagnosis of multiprocessor systems, an extended model that considers both processor and comparator faults is presented. It is shown that in this model the system diagnosability is t⩽Zδ/2Z, where δ is the minimum vertex degree of the system graph. However, if the number of faulty comparators is assumed not to exceed the number of faulty processors, the diagnosability of the model reaches t⩽δ. An optimal O(|E|) algorithm, where E is the set of comparators, is given for identifying all faulty processors and comparators, provided that the total number of faulty components does not exceed the system diagnosability, and an O(|E|)² algorithm for the case t⩽δ is also presented. These efficient algorithms determine the faulty processors by calculating each processor's weight, which is mainly defined by the number of adjacent relative tests stating `agreement'. After sorting the processors according to their weights, the algorithms determine all faulty components by separating the sorted processor list     

Damping ratio of polynomials with perturbed coefficients

Let a family of polynomials be P(s)=t ₀Sⁿ+t₁s ^n-1 . . .+t_n where O<α _j⩽t_j⩽β. Recently, C.B. Soh and C.S. Berger have shown that a necessary and sufficient condition for this equation to have a damping ratio of φ is that the 2ⁿ⁺¹ polynomials in it which have t_k=α_k or t_k=β_k have a damping ratio of φ. The authors derive a more powerful result requiring only eight polynomials to be Hurwitz for the equation to have a damping ratio of φ using Kharitonov's theorem for complex polynomials     

A note on a classical bound for the moduli of all zeros of apolynomial

Considers the monic polynomial f(z):=z ⁿ+a_n-1z^n-1+. . .+a₀ in the complex variable z with complex coefficients. Under the assumption that the nonleading coefficients of f lie in the disk |z|⩽A the authors give an estimate for the smallest disk |z|⩽R containing all zeros of f. The estimate has a guaranteed precision of a few percent. They proceed similarly to obtain a zero-free disk |z |⩽r     

Linear and nonlinear algorithms for identification in H∞ with error bounds

A linear algorithm and a nonlinear algorithm for the problem of system identification in H_∞ posed by Helmicki et al. (1990) for discrete-time systems are presented. The authors derive some error bounds for the linear algorithm which indicate that it is not robustly convergent. However, the worst-case identification error is shown to grow as log(n), where n is the model order. A robustly convergent nonlinear algorithm is derived, and bounds on the worst-case identification error (in the H_∞ norm) are obtained     

The stability of a family of polynomials can be deduced from afinite number 0(k3) of frequency checks

Let φ(s,a)=φ₀(s,a)+ a₁φ₁(s)+a₂ φ₂(s)+ . . .+a_kφ _k(s)=φ₀(s)-q(s, a) be a family of real polynomials in s, with coefficients that depend linearly on parameters a_i which are confined in a k-dimensional hypercube Ω_a . Let φ₀(s) be stable of degree n and the φ_i(s) polynomials (i⩾1) of degree less than n. A Nyquist argument shows that the family φ(s) is stable if and only if the complex number φ₀(jω) lies outside the set of complex points -q(jω,Ω_a) for every real ω. In a previous paper (Automat. Contr. Conf., Atlanta, GA, 1988) the authors have shown that -q(jω,Ω_a ), the so-called `-q locus', is a 2k convex parpolygon. The regularity of this figure simplifies the stability test. In the present paper they again exploit this shape and show that to test for stability only a finite number of frequency checks need to be done; this number is polynomial in k, 0(k³), and these critical frequencies correspond to the real nonnegative roots of some polynomials     

Interconnection of nonlinear causal systems

For nonlinear systems it is not a mathematically obvious fact that the simplest feedback system yields equations which are solvable, even when the gain in the loop is ⩽1. The authors treat this and more general issues. For example, it is not known (for a continuous-time system) if unity feedback for a plant C with gain <1 produces a well-posed system. It is shown that if the gain of C is <1 and C also loses sufficient efficiency at high frequency, then indeed the feedback system is well posed. The hypothesis that the gain of C is <1 can be replaced by the reasonable assumption that C saturates on large enough signals, and well posedness is still obtained. This approach also applies directly to electrical circuit connections. It is proved that rather general connections of amplifiers are well posed under the assumption that the amplifiers saturate and that they lose efficiency at high frequency     

A qualitative bound in robustness of stabilization by statefeedback

It is proved that placing the poles of a linear time-invariant system arbitrarily far to the left of the imaginary axis is not possible if small perturbations in the model coefficients are taken into account. Given a nominal controllable system (A₀, B ₀) with one input and at least two states and an open ball around B₀ (no matter how small), there exists a real number γ and a perturbation B within that ball such that for any feedback matrix K placing the eigenvalues of A ₀+B₀K to the left of Res=γ, there is an eigenvalue of A₀+BK with real part not less than γ     

Efficient algorithms for list ranking and for solving graphproblems on the hypercube

A hypercube algorithm to solve the list ranking problem is presented. Let n be the length of the list, and let p be the number of processors of the hypercube. The algorithm described runs in time O(n/p) when n=Ω(p ^1+ε) for any constant ε>0, and in time O(n log n/p+log³ p) otherwise. This clearly attains a linear speedup when n=Ω(p ^1+ε). Efficient balancing and routing schemes had to be used to achieve the linear speedup. The authors use these techniques to obtain efficient hypercube algorithms for many basic graph problems such as tree expression evaluation, connected and biconnected components, ear decomposition, and st-numbering. These problems are also addressed in the restricted model of one-port communication     

Sensitivity and robust stability of general input-output systems

The author considers a general model of an input-output system that is governed by nonlinear operator equations which relate the input, the state, and the output of the system. This model encompasses feedback systems as a special case. Assuming that the governing equations depend on a parameter A which is allowed to vary in a neighborhood of a nominal value A₀ in a linear space, the author studies the dependence of the system behavior on A. A system is considered insensitive if, for any fixed input, the output depends continuously on A. Similarly, the system is robust if it is stable for each A in a neighborhood of A₀. Stability is defined as an appropriate continuity of the input-output operator. The results give various sufficient conditions for insensitivity and robustness. Applications of the theory are discussed, including the estimation of the difference of operator inverses, and the insensitivity and robust stability of a Hilbert network, a feedback-feedforward system, a traditional feedback system, and a time-varying dynamical system described by a linear vector differential equation on (0, ∞)     

Some new properties of the structured singular value

J.C. Doyle et al. (1982) have shown that a necessary and sufficient condition for robust stability or robust performance in the H^∞-frame work may be formulated as a bound on the structured singular value (μ) of a specific matrix M which includes information on the system model, the controller, the model uncertainty, and the performance specifications. Often it is desirable to express the robust stability and performance conditions as norm bounds on transfer matrices (T) which are of direct interest to the engineer, e.g. sensitivity or complementary sensitivity. The present paper shows how to derive bounds on σ(T) from bounds on μ(M)     

On time mapping of uniform dependence algorithms into lowerdimensional processor arrays

Most existing methods of mapping algorithms into processor arrays are restricted to the case where n-dimensional algorithms, or algorithms with n nested loops, are mapped into (n-1)-dimensional arrays. However, in practice, it is interesting to map n-dimensional algorithms into (k-1)-dimensional arrays where k<n. A computational conflict occurs if two or more computations of an algorithm are mapped into the same execution time. Based on the Hermite normal form of the mapping matrix, necessary and sufficient conditions are derived to identify mapping without computational conflicts. These conditions are used to find time mappings of n-dimensional algorithms into (k-1)-dimensional arrays, k<n , without computational conflicts. For some applications, the mapping is time-optimal     

Necessary and sufficient conditions for mixedH2 and H∞ optimal control

It is shown that D.S. Bernstein and W.M. Hadad's (ibid., vol.34, no.3, p.293, 1989) necessary condition for full-order mixed H ₂ and H_∞ optimal control is also sufficient, and that J.C. Doyle et al.'s (Proc. Amer. Control Conf., p.2065, 1989) sufficient condition for full-order mixed H₂ and H_∞ optimal control is also necessary. They are duals of one another     

On a weaker notion of controllability of a language K withrespect to a language L

A necessary and sufficient condition for a prefix-closed language K⊆Σ* to be controllable with respect to another prefix-closed language L⊆Σ* is that K⊆ L. A weaker notion of controllability where it is not required that K⊆L is considered here. If L is the prefix-closed language generated by a plant automaton G, then essentially there exists a supervisor Θ that is complete with respect to G such that L(Θ|G)=K ∩ L if and only if K is weakly controllable with respect to L. For an arbitrary modeling formalism it is shown that the inclusion problem is reducible to the problem of deciding the weaker notion of controllability. Therefore, removing the requirement that K ⊆ L from the original definition of controllability does not help the situation from a decidability viewpoint. This observation is then used to identify modeling formalisms that are not viable for supervisory control of the untimed behaviors of discrete-event dynamic systems     

Decoupling of square singular systems via proportional statefeedback

Necessary and sufficient conditions for the decoupling of a solvable square singular system Ex˙(t)=Ax(t)+Bu(t ) with output y(t)=Dx(t), through an admissible control law of the form u(t)=Kx(t)+Hr(t) where H is a square nonsingular matrix. It has been shown that for a given singular system that satisfies these conditions, a propagational state feedback exists for which the system's transfer function is a diagonal, nonsingular, and proper rational matrix. The proofs of the main results are constructive and provide a procedure for computing an appropriate proportional state feedback     

Linear systems with state and control constraints: the theory andapplication of maximal output admissible sets

The initial state of an unforced linear system is output admissible with respect to a constraint set Y if the resulting output function satisfies the pointwise-in-time condition y(t)∈Y, t⩾0. The set of all possible such initial conditions is the maximal output admissible set O_∞. The properties of O_∞ and its characterization are investigated. In the discrete-time case, it is generally possible to represent O_∞ or a close approximation of it, by a finite number of functional inequalities. Practical algorithms for generating the functions are described. In the continuous-time case simple representations of the maximal output admissible set are not available, however, it is shown that the discrete-time results may be used to obtain approximate representations     

Damping margins of polynomials with perturbed coefficients

Considers the polynomial P(s)=t₀ Sⁿ+t₁ S^n-1 +···+t_n where 0<a _j⩽t_j⩽b_j. Recently, V.L. Kharitonov (1978) derived a necessary and sufficient condition for this polynomial to have only zeros in the open left-half plane. Two lemmas are derived to investigate the existence of theorems similar to the theorem of Kharitonov. Using these lemmas, the theorem of Kharitonov is generalized for P(s) to have only zeros within a sector in the complex plane. The aperiodic case is also considered