QFT template generation for time-delay plants based on zero-inclusion test

Plant template generation is the key step in applying quantitative feedback theory (QFT) to design robust control for uncertain systems. In this paper we propose a technique for generating plant templates for a class of linear systems with an uncertain time delay and affine parameter perturbations in coefficients. The main contribution lies in presenting a necessary and sufficient condition for the zero inclusion of the value set f(T,Q)={f(τ,q): τT[τ⁻,τ⁺], qQ∏_k=0^m−1[q_k⁻,q_k⁺]}, where f(τ,q)=g(q)+h(q)e^−jτω*, g(q) and h(q) are both complex-valued affine functions of the m-dimensional real vector q, and ω^* is a fixed frequency. Based on this condition, an efficient algorithm which involves, in the worst case, evaluation of m algebraic inequalities and solution of m2^m−1 one-variable quadratic equations, is developed for testing the zero inclusion of the value set f(T,Q). This zero-inclusion test algorithm allows one to utilize a pivoting procedure to generate the outer boundary of a plant template with a prescribed accuracy or resolution. The proposed template generation technique has a linear computational complexity in resolution and is, therefore, more efficient than the parameter gridding and interval methods. A numerical example illustrating the proposed technique and its computational superiority over the interval method is included.     

Stable polyhedra in parameter space

A typical uncertainty structure of a characteristic polynomial is P(s)=A(s)Q(s)+B(s) with A(s) and B(s) fixed and Q(s) uncertain. In robust controller design Q(s) may be a controller numerator or denominator polynomial; an example is the PID controller with Q(s)=K_I+K_Ps+K_Ds². In robustness analysis Q(s) may describe a plant uncertainty. For fixed imaginary part of Q(jω), it is shown that Hurwitz stability boundaries in the parameter space of the even part of Q(jω) are hyperplanes and the stability regions are convex polyhedra. A dual result holds for fixed real part of Q(jω). Also σ-stability with the real parts of all roots of P(s) smaller than σ is treated.Under the above conditions, the roots of P(s) can cross the imaginary axis only at a finite number of discrete “singular” frequencies. Each singular frequency generates a hyperplane as stability boundary. An application is robust controller design by simultaneous stabilization of several representatives of A(s) and B(s) by a PID controller. Geometrically, the intersection of convex polygons must be calculated and represented tomographically for a grid on K_P.     

H ∞ Optimal control

Our aim in this paper is to develop a new approach for solving the H ^∞ optimal control problem where the feedback arrangement takes the form of a linear fractional transformation. The paper is in two parts. In Part 1, a basic kind of model-matching problem is considered: given rational matrices M(s) and N(s), the H ^∞-norm of an error function defined as E(s)=M(s) – N(s)Q(s) is minimized (or bounded) subject to E(s) and Q(s) being stable. Closed-form state-space characterizations are obtained for both E(s) and Q(s). The results established here will be used in Part 2 of the paper (Hung 1989) to solve the H ^∞ optimal control problem.     

Inversion Problems in theq-Hahn Tableau

If { P_n(x;q)}_nis a family of polynomials belonging to the q -Hahn tableau then each polynomial of this family can be written as P_n(x;q) = ∑_{m = 0}ⁿD_m(n)_m(x) where _m(x) stands for (x;q)_mor x^m. In this paper we solve the corresponding inversion problem, i.e. we find the explicit expression for the coefficients I_m(n) in the expansion _n(x) = ∑_{m = 0}ⁿI_m(n)P_m(x;q).     

Asymptotic behavior of nonoscillatory solutions of neutral difference equations

The authors consider the m^th-order neutral difference equation D_m(y(n) + p(n)y(n − k) + q(n)f(y(σ(n))) = e(n), where m ≥ 1, {p(n)}, {q(n)}, {e(n)}, and {a₁(n)}, {a₂(n)}, …, {a_m−1(n)} are real sequences, a_i(n) > 0 for i = 1,2,…, m−1, a_m(n) ≡ 1, D₀z(n) = y(n)+p(n)y(n − k), D_iz(n) = a_i(n)ΔD_i−1z(n) for i = 1,2, …, m, k is a positive integer, {σ(n)} → ∞ is a sequence of positive integers, and R → R is continuous with u f(u) > 0 for u ≠ 0. In the case where {q(n)} is allowed to oscillate, they obtain sufficient conditions for all bounded nonoscillatory solutions to converge to zero, and if {q(n)} is a nonnegative sequence, they establish sufficient conditions for all nonoscillatory solutions to converge to zero. Examples illustrating the results are included throughout the paper.     

Numerical Computation of the Least Common Multiple of a Set of Polynomials

The paper presents a number of properties of the least common multiple (LCM) m(s) of a given set of polynomials P. These results lead to the formulation of a new procedure for computing the LCM that avoids the computation of roots. This procedure involves the computation of the greatest common divisor (GCD) z(s) of a set of polynomials T derived from P, and the factorisation of the product of the original set P, p(s) as p(s) = m(s)·z(s). The symbolic procedure leads to a numerical one, where robust methods for the computation of GCD are first used. In this numerical method the approximate factorisation of polynomials is an important part of the overall algorithm. The latter problem is handled by studying two associated problems: evaluation of order of approximation and the optimal completion problem. The new method provides a robust procedure for the computation of LCM and enables the computation of approximate values, when the original data are inaccurate.     

Semantics of sub-probabilistic programs

The aim of this paper is to extend the probabilistic choice in probabilistic programs to sub-probabilistic choice, i.e., of the form (p)P ^⋈(q)Q where p + q ⩽ 1. It means that program P is executed with probability p and program Q is executed with probability q. Then, starting from an initial state, the execution of a sub-probabilistic program results in a sub-probability distribution. This paper presents two equivalent semantics for a sub-probabilistic while-programming language. One of these interprets programs as sub-probabilistic distributions on state spaces via denotational semantics. The other interprets programs as bounded expectation transformers via wp-semantics. This paper proposes an axiomatic systems for total logic, and proves its soundness and completeness in a classical pattern on the structure of programs.     

Symbolic Transformations in the Problem of Analytic Continuation of the Hypergeometric Function p F p – 1(z) to the Neighborhood of the Point z = 1 in the Logarithmic Case

A method of analytic continuation of the generalized hypergeometric function _p F _{p – 1}(a; b; z),p > 2, to the neighborhood of the singular point z = 1 in the logarithmic case is developed. The singular component of the function is obtained in an explicit form by means of asymptotic methods and efficient symbolic transformations, and the regular part is found with the help of the finite element and collocation methods.     

On Factorization of Analytic Functions and Its Verification

An interval method for finding a polynomial factor of an analytic function f(z) is proposed. By using a Samelson-like method recursively, we obtain a sequence of polynomials that converges to a factor p*(z) of f(z) if an initial approximate factor p(z) is sufficiently close to p*(z). This method includes some well known iterative formulae, and has a close relation to a rational approximation. According to this factoring method, a fixed point relation for p*(z) is derived. Based on this relation, we obtain a polynomial with complex interval coefficients that includes p*(z).     

Clipping procedure in optimization problems and its generalization

A possibility of application of clipping procedure in the optimization task of quadratic functional E = (x, Ax) has been researched. It is shown that the acceleration of algorithm performance in the search for global minimum by a direct use of clipping procedure is insignificant. A modification of clipping procedure with q parameter (number of gradations) is proposed. It is shown that with the increase of q the probability of coincidence of gradients E(x) direction with its clipped analog E _C (x) = (x, Cx) goes up to 1.     

Recursive identification for EIV ARMAX systems

The input u _k and output y _k of the multivariate ARMAX system A(z)y _k = B(z)u _k + C(z)w _k are observed with noises: u _k ^ob ≜ u _k + ε _k ^u and y _k ^ob ≜ y _k + ε _k ^y , where ε _k ^u and ε _k ^y denote the observation noises. Such kind of systems are called errors-in-variables (EIV) systems. In the paper, recursive algorithms based on observations are proposed for estimating coefficients of A(z), B(z), C(z), and the covariance matrix Rw of w _k without requiring higher than the second order statistics. The algorithms are convenient for computation and are proved to converge to the system coefficients under reasonable conditions. An illustrative example is provided, and the simulation results are shown to be consistent with the theoretical analysis.     

Filtering of some nonlinear diffusions satisfying the general Bene condition

Under some regularity assumptions and the following generalization of the well-known Bene condition [1]:

Full-size image

, where F(t,z) = g⁻²(t)∫f(t,z)dz, F_t, F_z, F_zz, are partial derivatives of F, we obtain explicit formulas for the unnormalized conditional density q_t(z, x) α Px_t ε dz| y_s, 0 st, where diffusion x_t on R¹ solves x₀ = x, dx_t = [β(t) + α(t)x_t + f(t, x_t] dt + g(t) dw₁, and observation y_t = ∫_o^th(s)x_s ds + ∫_o^t(s) dw_2t, with w = (w₁, w₂) a two-dimensional Wiener process.     

Stable reduction of linear discrete-time systems via multipoint squared-magnitude CFE

This paper presents an elegant and computer-oriented procedure for the stable reduction of a linear discrete-time system via a multipoint continued-fraction expansion of its z-transfer function G(z). The proposed procedure involves the following three steps: (a) transform the z-domain squared-magnitude function P(z) = G(z)G(z ^?1) of the system frequency response to P(u) by the transformation u = z + z ^?1; (b) obtain an mth-order multipoint continued-fraction approximant P_m (u) to P(u); (c) factorize P_m (u) to yield a reduced z-transfer function G_m (z). The main feature of the procedure is that it guarantees the stability as well as the minimum-phase characteristics of the system and it also gives good overall approximations to both frequency and time responses.     

Parsimonious flooding in dynamic graphs

An edge-Markovian process with birth-rate p and death-rate q generates infinite sequences of graphs (G ₀, G ₁, G ₂,…) with the same node set [n] such that G _t is obtained from G _t-1 as follows: if e ? E(G_t-1){e\notin E(G_{t-1})} then e ? E(G_t){e\in E(G_{t})} with probability p, and if e ? E(G_t-1){e\in E(G_{t-1})} then e ? E(G_t){e\notin E(G_{t})} with probability q. In this paper, we establish tight bounds on the complexity of flooding in edge-Markovian graphs, where flooding is the basic mechanism in which every node becoming aware of an information at step t forwards this information to all its neighbors at all forthcoming steps t′ > t. These bounds complete previous results obtained by Clementi et al. Moreover, we also show that flooding in dynamic graphs can be implemented in a parsimonious manner, so that to save bandwidth, yet preserving efficiency in term of simplicity and completion time. For a positive integer k, we say that the flooding protocol is k-active if each node forwards an information only during the k time steps immediately following the step at which the node receives that information for the first time. We define the reachability threshold for the flooding protocol as the smallest integer k such that, for any source s ? [n]{s\in [n]} , the k-active flooding protocol from s completes (i.e., reaches all nodes), and we establish tight bounds for this parameter. We show that, for a large spectrum of parameters p and q, the reachability threshold is by several orders of magnitude smaller than the flooding time. In particular, we show that it is even constant whenever the ratio p/(p + q) exceeds log n/n. Moreover, we also show that being active for a number of steps equal to the reachability threshold (up to a multiplicative constant) allows the flooding protocol to complete in optimal time, i.e., in asymptotically the same number of steps as when being perpetually active. These results demonstrate that flooding can be implemented in a practical and efficient manner in dynamic graphs. The main ingredient in the proofs of our results is a reduction lemma enabling to overcome the time dependencies in edge-Markovian dynamic graphs.     

Über einen Ordnungsbegriff bei Einbettungsalgorithmen zur Lösung nichtlinearer Gleichungen

For solving the nonlinear systemF(x)=0 by using a continuation method a functionz implicitly defined byH(z, t)=0 has to be determined. In order to obtain approximationsz ^k toz(t _k ) the algorithmz ^k+1:=z ^k ?τ _k p(z ^k ,t _k , τ _k ),t _k+1:=t _k +τ _k , is used. The order of such a functionp is defined in this paper, and for certain classes of algorithms the corresponding orders are determined.     

Eigenvalue condition numbers and pseudospectra of Fiedler matrices

The aim of the present paper is to analyze the behavior of Fiedler companion matrices in the polynomial root-finding problem from the point of view of conditioning of eigenvalues. More precisely, we compare: (a) the condition number of a given root \({\lambda }\) of a monic polynomial p(z) with the condition number of \({\lambda }\) as an eigenvalue of any Fiedler matrix of p(z), (b) the condition number of \({\lambda }\) as an eigenvalue of an arbitrary Fiedler matrix with the condition number of \({\lambda }\) as an eigenvalue of the classical Frobenius companion matrices, and (c) the pseudozero sets of p(z) and the pseudospectra of any Fiedler matrix of p(z). We prove that, if the coefficients of the polynomial p(z) are not too large and not all close to zero, then the conditioning of any root \({\lambda }\) of p(z) is similar to the conditioning of \({\lambda }\) as an eigenvalue of any Fiedler matrix of p(z). On the contrary, when p(z) has some large coefficients, or they are all close to zero, the conditioning of \({\lambda }\) as an eigenvalue of any Fiedler matrix can be arbitrarily much larger than its conditioning as a root of p(z) and, moreover, when p(z) has some large coefficients there can be two different Fiedler matrices such that the ratio between the condition numbers of \({\lambda }\) as an eigenvalue of these two matrices can be arbitrarily large. Finally, we relate asymptotically the pseudozero sets of p(z) with the pseudospectra of any given Fiedler matrix of p(z), and the pseudospectra of any two Fiedler matrices of p(z).