BlockFormControl .pdf

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