NASA Contractor Report 3016
Lectures on Algeb r"ic System Theory:
Linex Systems Over Rings
Edward W'. Kamen
CONTRACT A-43TI9.B
JULY
1978
N/\SN
National Aeronautics
and Space Administration
Scientilic and Technical
lnlormation Otlice
1
978
PREFACE
This report provides an introduction to the theory of linear systems defined over rings. The theory is presented with a minimum of
mathematical details, so that anyone having some knowledge of linear
system. theory should find the work easy to read. The presentation
centers on four classes of systems that ean be treated as linear systems
over a ring.
These
are (i) discrete-time systems over a ri-ng of scalars
the integers; (ii) continuous-time systems containing time delays;
large-scale discrete-time systems; (iv) time-varying discrete-
such as
(iii)
time systems.
The
material given here is an expanded version of a series of lec-
tures given at
NASA Ames Research
during the week of
November
Center, Moffett Fie1d, California
7, L977. I an very grateful to Professor
R- E. Kalman and Brian Dooli-n for the opportunity of giving these lectures.
My
gratitude also extends to Eduardo Sontag' Yves Rouchaleau, and Bostwick
for countless hours of discussions on linear systems over rings'
Part of the research work presented here was supported by the U. S' Army
Research Office, Research Triangle Park, N. C., under Grant DAAG29-77-G-
Wlzman
0085.
1.
INTRODUCTION
1.1 Linear systems over fields.
Since the late 1950'sf a great deal of effort has been devoted
to the study of linear fj-nite-dimensional continuous-time and discrete-time
systems specified by stat,e equations defined over
a field K.
More precisely,
given a triple (FrGrH) of nxtr nxm, pxn matrices over a field Kr. a
m-
input p-output n-dimensional time-invariant discrete-time system is
defined by the state equations
x(t+1)=Fx11;+eu(t)
(1.1)
y(t) = Hx(t)
where E<Z =
set of integers. In the continuous-ti-me case, with r = n
field of real numbers, a time-invariant system is given by lhe state
equations
P
=Fx(r) +cu(r)
(r.2)
y(t) = Hx(t)
where
teR. In both (1.1) and (L.2) , the state x(t), input u(t),
output y(t) are column vectors over the field
-1-
K.
fi-eld
Tnitial efforts in studying linear systems defined over a
Kusuallyassl$edthatKwasaparticularinfinitefield,suchasthe
fieldRofrealnumbers.Infinitefieldsarefieldsthatcontaina
subsetwhichcanbeputintoaone-to-onecorrespondencewiththesetof
nurnbers
integers. In addi-tion to the field R' the field of rational
andthefieldofcomplexnrunbersareexamplesofinfinitefields.
theory of timeThere are several textbooks (e.9., lL,2,3l) on the
invariantandtime-varyinglinearsystemsdefinedoverthefieldR.
Inasequenceofpublicatlonsbeginningin1965'R'E'Kalman
|4,5,6Td.eveloped.analgebraictheoryfordiscrete-timesystemsofthe
field K'
form (1.1) defined over an arbitrary (finite or infinite)
in addition to being applicable to systems over the real or
systems over finite
complex numbers, Kalmanrs theory can be applied to
Hence,
fields, which includes linear sequential circuits [7] '
L.2 Discrete-time systems over a ring of sealars'
Afterthecompletionofhisworkondiscrete-timesystems
over arbitrary fields, Kalman initiated the study of discrete-time
sys_
rings. The notion of a ring is a generalization of the notion
and multiof a field: A ring is a set with two operations, called addition
elements
pli-cation; however' unlike a field' a rlng can contain nonzero
tems over
thatdonothaveamultiplicativeinverse(see[B,chapterI]]).
the usual
An example of a ring is the set of integers z with
addition and multiplication operations. since neZ has a multiplicative
a field'
inverse belonging Loz if and only if n = 1 or -1' Z is not
in a symbol
Another exanple of a ring is the set K[z] of polynomia]s
-2-
z
with coeffi-cients in a field K, with the usual operations of polynomial
additi-on and multiplication.
The only elements
in K[z] that are invertible
are the nonzero polynomials of degree zero.
The
first detailed results dealing with discrete-time
systems
over arbitrary colnmutative rings were derived in Rouchaleaurs Ph.D.
thesis t9l in
concerned
the supervision of R. E. Ka1man. This work was
L972 under
with the class of linear time-invariant discrete-time
systems
over a commutative ring A given by the state equations
x(t+1) =rx11; +cu(t)
(1.3)
y(t) = ux(t)
where
teZ, F, G, H are nxn, nxm, pxn matrices over the ring A, and x(t),
u(t) | y(t) are column vectors over
A.
An interesting example of a system over a ring is a system
with the ring of scalars equal to z. By definition, such a
system
accepts vector sequences ovey z, processes these sequences using integer
operations, and then outputs vector seguences over Z. These systems are
of interest from a computational standpoint, since integer operations
can
be implemented "exactly" on a digital computer (assuming that magnitudes are
less than IO12 for I2-digit precision), Further, systems over z appear
in various applications, such as coding theory [10] and scheduling or
sequencing problems
tfll
.
-3-
1.3 Continuous-time systems over rings of operators'
In1973,Kamen[12]showedthatalargeclassoflinearinfinitedimensional conti-nuous-time systems can be represented by first-order
vector differential equations defined over a ring of operators (due to
publication delays , l:l.2l did not appear in print until 1975) ' The ring
in t12l and [13,14] applies to time-invariant and timevarying continuous-time systems containing pure and distributed tine
delays. Independently of this work, williams and Zakian [15,16] constructed
approach developed
the
same
type of operator setting for a class of time-invariant continuous-
tlme systems with pure time delays'
In this section we shall define the operator framework for the
class of systems with commensurate delays given by the dynamical equations
ax(t) - of F.x(t -ia)+
'dt
?^a
1=U
y
I crt(t-ia)
i=0
_L
(t) _t
i=0
(1.4)
H,x(t
- ia)
T
a is a fixed positive number, the F., Gi'Hi are nxn' nxm' pxn
column
matri-ces over the field of real numbers R, and x(t), u(t) ' y(t) are
where
vectors over
R.
x(t) in (1'4) is usually referred to as the state at
time t; however, as a result of the delay terms' the actual state at time
t is the function segment x(t), t - qa < r < t- To solve (1.4) for t > 0,
The n-vector
we need to know the actual state at time t = O, which consists of the func-
tion segment x(t),
-qa < 'r 3 0.
-4-
In the mathematics literature, equations of the form (1.4), or
generalizations of (1.4), are usually treated as ordinary differential
equations in a Banach or Hilbert space consisting of function segments
(see [17,18,19]). In contrast, we shalt view (1.4) as a vector differen-
tial equation with coefficients belonging to a ring of delay operators'
The constructions are as follows-
Let V denote the linear spaie consisting of all R-valued functions
defined on R with support bounded on the left {i.e.,
for each veV, there
Let d:v+V denote the a-second
is a t-V-eR such that v(t) = o for all t<t-_).
V
delay operator on V defined by (dv) (t) = v(t-a), v€V. We can extend
d to
column vectors
v = (vl, - -. rtr)' over V by defining
(dv)(t) - (vl (t-a),..-,vn(t-a))'
where the
prime denotes the transpose operation.
r a.di where a.<R and
Let Rldl denote the set of all finite sums irlj
(d]v) (t) = v(t_ia), v€v. with the usual operations of polynomial addition
multiplication, R[d] is a ring of delay operators'
Now vlewing the state trajectory x and the input function u as
(1'4) in the form
column vectors over V (or some subspace of V), we can write
and
(r)
%tI = (F(d)x) (r) + (G(d)u)
(1.5)
y(t) = (H(d)x) (t)
-5-
the operator ring
where F(d), G(d), H(d) are nxnf rIxIIlr Pxrl matrices over
R[d] given
bY
q
F(d) =
I
i=0
_l_
F.d
, c(d) =
l_
r
I c'da,
a=U
fi
H, di
u(d) _L
l_
i=0
of time-delay systems given by (1'A) can be studied
(1.5) defined over the ring
i-n terms of the vector differential equation
Thus the class
Rtd].Weshallrefertothesystem(1.5)asalineartime-invariant
continuous-time system over the rinq of operators Rtdl '
given by the dynamical
EXAMPLE 1.1 Consider the time-delay system
equations
dx- (t)
-+=
dx" (t)
dtr
--xl(t-a) +xr(t) -xr(t-2a) + u(t)
= x- (t) + xl(t-a) - xr(t) + u(t-a)
y(t) = xr(t-a) - xr(t-2a) + xr(t)
(1.5) with
This sYstem of equations can be wrilten in the form
r'(d)
=
II
G(d)
=
-6-
[l
u
rar =
[-42
I
By
exploiting the structure of the operator-ring representation
(1.5), we can develop an algebraic theory for the class of time-delay
systems given
by (1.4). In particular, we can obtain constructive results
given in terms of operations on matrices and vectors defined over the ring
R[d], or ring extensions of R[d].
Examples
wilL be given in the next
three chapters of these notes.
As noted above, systems with'noncommensurate delays and distributed
delays can be studied in terms of differential equations over rj-ngs of
data for equations of the form
operators. AIso. as shown in [14], initial
(1.5), or generalizations of (1.5), can be incorporated into the operator
framework.
Note that in the representation (1.5), the elements of the ring
Rtdl act on functions; whereas in (1.3), the elements of the ring
A
act on values of functions. This is the reason for referring to (1.5)
as a system over a ring of operators and (1.3) as a system over a ring
of scalars.
using the
We
shall
show
that both types of systems can be studied
same techniques.
I.4 Discrete-time systems over a ring of operators.
In this section we shall
show
that there are discrete-time
systems
that can be treated as systems over a ring of operators. Consider the
class of discrete-time systems given by the following dynamical equations
qr
x(t + 1) = I r.x(t-i) + I c.u(t-i)
g1
a=U
t=U
S
v(r) = I n.x(t_t)
a=u
l
where EeZ, the Fi,Gi, H. are nxn' nxm, pxn matrices over a field K,
x(t),
u(t)'
y(t) are colunn vectors over
-7-
K.
(1.6)
5sginrssn
Note the similarity
(1'4) and (1'6) '
In fact' if
we
proceedaswedidaboveforcontinuous-timesystemswithtimedelays'
difference equation
it is clear that we can write (1'6) as a vector
riohtover the operator rinq K[ o] consistincr of al1 colvnomials in the
to the fj-eld
shift operator o:x(t)+x(t-1) with coefficients belonging
K. More PreciselY, we have that
x(t + 1) = (F(o)x) (t) + (G(o)u) (t)
(1.7)
y
where F(o), C(o),
tt (o
(r) =
(H (o)
x) (t)
) are matrices over Klol given
r(o) = -.iI"ro^,
1
G(o)
.i
-
lv,v
?r_
a
f
bY
.i
H(o) = ?a
)H.o
a
WeshallreferLothesystem(1.7)asalineartime-invariantdiscretetime system over the ring of operators K[o] '
(high-dimensional)
Via the representation (1.7), we can study large
discrete-time systems in terms of
some subset
of the set of all possible
statevariables.Thisismadepossiblebytumpingtogethercomponents
In ot'her
with memory in the coefficient matrices F(o), G(o), H(o).
aggregated model for
words, the representation (1.7) can be viewed as an
large discrete-time
sYstems'
-B-
The representation
(1.7) is a natural model for systems consisting
of an interconnection of subsystems separated by time lags with the
components
of x(t) equal to the states of the subsystems. This is
illustrated by the following
EXAMPLE
1.2
Suppose
example.
that K = R. Consider the discrete-time
system given by the following block diagram.
Here
xl(t) (resp. x, (t) ) is the state of the
function L/ (z+lj (resp. L/z-l)).
We
subsystem having transfer
have that
xr(r+1) =-*1(r) -xr(t-1) +u(t)
xr(t+1) = xr(t) + xr(t-1)
Y(t) = xr(t)
These
equatl cr:s can be w ritten
r'(o)
=
[: I
i-n
the form (1.7) with
H(o)
[]
-9-
=F
!
. Defining xt (t) =
have a representation of order two over R[o]
a f our-dimensional representation
x, (t-1) and x,4z(t) = x. (t-1) , we also have
Thus
we
over
R
given by
tr+rf Fr
'll
xrtt+r)l lo
*-(r+r)l
II
rll
"-
xntt+rl
Y
I
L.
-'-l
F,
,Jl '-
o
0
1.
I
;ll";;.;l.l;1",.,
0
o
o
1
0
'-l [r-''l b]
I
I i*rt.rl l.
(1.
B)
I
(t) = x, (t)
TherepresentationoverR[o]canbeveryuseful'becauseinsomeproblems
work with the
it is more efficient from a computatj-ona1 standpoint to
than the four-dimensional
two*dimensionar representation over R[o], rather
Chapter 4'
representation over R' An example will be given in
1.
5 Additional
examPles'
In addition to the
examples given above' there are many other
examplesofsystemsthatcanbetreatedaslinearSystemsoverrings.
Theseincludesystemsgivenbydiscretizedpartialdifferentiatequations
digital filters viewed as linear
l2O,2Ll and linear two-dimensional
in one variable
defined over a ring of proper rational functions
systems
122)
'
Lineartime-varyingsystemscanalsobeviewedassystemsoverringis,
inthiscasearingoftimefunctions.However,thealgebraictheory
oftime-varyingsystemsdiffersfromthetheoryoftime-invariantsystems.
from the fact that time-varying
The primary reason for the difference it"*=
systemsrviewedassystemsoveraringoftimefunctions'mustbestudied
cal1ed a pseudolinear
in terms of a special type of nonlinear transformation'
-10-
transformat.ion [23].
In the last chapter of these notes' we develop this
The
approach for the class of linear time-varying discrete-Lime systems'
theory is based on the concept of a semilinear transformation, which is
an example of a pseudolinear transformation'
- 11-
2.
REPRESENTATION AND REALIZATION THEORY
2.I Abstract systems over rings'
ForthethreeclassesofsystemsdefinedinSecti-ons1.2-L.4,
depend only on
it turns out that many structural and dynamical properties
thetriple(F,G.H)ofmatricesappearinginthestateequations.In
(e.9.,
other words, the particular form of the dynamical equations
primary consideration'
discrete time or continuous time) is not always a
Thusi|ispossibletodevelopageneraltheoryofsystemsoverrings
This was the
specified in terms of a triple of matrj-ces over a ring'
rings'
by Sontag in his survey paper 1241 on systems over
approach taken
define the major components of the theory' beginning
with the notion of an abstract system over a ring'
and let n' m' p be
DEFINITION 2.1 Let A be a commutative ring
In thi-s section,
we
fixedpositi-veintegers.Anabstract(free)lineartime-invariantsystem
overAi-satriple(F,G,H)ofnxn,fixlllrPxllmatricesoverA.Theinteger
n is called the dimension of the system (F'G'11) '
Althoughtheconceptofanabstractsystemdoesnotincludeany
explicitreferencetodynamicalbehavior'ana-bstractsystem(F'G'H)
canbeinterpretedasadynamicalsystembyassociatingasetofState
equationsspecifiedintermsofF'G'H'Forinstance'(F'GfH)canbe
interpretedasadiscrete-timesystemovertheringofscalarsA,given
by the state equations (1'3)'
Let (F,G,H) be an abstract system over the ring A'
Suppose that
CisaringextensionofA,i.€.,AisasubsetofCwiththeproperty
thatadditionandmultiplicationinC,whenrestrictedtoelementsinA,
rn other words. the
are identicar to addition and muttiplication in A.
-L2-
ringAisasubringofC'ThensincetheelementscomprisingF'G,H
can be viewed as elements of c, (F'G,H; can be viewed as an abstract system over C.
ItisofparticularinteresttonotethatwhenAisanintegral
Integral
domain, there is a ring extension of A which is a fie1d.
domains are commutative rings that do not contain divisors of zeto'
Thatis,ifab=Oforsomea'b€A,theneitheraorbmustbezero.
Examples of integral
domains are the ring of integers Z and the operator
rings R[d] and Klol constructed in the preceding chapter'
An i-ntegral domain A can be viewed as a subring of a field
Q
(A)
'
ca1led the quotient field of A. The field Q(A) is equal to the set of all
formalratiosa,/bwherea,b€A,blo,withadditionandmultiplication
defined by
ut/bt+ ar/b, = (arb, *.2b1)/$Lb2)
(ar,/br)
Gr/b) =
(arar) / (br/b2)
For example, the quotient field of Z is the field of rational
and the quotient field
Now
-,.;:
numbers
of R[d] is the field of rational functions in d'
given an abstract system (F,G,H) over an integral domain A'
:a:l view (F,G,H) as a system over the quotient field Q(A) '
-;i-3i3 =x. s--s the possibility
of utilizing
results from the theory of
svs:e!:ls c-.-=r :i=lCs in the study of systems over rings'
Although
this approac:: is i:seful (e.g., in the realization problem), the
-
l3-
Thus
quotient-field
framework seldom gives a complete solution to a given
problem, si.nce in general the results are specified in terms of elements
of Q(A), rather than elements of A'
Next, we have the concept of an input/output sequence'
input/output
DEFINITION 2.2 Let m,p be fixed positive integers" An
(L/o) sequence f over a commutative ring A is a sequence f = GL' J2' "')
system
consisting of pxm matrices over A. The i/o sequence of an abstract
(F,G,H)oradynamicalsystemspecifiedintermsof(F'G'H)isthesequence
i-I
f = (J,, J", ...) where Ji = H(F )G for r = r'z'"'
LZ
In the remainder of this section, we shall show that the i/o sequence
associated with the systems defined in sections 1.2 - L.4 completely characterizes the input/output behavior of these systems'
(a) Consider the discrete-time system over the ring of scalars
Solving (r.3) by iteration,
with the dynamical equations (1.3).
that the state x(t) at time t resulting from initial
t^o < t and i-nput u(t),
A
we have
state x(to) at time
t = ao is given by
t-t ox(to) +-'l
- i'rc-i-I"rr(i),
x(t) = I'
t > to
(2.1)
:
I-L-!
o
If x(t ) = O, the output resPonse is
L-t
y(t) = I
i-
HF
L-r-rcu(i),
t
-L4-
t >t
(2.2)
From
(2.2) it is seen that the input,/output behavior of the system is
i -1*G
ptetely determined by the sequence (tr_,tr,...) wher" Ji = HF-
com-
for i = L,2,.-.
(b) consider a continuous-time system over the operator ring R[d]
with the dynamical equations (f.5).
that x(t) = O for
t < O and taking the (onesided) Laplace transform of (1.5), we get
Assuming
y(s) = tt(e-as) (sr - r("-u");-161.-t=;u1=1
where
r(e-as),
settingd=.-"",
of u (t)
(v
(t) ) .
G{e-as)
*") are
, H(e
_ac
and where
Thus
computed from
F(d), G(d), H(d)
by
U(s) (resp. v(s)) is the Laplace transform
the transfer function matrix Tlsre-as) is given
T(s,"-as) = n(e-as) (sr - F(.-""))-rc(.-t")
we have that
Expanding (sr - F(.-""))-1 i.rto a power series ir,
"-1,
T(s,e-as) = I Hle-as1Ui-1(.--=)G(e-as)s-i
i=1
Hence
T(s,e-as) can be determined from the sequence (Jl(d),J2(d),...),
vhere J. (d) = H(d)ri-l(a)G(d).
-15-
by
operator ring
(c) Consider a discrete-time system over the
(f'7) ' we shall specify the input'/
K[o] with the dynarnical equations
the formal z-transform defined as follows'
output behavior using
LeEzbeasymbol'Givenafunctionf:Z->KwiLhf(t)equaltozero
fort<0,wedefinethe(formal)z-Lransfoxmofftobetheformalpower
-r?-i
series F(z--; = L f(i)z
the z-transform
,::h. that x(t) = O for ts O and take
of (1.7) '
we get
r
y(z-r) = T(z-1-)u(z-1-)
-I.
is lhe transier function matrix'
= H(z ) \zr- - r,(r-t))-lc("-l)
-t
-1-)) -1 into a formal Power series Ln z -, we have that
(z
F
Expanding QI
*)
-1
where T(z
e-L)r-i
,,(r-r) = i
"1"-1;ui-r(r-1)c
i=l
(2. 3)
where J' (o) = H(o)ri-l(o)G(o) '
' J2G)' " ') '
the expansion (2;3)
However' it should be noted that
Thus the sequence (Jl(o)
determines r("-1)-
isnotunique.Therefore,theinput/outputbehaviorofadiscrete-time
uniquely by a sequence (Jl(o)' J2(o)
system over K[o] cannol be characterized
over Klol
.
2.2. Problem of realization
to realizability
rn this section we present a general approach
systems' The results given here can
based on the concept of abstract
systems over a ring of scalars
be applied directty to discrete-time
a ring of delay operators'
and continuous-time systems over
-16-
2.3
DEFINItION
An abstract system (FrG,H) over A is a realization
of an i/o sequence (J1,J2,...) over A if and only if Ji = Hlpi-115
for i = I,2,...
A reali-zation (F,G,H) is mi-nimal if its di-mension is
minimal among all possible realizations.
Let us first
consider the realization
of a scalar sequence f
=
(a.,a.,..-),
a-e A" To the sequence f, we associate the formal power
LZa
s
'
-r =
series w(z-r)
I rrr-t in the symbol r-1 rith coefficients in the ring
i=I
A. The power series w(z-l-) is said to be rational if it can be written
as a ratio of the form
cn-1_z n-1 +c n-z^z n-2 f ... + c1z +
w(z ') n
n-l
z+e-z+...+e-z+e^
-l
cO
(2.4)
N-IIU
where the c.,e. € A.
l_
We
J_
then have the following resuLts
on
realization.
The proofs of
these results are omitted, as lhey are easy generalJ-zations of the field
case.
PROPOSITfON
2.4
A scalar sequence is realizable if and only if
its associated power series r(r-1)
PROPOSITION
2.5
series given by (2.4).
common
is rational.
Let f be a scalar sequence with associated power
If the polynomials comprisir,g r(r-1)
contain
factors of degree > 1, then (r,g,h) is a mi_nimal realization
C
1
00
l
t0
r-
,a
0
0
L
e-e
0
.-e
2
-Ll -
,h=
no
of f
F. cr ...""_il
The
extended to matrix
result in Proposition 2'4 can be
t = (rfr2,...)
sequenc
u":;...1" t"':lt matrix-:*:t
as rorlows. Ler w(r-I)
' By definition'
.,'€" wt'-rl =rl1
series in ,-1 t"=o"iated with f i
"" scalar power series
whose elements are
can be written as a matrix
"("-t)
if each element of w(z-l) is
ir, ,-r. The matrix w(z-\; is rational
rational
-
We
then have the following result [24] '
PROPOSITION
2'6
The
and onlY if
matrix sequence f is realizable if
:
its associated power series is rational'
realican be aPProached bY first
The realization of matrix sequences
the resulting realizations are seldom
zing the elements of w(z-I) ' but
teaLizaspecial class of rings, minimal
minimal. As will be seen' for a
Hankel
(J1'J2" ") can be constructed from the
tions of a matri-x sequence f =
matrix
B
(f) given
bY
[",.
tz
I
It2 J^
"3
J3
t4
I
I
B(f)
=
l"^
J 4)
J-
I
I
I
l
1
L
f over a field K is
It is well known [6] that a matrix sequence
B(f) is finite' The rank of B(f)
realizable if and onlY if the rank of
minors of B(f) of order greater
all
that
q
such
integer
smallest
is the
B(f) is finite' f has a minimal
than q are zero' If the rank of
-
IB-
of dimension equal to the rank of B(f).
realization
Realizability
results for matrix sequences over fields can be applied
to matrix sequences over an integral domain A: Given such an f, we can view
f as a sequence over the quotient field Q(A). Then since Q(A) is a fi-eld,
f has a realization
finite
over Q(A) if and only if the Hanke1 matrix B(f)
rank as a matrix
over
Q
(A)
.
has
But since we are seeking realizations
over Q(A) implies realiz-
over A, we would like to know when realizability
over A. As proved in t9l, this is the case for the class of rings
ability
referred to as principal
t25,26,271)
A
ideal domains (for more general results
see
.
principal ideal domain (p.i.d.) is an integral
domai-n
A with the
property that, for any subset S of A such that a + beS whenever a,beS
and abeS whenever aeA, beS, there is an element aeS such that S = {ab:beA}
(i.e.,
every ideal S of A i-s generated by a single element
aeS )
.
The
ring of integers and the operator rings a[d] and K[o] are examples of
p. i.d. 's.
since realizability
is a p.i.d.,
over Q(A) implies realizability
over A when
A
we see that i-f a matrj-x sequence oveg z has a realizatj-on
over the fietd of rati-onal numbers, there is a realizaLion over Z; and if
a matrix sequence over Rlcll has a realization
functions in d, there is a realization
over the field of rational
over R[d].
These are very interes-
ti-ng, results.
It is proved in i9l that a realizable matrix seguence f over a p.i.d.
has a minimal realization
of dimenslon equal to the rank of the Hankel
matrix B(f) as a matrix over Q(A). In the p.i.d.
case, mj-ni-mal realizatj-ons
can be computed from B(f) using Rouchaleau's algorithm t9l.
-19-
The al-gori-thm
yieldsami-nimalrealizationoverQ(A)usingsilverman'sformulas,fromwhich
aminimalrealizationoverAisgeneratedviaasimilaritytransformation.
Thestepsofacondensedversionofthisalgorithmaregivenbelow.
of pxm matrices
Let f = (J r,J r-. . ) be a matrix sequence consisting
finite rank equal to n'
defined over a p-i.d' A' Suppose that B(f) has
Then a minimal
realization of f over A can be constructed by carrying
out the following steps'
(1) Let C be a nxn submatrix of
(2) Let D be the
nxnm submatrix
B
(f) having rank n as a matrix over
of
B
(A) '
Q
(f) containing the same rows as c
first n block columns of B (f) '
be the
(3) From D construct a nxn matrix V as follows' Let bl
and the
greatestcommondivisoroftheelementsinthefi-rstrowofD.Thereis
anA-linearcombinationvrofthecolumnsofDhavingbrasfirstelement;
r'eA such that the first element
anrl for each column d. of D' there is a
d2- '2uL ' ' un* - r*nvrJ '
of d.a - rirt i" zero. Define Dl = [d1 - tltl
with the second row' which yields a
Apply the sarne procedure to D1 working
column
vectorvrandarilatrixD2'Continueuntil[t1't2"'t,,]=Visconstructed'
of B(f)
(4) Let N be the nxrn submatrix of the first block column
containing the
same rows
as c'
B(f)
(5) Let E be the pxn submatrix of the first block row of
containing the
(6) Let
same columns as C'
M
right of C'
be the nxn submatrix of B(f) sitting to the
Then (F,G,H) is a minlmal realization of f where
F
= tv-l)l,t(c-t)v, c = (v-1)n,
-20-
H =B(c-1)v
(2.5)
2.3
Example
Consider the continuous-time system with time delays given by the
transfer function matrix
T(s,e-s1
We
=
)
s
want to
+
(e-c -I) s-e -c
compute
t . "-'"1
e-s s+
[-'
-1
["
a mj-nimal realization of T(",.-=) given by a triple
(F(d), c(d), H(d)) over the operator ring n[d] with
T(s,e-s) = H(e s) (sr -
F
(e-s)
)-lc(.-=)
Si-nce Lhe least common denominator (as a polynomial
in s) of T(sre-s)
has degree equa
to two, it follows that T(=,.-") has a realization over Rldl
of
we
dimensi-on 4.
shall
compute a minimal
realization usi-ng the
algorithm. Fir t, expanding T(sre-s) into a power series i., =-I,
. -s.
T(s,e
)
I
I'
=t
above
we get
-l
1 -3
l- Il"-1* l-I -"-= r+e-JJ
"-r.
|
-s l=
- -1 I "-'*lf-e-2s .'*r-[
o J*
L"-=
.-=
-2I-
Then
t
T
lr
l_,
l---I-
-o--
tl-"
le
I
B(f)=
t---
-e
e
-r1
-S
.S
I
I
I
I
t
I
I
I
I
-s
0
l++e
-s
1+e
-1
-2s
I
I
1
t
I
+l- t'
e-s_
-2s
I
I
I
L
of B(f) must be less
Since there is a realization of dimension 4, the rank
any more blocks
than or equal Lo 4, so it is not necessary to consider
in B(f) than those given above'
Checking the minors
of the 4x4 submatrix of
2. Thus there is a realiB(f) given above, we find that the rank of B(f) is
zation of dimension 2. we then choose
['L-' "1ol
so that
il1
-s
e-e
ID= |l_
|;I
0e
-22-
-s
-s
1+e
-1
1
I
Applying the procedure g:iven in Step (3) to D, we get
[-r
.._tt
v -t
l-'
lfehavethatN=E=Cand
M
o
I
I
^-sI
,*.-1
[-.-"
=
-t
L.-=
-]
Then from (2.5) , we have the following mlnim a1 reali zation of T(s,e "):
F(d)
In
=
F.
L. ,
component
dx, (t)
dr
dx, (t)
*
t*u*u'l
=
c (d)
-.1'
Fq
=I
H
(d)
J
form, the realization is given
--
FE
tt
['
ei
by
-xI(t-1) + xr(t) + xr(t-1) + x2(L-2') + u1(t) + u, (t-1)
= xr(t) + ur(t)
y1(t) = x, (t)
vr(t) = -xr(t) +xr(t-1)
-23-
3. REACHABILITY, OBSERVABILITY,
AND DUALITY
Weshallnowstudytheconceptsofreachabilityandobservability
fordiscrete-ti-meSystemsoveraringofscalarsandcon|inuous-time
Systemsovertheoperatorringn[d].Theresultsobtainedhereleadto
systems over
a definition of reachability and observability for abstract
rings.Inthelastpartof,section3.3,weconsideraconceptofduality
for abstract
systems.
3.1 Discrete-time systems over a ring of scalars'
equations
Consider the discrete-time system given by the state
x(r+1)
=Fx111 +Cu(t)
(3.1)
y(t) = ttx(t)
the ring A' Let An denote
where FrGrH df€ flxor fiXIIIr pxn matrices over
the set of all
n-element column vectors over A.
DEFINITION
3.1
ThE
there is an integer N >
0
system (3.1) is reachable if for any xcAh'
and inputs u(0) , u(1) , .. " ,u(N-1) thaL drive
the system from the zero state at time t =
O
to the state x at time t
n
Thesystemisreachableinnstepsi-fforanyx€A..,theintegerNcan
=N.
be taken
to be n.
the initial
time
of generality' since the
system
In Definition 3.1,
does not imply any loss
we have taken
to be zeYa- This
is time i-nvariant-
Let v1'v2 ,..',Yqbe fixed elements belonEing to An . We say
be written
that xeAn is an A-linear combination of vr'vr" " 'vn if x can
in the
i
form
q
x= I? ..n.a
-r
I-I
for some e.a €A
-24-
!;1.
ffi
Hl
In terms of this conceptr we have the following criterion for reachability.
PROPOSITTON
3.2 The following conditions are equivalent.
(1) The system (3.1) is reachable.
(2) The system (3.1) is reachable j-n n steps.
(3) Every element of An can be written as an A-linear combi-nation
of the columns of G,FG,...,Ft-lG.
Proof. f'rom (2.1), the state x(n) at time t = n starting
x
from
(0) = 0 is given by
-_1
x(n) = i u"-i-ta,rtil
(3.2)
i=0
The equivalence
of condi-tions (2) and (3) follows frorn (3.2)-
The
equivalence of conditions (1) and (2) follows from the Cayley-Hamilton
theorem [8, page 400].
coRoLLARY
3.3 Let
m
= 1 (the single-input case). Then (3.1) is
reachable if and only if the nxn matrix [G,FG,...,Ft-lG] is invertible
over A, which is the case if and only if the determinant of [G'FG,...,Ft-lG]
has an inverse in e.
EXAMPLE
3.4
Suppose
that. (3"1) is a singte-input system over the ring
of integers Z. Since the only invertible elements of Z ate *1 and -1,
by Corollary 3.3 we have that the system is reachable if and only if the
determinant of [G,FG,...,Ft-lG] is equal to *] or -1" Thus, given a system
selected "at random", it is very unlikely that every element in Zn can
be
reached using integer-valued controls.
Again consider the system (3.1) defined over the ri-ng A" Let U de-
note the
nxmn
matrix [G,FG..,.rrt-lc]" and let
ueAmn
denote the control
vector u = [u(n-1) u(n-2) .." u(1) u(0)]'. It foltoios from (3.2) that u drives
-25-
the system to the state xcAn at time t = n if and onlv if u satisfies the
equation x = Uu. If the system is reachable, .in the single-input case there
__-I
-1
a unique solution given bY u = U X, wnere u l-s the inverse of U' In the
multi-input case (m > 1), the computation of a control u (if one exists) is IN
general a difficult
Problem-
For a cl-ass of fields, we have the following
result.
THEOREM
-1
3.5 Let A
=
for any a.€K. Then the system (3.1) is reachable if and only if the nxn
matri-x U(U') is invertible
u
K, where K is a field with the property that l-rur'/
over K, in which case a solution ,"tf,t of x = Uu is
= (u') Iu(u')l-l 'x.
of
The above result is well known for the case in which K = R = field
real numbers" The usual proof for the K = R case extends to the class of
fiel-ds Kwith the property thatlr.rt
that
when K
I -I for any a.<K. It is also well
= Rr the control u = (u') Iu(u')l-1x minimizes lirrll, *L,"r" ll
known
ll
denotes the Euclidean norm, and where u ranges over all solutions of x = Uu.
In the ring case. j.nvertibility of U(U') over A implies that the
system
is reachable, but the converse i-s not true:
EXAMPLE
3.6 Consider the discrete-time system ovex Z given by x(t + 1)
x(t) + u,(t)
+ u.(t), y(t) =Hx(t).
L2
Here
G= [1 1], andU = G. Since the
columns of u generale z, the system is reachable. But u(u') = 2, which does
not have an inverse in Z.
Novi assume
that A is an integral domain with quotient field
Q
(A)
having the property- that I*.*2 I -r for any a.ee(A). suppose that the system
"l- l(3.r), viewed as a system over Q(A), is reachable. Then by Theorem 3.5,
any x€An can be reached by applying the eontrol u = (U')[U(U')]-Ix,
in general is defined over
Q
(A)
. This is an acceptable solution if the
control over Q(a) can be generated.
-26-
I
Fi
$
which
=
3.7 Again let (3.1) be a system ovey Z. Viewing (3.1)
EXAMPLE
as
a system over QG) , the f ield of rational nurnbers, we have that it is
reachable if and only j-f the determinant of U(U') is nonzero. In this case,
the control
u
= (U')[U(u')] -t 'x would be a vector of rational
numbers
in
general.
For systems over Z, a very interesting problem is the computati-on of
integer-valued. controls u that minimize llull, wfrere u ranges over all integervalued solutions of x =Uu.
the determinant of U(Ur) is equal to +1 or
-1, an integer-valued solution minimizing llull is u = (U') [U (u, ) ] -1x. Unfor-
tunately, invertibility
When
of U(U') is too severe of a condition to be of
much value.
For systems over a p.i.d. (such as Z), controls belonging to A*t .-r,
be computed by first putting U into di_agonal form (the Smith form) using
row and column operations (see [28, page 109] ) . The details of this
proce-
dure will not be considered here.
We now
consider the concept of observability.
DEFINITION
3.8 The system (3.1) is observable if for any nonzero i-nitial
state x(O)<An, there is an integer N > 0 such that the output response y(t)
resulting from x(0) is nonzero for at least one value of t <{0,1,...,N-1}.
system is observable in n steps if
for any nonzero x(O)eAn, the integer N
be taken to be n.
PROPOSITfON
3,9 The following conditions are equivalent.
(1) The system (3.1) is observable.
(2) The system (3.1) is observable in n steps.
(3) There is no nonzero x€An such that
x' [H" (F') (H,),...,
(F')t-l(H';
1 = g.
-21
-
The
can
Proof.
initial
state
From (2.1), the output response y (t)
ILI
[." ,J
S
t < n-l resulting
from
in the form
x (0) ean can be expressed
t::] =
for 0
(3.3)
x (0)
lo,""-'J
Tire equivalence of conditions (2) and (3) follows directly
from (3.3).
The equivalence of conditions (1) and (2) follows from the Cayley-Hamilton
theorem.
Let V denote the npxn matrix
FI
v = tt
IHF
l:l
l'6-,1
IJ(F
I
U
and 1et y€Atp denote the response vector ty(O) y(1) ... y(n-l)l
the response vector y resulting from initial
given by y = vx.
icnowledge
We
By (3.3),
state xeAn at time t = 0 is
would like to be able to compute the initial
state x
from
of y. In the case of systems over fields, thi-s problem is dual to
the problem of computing controls in the generation of states. ln particular,
we have
the dual of Theorem 3.5.
3.10 Let A = K, where K is a field with lr.r' I -I for any a.€K.
fhen the system (3.1) i-s observable if and only if the nxn matrix (V')V is
THEOREM
invertible over K, in which case, given y = Vx for
-24-
some
x€Kfl, x = (V'V)-1(V')y.
Proof.
Recall that a system over a field is observable if and only if
its dua1, specified in terms of the matrices F',H',G',
is reachable [5].
Then apply Theorem 3.5.
Although the d.uality between reachability
and observability
does not
extend to systems over rings (see Section 3.3), Theorem 3.10 can be extended
to systems over an integral domain as follows.
COROLLARY
3.11 Suppose that A is an integral domain with I . u.' I -t
"L 1
for any a.eQ(A). Then the system (3.1) over A is observable if and only if
(V')V is invertible over Q(A), in which case, given y =Vx for
some xeAn,
x = (v'v)-l '(v')y.
Proof. It is easily verified that the system (3.1) is observable if
and
only if it is observabl-e as a system over the field Q(A). Then apply Theorem 3.10.
3.2 Contj-nuous-time systems over a ring of delay operators
Consider the continuous-time system given by
q*P = (p(d)x) (r) + (c(d)u) (r)
(
y
(t) =
(tt (d)
x) (t)
where F(d), G(d), H(d) are nXnr nXrrlr pxn matrices over the operator ri-ng
RIdl
.
Given a fixed positive nunber tl , let i,2( to,trJ;Rn) d.enote the Hilbert
space of square-integrable functions on
lltll "t a function belonging to
llt
[0,t1] with values in Rn- The norm
2n
L- ( [o,trJ ;R-')
ll' =
ff
'tt'
is defined
,', ll'u.
-29-
by
3.4)
where the norm
We
in the integrand is the Euclidean norm.
can now oefine the notion of Euclidean reachability.
3.12 rhe system (3.4) is Rn-reachable in ti-me a1 t
DEFINITION
if for any x€Rn, there is an input rrul,2([O,tr];nm) that drives the
O
system
to the state x at time t = t1 with ini-tia1 state function x(t) = 0 for t < 0'
We
shall give a necessary and suffici-ent condition for Rn-reachability
terms of the following constructions-
Let I'4(t) denote the inverse Laplace transforrn of th.e nxn na+-ri>i Ir'("-t"))-le(.-t").
rt can be shown (see [14]) that the state x(t 1) at time t1
resulting from the input urt'2 ([c,tl];Rm) with x(t) = 0 for t < o i s given
x
(tr)
tt*,.,
=
f
r0
Define the map ).(tr):L2([0,t1];Rm)-' RD:u +
-
map
(3.s)
s) u (s) ds
fL
- s)u(s)ds.
Jott,a,
We then have the following result which follows directly fron (3.5).
PROPOSITION 3.I3 The system (3.4) is Rn-reachable in time t, if
only if the
by
and
tr(tr) is onto.
we can get an explicit condition
*
adjoint I (t1) ot tr (tt) defined bY
for reachability in terms of the
f tarl ,Rn*L2([0,t1];f)'x-m'(t, - s)X, 0 < ". tl
Here we are using
on any finite
the result that the elements of M(t) are square-integrable
interval 0 S t =
t1
.
- 30-
composition
l
(t1)
l *"(t1) is
a map from Rn into Rn given by
f (t1) I (ta)
:
x+B (ra) x
where
B
The
(r1)
=
I.t'.' - s)M'(L, - s)ds
matrix B(t1) is the controllability grami-an for time-delay systems.
THEOREM
3.14 The system (3.4) is Rn-reachable in time t1 if and only
if B(tl) is invertible, in which case the control r = tr*(tf)B-1(tr)x sets
up the state xeRn at time t = tt. Further, thi-s control minimizes llull,
where u ranges over all solutions of x = tr(tr)u.
Proof. Follows from standard results in the theory of linear transformations and their adjoints (refer to Luenberger's book [29]).
Although B(t) is constructed from the matrices F(d) and G(d), we would
like to have a cri-terion for Rn-reachability specified directly in terms
of F(d), c(d). This can be accomprished by first noting that the system
(3.4) is Rn-reachable in time tl if and onry ir l* 1tr; is one-to-one,
which is the case if and only if there is no nonzero xcRn such that x'M(t) =
for 0 < t < t .
I
THEOREM
r
c (d)
We
then have the following result.
3.15 Glven the system (3.4),
- .^r
I ".dt,
a=u
suppose
that Ftal = fn,di
i:d
and
where the F. and G. are matrices over R. Then the following
l_
l_
are equivalent.
- 31-
0
n(r) The system is R"-reachable in time tI for
n_
(2) The system is R"-reachable in time t1 for
(3)
some
any
t I > 0.
t-I > q(n-])a + ra.
n
There is no nonzero xeR' such that
xt
Proof.
[c(d),F(d)c(d),...,T(a)n-lc(d) ] = 0.
we shall show that (1) implies (3):
clearly, (2) +(I).
there is a nonzero xeRn such that x'[G(d) ,F(d)c(d),...,F(d)n-le(a) I = c'
bY
Then by the cayley-Hamilton theorem, x'F(d)i-Ic(a) = o for all i > 1. Now
Suppose that
definitlon of M(t), it can be
M
expanded
(r) = |
tr tal
i=1
i-t.
into the series
(u)
)
ti-l, t '
o
Thus, x,M(t) = O for all t > 0, so the system is not Rn-reachable.
(3)+(2): Suppose that the system is not Rn-reachable for tl t Q(n-L)a + ra'
+ ra'
Then there exists a nonzero xeRn such that x'M(t) = O for O < t < q(n-1)a
Now
let A(t) denote the inverse Laplace transform of (sI - r("-t"))-1'
T
Then M(t) = (AG(d)) (t) = [ att - ia)G..
i=0
Evaluating M(t) at t = ia
and
noting that A(o) = r = nxn identity matrix, we have that x'Gi = 0 for i
o,It2,
.
.. tT.
Taking the first
Hence x'G (d) = o.
=
derivative of x'M(t)
- ia ja) c
O, we have that x' (F(d)AG(d) ) (t) = x' Ei' ^ I: r'.A(t
^r=u
t=u
lr=
at
t= ia* ja, we get
Evaluatingthis
forO < t< q(n-l)a+ ra.
for t
=0
0r1,...,q and j = O r.,.. -,r, whi-ch implies that x'F(d)G(d) = 0'
Continulng in this manner, we can show that x'r(d)i-]e (a) = 0 for i = I,2'""n'
::tF.G.
r-l =
O
Now
for i
let
U
=
(d) denote
the
nxmn
and Let R(d) denote the quotient
sufficient
matrix [c(d),F(d)G(d),--.'F16;n-lc(d)
field of Rldl -
condition for Rn-reachability'
--12-
we then have
J,
the following
COROLLARY
3.16
SuPPose
that the rank of
U
(d) , viewed as a matrix
over R(d) ' is egual to n- Then the system (3.4) is Rn-reachable.
Proof. The rank of U(d) is equal to n if and only if there is
no
;lonzero xeR(d)n such that x'U(d) = O. Then apply Theorem 3.15.
A generalized version of condition (3)
i-n Theorem
3.15 was given
bY
Sontag [24, page 2Bl - Results simj-Iar to those given in Theorem 3.15
were clerived by Williams and Zakian [16] '
For a geometric version of these
results, see Byrnes i301.
Unfortunately, the notj-ons of Rn-reachabi-lity and Rn-controllability
(driving
x
(t) to zero at
some
time t, > o) are of limited use in the
design of control systems with time delays, since the value of
x
(t) at time
is not the complete state of the system. For example, the existence of
an open-loop or closed-loop control which drives x(t) to zero at some time
"lt
0 does not imply that x(t) will remain zero for all tt
al. This of
course is due to the storage of signals within the delay lines.
In the literature on systems with time delays, conditions based
on
ihe concepts of exact or approximate function space reachability are usually
considered [31]. These conditions are much stronger than Rn-reachability
since they deal with the problem of reaching (from zero) or controlling
(to zero) Rn-valued function
segirnents,
rather than points in
Rn.
It is interesting to note that the rank condition in Corollary
is stronger than Rn-reachability:
EXAMPLE
F (d)
3.17: Consider the system(3.4) with
FE
IJ
and
G
(d)
=
I
so that
tt,
bl
l-r
-33-
U
(d)
[-r
_tl
-lt
te
r-T
ql
3.16
)
2
!L^
^.-^!^,
There is no nonzero x€R such that x'u(d) = o, so the system is R--reachable'
But the rank of U(d) is equal to one. Thus Rn-reachabitity does not neces-
sarily imply that the rank of U(d) is equal to n'
A very interesting open question is whether or not the rank condition
in corollary 3.16 is equj-valent to one of the various notions of function
Spacereachabilityspecifi-edintermsofsometopologicalstructure.
There i-s a much stronger condition than the rank condition given in
Corollary 3.16. Namelyf we can require that any xeR[d]t.u' be written
as an nldl-Iinear combination of the columns of U(d). In the single-input
case, we can do this if and only if the determinant of u(d) is equal to
in
nonzero element of R (which is seldom the case) ' As will be seen
the next chapter, this condition is necessary and sufficient
asslgnabllity,,using
a
for "pole
state feedback of the form u = -B(d)x, where the feedback
nratrix B(d) is a lxn matri-x over e[d] '
The last toPic of this section is Rn-observabilitY.
DEFINITION
3.18
if for any nonzero initial
The sYstem (3'4)
is Rn-observable in time tl t
0
state x(O)eRn withx(t)=0foral1t<0,
of
the output response y(t) resulting from x(0) is nonzero for some range
values of t belonging to [0,t]1.
The next result states that Rn-observabilitY
is dual to
Rn-
reachabilitY.
PROPOSITION 3.
19
ThE
system (3.4) is Rn-observa-ble in time t1 if
only if the dual system' specified by the matrices F(d)', H(d)',
n_
isR '-reachable in time trProof. Follows from the theory of adjoints [29].
and
-34-
G(d)
3.2O Given the system (3.4), suppose that F(d)
COROLLARY
o
=
s
I t ]. da and H(d) = | H.ar. Then the following are equivalent.
l
:
I_U
-^
r=(J
n
is R---observable in time t I for sorne t, > 0.
n
The system is R---observable in time t, for any t, > g(n-l)a + sa.
(1) The system
(21
ll
(3) There
is no nonzero xeRn such that
V
Duallzing Corollary 3.16, we have t'hat the system (3.4) is
observable
if
the rank
of
Rn-
lH(d)',F(d)'H(d) ',...,(F(d)')n-lu(d)'1,
viewed as a matrix over the quotient field R(d), is equal to n.
The relation-
ship (if there is one) between this rank condition and the various notions
of function space observability is not known at present.
Suppose
response
that (3.4) is Rn-observable in time tr.
y(t) on lO,trJ resultj-ng from initial
Theorem 3.1-4 we can derj-ve an expression
The straight-forward
state
for x(0) in
Given
x(O)eRn
terms
the output
by dualizing
f y(t) on [0,t'].
details are omitted.
3.3 Abstract systems.
The results given in Sections 3.I and 3.2 suggest the following notions
of reachability
I
I
and observability
for abstract systems. Here we afso define
canonical systems and minimal systems.
DEFINITIOI{ 3.2}
Let (F,G,H) be an n-dimensional abstract system
over the commutative ring A. Then (F,G,H) is reachable if any xeAn can
be written as an A-linear combination of the columns of GrFGr...,Ft-lG.
The system is observable if there is no nonzero xcAn such that x'[H'rF'H',
h-
1
...(r")"'H'l
The system
= O. The system is canonical if i-t is reachable and observable.
is minimal if its input/output
Itr
-JJ-
sequence
f = (HG,HFG,...'H(r'i-l)G,..-)
r
cannot be realized by a system over A with dimension strictly
When
less than n.
A is a field, it i_s known [6] that a system is canonical if
only if it is minimal.
when
A is not a field, it is still
true that
and
a
canonical system is minj-mal, but the converse is not necessarily true:
EXAMPLE
3-22 Consider the one-dimensional system (1,d,1) over R[d].
is obviously rninimal. But since Ridl I{ar(a):n(d)eRldl}, it is not
reachable, so it j_s not canonical.
The system
i
We
define the dual of (l.,G,H) to be the system(Fr,H',cr). If (r',H',G')
is reachable, it can be
shown
that (F,c,H)
j_s
observable. But it is not
necessaril-y true that observability of (F,G,H) implies reachability of
(F, ,Ht ,Gt )
:
EXAMPLE
3.23 Consj-der the system (F,G,H) over Z with F = I and H = 2.
There is no nonzero xeZ such that Hx = 0, so the system i_s observable.
But not every x€Z carr be written in the form x = (H')a:2a
for some aeZ,
so
the dual is not reachable.
Thus reachability
of the dual is a stronger condition than observability
of the given system. rn the next chapter, we shall see that the stronger
condition is useful in the construction of state observers.
A reachable system whose dual is also reachable is said to be a split
system [24].
For split
systems, it is possible to approach the design of
regulators by feeding back an estimate of the state obtained. from a state
observer. An interesting question is whether or not a given lnput/output
sequence can be realized by a split
system. For results on this, see Sontag [24]
and Byrnes [30].
-36-
4.
CONTROLLERS AND OBSERVERS
4.L Introduction.
In the first
part of this chapter, we consider the construction of
feed.back controllers
is illustrated
for abstract systems over rings.
The general theory
by examples involving the three classes of systems defined
in Sections I.2 - L.4.
In the last section of the chapter, we consider the
construction of observers by dualizing the results on feedback controllers.
4.2 Assignability.
Let O be a ring extension of the ring A. Given a fixed element
0belonging toQ, let A[0] denote the subring of fl consisting of all finite
q
of the form .'^L lwhere a.eA and 00 = 1. Given a symbol z, LeLAlzl
l1=u ".Ot,
denote the ring of polynomials in z with coefficients in A. Finally, 1et p
sums
denote the
map
p:AIz]+A[0]
:
qq
rt
r
-1
-+ F) a.z
) a.0
ll-''^
].=u
a=U
,'^
The element 0 is said to be transcendental over A if the map p is
one-to-one. That is, there does not exist a nonzero polynomial tr(z)eAlzl
such that p(n(z)) = t(0) = 0.
If 0 is transcendental over A. the rings Alzl
and A[0] are isomorphic (i.e..
p is onto and one-to-oner and p(TIT2+ n3)
p
(nr) I (rir) + o (nr) for any n
L,n 2,
Tr3€A
=
Iz] ) .
tf 0 is not transcendental over A, it is said to be algebrai-c over
A.
If 0 is algebraic over A, an element of A[0] does not have a unique expression
as a polynomial in 0 with coefficients in A.
Nevertheless, we can sti1l
say that bea is a zero of n(0)eA[0] if there exists a B(0)eA[0] such that n(0)
= (0 -
b)B(0).
Let (FrGrH) be an abstract system over A. As before, we assume that
the system
F iS nxn, G is nxm, and H is pxn. Given a mxn matrix B over A,
(F-cB,c,H)wilfbereferredtoasaclosed-Ioopsystemformedfrom(F'G'H)'
The matrix B is called the feedback matrix (or controller) '
Now
given
+
where I
O€0)A, let det(or - F + GB) denote the determinant of 0I - F GB'
isan
is the nxn identity matrix. It can be shown that det (0I - F+GB)
"it t'oi, a'EA' rn terms of these construcelement of A[0] of the form 0t *
i=oaa
tlons, we have the following concepts'
DEFINITTON
4.1 The triple
(l',G,0) is coefficient
assignable if
b0,b1,... ,bn-l belonging to A' there is a B over A such that
n n-r
I r.r_ gt. The triPre (F,c,0) is zero assignable
det (0I -F+GB)=
r=u
F + s'
if for an! crr c2,... ,cra belonging to A, there is a B over A such that det(Ol -
for
any
- c-).
- c^)...(0
= (0 - c-)(0
-t'
n
2.
Asindicatedbelow,forthethreeclassesofsystemsdefinedin
sections L.2 - L.4, zero (or coefficient) assignability implies that
by
employingstatefeed.back,wecanspecifythe''aslrmptotic''behaviorofthe
state response resulting from arbitrary initial states wi-th zero input'
(a)Consideradiscrete-timesystemoveraringofscalarsAgiven
by the dYnamical equations
x(t + t)
y (t)
We can
Fx(t) + eu(t)
Hx
(4.
feed back the state x(t) bY setting
u(r) =-Bx(t) +r(t)
(4.2)
is the feedback matrix defined over a and r (t) is an external inPut
or disturbance. Combining (4.1) and (4.2), we have that the closed-loop
where B
-38-
F
I
t
F-.1
8.
li
lr
i
1
r)
(t)
is given
system
by
x(t+1) = (F-GB)x(r) +cr(r)
y(t) = Hx(t)
(
4. 3a)
(4. 3b)
Let o-1 denote the left-shift
operator defj-ned by (o-lt) (t) = f (t + 1),
where f is a function on Z with'values in A. Then viewj-ng A as a subring
--1_J, we can write (4.3a) in
ot- Ato
the form
(o-1r-F+cB)x=cr
(4.4)
Fron a well-known result in matrix theory [g, page 334), we have that
., -1_
-r
-1
ldet(o--I
- F + cB)llo-'l't - F + GBI-'=
Adj(o-tl
- F + cB)
(4. s)
where Adj (o-1-t
- F + cB) is the transpose of the matrix of cofactors of
s-l tI - F + GB. It follows from (4.4) and (4.5) that if the triple (F,G,o-I)
is zero or coefficient assignable. by selecting the feedback matrix B,
we can specify the behavior
of the free response x(t) (i.e., r(t) = 0 for
t > 0) as t-'@- rn particular, by choosing B so that det(o-lt - F + GB) o-t. r. have that the free response x(t) is zero for t > n, starting from
any initial
state x(0)ean. This is often referred to as,,dead-beat,,control.
(b) consider the di-screte-time system over the operator ring K[o]
gi-ven by
x(t + 1) =
y(t) =
(r'(o)x)
(r) + (c(o)u) (r)
(H(o)x) (t)
-39-
(4.6)
Setting u(t) = -(B(o)x)(t) + r(t), we have that the closed-loop system is
given by
x(t + 1) = (r(o) - c(o)B(o)x) (t) + (G(o)r) (t)
(4.7b1
v(t) = (H(o)x) (t)
whereB(o)isamatrixoverKto].Inthiscase,thefeedbacksignal
-(B(o)x) (t) consists of delayed versions of x(t) '
Let o-1 denote the inverse of o, so that o-l i" the left-shift
operator.
Now we can
view K[o] as a subring of the ring f[o, o-1] consisting
ii l,
i-i
of all finite sums I^ .f'ar.o'o-J wi_th the a..<K. It is important to
rhar o-1 i_s nor ,r"il:.1;:nra1 over Ktol . To see rhis, consider rhe
polynomiat rG) = oz- Le(iciol)tzl . Wehave that n(o
l
*)
-1
- 1=
= o(o*)
note
0,
so the map p defined above is not one-to-one. It follows that the ring
-1
is not isomorphic to (Ktol) tzl.
K[o,o-']
viewing (4.7a) as an operator equation over K[o'o-t] ' t" have that
(o-rr - F(o) + e(o)B(o))x = G(o)r
(
4.8)
As in the ease of systems over A' it follows from (4.8) that if the triple
_1
(F(o), c(o), o-f) is zero or coefficient assignable' we can specify the
behavior of the free response x(t) as t + @. In fact, if B(O) is chosen
that the determinant of o-1r - r(o) + G(o)B(o) is equal to o-n' the free
response
x(t) will be zero for t = ar-, where t, is
-40-
some
positive integer'
so
(c) Consider the closed-1oop continuous-time system over R[d]
given by
(t)
dr
dx
(F
(d) -
G
(d) B (d)
x) (t) + (c (d) r) (t)
(4.9a)
y(t) = (tt(d)x) (t)
(4. eb)
As in the previous example, the feedback signal -(B(d)x)(t) consists of
delayed versions of x(t).
Letting D denote the derivative operator, we can view R[d] as
a
subring of R[d,D] which consists of delay differential operators of the
ii
form ))a..d-D'
acting on some (unspecified) space of functions (see[14]
:; l_"1
r_l
for details). As
shown
in [12], D is transcendental over R[d], so R[d,D] is
isomorphic to the ring (R[d] ) lzJ of polynomials in z with coefficients in
Rtdl
.
Viewing (4.9a) as an operator equation over R[d,D], we have that
(DI - F(d) + c(d)B(d))x = G(d)r
In this case, if lhe triple
(F(d),c(d),D) is zero or coefficient
(4.10)
assignable,
by choosing B(d) we can get the free response x(t) to converge to zero at
an exponential rate u-tt fot any a > O (see [14] ) .
4.3 Single-input case.
Let (F'G,H) be an abstract system over A, where now G is an n-element
column vector over A (i.e.,
m
= 1, which is the single-input case). Given 0€fl,
-4r-
where Q
is
some
ring extension of A, in this section we shal1 present
necessary and sufficient conditions for the triple
(F,Gr0) to be zero or
coefficient assignable. Our first approach to this problem is based on the
concept of cyclicity which we now define.
DEFINfTION
to
4.2 A nxn matrix F over a commutative ring A is said
cyclic with generator gcAn if every element of An can be expressed
be
asa finite
A-linear co.mbination of gfFgr... rFigr...
It follows from the Cayley-Hamilton theorem that a nxn F is cyclic
wj-th generator g if and, only if the el-ements g,Fg,...,Ft-1g
generate An;
i.e., every element of An can be written as an A-linear combination of
n-l-9. Hence F is
_
t",F7,...,E
cyclic with generator 9 if and only if the
del-erminant of the matrix lg,Fg,...,F"
h-
-gl has an inverse in A.
1
We
also
have the following result.
PROPOSITION
4.3 Let (F,G,H) be a single-input system, so that 6:
Then (F.g,H) is reachable (nefinition
geA
3,21) if and only if F is cyclic with
generator g.
As we now show,
cyclj-city is equivalent Lo the existence of
particular canonical form. As before, let z
be
a
a symbol. Gi-ven a nxn matrix
n-1
t- over Af we have that det (zI - F) = ,n+ | u., - for
some
a=u
F=
01
00
b
00
::
00
10
0
-a-U1
,s
-a_
-a2
(4. 1-
;
o
I
-43
-42-
a.€A.
Define
1
PROPOSITION
4.4 The matrj_x F is cyclic with generator g if and only
if there exists a nxn invertible matrix p over A such that F = p-lr'P
P-1 g, where F and g are given by (4.11).
9r P can
be taken to be the matrix [q,Fg,...,F
and.
If F is cyclic with generator
n-]
n-1-" -sl
'n, -I
., (r)"
ts,F9,..
This result is an easy generalization of the field case, so the proof
is omitted.
cyclicity
Using Proposition 4.4, we can prove the following result relating
and assignability.
THEoREM
4.5 Let (F,9,H) be a single-input system and let 0 be a fixed
element of Q:A, with
0 transcendental over A, Then the following are
equivalent.
(1) F is cyclic with generator g.
(2) The tripte
(F,g,0) is coefficient
(3) The triple
(F,g,0) is zero assi_gnable.
Proof.
Clearly, (2)l(3).
assignable.
It follows from Sontag 124, proposition
4.31
that (3) implies that (F,g'H) is reachable. Hence F is cyclic with generator
9.
So the proof is completed if it is shown that (1))(2) :
beJ-onging to A, fet e denote the row vector [bo--o
n-1
v;hered.et(zl-F)
=zn+
I
Given bO,bI,...,bn_1
b1-u1...brr_l - arr_al,
Thendet(Ol-F+gil
=
n-I
t-=U ^,rt.
-a
u^n + .^fFI b.',0
. where F,g are given by (4.11). rf F is cyclic with generator g,
a=u
it foltows from Proposi-tion 4.4 LhaL det(ol - r * S"l = det(ol - F + gB)
i,vhere B
= B(P-,1-).
Thus the triple
By Theorem 4.5t if
zero or coefficient
(l',g,0) is coefficient
assignable.
0 is transcendental over A, the lriple
(F,g,0) is
assignable if and only if the determinant of [g,Fg,...,Ft-lg]
has an inverse in A. Unfortunately, this condition can be very severe. For
example, in the case of a si-ngle-input continuous-time system over R[d], the
triple
(F(d),g(d),D) i-s zero or coeffici-ent assignable if and only if the
l_.r_
I
I
determinant of
...
Historical archive . public document
