BlockFormControl

Block-Form Control of Linear Time-lnvariant Discrete-Time Systems Defined over Commutative Rings E. \M. Kamen School of Elec'tri,cal and Computer Engi,neering Georgia lnstitute of Technology Atlanta, Georgia 30332-0250 Submitted by A. C. Antoulas ABSTRACT A new approach based on a block-input, block-output state model is developed for the study of li"ear time-invariant discrete-time systems whose coefficients belong_ to 1 commutative ting with 1. It is well larown that such systems arise in the study of various classes of complex linear systems including systems depending on parameters and multidimensional systems. By time-compressing the block-input state representation, new results are obtained on the construction of a memoryless block-form state feedback control law that ields a type of assignability and/or deadbeat control. These results are then duali zed to ield results on a new type of state observer based on a block of output measurements. The observer and state feedback controller are then combined to yield new results on input-output regulation and set-point trach"g Pt systems defined over an arbitrary commutative ring. In the last part of the paper, the block-input form is utilized to study the stabilization of systems deftned over a normed algebra. 1. INTRODUCTION ? i t : i I g In addition to the well-developed the ory of linear time-invariant systems based on linear equations with coefficients in the field R of real numbers, there is a large b"dy of work on linear time-invariant systems whose coefficients belong to a commutative .itrg R [see Sontag (1976, 1985), Brewer et al. *A preliminary version of this paper was presented at the IMA Workshop on Linear Ngebra for Control Theory, Minneapolis, june 1992. LII{EAR ALGEBRA AI,{D ITS APPLICATIOI:{S 205_206:805_829 @ Elsevier Science Inc., 1994 655 Avenue of the Americas, New York, NY 10010 (1994) oo24-37e5 /e4/ 805 $7.00  806 E. W. KAMEN (1986), and Kamen (fggt)]. In the discrete-time case, an m-input, p-output n-dimensional linear time-invariant system defined over a commutative *"g R with multiplicative identity I is given by the state model *(k + t) : Ax(k) * Bu(k), vG) where ft is the discrete-time : (r.1) C*(k), index, A, ( B,C are 1.2) nXn, nXm, pXn matrices over R, and the input z(ft), output y(k), andstate r(ft) are column vectors over R. of systems of the form (1.1), (I.2) that arise in applications .Examples integer systems with R : Z : the ring of integers, po|-*rotrtz"d lncluje famllles of systems with R a ring of real-valueJ function-s deffned on some parameter set such as a subset of N-dimensional Euclidean space RN, and maltidi.rnensional systems with R a convolution ring of real-vaiued functions deftned on the s-fold cartesian product z x z x ... x Z for some integer s [see Sontag (1976, 1985) and Kamen (fgsf) for details]. one of the topics t}at has been extensively studied in the literature on system-s over rings is state feedback control using a mem.oryless (or static) controller given by "(k): -Fx(k) or a dynamic controller of dimension r gpven by "(k): -Fx(ft) ( + Gu(k), 1.3) (L.4) where D(k) is the r-dimensional state vector of the feedback controller given by "(k + l) It (t.3)-(1.5), F, G, H, J ring R. are : Ho(k) + I*(k) m x n, m x r, ( 1.5) r x r, r x n mat*;1ces over the Part of the focus of the past work has been on the problem of assi,gnabl,t- itA by state feedback; in other words, the control objective is to "assi[n" (in some sense) lh", dyt?*ics of the closed-loop system by using stat" f"edback of the form (t.g) or (1.4), (1.5). In particular, in the case of the memoryless state feedback control (t.g), we can ask whether or not we have cofficient assi,gnabtllty-that is, glven any elements as, a1,..., an_L belongi"gi" the tittg R, whether there is a feedback gain matrix F over R iuch that with the  LIhJEAR TIME-INVARIANT DISCRETE.TIME SYSTEMS 807 control (1.3), the resulting closed-loop characteristic polynomial det(zl* - A + BF) is equal to zn * an-Lzn-r + "' *arz * ao. Here ln is the n X n identity matrix. For systems over a field, it is well known that coefficient assignability is equivalent to reachability of the gtven system, which in turn is equivalent to tB]. Howright invertibility of the reachability rnatrix f : lB AB "' Anever, for systems over a commutative ritrg R, in general reachability is not sufftcient for coefftcient assignability by memoryless state feedback, where in tB] has a right the ring case, reachability means that f - ln AB "' Aqinverse over R for some integ er q In the case of dynamic state feedback given by (L.4), (1.5), coefficient assignability is deftned as follows. First, combining (1.1), (t.Z) with (L.4), (1.5), we have the following (n + r)-dimensional state equation for the closed-loop system: l;ll I ill :Lle-BF T 'rl [;[]l The closed-loop characteristic polynomial is A _I +BF -BGl zl,- Hl' ( 1.6) Then the given system (1.1), (1.2) is dynami,cally coefficient assignable if there exists a positi'u" integer r such that the.coeffrcients of the (n + r)degree polynomial defined by (1.6) can be assigned arbitrarily by choosing F, G,H, I, In the work of Emre and Khargonekar (fgSZ), it was shown that arry reachable system (1.1), (f.2) over a commutative ring R is dynamically coefftcient assignable. However, in the general case when there are no restrictions on the ring R, existing techniques for constructing a dynamic state feedback controller yield controllers whose dimension r is in general on the order of n2, which can be rather excessive even for systems whose dimension n is not large. For certain special classes of rings, there exist assignability-type results using memoryless or low-order dynamic state feedback controlleis [e.g., see Sontag (1985), Brewer (f992), and Brewer et al. (lees)1. In this paper a new approach based on a block-input, block-ouput state model is developed for the study of linear time-invariant discrete-time systems deffned over an arbitrary commutative ring R with 1. For linear dme-invariant and periodically time-varying discrete-time systems deffned  808 E. W. KAMEN over the reals R, results based on block-input, block-output models (also called lifted representati.ons) have been derived by a numbei of authors [e.g., see Khargonekar et al. (1985), powell et al. (1g87), Buescher (fggg), Haigawara and Araki (I98S), Francis and Georgiou (19gg), Albertos (f990), Albertos and Ortega (1989), and Lozano (l9S-9)1. In the work of Kamen (1992a, 1992b), a block-form approach is developed for the class of linear discrete-time systems with general time-varying coefftcients, and in the work of Gnzzle and Kokotovic (rgss) and Grizzle and Moraal (rgg0), a block-form approach is developed for a large class of nonlinear time-invariant discretetime systems. For linear time-invariant discrete-time systems over a commutative ring (which includes systems over the reals R), we begin in Section 2 with th; generation of the block-input form of the state model. By time-compressing this representation, new results are obtained on the construction of a memoryless block-form state feedback control law that yields a t}pe of assignability, or that results in deadbeat control. These constructioni are duilized in section 3 to obtain results on the assignability of the error dynamics of a new type of state observer based on a block of output measurements. The observer and state feedback controller are then combined in section s and 4 to yield new results on input-output regulation and set-point trachng. In section 5 of the paper, the focus is on the stabilization oT systems deffned over normed algebra. It is shoum that the construction of stabilizing 1_ controllers can be approached in terms of the solution to a generalized lineai quadratic formulation based on the block form. ?. THE BLOCK-INPUT FORM AND STATE FEEDBACK CONTROL Again consider the discrete-time system (1.1), (1.2) deftned over a commutative i"g { with 1. To simplify the notation, in the following development we shall denote the system by the triple (A, B, C). - - Given a positiveinteger q ) 1, let I] denote the n X nq q-step reachabtltty matrtx deffned by lq: ln AB Aq-rB]. in the Introduction, the system ( A, B, C) is reachable (oming if for some integer q l, q has a right inverse over R; that is, there exists an nry X n matrix (L)" over R such that q(q)" - In. It follows As noted reachable) from the Cuyl"y-Hamilton theorem for matrices over a commutative ring that  809 LINEAR TIME-INVARIANT DISCRETE.TIME SYSTEMS the system ( A, B, C) is reachable if and only if [see bt"*"r et al. (1986)]. Given a positive integer q I; has a right inverse over R times, we have that (/c + q) : AQ *(k) + TrUn( k), (2.1) where Uq(k) is the mq-element block-input vector defined by "(k+q 1) "(k+q-2) uq(k) : a u(k + 1) "(k) Equation (2.f) is the bLock-input form of the state equation for_the sl,stem (i,n,C) deffned by (1.1), (t.z). t'lote that since rJn(k + 1) depends on 4(k) when q > l, we cannot view (2.1) as the state equation of a mg-input rpt"*. However, by time scaling w€ can generate a mq-input representation as follows. The time scaling is Jccomplished by replacing k with kg in the time signals 4(k) and r(k). If q > l, then Q(kq) and r(kg) are time compressiont .if 4tt) and r(k), respectively. It should be noted that for systJms over the t"'"lr (i."., R : R), tfre block-input state equation (Z.t) and tle idea of time scaling (2.1) can be found in the work of Powell et al. (1987), Buescher (1988), and Albertos IfSSO). Now replacin1 k by kq in (2.1), we obtain the state equation *(kq + q) - Aq *(kq) + TnUr(kq) . (2.2) When g : L, (2.2) reduces to (2.1), but for q > l, (2.2) is a time-compressed state equation of the system (A n,C). It particular, one time step in (2.2) correspbnds to g time steps in the original state equation (f.f).- Equation (2.2) i; the q-scaLed black-input fonn of the state equation for the system (A, B,c). Since 4(/cq) is independent of 4((k + 1)q), it is clear that (2.2) can be of a mq-input system over the ring R. As will be viewed as tie siate "q,t"tion seen below, due to the increased number of inputs, state feedback control is easier to carry out in terms of the state equation (Z.Z) than (1.r). it is in terms of  810 E. W. KAMEN With respect to the time-compressed representation (2.2), we can consider the memoryless block-form state feedback control law given by Un(kq) : - Fq *(kq) , k: 0, I ,2,.,., (2.3) where Fq rs a mq X n matrix over the ring R. Inserting the control (2.3) into (2.2), we have that the resulting closed-loop state equation on the kq time scale is given by x(kq + It q): (en - q F)*(kq), k:0, 1,2,... (2.4) should be noted that although the block-form control law (2.3) is memoryless (on the kq time scale), the implementation of the control (2.3) does require that the entries of Un(kq) be stored until they are needed. Thus, the implementation of the control (Z.g) does require memoy, but the form of the controller dynamics is of a very special type in comparison with the general form of the dynamic state feedback controller defined by (L.4), (1.5). The deftnition of the block control (2.3) leads to the following fundamental concept. I)nplNrrroN 2.L, The system (A, assignable for some integer g a nry X n matrix Fq over R such that B,C) defined by (1.1), (1.2) i, Aq lrFn :Q. Suppose that the system ( A, B, n X n matrix ? C) over R, there is an with the state feedback control Un(kq) system (2.4) is giver by *(kq + q) : (2.5) is g-step assignable, so Fo that given any over R such that (2.5) holds. Then : - Fq x(kq), the resulting Q"( kq), q-step k - 0,L,2,.., closed-loop (2.6) From (2.6), we see that the closed-loop system's state dlmamics on the kq if the system is g-step assignable. We have the following necessary and sufficient condition for g-step tim,e scale are completely assignable assignability. Tsnonnu 2.L. The system ( A, B, C) is q-step assignable for soffta inte71 if and only lf the system is reachable. In adrli,tion, if (A, B,C) is ger q  LINEAR TIME.INVARIANT DISCRETE-TIME SYSTBMS reachable, so that ln has a ri,ght i,noerse (I;)" oDer R, then n-step assignable, and fo, anA n X n, m"atri,x A ooer R, Aq satisfiedu:ith q - 811 (A, B,C) lnE, : a OS 0s n and (2.7) Proof. Suppose that (A, B,C) is reachable, so that I) has a right inverse (I))" over R. Given Q over R, it is clear that (Z.l) is a solution to (2.5) with q : n. Conversely, suppose that (A, B, C) is g-step assignable for some g > 1. Then setting Q : An - 1, there exists a matrix Q over R such that Aq - lnFn : Aq - I. Thus, lrFo : I, which shows that In has a right I inverse over R,'and therefore the syitem is reachable. From Theorem 2.1 we see that reachability of the system (A, g,C) is equivalent to complete assignability on the kn time scale of the closed-loop system's state dynamics. Of course, this construction does not in general allow for the speciftcation of arbitrary closed-loop dlmamics on the original time scale. There is one very important case where assignability on the kg time scale does result in a correspon&ng result on the /c time scale, and that is in dpadbeat control. To be precise, suppose that there is an { over R such that As -lnFo:0. Then from (2.6), x(kq + q):0 for /c : 0,I,2,... and for any inidal'state r(0), so we have deadbeat control on the kq ttme scale. But by (2.3), U,(kq): 0 for k : L,2, ..., since x(kq\ : 0 for /c : L,2,..., and by deftnition of U"(k), it must be true that u(k):0 for k: q,q + L,... . Then since r(k +'f) : Ax(k) + nu(k), the state r(ft) must also be zero for all k > g. Therefore, we also have deadbeat control on the /c time scale. Combining the above observations with Theorem 2,1, we have the following result. Tsnonnu 2.2. Su.ppose that the systenx ( A, B, C) is reachable so that l, has a right irwerse (1,)' ooer R. Then with q : n and F, : (1,)'A", the control (2.S) tu a deadbeat control on the k ttmp scab; that is, the state x(k) of the rextlti,ng cLosed-loop system i,s zero for all k > n, starting from any ini,tial state x(0) u:ith entries in R. By Theorem 2.2, reachability is a sufftcient condition for the existence of a deadbeat control on the k time scale. It is worth stressing that this result is valid for systems over an arbitrary commutative ring R with 1. We conclude this section with the following necessary and sufficient condition for existence of a deadbeat control.  8L2 E. w. KAMEN THnonnvr 2.3. There exist an i,nteger q of the fo* (2.3) such that x(k) - 0 for all k 2 q, starting from anA initial state r(0), if and only if there exists a mq x n matrix O, oDer R such that Aq : ln0* in u:hich case the control (2.3) u:ith Fn _ (2.8) @q is a deadbeat control on the k tim"e scale. Proof . If (2.8) is satisfied, it follows from the arguments glven above that the control (2.3) with Fq _ Qq is a deadbeat control; i.e., x(k) : 0 for all k 2 q. Conversely, suppose that there is a control of the form (Z.g) such that x(k) : 0 for all k 2 q and for any r(0) deftned over R. Then from (2.4), ('+q lnFn)r(O) - 0 for all n-vectors r(0) over R. It follows that Aq TnFr- 0, and thus (2.8) is satisfted. It should be noted that if A has an inverse I over R, the condition (2.8) is equivalent to requiring that Tq has a right inverse over R, which implies that the system (A, B,C) is reachable, So in this case, the existence of a deadbeat control of the form (z.g) is equivalent to reachability. 3. STATE OBSERVERS AND INPUT-OUTPUT REGULATORS In the first part of this section, w€ first consider the construction of a block-form state observer by "dualizittg" the results grven in the previous section. Then the state observer is combined with a state feedback controller to generate a type of input-output regulator. Again consider the system ( A, B, C) over the commutative titrg R deftned_by (1.1), (1.2). Given an integer q q-step obseraablllty matrix defined by oq- l'J, rh"system(A,B,C)issaidtobestronglaobseraableifforsomeg> has a left inverse over R, which is the case if and only if C), has a left inverse over R.  LINEAR TIME.INVARIANT DISCRETE-TIME SYSTEMS 8T3 With (A',C', nr) defined to be the dncal of the system (A, B,C), where superscript T denotes the transpose operation, it is easy to see (and well known) that the system ( A, B, C) is strongly obseruable if and only if the dual system ( A' , C' , Br ) is reachable. Now to be able to deftne a block-form obsenrer for the system ( A, B, C), we first need to generate a block version of the output equation (1.2). First, let Eq denote the pq X mq matrix deftned by [o o ... lo o ... O F-IO "ql...l o o ... CB o I cB CAB I I L; i, ... cer-'n cAq-'u) Then iterating (1.1), (t.Z) the output equation: q I times, we have the following block form of Yq(k)- Qr*(/.) * where C)q Enun(k), ( 3.1) is the obsenzability matrix and Yq(k) is the pq-element block-out- put vector defined by y Yq(k) : (k) a$+1) a$+q-2) a$+q 1) Along with the block-output equation (3.1), we have the block-input state equation (2.1), which is repeated below for convenience: *(k + q) : AQ*(k) + lrun(k). (3.2) Recall that lq is the g-step reachability matrix. Based on the block form (3.2), (3.1) of the system the state observer by (A, B, C), we define ft.(k + q) : Ae i(k) * Lr[rn( k ) Qni(/r) - EqUr(/.)] + lrUr(k), k  8t4 E. W. KAMEN In (3.3), ft(k) is the estimate of the state x(k) at time k, and L o is the n x pq observer gain matrix deftned over the rittg R. Note that (g.S) differs from the standard form of a state obseruer in that the next estimate i(k + q) is computed q steps ahead of the previous estimate, and the block output vector Yq(k) is used to compute the next estimate [rather than the output value A(k)]. Also note that in order to start the recursion deftned by (3.3)-, it is necessaryto specifyinitialestimates ft,(k)for k-0, 1,...,q 1. Defining the estimnti,on error fr(k) : x(k) - ft(k) and using (3.1)-(3.3), we have that the obsenrer error dlmamics are given by fr(k + q) : le, - Lqonl *(k), k (3.4) We shall say that the error dynamics giver by (g.a) are q-step assignable if for any nXn matrixW over R, tlereis a nXpq matrix Lq over R suchthat Aq -LnQr:W. If (3.5) holds, (3.5) then the error equation (3.4) becomes fr(k + q) -- wft(ft) , (3.6) k and thus, the error dlmamics are completely assignable over a q-step interval. It is easy to see that g-step assignability of the observer error dynamics (3.4) is dual to g-step assignability of the closed-loop system dynamics (2.4) as deftned in the previous section. More precisely, the assignability of the observer error dlmamics is equivalent to the assignability of the closedJoop dynamics for the dual system following dual of Theorem 2.1. (A',Cr,Br). In particular, we have the Tneonsu 3.1. The obsenser eror d4namics (3.4) are q-step assignable for some integer q >I ff and only if the system (A,B,C) is strongly obsercable. ln add.iti,on, if (A, B,C) i.s strongJy obsentable so that A, has a left i,noerse (dt-)t ooe, R, then the error dynimlcs are n-stq assignabie, and for any n )1 n matrixW ooer R, Aq - LrOn - W is satisfied ui,th q : n and L,:lA" -w](o,)'. (e, From Theorem 3.1, we see that strong observability of the system S, C) is equivalent to complete assignability over a n-step interval of the observer error dlmamics. It is interesting to note that this assignability is on  LINEAR TIME-INVARIANT DISCRETE.TIME SYSTEMS 815 scale, whereas in the state feedback control problem the assignability is on the kn time scale. We also have the dual of Theorem 2.2. the k time THBonEM 3.2 . so that On has gain Ln Suppose that the system ( A, B , C) ,s strongly obsertsable iruserse (0,)' oDer R.Then usith q - n andthe obserrer "tnft the A"(Qn)', x(k) : i,(k) fo, all f(o),f(1),...,i(n 1). obsertser (3.3) is a deadbeat obsertser; that is, k By Theorem 3.2, we see that strong obseruability implies that the system's true state x(k) can be determined exactly for k 2 n starting from any initial l). A necessary and sufftcient condition for estimates f(0), f(1),...,i(n the existence of a deadbeat observer of the form (3.3) is grven in the following result which is the dual of Theorem 2.3. THnonnvr 3.3 . There exist an integer q - f ( k) for all k 2 q starting from anA initial estimates f(0), i(1), . . ., ft(q L) if and only if there exists a n x pq matrix Pn ouer R such that (3.3) such that x(k) Aq : PnOq, in u->hich case, the obseruer (3.3) u->i,th Lr: Pn has the deadbeat property. In the remainder of this section it is shown that the state feedback control law (2.3) studied in the previous section can be combined with the " q-scaled version" of the observer (3.3) to yield a type of input-output regulator. First, replacing k by kq in (3.3), *" have that on the kg time scale the obsenrer is given by ft(kq + q) : Ae + ft(kq) + LrlYr(kq) Lur(kq), o ni(kq) k ErUr(t q)l (3.7) Then in the control law (2.3), we replace x(kq) with t(kq), where i(kq) it the state estimate provided by the observer (3.7). This results in the following control law: un(kq): -Fqi(kq), k_0, 1,2,... (3.8) is worth stressing that in order to implement the control (3.8), it is only necessary to compute the estimate ft(kq) on the kq time scale; in other It  816 E. W. KAMEN words, it is only necess ary to operate the obsenrer on the kq time scale. Hence, it is the g-scaled version (3.7) of the obsenrer that we shall utilize in the study of input-output regulation. Replacing k by kq in the error equation (3.4), i(kq + q): len *" have that - Lqonl fr(kq), k: 0, 1,2,..., (3.g) and inserting (3.8) into the g-scaled version of (3.2;, we obtain : AT*(kq) lrFrft(kq), k- *(kq + q) But i(kq) - x(kq) *(kq + q) - i(kq), : le, 0, 1 ,2,.... (3.10) and thus from (8.10), TrFrl "( kq) + frCrfr(kq), k : 0, I ,2,... . (3.1 1) Then combinitrg (g.g) and (3.11), we have that the closed-loop system resulting from the control (3.8) is giver by | *(kq +q) lrt*, +q) : l- -r'"n k:0, Aq??,",]l;l il)l 1,2,... (3.12) Equation (3.12) is the state model of the closed-loop system in the kq time scale. Now if the system ( A, B, C) is reachable and strongly obsenzable, then by Theorems 2.1 and 3.1, for any n X n matrices A and W over R, there exist matrices Fn and Ln over R such that I e" Lo lnEn lnFn A" - LnQn f^Frl wl ( 3. 13) In other words, the system matrix of the closed-loop system (3.t2) on the kn time scale can be assigned up to the extent indicated by (3.13). In particular,  LINEAR TIME-INVARIANT DISCRETE.TIME SYSTEMS if a and W are chosen to (3.13), we have that 8L7 be zero, then setting q - n in (g.tZ) and using r): TnFnfr(kn), k-0, ft(kn + n) : 0, k_ 0, 1,2,.... x(kn + 1,2,..., Combining these two equations gives x(kn) k-2,3,4,..., -0, and thus we have deadbeat control on the kn ttme scale. But since U,(k")- k - 0,L,2 -F,ft,(kn), (3. 14) and i(kn) - x(kn) for k : 2,3,4,..., and since x(k + 1) : Atc(k) + Bu(k), it must be true that x(k) - 0 for k_ 2n,2n + L,2n + 2,... . Hence, the control (3.14) with observer (9.7) with q - n is a dpadbeat input-output regulator on the k time scale. Combining the above results with those of the previous section, w€ have the following result on input-output regulation. Tunonnvr 3.4 . A necessary and sfficient conditi,on fo, the existence of a dnadbeat input-output regulator gioen by (3.8) and (3.7) is that there exi,st an integer q Aq in u;hich Lo: co.se, Po is a - TrQr : PnO * the contro, (3.8) u:ith Fo_ Oo and, the obseraer (3.7) u:i,th ln a'ddition, if the system (A, B,C) i,s d,eadbeat regulator. and strongly obseraable, then q canbe set equal to n, Fn canbe set equal to (ln)'A", oi{ r, can be set equal to A"(On)', where (I;)" is a right inoerse of Tn and (O,)' is aleft i,ruserse of Qn. rei,o,6lxsble 4. APPLICATION TO TRACKINC In this section, we utilize the results derived in the previous two sections to solve a $1pe of trachng problem, called setaoi,nt control. We begin with set-point control of the state x(k) for the system (A, B,C) defined by (1.1),  818 E. W. KAME}I (L.2), and then we consider set-point control of the output y(k), For existing results on trachtg in the case of systems over a ring of funciionr defined o1 i parameter set, the reader is referred to the paper by Conte et al,(1992). Given an n-vector 4 over the titrg R, in state set-point control the over R th; forces the state resPonse x(k) to be equal to x d, the desired set point. Since the state response of the system is giver by x(k + 1) : Ax(k) + Bu(k), the existence of a set-point control u(k) requires that there exists an m-vector tJ@ over R x objective is to determine a control inpui u(0 such that x6:Ax6*Bu,*, (/ - A)*a: (4.1) 81tr*. Now, deftning the translations 7(k) : )c(k) - xd, n$)-u(ft) -u*, we have *(k + t) : )c(k + t) - x4: Ax(k) * Bu(k) - xd, i(k +l):A[ ,(f) +xal+Bla(t)*u*] -xd, x(k+ 1):Ai(/r) +Bn$) + (A-r)*o*Bu*. Then if there exists a u6 over (4.2) R satis$ring (+.t), Equation(4.2) reduces to i(k + 1) - Afr(k) + Bn(k), (4.3) We can write (+.S) in the block-input form *(k + q) - Aei(k) + TrUn(k), (4.4)  819 LINEAR TIME-INVARIANT DISCRETE-TIME SYSTEMS where n$+q aq$): 1) u6 a$+q-2) ue : a u(k+ Uq(k) ;* 1) u@ "(k) Replacitrg (4.5) a k by kq in (4.4) gives *(kq + q): Alx(kq) + Tnlr(kq). nq X n matrix Now suppose that for some q Fq over R. Thet by Theorem 2.3, the state feedbdck control on(kq) : - Fq Aq i(kq) (4.6) in a deadbeat control on the k time scale. That is, n(k) = Q for k: Q,cl + L,q + 2,.... Hence, *(k):xa for k: Q,cl + L_,_q +2,...' results and so the control (4.6) results in state set-point tracking. In addition, using (4.5) we have the the control (4.6) can be rewritten in the form Ur(kq) : - Fq Aq l*(kq) - * ol + 1"3 uI ' " ull' . (4.7) From the above constructions and using Theorems 2,2 and 2.3, we have the following result. Turonnrra 4.1. Ci,rsen the desi,red set point x 4 ooer R, there is a deadbeat set-poi,nt trackl,ng cantrol of the form (4.7) if and qnlA i,f there is an m-lsector |l,6.oDerRsuchihot(l-A)xa:Bu*,andthereexi,stani'ntegerq> amntri,x F, over Rsuchthat Aq : loEo. ln addition, i,f the system(A, B,C) is reachailu, then q can be set uq'uol tu n and Fq can be chosen to be F*: (I;)'An, where (I;)" is a ri,ght inrserse of I;. Now given a p-vector Ua over R, in output set-point control we want to u&) that will force the output y(k) to be equal to U a, the ftnd a "onttol  820 E. W. KAMEN desired set point. The existence of such a control requires that there exist an m-vector n,@ over R and an n-vector x@ over R such that x@:Ax**Bu,*, Cx*, Ua: that is, : l';^ f "lL;:l ;l A sufficient condition for (4.8) to be satisfied is that (4.8) I - A is R and the p x m matrix c(I - A)-rB has a right inverse which case a solution to (4.8) is Lr,@ : VA are assuming is the case. V over R, in (4.e) a, x@: (/ - A)-'Bu*: Clearly, right invertibility invertible over (I - A)-"rAo. (4.10) of C(I - /r)-LB requires that p 4 m, which we To see that (4.9), (4.10) is a solution to (+.S), first multiply both sides of (4.t0) on the left by the matrix I A. This results in the eqlation x@ : Ax* + 81tr*.Now multiplyt"g both sides of (4.10) on the left by C gives Cx*: C(I - ,.1-t nVyo: yo. Hence, the second equation constituting (+.S) is also satisffed. summarizing the above constructions, we have the following sufficient conditions for the existence of a deadbeat output set-point trackei. THronau C(l - A)-rB 4.2. Suppose that I - A is i.noertible has a right inrserse V ooer R. ooer R, p 4 m, and A^ko slrppose thai there is an : lrF, for some F, ooer R. Then the control iltteger q _2 I wch that,As (+.2) u:lth xo_: (I A)-tBu* 'onld u-: VAa'results in dead.beat antput - y(k) : Va fo, k : q, q + I,..., and x(k) : x' ad.dition, if the qstem(e,n,C) ls reachabt"e,thei q can b9 set equal to n, and Fn can be chosen to be F^ : (l*),A" where (1,), is a rigft.t intserse of 1,. set-point tracki.ng; that is, fork: q,q + 1,... . ln we conclude this section by considering the case when the state r(ftq) cannot be directly measured, and thus must be estimated. In this case we  LINEAR TIME-INVARIANT DISCRETE-TIME SYSTEMS BzL shall utilize the obsenzer givet by (3.7) and the control law (4.7) with x(kq) replaced by the estimate ft,(kq). Using the above results and those in the previous sections, we have the following sufficient conditions for the existence of a deadbeat output set-point tracker. THeonru 4.3. Suppose that I - A is i,noertibl,e ooer R, p 4 m, and C(l - A)-LB has a right inoerse V oaer R. Ako suppose that there is an i,nteger q >- I atch thnt As :lnFr: PnAn for some matrices_F.n 1nd P, ounl R.'Then the observer (s.z)' *itt Lo: Po and the control (4'7) toith x&fl: i&fl, xa: (l - a)-tBu*, and'u*:'Vga rewlts in d'eadbeat outtriking; that is, y(D:ga for k:2q,2q + !,'.-, and put 'x(k)setaoini : xa for k : 2q,2q + 1,. -. . tn a.dli,tion, if the system (L n,C) ts reachable and strongly obsensable, then q can be set e.qual to n, F, can be set equal to (l^\'A", ond P* canbe set equal to A"(O,)t, ushere (ln)' is a right i,nrserse of l^ and (O,)' tis aleft inrterse of O,. 5. STABILIZATION A limitation of control-theoretic results based on reachability and strong observability is that these dynamical properties may be too "strong" for certain rings R of interest. To achieve more general results, we can consider schemes that yield a stable closedJoop system rather than attempting to assign the closed-loop dynamics. This of course requires a notion of stability, whiih can be introduced in a purely algebraic way [e.g., see Khargonekar and Sontag (1932) and Sontag (1985)1, or can be introduced by adding a topologrcal structure on the .i"g R [e.g., see Byrnes (1980), Kamen and Green (1980), Green and Kamen (19s5), and Kamen (1985)1. In this section, we utilize the block-input form of the state equation to study the problem of stabilization for systems (e, n,C) deffned over a ring R, but wh6re now R also has the structure of a normed algebra over the real R. More precisely, it is assumed that R has a norm ll ll, and R contains a copy of the reals R, so that R is an R-algebra. Given an n-vector x : l*, *, "' xnl' ove, R, we deftne the norm of x by ;lrll' : llrrll2 + llrnlln + "' +llr,ll2. For any matrix M over R, the norm llM ll is the induced operator norm. A system (L n,C) over R defined by (1.1), (1.2) is said to be asymptoticaLly stable (AS) if for any initial state r(0) over R ll a*"(0)ll -o as k+." (5.1)  822 E. W. KAMEN It is easy to prove (and is well known) that (5.1) is equivalent to the existence of a positive integ er q such that llAqll (5.2) Suppose that (A, B,C) is AS, and let gmin denote the smallest positive integer_such that (5.2) holds with q : g^in It is known that Qmin may be larger than n, the size of the matrix A. Note that this is in contrast to the property of reachability in that reachability always implies reachability in n steps. Given r!" system ( A, B , C) and a positive integer q the g-scaled block-input state equati o; (2.2) which is reprod,r"J below: *(kq + q) : AQ *(kq) + trUr(kq) (5.3) . Then as discussed in Section 2, with the control un(kq) - -Fq*(kq), k- o, I ,2,..., (5.4) the resulting closed-loop system in the kq time scale is giver by *(kq + q) _ l/r, TrFrl "( kq), k- 0, I ,2,.... (5.b) We then have the following concept. DnnNrrroN 5.1. The system (A, B,C) is q-step stabilizable for some integer g R such that ileq_qFl (5.6) We have the following result on g-step stabilizability. PnoposrrroN 5.f . Suppose that the system (A, B,C) is q_step stabilizable, .so that there exists an Fq oner R such that (5.6) is satisfi,ua. rhen the control (5.4) stabilizes the giaen system on the k time scale; that is, llr(k)ll -+ 0 for Proof. anA initial state r(0) -orser R. Suppose that there exists an Fo over R such that llAq C equation (5.5) satisfies the inequality ll "(kq)ll < "*ll*(o)ll , k: L,2,... - I; F,,ll-  823 LINEAR TIME-INIVARIANT DISCRETE-TIME SYSTEMS 0 as Then since c k + m, but it must be shown that convergence to zero occurs on the k time scale. To see this, first note that since Ur(kq) : -Fqx(kq), llur(tcq)ll + 0 as k -+ @, which implies that llz(k)ll * o as k + &. Then since x(k + 1) - Ax(k) + Bu(k), for any initial state r(0), ll*(kq+i)-Ai*(tilll+0 as k+oo for i-L,27...1c1 1, t llr(k)ll -+ 0 as k + oo. By Propositions 5.1, we see that g-step stabilizability is a sufftcient and thus it must be true that condition for the existence of a stabilizing state feedback control. As a partial converse to this result, it turns out that if the system ( A, B, C ) is stabilizable by memoryless state feedback [i.e., there is an F over R such that x(k + 1) - ( A - BF)x(k) is AS], then the system is g-step stabilizable for some q 5.2. If there is an F ooer R such that x(k + 1) : ( A Bilx!) is AS, then the system (A, B,C) is q-step stabilizable fo, soffLe PnoposrrroN q - Proof . Suppose that there exists an F over R such that x(k + 1) - ( A BF)x(k) is CS. Then there is a positive integer q such that ll(a BF)qll (A -BF)':AQ lnF, for some nq X n matrix Fq over R. Thus (5.6) is satisfted, and the proof is completed. By Propositions 5.1 and 5.2, the stabilization problem "reduces" I to ftnding an Fq over R such that ll A: TqEqll is minimized and the minimum value is less'than 1. Of course, there is the problem of selecting q. One approach would be to start with some value of q such as q - n, and then r"q,r"tttially increase q until a minimum less than I is achieved. If a minimum less than I is not found after considering a large range of values of q, one would expect the "probability" to be high that the system is not stabilizable. Of course, if lq has a right inverse (lq)" over R for some q >_L-(i."., the system is reachable), then a minimizing'Fn is F, : (lq)'Aq, and the minimum value is zero. This results in Ceadbeat'control, which was considered in Section 2.  824 E. W. KAMEN In the remainder of this section, we show that the computation minimizt-ng Fq can be carried out using a generalized linear quadratic of a (LQ) approach. This construction requires that the normed algebra R have an inner product given by ( x, A) € R for all x, A c R, and which satisfies the standard assumptions: For all x, A, z c R and a € R : (a, x), (x*z,A)- (*,y) + (z,A), (x, a) (o*, A) - a(x, (*,*)As is well known, if A) , ll"llt. R is an algebra over the reals R with an inner product (*,A) that satisfies the additional properties for all x, e R x, _ and (*, *) - 0 if and only if 0, then R can be made into a normed algebra by defining the norm by llrll - ( x, x)tt'. In addition to the inner product operation, we also require a *-operation from R into R with the properby that (x, Az) - (y* x, z) for all x, U, z € R. Examples of normed algebras with a *-op"ration that arise in applications are given in Green and Kamen (tgAS) and Kamen (lg85). Finally, the inner product, norm, and *-op"ration can be extended to vectors and matrices over R as follows. Given the n-vectors x l*, xz "' *nf' and A - lA, Uz ... Unf',we deftne n \l /r (*n, (*, a) llrll i:I : (x, u), *)t/'  LINEAR TIME.INVARIANT DISCRETE-TIME SYSTEMS - (rprj) over R, we deftne lryx P overR, anynXn matrix and given a matrixW : (P*, A) (x, P* - 825 (u:fi).Note that for A). (5.7) Now grven a mq X mq u:eightingmatdxW over R, consider the quadratic cost functional I* - ll " k_0, 1r2r..., (kq + q) ll' +llwu,(kq) ll' (5.8) where x(kq) is given by (5.3). The objective is to solve the generalized LQ problem; that is, we want to compute a block input {.lr(kq) over R that minim rzes the cost l * for each k ( A, B , C ) is given Tseonnv in the next result. 5.1. lf for son'Le integer q 1ryxW is imsertible ooer R, then a control Ur(kq) that mini,mi,zes J7, un(kq) : - [ ri rn + 1ry *w ]-'ry^ ' *(kq) Proof. In terms of the inner product (','), the cost i,s (5.e) - /1 can be written in the form (*(kq + q), x(kq + q)) + (wur(kq),wur(t I*: Inserting the expression (5.3) for x(kq + q) into (5.10) and q)). (5.10) using (5.7) gives Ir,: ( "( kq) ,( Ar)* A, *(kq)) + z(*(kq), ( A')* trUr(t q)) + (ur(kq) , [s fn + 1ryxw]un(kq)). Then gives if ryq + W*W I^: ll tn $il * ( is invertible over R, "completing the square" in + [rirn + zryxw]-'t;^ n*(t " $q), ( A,)*le, rn(S rn + illl' 1ryxw )-' t;^ rf*f tq)) ]r  826 It E. W. KAMEN is then obvious that the minim tzingcontrol is given by It is interesting to note that the optimal (5.9). t control (5.9) is in the form (5.4) where Fq: tryq + w*wl*'r;e, (5.1 1) Also, one should note the simple form of the feedback gain Fn; in particular, Fn be c-om,puted without having to solve a Riccati equatioh, as one must 2an in the standard LQ approach to systems over the reals. As seen from the following result, with a proper selection of the weighting w, the control (5.9) is a stabilizing control if the system is g-step stabili"zablel 5.2. 9rppose that the system (A, S,C) is q-step stabilizable q 2 r. Let w : or/zln*, where o is a strictlE positi.ae real for number' Then i,f o is sufficiently small'and $lo + clo^ is {noertible orser Tsnonnu some integer R, the control (5.9) results in a closed-loop tyitnh that & eS. Proof. .S,1ppose over R such that control is ll 1,,: that there is a control Ur(kg)^: -Gqx(kq) with ,qq lqcqll ll( ^n rrGn) "( t illl' + ollcr*(kq)il' Gq (5.12) Let Fo denote the feedback gain of the optimal control with W : aL/zlo*. Then since the cost with the optimal control cannot be greater than the cost (5.L2), it must be true that ll( rnFr) ^' "( rrq)ll' + olltn*(kq) ll' * ll( a' r,G,) "( rrilll' + ollc,*(kq) ll' Thus, since lleq ll A, Tqcqll lnErll < 1. Therefore, by Proposition S.r the resulting closed-loop AS. I :_o)"r* With W and the feedback gain Fq given by (5.11), the system matrix Aq TnFn of the resulting closed-loop system on the kq time scale is system is given by Aq TrFr: ft- tn(ryq + orr*)-'ry]r^, (5.13)  LINEAR TIME.INVARIAN{T DISCRETE-TIME SYSTEMS 827 Here we are assuming that the inverse ir, (5.13) does exist. Now by Theorem 5.2, we know that the closed-loop system with the system matrix given by (5.13) is AS if the system is g-step stabilizable and a is chosen to be sufftciently small. Hence, it is possible to test for stabilizability (modulo the invertibility requirement) by chechng to see if the norm of Ir, L(ryq + crq*) -r r;7 o, is less than I for some integer value of q and some positive value of o. 6. CONCLUDINC COMMENTS It is clear that the results in Section 5 can be dualized to yield correspondresults on the construction of block-form observers deftned by (3.3) *ittt error dynamics that are AS. In addition, the stabilization results can also be applied to the design of input-output regulators grven by the observer-statefeedback-controller combination &scussed in Sections 3 and 4. Via this approach, new results on regulation and set-point tracking can be obtained without having to require reachability and strong observability of the glven system. The details are not pursued here. itg REFERENCES Nbertos, P. 1990. Block multirate input-output model for sampled-data control systems, IEEE Trans. ,\utomnt. Control 35:1085-1988. Nbertos, P. and Ortega, R. 1989. On generalized predictive control: Two alternative formulations,,\utomatica 25:753-755. Brewer, J. W., Bunce, J. W., and Van Vleck, F. S. 1986. Linear Systems oDer Com,matati,oe Rings, Marcel Dekker, New York. Brewer, I. W. 1992. Ary PID is FC-l and C[X ] is FC, in Proceedings of the IMA Workshop on Linear Algebra fo, Control Theory, Inst. for Mathematics and Its Applicati,ons, Univ. of Minrr"rot", Minneapolis, to appear. Brewer, ]. W., Klingler, L. C., and Schmale, W. 1993. AlVl ir a CA-ring and coefftcient assignment is properly weaker than feedback cyclization over a PID, to appear. Buescher, K. L. 1988. Representation, Analysis, and Design of Multirate Discrete-Time Control Systems, M.S. Thesis, Univ. of Illinois, Urbana-Champaign.  828 B)anes, E. W. KAMEN c. I. 1980. Realization theory and quadratic optimal controllers for systems in Proceedings of the lgth IEEE Conference on Decision and Control. Conte, G., Jetto, L., Longhi, S., and Perdon, A. M. 1992. Simultaneous trachng for a family of linear plants, in Proceedings of the slst IEEE conference on Decision and Control, Tucson, Ariz., pp. 2884-2887. Emre, E. and Khargonekar, P. P. 1982. Regulation of split linear systems over rings: deftned over Banach and Frechet algebras, Coefffcient assignment and observers, IEEE Trans. Automat. Control AC27:104-113. Francis-, B. A. and Georgiou, T. T. 1988. stability theory of linear time-invariant plants with periodic digital controllers, IEEE Trans. Automat. Control 33:820-g32. Green, W. L. and Kamen, E. W. 1985. Stabilizability of linear systems over a commutative normed algebra with applications to spatially-distributed and parameter-dependent systems, SIAM J. Control Optim.23:l-18. Gizzle, J. w. and Kokotovic, P. v. 1988. Feedback linearization of sampled-data systems, IEEE Trans. Automat. Control 33:857-85g. Grizzle, j. w. and Moraal, P. E. 1990. Newton observers and nonlinear discrete-time control, in Proceedings of the 29th IEEE conference Decision and control, Hawaii, pp.760-767. Haigawara, T. and Araki, M. 1988. Design of a stable state feedback controller based on the multirate sampling of the plant output, IEEE Trans. Automtfi. control 33:812-819. Kamen, E. W. 1985. Stabilization of linear spatially-distributed continuous-time and discrete-time systems, in Multidimensional Systems Theory (N. K. Bose, Ed.) Reidel, Dordrecht, pp. 101-146. Kamen, E. W. 1991. Linear systems over rings: From R. E. Kalman to the present, in Mathematical System Theory-The lnfluence of R. E. Knlnnn (A. C. Antoulas, Ed.), Springer-Verlag, Berlin, pp. 3Il-324. Kamen, E. w. 1992a. study of linear time-varying discrete-time systems in terms of time-compressed models, in Proceedings of the 31st IEEE conference on Decision and. Control, Tucson, A.ir., pp. 3070-3075. Kamen, E. W. 1992b. Regulation of time-varying discrete-time systems based on a time-compressed formulation, in Proceedings of the Symposium on lmplicit and Nonlinear Systems, Arlington, Tex., pp. 267-274. Kamen, E. W. and Green, W. L. f980. Asymptotic stability of linear difference equations deffned over a commutative Banach algebra, J. Math. Anal. Appl. 75:584-601. Khargonekar, P. P. and sontag, E. D. 1982. on the relation between stable matrix fraction factorizations and regulable realizations of linear systems over rings, IEEE Trans. Arnomat. Control AC-27:627-638. Khargonekar, P. P., Poolla, K., and Tannenbaum, A. 1985. Robust control of linear time-invariant plants using periodic compensation, IEEE Trar*. Atfiomat. con- trol AC-30:1088-1096. R. 1989. Robust adaptive regulation without persistent excitation, rEEE Trans.'\utomnt. Control 34:1260-1267. Lnzano,  LINEAR TIME-INVARIANT DISCRETE-TIME SYSTEMS 829 Powell, B. K., Cook, J. A., and Gnzzle, J. W. 1987. Modeling and analysis of an inherently multi-rate sampling fuel injected engine idle speed control loop, in Proceedings of the 1987 Ameri,can Control Conference, Minneapolis, pp. r54-1549. Sontag, E. D. 1976. Linear systems over commutative rings: A survey, '\utomnt. 7:I-34. Ri,cherche E. D. 1985. An introduction to the stabilization problem for parametrized families of linear systems, Canterrry. Math. 47;369-400. Sontag, Recehsed B May J993; final marwscri,pt accepted 20 September 7993