High-performance numerical algorithms and software for subspace-based linear multivariable system identification

Basic algorithmic and numerical issues involved in subspace-based linear multivariable discrete-time system identification are described. A new identification toolbox—SLIDENT—has been developed and incorporated in the freely available Subroutine Library in Control Theory (SLICOT). Reliability, efficiency, and ability to solve industrial identification problems received a special consideration. Two algorithmic subspace-based approaches (MOESP and N4SID) and their combination, and both standard and fast techniques for data compression are provided. Structure exploiting algorithms and dedicated linear algebra tools enhance the computational efficiency and reliability. Extensive comparisons with the available computational tools based on subspace techniques show the better efficiency of the SLIDENT toolbox, at comparable numerical accuracy, and its capabilities to solve identification problems with many thousands of samples and hundreds of parameters.     

Minimal system inverses for linear multivariable systems

The problem of minimal inverses for linear time invariant multivariable systems is formulated and constructively solved in a state space setting. Unknown initial states as well as zero initial states are considered. The spectrum of the minimal inverse is shown to be unique and constructable from the original system without first calculating the whole inverse. This leads to a simple way of introducing the equivalence of “zeros” in state space terminology.     

On the convergence of multivariable Lagrange interpolants

LetA _dj be a triangular array in a compact setXC ⁿ . Forf analytic in a neighborhood ofX, letL _d (f) denote the Lagrange interpolant tof at staged of the array. In the caseX is locally regular, we construct a continuous function satisfying the complex Monge-Ampère equation onC ⁿ –X, such that iff is analytic onR forR>1 then, for someB>0, we have L _d (f)–f _x B exp(–d logR. In particular, since1 onX, iff is analytic on1, then lim _d L _d (f)–f _x =0.Communicated by Edward B. Saff.     

On-line identification of language measure parameters for discrete-event supervisory control

The discrete-event dynamic behavior of physical plants is often represented by regular languages that can be realized as deterministic finite state automata (DFSA). The concept and construction of signed real measures of regular languages have been recently reported in literature. Major applications of the language measure are: quantitative evaluation of the discrete-event dynamic behavior of unsupervised and supervised plants; and analysis and synthesis of optimal supervisory control algorithms in the discrete-event setting. This paper formulates and experimentally validates an on-line procedure for identification of the language measure parameters based on a DFSA model of the physical plant. The recursive algorithm of this identification procedure relies on observed simulation and/or experimental data. Efficacy of the parameter identification procedure is demonstrated on the test bed of a mobile robotic system, whose dynamic behavior is modelled as a DFSA for discrete-event supervisory control.     

The rate of convergence of GMRES on a tridiagonal Toeplitz linear system

The Generalized Minimal Residual method (GMRES) is often used to solve a nonsymmetric linear system Ax = b. But its convergence analysis is a rather difficult task in general. A commonly used approach is to diagonalize A = XΛ X ⁻¹ and then separate the study of GMRES convergence behavior into optimizing the condition number of X and a polynomial minimization problem over A’s spectrum. This artificial separation could greatly overestimate GMRES residuals and likely yields error bounds that are too far from the actual ones. On the other hand, considering the effects of both A’s spectrum and the conditioning of X at the same time poses a difficult challenge, perhaps impossible to deal with in general but only possible for certain particular linear systems. This paper will do so for a (nonsymmetric) tridiagonal Toeplitz system. Sharp error bounds on and sometimes exact expressions for residuals are obtained. These expressions and/or bounds are in terms of the three parameters that define A and Chebyshev polynomials of the first kind.     

Stability of a linear difference system with random parameters

Necessary and sufficient conditions are derived for the mean-square exponential stability of a system described by an n-th order stochastic difference equation.Translated from Matematicheskie Zametki, Vol. 8, No. 6, pp. 753–760, December, 1970.The author wishes to thank R. Z. Khas'minskii for suggesting this problem.     

Emprical distribution for linear system identification

Asymptotic properties of empirical distributions of approximate errors for least squares identification are developed in this work. As a preparation, it is first shown that a law of large numbers type of result holds for the empirical distribution. Then a scaled sequence is proved to converge to a Gaussian process with a Brownian bridge component. These results are useful for carrying out statistical inference tasks, goodness of fit tests, and related matters     

Spectral gap and convergence rate for discrete-time Markov chains

Let P be a transition matrix which is symmetric with respect to a measure π.The spectral gap of P in L2(π)-space,denoted by gap(P),is defined as the distance between 1 and the rest of the spectrum of P.In this paper,we study the relationship between gap(P) and the convergence rate of Pn.When P is transient,the convergence rate of P n is equal to 1 gap(P).When P is ergodic,we give the explicit upper and lower bounds for the convergence rate of Pn in terms of gap(P).These results are extended to L∞(π)-space.     

The rate of convergence of GMRES on a tridiagonal toeplitz linear system. II

This paper continues the recent work of the authors’ [R.-C. Li, W. Zhang, The rate of convergence of GMRES on a tridiagonal Toeplitz linear system, Numer. Math. 112 (2009) 267-293 (electronically published on 19 December 2008)] on the rate of convergence of GMRES for a tridiagonal Toeplitz linear system Ax=b. Much simpler formulas than the earlier ones for GMRES residuals when b is the first or the last column of the identity matrix are established, and these formulas allow us to confirm the rate of convergence that was conjectured but only partially proven earlier. Simpler and sharper bounds than earlier ones when all b’s entries, except its first and last ones, are zeros are also obtained.     

Suboptimal linear feedback for a class of stochastic discrete-time systems

The well-known optimal linear feedback of the linear quadratic problem with jump Markov and independent disturbances is also a suboptimal feedback of the problem perturbed by a nonlinear element with a small parameter if the element is continuous. The assertion is shown and an asymptotic expansion is given.     

Stability and stabilizability of linear infinite-dimensional discrete-time systems

This paper contains three results on stability and stabilizabilityof linear time invariant infinite-dimensional discrete-timesystems. (1) Power stability is characterized in transfer-functionterms using the concepts of stabilizability and detectability.(2) Under the assumption that the input operator is campact,we present a necessary and sufficient condition for stabilizabilityinvolving spectral properties of the system operator and a projectionof the infinite-dimensional system onto a certain finite-dimensionalsubspace of the state space. (3) It is shown that, if the inputand output spaces are finite-dimensional, then stabilizationby finite-dimensional dynamic output feedback is possible ifand only if the systems is detectable and stabilizable.     

Fitting continuous-time and discrete-time models using discrete-time data and their applications

An exponential function scheme, which is an extension of the time-domain prony method, and a mixed-matching method are developed for fitting the coefficients of both continuous-time and discrete-time transfer functions, using the discrete-time data of either continuous-time or discrete-time systems. When the discrete-time data are obtained from a continuous-time (discrete-time) system and the discrete-time (continuous-time) models are desirable, the proposed method can be applied to perform the model conversions. If the discrete-time data are obtained from a high-degree system, the proposed method can be applied to determine the reduced-degree models.     

On a norm and approximate characteristics of classes of multivariable functions

We introduce a space of quasicontinuous functions and study its approximate characteristics, i.e., ε-entropy and widths. We establish inequalities for norms of trigonometric polynomials in this space. In addition, we obtain exponents of the ε-entropy and widths of some classes of functions with low smoothness. __________ Translated from Sovremennaya Matematika. Fundamental'nye Napravleniya (Contemporary Mathematics. Fundamental Directions), Vol. 25, Theory of Functions, 2007.     

Unknown-input present-state observability of discrete-time linear systems

A generalized definition of the present-state unknown-input observability is given as well as the corresponding unobservable subspace for discrete-time linear dynamical systems whose initial state is known, unknown, or partially known. It is shown that the time sequence of the unobservable subspaces have interesting properties explicable via generalized reachability subspaces, namely, the properties of conditional monotonicity and those associated with it. Furthermore, an observer is constructed to determine the present state.     

Reachability realization and stabilizability of switched linear discrete-time systems

In this paper, the reachability realization of a switched linear discrete-time system, which is a collection of linear time-invariant discrete-time systems along with some maps for “switching” among them, is addressed. The main contribution of this paper is to prove that for a switched linear discrete-time system, there exists a basic switching sequence such that the reachable (controllable) state set of this basic switching sequence is equal to the reachable (controllable) state set of the system. Hence, the reachability (controllability) can be realized by using only one switching sequence. We also discuss the stabilizability of switched systems, and obtain a sufficient condition for stabilizability. Two numeric examples are given to illustrate the results.