Publications about 'discrete-time' |
Books and proceedings |
(This is a monograph based upon Eduardo Sontag's Ph.D. thesis. The contents are basically the same as the thesis, except for a very few revisions and extensions.) This work deals the realization theory of discrete-time systems (with inputs and outputs, in the sense of control theory) defined by polynomial update equations. It is based upon the premise that the natural tools for the study of the structural-algebraic properties (in particular, realization theory) of polynomial input/output maps are provided by algebraic geometry and commutative algebra, perhaps as much as linear algebra provides the natural tools for studying linear systems. Basic ideas from algebraic geometry are used throughout in system-theoretic applications (Hilbert's basis theorem to finite-time observability, dimension theory to minimal realizations, Zariski's Main Theorem to uniqueness of canonical realizations, etc). In order to keep the level elementary (in particular, not utilizing sheaf-theoretic concepts), certain ideas like nonaffine varieties are used only implicitly (eg., quasi-affine as open sets in affine varieties) or in technical parts of a few proofs, and the terminology is similarly simplified (e.g., "polynomial map" instead of "scheme morphism restricted to k-points", or "k-space" instead of "k-points of an affine k-scheme"). |
Articles in journal or book chapters |
The area of hybrid systems concerns issues of modeling, computation, and control for systems which combine discrete and continuous components. The subclass of piecewise linear (PL) systems provides one systematic approach to discrete-time hybrid systems, naturally blending switching mechanisms with classical linear components. PL systems model arbitrary interconnections of finite automata and linear systems. Tools from automata theory, logic, and related areas of computer science and finite mathematics are used in the study of PL systems, in conjunction with linear algebra techniques, all in the context of a "PL algebra" formalism. PL systems are of interest as controllers as well as identification models. Basic questions for any class of systems are those of equivalence, and, in particular, if state spaces are equivalent under a change of variables. This paper studies this state-space equivalence problem for PL systems. The problem was known to be decidable, but its computational complexity was potentially exponential; here it is shown to be solvable in polynomial-time. |
It is shown that, for neutrally stable discrete-time linear systems subject to actuator saturation, finite gain lp stabilization can be achieved by linear output feedback, for all p>1. An explicit construction of the corresponding feedback laws is given. The feedback laws constructed also result in a closed-loop system that is globally asymptotically stable, and in an input-to-state estimate. |
We provide an explicit KL stability or input-to-state stability (ISS) estimate for a sampled-data nonlinear system in terms of the KL estimate for the corresponding discrete-time system and a K function describing inter-sample growth. It is quite obvious that a uniform inter-sample growth condition, plus an ISS property for the exact discrete-time model of a closed-loop system, implies uniform ISS of the sampled-data nonlinear system; our results serve to quantify these facts by means of comparison functions. Our results can be used as an alternative to prove and extend results of Aeyels et al and extend some results by Chen et al to a class of nonlinear systems. Finally, the formulas we establish can be used as a tool for some other problems which we indicate. |
For analytic discrete-time systems, it is shown that uniform forward accessibility implies the generic existence of universal nonsingular control sequences. A particular application is given by considering forward accessible systems on compact manifolds. For general systems, it is proved that the complement of the set of universal sequences of infinite length is of the first category. For classes of systems satisfying a descending chain condition, and in particular for systems defined by polynomial dynamics, forward accessibility implies uniform forward accessibility. |
This paper deals with the problem of global stabilization of linear discrete time systems by means of bounded feedback laws. The main result proved is an analog of one proved for the continuous time case by the authors, and shows that such stabilization is possible if and only if the system is stabilizable with arbitrary controls and the transition matrix has spectral radius less or equal to one. The proof provides in principle an algorithm for the construction of such feedback laws, which can be implemented either as cascades or as parallel connections (``single hidden layer neural networks'') of simple saturation functions. |
This paper summarizes the definitions and several of the main results of an approach to hybrid systems, which combines finite automata and linear systems, developed by the author in the early 1980s. Some related more recent results are briefly mentioned as well. |
This paper deals with the orders of input/output equations satisfied by nonlinear systems. Such equations represent differential (or difference, in the discrete-time case) relations between high-order derivatives (or shifts, respectively) of input and output signals. It is shown that, under analyticity assumptions, there cannot exist equations of order less than the minimal dimension of any observable realization; this generalizes the known situation in the classical linear case. The results depend on new facts, themselves of considerable interest in control theory, regarding universal inputs for observability in the discrete case, and observation spaces in both the discrete and continuous cases. Included in the paper is also a new and simple self-contained proof of Sussmann's universal input theorem for continuous-time analytic systems. |
Controllability questions for discrete-time nonlinear systems are addressed in this paper. In particular, we continue the search for conditions under which the group-like notion of transitivity implies the stronger and semigroup-like property of forward accessibility. We show that this implication holds, pointwise, for states which have a weak Poisson stability property, and globally, if there exists a global "attractor" for the system. |
A basic open question for discrete-time nonlinear systems is that of determining when, in analogy with the classical continuous-time "positive form of Chow's Lemma", accessibility follows from transitivity of a natural group action. This paper studies the problem, and establishes the desired implication for analytic systems in several cases: (i) compact state space, (ii) under a Poisson stability condition, and (iii) in a generic sense. In addition, the paper studies accessibility properties of the "control sets" recently introduced in the context of dynamical systems studies. Finally, various examples and counterexamples are provided relating the various Lie algebras introduced in past work. |
This paper deals with systems that are obtained from linear time-invariant continuous- or discrete-time devices followed by a function that just provides the sign of each output. Such systems appear naturally in the study of quantized observations as well as in signal processing and neural network theory. Results are given on observability, minimal realizations, and other system-theoretic concepts. Certain major differences exist with the linear case, and other results generalize in a surprisingly straightforward manner. |
This paper presents a geometric study of controllability for discrete-time nonlinear systems. Various accessibility properties are characterized in terms of Lie algebras of vector fields. Some of the results obtained are parallel to analogous ones in continuous-time, but in many respects the theory is substantially different and many new phenomena appear. |
We investigate the effect of sampling on linearization for continuous time systems. It is shown that the discretized system is linearizable by state coordinate change for an open set of sampling times if and only if the continuous time system is linearizable by state coordinate change. Also, it is shown that linearizability via digital feedback imposes highly nongeneric constraints on the structure of the plant, even if this is known to be linearizable with continuous-time feedback. |
This paper studies accessibility (weak controllability) of bilinear systems under constant sampling rates. It is shown that the property is preserved provided that the sampling period satisfies a condition related to the eigenvalues of the autonomous dynamics matrix. This condition generalizes the classical Kalman-Ho-Narendra criterion which is well known in the linear case, and which, for observability, results in the classical Nyquist theorem. |
Weak controllability of bilinear systems is preserved under sampling provided that the sampling period satisfies a condition related to the eigenvalues of the autonomous dynamics matrix. This condition generalizes the classical Kalman-Ho-Narendra criterion which is well known in the linear case. |
Let Ul, U2, ... be a sequence of observed random variables and (T1(U1),T2(Ul,U2),...) be a corresponding sequence of sufficient statistics (a sufficient sequence). Under certain regularity conditions, the sufficient sequence defines the input/output map of a time-varying, discrete-time nonlinear system. This system provides a recursive way of updating the sufficient statistic as new observations are made. Conditions are provided assuring that such a system evolves in a state space of minimal dimension. Several examples are provided to illustrate how this notion of dimensional minimality is related to other properties of sufficient sequences. The results can be used to verify the form of the minimum dimension (discrete-time) nonlinear filter associated with the autoregressive parameter estimation problem. |
An abstract operator approach is introduced, permitting a unified study of discrete- and continuous-time linear control systems. As an application, an algorithm is given for deciding if a linear system can be built from any fixed set of linear components. Finally, a criterion is given for reachability of the abstract systems introduced, giving thus a unified proof of known reachability results for discrete-time, continuous-time, and delay-differential systems. |
A state-space realization theory is presented for a wide class of discrete time input/output behaviors. Although In many ways restricted, this class does include as particular cases those treated in the literature (linear, multilinear, internally bilinear, homogeneous), as well ss certain nonanalytic nonlinearities. The theory is conceptually simple, and matrix-theoretic algorithms are straightforward. Finite-realizability of these behaviors by state-affine systems is shown to be equivalent both to the existence of high-order input/output equadons and to realizability by more general types of systems. |
Considered here are a type of discrete-time systems which have algebraic constraints on their state set and for which the state transitions are given by (arbitrary) polynomial functions of the inputs and state variables. The paper studies reachability in bounded time, the problem of deciding whether two systems have the same external behavior by applying finitely many inputs, the fact that finitely many inputs (which can be chosen quite arbitrarily) are sufficient to separate those states of a system which are distinguishable, and introduces the subject of realization theory for this class of systems. |
Conference articles |
This paper studies the input-to-state stability (ISS) property for discrete-time nonlinear systems. We show that many standard ISS results may be extended to the discrete-time case. More precisely, we provide a Lyapunov-like sufficient condition for ISS, and we show the equivalence between the ISS property and various other properties, as well as provide a small gain theorem. |
This note addresses the following problem: Find conditions under which a continuous-time (nonlinear) system gives rise, under constant rate sampling, to a discrete-time system which satisfies the accessibility property. |
Internal reports |
This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders.
This document was translated from BibT_{E}X by bibtex2html