This file was generated only in order to help search engines; its contents will display poorly, as the file was obtained by filtering out all symbols.
The file that you really want to look at is the (gzipped) postscript,
or the pdf, version of the one that you are currently looking at.
These files, as well others, with publication information, can be found in
Eduardo Sontag's
Online Papers site.
If the file that you are looking at is named "foo.html", then
the file that you want is (only one of the formats may be
available) foo.ps.gz and/or foo.pdf.
For convenience, here are direct links to those files (the pdf file is in some
cases unavailable):
Remarks on universal nonsingular controls for discrete-time
systems
Eduardo D. Sontag Department of Mathematics
Rutgers University New Brunswick, NJ 08903 sontag@hilbert.rutgers.edu
Fabian R. Wirth
\Lambda
Institut f"ur Dynamische Systeme
Universit"at Bremen D-28344 Bremen, Germany fabian@mathematik.uni-bremen.de
August 26, 1997
Abstract 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.
1 Introduction In a number of recent papers the question of existence of controls with certain universal properties has been addressed for continuous as well as discrete-time systems. Both aspects of the theory, namely observation and control, have been studied. Interest in this subject started with the analysis of universally distinguishing inputs, that is inputs that lead to different outputs for any pair of initial conditions that is distinguishable, see [7], [11], [9]. Subsequently, the problem of existence and genericity of universal nonsingular controls, that is, controls that steer every point of the state space into the interior of its reachable set was studied in [8]; this notion is in a sense dual to distinguishability. In this short note, a remaining gap is closed in that we study the existence of universal nonsingular (or universally regular) control sequences for analytic discrete-time systems. This problem turned up in a study of exponential growth rates of perturbed time-varying linear systems, [14]. For this setup it is also necessary to study discrete-time systems with a transition map that is not defined for all pairs of states and control values (x; u), which is done by introducing analytic
\Lambda Author for correspondence
Running Title: Universal nonsingular controls Keywords: analytic discrete-time systems, forward accessibility, universal controls 1991 Subject Classification:32B20, 93C10, 93C55
1
"exceptional" sets. This paper is organized as follows. After defining the precise class of discrete-time systems and stating the problem in Section 2 we prove the main results on universal nonsingular controls in Section 3 under the condition of uniform forward accessibility. In the ensuing Section 4 certain classes of systems are discussed where the structure of the system guarantees uniform forward accessibility from the entire state space if forward accessibility holds. This discussion depends on stationarity of descending chains of singularity loci, which holds for algebraic systems (those defined by polynomial dynamics). Section 5 is used as an appendix to review some facts on analytically defined sets.
2 Preliminaries We begin with a discussion of the problem and the main results for standard analytic, discretetime invertible systems. Let M; U be real-analytic, connected, paracompact manifolds of dimension n, resp. m. An analytic map f : M \Theta U ! M gives rise to an analytic discretetime system of the form
x(t + 1) = f (x(t); u(t)) ; t 2 N (1)
x(0) = x0 2 M : For now let us consider the standard assumption that for each u 2 U the map f (\Delta ; u) : M ! M is a diffeomorphism of M . The solution of system (1) corresponding to an initial value x0 and an admissible control sequence u 2 U N is denoted by x(\Delta ; x0; u).
The forward orbit at time t from x is defined by:
O+t (x) := fy 2 M ; 9 u 2 U t with y = x(t; x; u)g and the forward orbit from x is:
O+(x) := [
t2N O
+ t (x):
The system (3) is said to be forward accessible if int O+(x) 6= ; for all x 2 M and uniformly forward accessible from V ae M it there exists a t 2 N such that int O+t (x) 6= ; for all x 2 V . Forward accessibility may be characterized by a rank condition on the iterates of f . We define f1(x; u) := f (x; u) and recursively ft+1(x; u0; : : : ; ut) := f (ft(x; u0; : : : ; ut\Gamma 1); ut). A pair (x; u) 2 M \Theta U t is called regular if the rank of the Jacobian of ft with respect to the control variables is full, i.e. if
r(t; x; u) := rk @ft@u
0 : : : @ut\Gamma 1 (x; u) = n : (2)
For system (1) we are interested in the set of universal nonsingular control sequences u for M or for a relatively compact subset V ae M , where we call a finite control sequence u 2 U t universal nonsingular for M (or V ) if (x; u) is a regular pair for every x 2 M (respectively every x 2 V ). An infinite sequence u 2 U N is called universal if for every x 2 M (or V ) there exists a tx such that for all t * tx it holds that r(t; x; u) = n. We denote the sets of universal nonsingular controls by S(t; M ), S(t; V ), S(N; M ) etc.
We now formulate the main results in terms of this standard discrete-time setup. The proofs are omitted here, as they will follow from the more general theorems proved in Section 3. For a discussion of semi-analytic sets and our use of the term generic we refer to Section 5.
2
Proposition 2.1 Let V ae M be semi-analytic. Assume that system (1) is uniformly forward accessible from V in t\Lambda steps. Then S(t; V ) is generic in U t for all t * t\Lambda (n + 1). If furthermore V is compact then the complement of S(t; V ) is contained in a closed, analytically thin, subanalytic subset of U t for all t * t\Lambda (n + 1).
Uniform forward accessibility can be inferred from accessibility if either M is compact or the system (3) is algebraic. We will discuss the latter assumption in more detail in Section 4. Thus we also obtain the following corollaries.
Corollary 2.2 Assume that M is compact and that system (1) is forward accessible, then the complement of S(t; M ) is a closed, subanalytic, analytically thin subset of U t for all t 2 N large enough.
Corollary 2.3 Let M; U be real-algebraic manifolds and assume that the map f is algebraic. If system (1) is forward accessible then there exists a _t such that it is uniformly accessible from M in time _t. Hence S(t; V ) is generic in U t for all t * _t(n + 1).
The above statements are proved in the following more general context. Assume we are given a proper analytic subset X ae M \Theta U and an analytic map f : W ! M , where W := (M \Theta U ) n X. For fixed u 2 U the domain of definition of f (\Delta ; u) is denoted by W (u) ` M , while the domain of definition of ft is denoted by Wt ` M \Theta U t. For x 2 M define the set of admissible control values U (x) by fxg\Theta U (x) = (fxg\Theta U )nX, and denote in a similar fashion the admissible sequences for x of length t or of infinite length by U t(x); U N(x). We consider the discrete-time system
x(t + 1) = f (x(t); u(t)) ; t 2 N (3)
x(0) = x0 2 M ;
u 2 U N(x0): We assume that the set of admissible control values U and the map f satisfy
(i) For all x 2 M it holds that fxg \Theta U 6ae X. (ii) Usub := fu 2 U ; W (u) = M and f (\Delta ; u) : M ! M is submersiveg is the complement
of a proper analytic subset of U . (Recall that f (\Delta ; u) is called submersive if @f (\Delta ; u)=@x has full rank for every x 2 M .)
(iii) For all t 2 N, and all x 2 M , ft(x; \Delta ) is nontrivial with respect to u, i.e. if
@ft(x; \Delta )=@u0 : : : @ut\Gamma 1 has full rank in some point u 2 U t(x), then in each connected component of U t(x) there exists a point where this rank condition is satisfied.
Remark 2.4 (i) Note that the condition u 2 Usub means in particular that f (\Delta ; u) is defined on all of M . If we denote U tsub := (Usub)t then an application of the chain rule shows that ft(\Delta ; u) is submersive for u 2 U tsub. Furthermore the complement of U tsub is a proper analytic subset of U t. (ii) With respect to assumption (iii) note that in each connected component of Wt the set of points where @ft=@u0 : : : @ut\Gamma 1 does not have full rank is analytic. Thus the assumption states that either the rank condition is generically satisfied in U t(x) or not at all. In the case X = ;, this assumption is automatically fulfilled by the connectedness of U .
3
Note that Xt := (M \Theta U t) n Wt need not be analytic in M \Theta U t for t ? 1. The reason for this is that
Xt+1 = (Xt \Theta U ) [ f(x; u0; : : : ; ut) 2 Wt \Theta U ; (ft(x; u0; : : : ; ut\Gamma 1); ut) 2 Xg ; (4) and the set on the right hand side is only an analytic set in Wt \Theta U and may not be analytic in M \Theta U t+1. For details on this question see [6], Chapter IV, Proposition 4'.
Let us note that from (4) it follows that Xt is a closed, oe-analytic subset of M \Theta U t. This may be seen in an inductive manner, as follows. For t = 1, the statement is clear by assumption. Assume by induction that Xt is a closed, oe-analytic subset of M \Theta U t. Then Xt \Theta U is a oe-analytic subset of M \Theta U t+1. Furthermore, the set
A := f(x; u0; : : : ; ut) 2 Wt \Theta U ; (ft(x; u0; : : : ; ut\Gamma 1); ut) 2 Xg is an analytic subset of Wt \Theta U , and thus is in particular closed in Wt \Theta U . An elementary topology argument implies that then also (Xt \Theta U ) [ A is a closed subset of M \Theta U t+1. This set is oe-analytic, because each of the two sets is oe-analytic. The induction step is complete. We give an example to illustrate the situation.
Example 2.5 Let M = R, U = R2 and
X = f(x; u; v) ; u = 0g [ f(x; u; v) ; x = u and v = 0g : Consider the system
x(t + 1) = f (x(t); u(t); v(t)) = v(t)x(t) + sin 1u(t) ! : For x(0) = 0 it follows that x(1) = sin(1=u(0)). We claim that the exceptional set X2 is not analytic in M \Theta U 2. Indeed, consider the following set:
B := X2 " f(x; u1; v1; u2; v2); x = u2 = v1 = v2 = 0g: Observe that B = f(0; u1; 0; 0; 0); u1 2 B0g, where
B0 = fu1 ; u1 = 0; or u1 6= 0 and sin ` 1u
1 ' = 0g :
If X2 were an analytic subset of M \Theta U 2, then B0 would be an analytic subset of R. But this is false, as 0 is a limit point of isolated points of B0, but analytic subsets have finitely many connected components when intersected with any compact subset of the ambient space.
For systems of the form (3) the definitions of forward accessibility, uniform forward accessibility, regularity and universal non-singularity remain the same, with the possible exception that the defining equations should only be considered where they make sense. Note in particular that if u 2 S(t; V ) for some V ae M then it follows that the transition map is defined i.e. (x; u) 2 Wt for all x 2 V . The relation between accessibility and regularity is clarified by the following observation, which is a reformulation of results from [1]. The proof is included for the sake of completeness.
4
Lemma 2.6 Let V be a semi-analytic subset of M . System (3) is uniformly forward accessible from V iff there exists a t 2 N such that all pairs (x; u) from a generic subset Z ae (V \Theta U t) " Wt are regular and for all x 2 V it holds that fxg \Theta U t " Z is generic in fxg \Theta U t.
Proof. If (3) is uniformly forward accessible from V we may choose a t 2 N such that int O+t (x) 6= ; for all x 2 V . By Sard's theorem for each x 2 V there exists a ux 2 U t(x) with r(t; x; ux) = n. The singular set of ft restricted to V \Theta U t " Wt is defined by the simultaneous vanishing of principal minors of the Jacobian of ft with respect to the control variables and thus analytic in V \Theta U t " Wt, i.e. given by the intersection of an analytic set with the semi-analytic set V \Theta U t " Wt. By the existence of the pairs (x; ux) this set contains no set of the form fxg\Theta U t(x) and using Assumption (iii) it contains no connected component of (V \Theta U t) " Wt. This shows the existence of the generic set with the desired properties. The converse implication follows using local surjectivity (w.r.t. the control variables) of the map ft in (x; u) which is guaranteed due to regularity. 2
To conclude this section let us point out that by the assumptions we have made so far sets
of the form
Yt(i1; : : : ; il) := f(x; u0; : : : ; ut\Gamma 1) ; rk @ft@u
i1 : : : @uil (x; u
0: : : : ; ut\Gamma 1) ! ng (5)
for some index set fi1; : : : ; ilg ae f0; : : : ; t \Gamma 1g are only analytic in Wt as only there the derivatives are defined. In some cases a stronger property holds (for instance for the systems studied in [14].) We formulate this in the following assumption
Assumption 2.7 For each t 2 N and any index set fi1; : : : ; ilg ae f0; : : : ; t \Gamma 1g the set Yt(i1; : : : ; il) [ Xt is analytic in M \Theta U t.
In particular this holds if f is defined on M \Theta U , i.e. in the situation of Proposition 2.1.
3 Universal nonsingular controls The main result of this paper shows that uniform forward accessibility from V implies that the set of universal nonsingular control sequences for V are generic if the length of the control sequence is large enough. The idea of the proof is taken from [10] and differs from an approach taken in [13] which gives less information on the length of control sequences sufficient for the existence of universal nonsingular controls.
Proposition 3.1 Let V ae M be semi-analytic. Assume that system (3) is uniformly forward accessible from V in t\Lambda steps. Then S(t; V ) is generic in U t for all t * t\Lambda (n + 1). If furthermore V is compact and Assumption 2.7 holds then the complement of S(t; V ) is contained in a closed, analytically thin, subanalytic subset of U t for all t * t\Lambda (n + 1).
Proof. Throughout this proof we will assume without loss of generality that t\Lambda = 1, otherwise we may consider the map ft\Lambda and the control range U t
\Lambda . Consider, for each element x 2 V
and each t * 0 the following set
Bt(x) := fu 2 U t(x) ; rk @f@u (ft\Gamma 1(x; u0; : : : ; ut\Gamma 2); ut\Gamma 1) ! ng :
5
For each x B1(x) is a analytic subset of U (x) since it is the set defined by the simultaneous vanishing of the principal minors of the Jacobian of f with respect to u. By uniform forward accessibility and the nontriviality of f it follows that the dimension of B1(x) is at most m \Gamma 1. Observe that, for each t
(u0; : : : ; ut) 2 Bt+1(x) iff ut 2 B1(ft(x; u0; : : : ; ut\Gamma 1)) : (6) Consider also, for each t the analytic subset of ~Wt := Wt " (V \Theta U t) given by
Gt := f(x; u0; : : : ; ut\Gamma 1) ; (u0; : : : ; ui) 2 Bi+1(x) ; 8i = 0; : : : ; t \Gamma 1g : The analyticity of Gt follows as each of the definitions describing the set can be expressed in terms of vanishing principal minors. We claim that Gt has dimension at most n + t(m \Gamma 1). This is obviously true for t = 0 so we may by induction assume it to be true for t and consider the analytic map
sst : ~Wt+1 ! ~Wt
(x; u0; : : : ; ut) 7! (x; u0; : : : ; ut\Gamma 1) : Note that
A := sst(Gt+1) ae Gt
by definition of these sets. For each fixed (_x; _u0; : : : ; _ut\Gamma 1) 2 A,
ss\Gamma 1t (_x; _u0; : : : ; _ut\Gamma 1) " Gt+1 = f_xg \Theta f_u0g \Theta : : : \Theta f_ut\Gamma 1g \Theta B1(ft(_x; _u0; : : : ; _ut\Gamma 1)) ae ~Wt \Theta U ; by Equation (6). Thus this fiber has dimension at most m \Gamma 1. Applying Proposition 5.1 Part 2 it follows that
dim Gt+1 ^ [n + t(m \Gamma 1)] + [m \Gamma 1] = n + (t + 1)(m \Gamma 1) as claimed. We conclude, for the special case t = n + 1 that the set Gn+1 has dimension at most
n + (n + 1)(m \Gamma 1) = m(n + 1) \Gamma 1 :
Finally consider the projection ss of Gn+1 onto U n+1. As analytic maps cannot increase dimensions by Proposition 5.1 ss(Gn+1) can have dimension at most m(n + 1) \Gamma 1. By assumption (ii) the set U n+1sub n ss(Gn+1) is generic in U n+1. This set consists of universal nonsingular controls by definition of Usub. In case that the map ss is proper it follows by definition that ss(Gn+1) is subanalytic. In particular under the assumptions of the second part of the proposition (Xt [ Gt) " (V \Theta U t) is a semi-analytic subset of M \Theta U t. Due to the compactness of V we obtain that ss((Gn+1 [ Xn+1) " (V \Theta U n+1)) is subanalytic in U n+1 and closed. For the case of t ? t\Lambda (n + 1) note that the concatenation of a universal nonsingular control sequence with u 2 Usub is universal nonsingular, which follows from an application of the chain rule. This shows genericity of the universal nonsingular controls for all t * t\Lambda (n + 1) and completes the proof. 2
Corollary 3.2 Assume that M is compact and that system (3) is forward accessible, then the complement of S(t; M ) is closed and analytically thin in U t for all t 2 N large enough. If furthermore Assumption 2.7 holds, then the complement of S(t; M ) is subanalytic in U t for all t 2 N large enough.
6
Proof. Using a standard compactness argument it is easy to see that system (3) is uniformly forward accessible from M for some time t\Lambda . With a similar argument it follows that the set of universal nonsingular control sequences is open. Now the previous Proposition 3.1 shows the assertion. 2
It is worth noting that for systems defined on compact, complex manifolds satisfying Assumption 2.7 a stronger statement holds because of the holomorphic structure. Note that in this case condition (iii) is superfluous as analytic subsets of complex manifolds are nowhere separating so that in this case Wt and U t(x) have only one connected component, see [5], Proposition 7.4.
Corollary 3.3 Let M; U be complex manifolds and let M be compact. Assume that the map f : (M \Theta U ) n X ! M is holomorphic, where again X is an analytic subset of M \Theta U . We assume the complex analogies of assumptions (i) and (ii) and Assumption 2.7. If (3) is forward accessible, then there exists a t\Lambda 2 N such that for all t * t\Lambda the complement of S(t; M ) is a proper analytic subset of U t.
Proof. As system (3) is forward accessible we have regular pairs (z; u) for every z 2 M . We may interpret M; U as real analytic manifolds of dimensions 2n resp. 2m. Writing (in local coordinates) x + iy = z, v + iw = u and f (z; u) = g(x + iy; v + iw) + ih(x + iy; v + iw) we may consider the real-analytic system given by the maps g; h which is also forward accessible. We follow the steps of the proof of Proposition 3.1 with a few modifications. First of all the sets Bt(x; y) are defined using the complex derivative:
Bt(x; y) := f(v; w) 2 U t(x; y); rk @f@u (ft\Gamma 1(x+iy; v0+iw0; : : : ; vt\Gamma 2+iwt\Gamma 2); vt\Gamma 1+iwt\Gamma 1) ! ng: Note that for each (x; y) the dimension of Bt(x; y) is at most 2m \Gamma 2 because of the underlying complex structure. Considering again the map ss and the sets Gt; Xt of the proof of Proposition 3.1 it follows by Remmert's proper mapping theorem ([5] Theorem 45.17) that the complement of the universal nonsingular control sequences is an analytic subset of U t. As it not equal to U t for all t large enough the assertion follows. 2
Corollary 3.4 Let system (3) be forward accessible. The complement of S(N; M ) is of first category in U N endowed with the topology of pointwise convergence.
Proof. Let Vn be an exhaustion of M (i.e. V1 ae V2 ae ::: and [n2NVn = M ) consisting of compact, semi-analytic sets Vn. Denote by tn the time at which (3) is uniformly forward accessible from Vn. For each n 2 N consider the set
S(tn; Vn) \Theta Usub \Theta Usub \Theta : : : ae S(N; Vn) : Note that the closure of U N n S(N; Vn ) has empty interior. It holds that"
n2N S(
N; Vn) ae S(N; M )
and thus
U N n S(N; M ) ae [
n2N U
N n S(N; Vn ) :
Thus U N n S(N; M ) is a countable union of nowhere dense sets. This completes the proof. 2
7
4 Uniform accessibility As we have seen in Proposition 3.1 uniform accessibility implies the generic existence of universal controls. It is therefore useful to ask under which conditions a system of the form (3) is uniformly accessible from the whole state space M . In [2] some conditions guaranteeing forward accessibility of discrete time systems have been investigated. These depend on the topology of M or on the dynamical behavior of the system.
In this section we investigate certain system classes which guarantee (forward) uniform accessibility on M from forward accessibility.
Definition 4.1 We say that the map f : W ! M satisfies a descending chain condition if any descending chain Z0 ' Z1 ' : : : of sets of the form
Zt = fx 2 M ; (x; u) is not a regular pair; 8u 2 U 0t g is stationary, where for each t 2 N the set U 0t is a set of control sequences. Note that in general a descending chain of analytic sets is only stationary on compact subsets of M , see [6] Corollary 1 to Theorem V.2.1.
Theorem 4.2 Let system (3) be forward accessible and assume that f satisfies a descending chain condition. Then, there exists a _t 2 N such that system (3) is uniformly accessible from M in time _t.
Proof. Consider the family of sets given by
Zt := fx 2 M ; int O+t (x) = ;g : Applying Lemma 2.6 to V = fxg and using Assumption (ii) we obtain
Zt = fx 2 M ; r(t; x; u) ! n; 8u 2 U tsubg ; We wish to show that Zt0 = ; for some t0. To this end we show that the family (Zt)t2N is descending. If x =2 Zt then there exists a u 2 U tsub such that r(t; x; u) = n and if u0 2 Usub it follows from the chain rule that also r(t + 1; x; (u; u0)) = n and thus x =2 Zt+1. Hence the family (Zt)t2N is descending
M = Z0 ' Z1 ' : : : ' Zt ' : : : and it is stationary at some t0, that is, Zt0 = Zt0+1 = : : :. We claim that Zt0 = ;. Otherwise let x 2 Zt0 and choose u 2 U t
0sub. As (3) is forward accessible we have int O+t (x(t0; x; u0)) 6= ;
for some t 2 N and using Lemma 2.6 again it follows that there exists a u 2 U tsub such that n = r(t; x(t0; x; u0); u) = r(t0 + t; x; (u0; u)). This shows that x =2 Zt0+t and thus the family (Zt)t2N is not stationary at t0, a contradiction. 2
A first application lies in the consideration of real-algebraic systems. For an introduction to real-algebraic manifolds, i.e. real-algebraic varieties that do not have singular points we refer to [4] Chapter 3. To keep technicalities to a minimum we will restrict ourselves to embedded real-algebraic manifolds here. We briefly recall the basic notions of real-algebraic sets. A set X ae Rd is called algebraic if it is the zero locus of a set of polynomials in d
8
indeterminates. To an algebraic set X we may associate the ideal I(X) of polynomials that vanish on X. By the Hilbert Basis theorem any increasing chain of ideals in R[X1 ; : : : ; Xd] is stationary, i.e. the ring is Noetherian, see [3] Chapter 7. As a consequence a descending chain of algebraic sets in Rd is stationary as X1 ' X2 implies I(X1) ` I(X2).
There are two equivalent ways to view algebraic subsets of an algebraic set X ae Rd : They are either given as the intersection of an algebraic subset of Rd with X or as the zero locus of a family of functions contained in R[X1 ; : : : ; Xn]=I(X). Hence a descending family of algebraic subsets of X is stationary.
An embedded real-algebraic manifold M ae Rd is a smooth embedded manifold that is an algebraic subset of Rd at the same time. We note that if M is a real-algebraic manifold and X is an algebraic subset of M then also M n X may be interpreted as an embedded realalgebraic manifold, see [4] Proposition 3.2.10. Given two real-algebraic embedded manifolds Y; Z a map f : Y ! Z is called algebraic (or regular in [4]) if each coordinate function is an element of the ring of algebraic functions on Y given by
f pq ; p; q 2 R[X1 ; : : : ; Xn]=I(Y ); q(x) 6= 0 8x 2 Y g ;
We are now in a position to formulate the following corollary. Corollary 4.3 Let M; ~U be real-algebraic, embedded manifolds. Assume that ~X ae M \Theta ~U is algebraic and that f : ~W ! M is algebraic.
Let U be an open, connected subset of ~U . Define the exceptional set X := (M \Theta U ) " ~X and consider system (3) given by the restriction of f to (M \Theta U )n X. If system (3) is forward accessible then there exists a _t such that it is uniformly forward accessible from M in time _t.
Proof. The assumptions of Theorem 4.2 are satisfied as any descending family of algebraic sets is stationary, and under the assumptions of this corollary the sets considered in Definition 4.1 are algebraic as they can be expressed in terms of vanishing principal minors of algebraic functions. 2
It is worth noting that we cannot expect that _t depends on the dimension of M or U . This
is shown in the following example.
Example 4.4 Let M = R, U = (a; b) ae R for some constants 0 ! a ! b and X = ;. Let g(x) = x + 1 and h(x) = cx(x \Gamma 1) : : : (x \Gamma 2k) for some k 2 N; c ? 0. For the system
x(t + 1) = g(x) + uh(x) we see that O+2k+1(0) = f0; 1; : : : ; 2k + 1g. It is easy to see that in this example the system is uniformly accessible from M in 2k + 2 steps. Note furthermore that we can choose the constant c in such a way that h0(x) ? \Gamma 1=b; 8x 2 R which ensures that condition (ii) on the genericity of submersive control values holds.
5 Appendix: Some remarks on analytically defined sets A subset of an analytic manifold M is called analytic if it is closed in M and can be locally described as the zero locus of a family of analytic functions. One of the celebrated results of the theory of holomorphic mappings in several variables is Remmert's proper mapping theorem ([5] Theorem 45.17) which states that in the complex case the image of an analytic
9
set under a proper map is itself analytic. In the real case this property fails to hold. In order to remedy the situation the class of subanalytic sets has been introduced, see [12] for an overview of the theory. Let us briefly indicate the main notions: A subset Z ae M is called semi-analytic if for each x 2 Z there exists a neighborhood W such that W " Z can be represented as a finite union of solution sets of a finite number of analytic equalities gi(x) = 0 and inequalities hj(x) ? 0. A subset S in M is called subanalytic if there are an analytic manifold N , a semi-analytic subset T of N and an analytic map OE : N ! M that is proper on the closure of T such that OE(T ) = S. A further generalization of this is given by the notion of oe-analytic sets: Recall that an embedded manifold N of an analytic manifold is a set with the property that around each point in N there exists a coordinate chart ('; W ) such that '(W " N ) = f(xi)i=1;:::n 2 Rn ; xq+1 = : : : = xn = 0g for some 1 ^ q ^ n. A oe-analytic set is defined as an at most countable union of embedded manifolds. (This extends the class of subanalytic sets as a subanalytic set can always be decomposed into a locally finite countable union of embedded submanifolds, see [12] Sections 8/9.) To summarize we have now defined analytic, semi-analytic, subanalytic and oe-analytic sets, where each class is an extension of the previous one. The dimension of a oe-analytic set is defined as the maximal dimension of one of its components. This definition is compatible with the definitions of dimension of the other classes of analytic sets. Note in particular that it does not depend on the particular countable decomposition of a oe-analytic set. If the dimension of a oe-analytic set X is strictly less than the dimension of the manifold M then a set Y with M n Y ae X is called generic. The reason for this terminology is that X has measure zero and is of first category, i.e. a countable union of nowhere dense sets. The complement of a generic set will be called analytically thin. In the proofs we have used the following results on oe-analytic sets and analytic maps. For a proof we refer to [10] Proposition A.2.
Proposition 5.1 Assume that M; N and Mi; i = 1; : : : ; k are analytic manifolds. Let f : M ! N be an analytic mapping. Then:
1. If Z is a oe-analytic subset of M , then f (Z) is a oe-analytic subset of N , and dim f (Z) ^
dim Z.
2. For all Z ` M ,
dim Z ^ dim N + maxy
2N hdim f
\Gamma 1(y) " Zi :
3. If Zi is analytically thin in Mi, for i = 1; : : : ; k then Z = Z1 \Theta : : : \Theta Zk is analytically
thin in M1 \Theta : : : \Theta Mk and
Z = Z1 \Theta : : : \Theta Zk ` M1 \Theta : : : \Theta Mk satisfies dim Z = Pi dim Zi.
References
[1] F. Albertini and E.D. Sontag. Discrete-time transitivity and accessibility: analytic
systems. SIAM Journal on Control and Optimization, 31(6):1599-1622, 1993.
[2] F. Albertini and E.D. Sontag. Further results on controllability properties of discretetime nonlinear systems. Dynamics and Control, 4:235-253, 1994.
10
[3] M. Atiyah and I. MacDonald. Introduction to Commutative Algebra. Addison-Wesley,
Reading, Massachusetts, 1969.
[4] J. Bochnak, M. Coste, and M.-F. Roy. G'eom'etrie alg'ebrique r'eelle. Ergebnisse der
Mathematik und ihrer Grenzgebiete, 3. Folge Band 12. Springer-Verlag, Berlin, 1987.
[5] L. Kaup and B. Kaup. Holomorphic Functions of Several Variables: An Introduction to
the Fundamental Theory, volume 3 of Studies in Mathematics. de Gruyter, New York, 1983.
[6] R. Narasimhan. Introduction to the Theory of Analytic Spaces, volume 25 of Lecture
Notes in Mathematics. Springer-Verlag, Berlin, 1966.
[7] E.D. Sontag. On the observability of polynomial systems, I: Finite-time problems. SIAM
Journal on Control and Optimization, 17(1):139-151, 1979.
[8] E.D. Sontag. Universal nonsingular controls. System & Control Letters, 19:221-224,
1992. Errata, ibid., 20:77,1993.
[9] E.D. Sontag and Y. Wang. Orders of input/output differential equations and state-space
dimensions. SIAM Journal on Control and Optimization, 33(4):1102-1126, 1995.
[10] E.D. Sontag. Critical points for least-squares problems involving certain analytic functions, with applications to sigmoidal nets. Advances in Computational Mathematics (Special Issue on Neural Networks), 5:245-268, 1996. Summary as "Critical points for neural net least-squares problems," in Proc. 1995 IEEE Internat. Conf. Neural Networks, IEEE Publications, 1995, pp. 2949-2954.
[11] H.J. Sussmann. Single-input observability of continuous-time systems. Mathematical
Systems Theory, 12:371-393, 1979.
[12] H.J. Sussman. Real-analytic desingularization and subanalytic sets: An elementary
approach. Transactions of the AMS, 317(2):417-461, 1990.
[13] F. Wirth. Universal controls for homogeneous discrete-time systems. In Proc. of the
34th IEEE CDC, New Orleans, LA, pages 25-26, 1995.
[14] F. Wirth. Dynamics of time-varying discrete-time linear systems: Spectral theory and
the projected system. to appear in SIAM Journal on Control and Optimization, 36(2), 1998.
11