Controllability and Observability (C.I.M.E. Summer Schools, 46)

which agree on

['" t].

In view of the classical terminology "linear differential equations with constant coefficients", we introduce the nonstandard (1.15)

DEFINITION.

A real, continuous-time, finite-dimensional

linear dynamical system E

= (F( ·),

G(·), H(·»

is called constant

iff all three matrix functions are constant. In strict analogy with (1.15), we say: (1.16)

DEFINITION.

A discrete-time, finite-dimensional, linear,

constant dynamical system E over

K

is a triple

(F, G, H)

of

-

22 -

R. E. Kalman

n X n, n X m, p X n

.

matr~ces

K over th e f<eld ~.

mine the equations of motion of i

Hx( t),

y(t) t E~,

in the following manner:

Fx(t) + Gw(t),

X( t + 1) {

x E

x",

w(t) E

If',

and

y(t) E KP•

In the sequel, we shall use the notations F, -, H)

These maps - deter-

(F, G, -)

or

to denote systems possessing certain properties which

are true for any

H or

G.

Finally, we adopt the following convention, which is already implicit in the preceding discussion:

(1.18) E

DEFINITION.

The dimension

n

is equal to the dimension of XE as a

of a dynamical system v~ctor

space.

-

23 -

R. E. Kalman

2.

STANDARDIZATION OF DEFINITIONS AND "CIASSICAIl'RESULTS

In this section, we shall be mainly interested in finitedimensional linear dynamical systems, although the first two definitions will be quite general. Let

E

Section 1.

be an arbitrary dynamical system as defined in We assume the following slightly special property:

There exists a state

(j)(t;

T,

and an input

x*

x*, m*)

for all

x*

For simplicity, we write and

t,

T

and m*

x*

n have additive structure,

ing.)

m*

0

such that E T and as

O.

t>

T.

(When X

will have the usual mean-

The next two definitions refer to dynamical systems

with this extra property. DEFINITION.

An event

there exists a t E T and an on

(T,

x»

(T,

x)

wEn

is controllable iff§

(both

t

and w may depend

such that

(j)( t; T, x, Ul) In words:

0

an event is controllable iff it can be transferrc

to

0

in finite time by an appropriate choice of the input function

w.

Think of the path from

function defined over

(T, x)

to

(t, 0)

as the graph of a

[T, t].

§The technical word iff means if and only if.

-

24

-

R. E. Kalman Consider now a reflection of this graph about

T.

This

suggests a new definition which is a kind of "adjoint" of the definition of controllability: DEFINITION. 1s an

(T,

sET

x»

An event

and an

00

E

n

(T, x) is reachable iff there

(~

sand

00

may depend on

such that x

=
We emphasize: different concepts.

0,

00).

controllability and reachability are entirely A striking example of this fact is encountered

below in Proposition (4.26). We shall now review briefly some well-known criteria for and relations between reachability and controllability in linear systems.

(2.3)

PROPOSITION.

In a real, continuous-time, finite-dimensional,

linear dynamical system (a)

reachable if and only if some W(s,

(b)

E = (F('), G(')' - ),

s E

an event

x E range W(s, T)

(T, x)

for

s < T, where

~,

T) = IT ~F(T, a)G(a)Gr(a)~F(T, a)du s

controllable if an only if x E range some t E

~,

t >

T,

W(T, t) for

where

The original proof of (b) is in KALMAN [1960b]; both cases are treated in detail in KALMAN, FALB, and

JL~IB

[1 969, Chapter 2,

is

-

25 -

R. E. Kalman Section 2].

Note that if G(·)

we cannot have reachability, and if G(·) zero on

(- 00, T)

is identically zero on is identically

(T, + 00) we cannot have controllability.

For a constant system, the integrals above depend only on the difference of the limits; hence, in particular

So we have

(2.4)

PROPOSITION.

In a

rea~continuous-time,

linear, constant dynamical system an event for all

T

finite-dimensional,

(T, x) is reachable

if and only if it is reachable for one

T;

an ev:nt

is reachable if and only if it is controllable. From (2.3) one can obtain in a straightfoF~~rd fashion also the following much stronger result: (2.5)

THEOREM.

In a rea1 continuous-time, n-dimensional,

linear, constant dynamical system L = (F, G, -)

a state

x

is reachable (or, equivalently, controllable) at a~ T E ~ if and only i f x E span (G, FG, ••• ) C ~n; if this condition is satisfied, we can choose with

°> 0

arbitrary.

s

=T

-

0, t

=T

(The span of a sequence of matrices is to

be interpreted as the vector space generated by the columns of these matrices.)

+ 0,

-

26

-

R. E. Kalman A proof o:r (2.5) may be found in KALMAN, HO, and NARENDRA

[1963] and in KALMAN, FALB, and ARBIB [1969, Chapter 2, Section

3]. A trivial but noteworthy consequence is the fact that the definition of reachable states of E is "coordinate-free":

(2.6)

COROLJJL~Y.

states of E ~

Xz,

The set of reachable (or controllable)

in Theorem (2.5) is a subspace of the real vector

the state space of E.

Very o:rten the attention to individual states is unnecessary and therefore many authors prefer to use the terminology completely reachable at x E

X~

.

T"

~s reachabl~ ""~ , or ~

event in E

for

"every event

( 'l", x),

completely reachable " for

is reachable", etc.

is

"l.

fixed,

'l" =

" every

Thus (2.5), together with the

Cayley-Hamilton theorem, implies the BASIC

~MA.

A real, continuous-time, n-dimensional,

linear, constant dynamical system E

= (F, G, -) is comnletely

reachable if an only if rank

(2.8)

(G, FG, ••• , yn-1G)

n.

Condition (2.8) is very well-~~own; it or equivalent forms of it have been discovered, explicitly used, or implicitly assumed by many authors.

A trivially equivalent form of (2.7) is given by

COROLLARY 1.

A constant system E

completely reachable if and only if the

= (F,

s~allest

is

F-invariant

subspace of XL containing (all col~on vectors of) itself.

G, -)

G is

~

_

27-

R. E. Kalman

A useful variant of the last fact is given by

(2.10)

COROLLARY 2.

(W. Hahn)

A constant system E = (F, G, -)

is completely reachable if and only if there is no nonzero eigenvector of F which is orthogonal to (every column vector of)

G.

Finally, let us note that, far from being a technical condition, (2.5) has a direct system-theoretic interpretation, as follows: PROPOSITION.

(2.il)

The state space

~

of a real, continuous-

time, n-dimensional, linear, constant dynamical system E

= (F,

G, -)

may be written as a direct sum

which induces a decomposition of the equations of motion as (obvious notations) dx/dt {

dx,jdt

The subsystem L a state

= (Fil, Gl, -)

x = (~, x E ~ 2) PROOF.

of E;

l

is completel v reachable.

is reachable i f and only if x 2

We define

Xl

tion, every state in Xl

Xl

= O.

to be the set of reachable states

by (2.5) this is an F-invariant subspace of

finite-dimensionality,

Hence

is a direct summand in

XE" ~"

Hence, by By

construc-

is reachable, and (every column vector of)

-

28

-

R. E. Kalman G belongs to F = 0, ll

Xl'

The F-invariance of Xl

implies that

which implies the asserted form of the

e~uations

of

motion.

0

REMARK.

Note that

X 2

is not intrinsically defined

(it depends on an arbitrary choice in completing the direct sum). Hence to say that state if

"(0, x

2)

is an unreachable (or uncontrollable)

x 2 -f 0" is an abuse of language.

More precisely: the

set of all reachable (or controllable) states has the structure of a vector suac~ bltthe set of all unreachable (or uncontrollable) states does not have such structure.

This fact is important to

bear in mind for the algebraic development which follows after this section and also in the definition of observabi1ity and constructibi1ity below. chosen in such a way that

In general, the direct sum cannot be F = 0. 12

While condition (2.8) has been fre~uently used as a technical re~uirement

in the solution of various optimal control problems in

the late 1950 s, it was only in 1959-60 that the relation between (2.8) and system theoretic questions was clarified by KALMAN (1960b-c] via Definition (2.2) and Propositions (2.5) and (2.11). 11 for further details.)

(See Section

In other words, without the preceding

discussion the use of (2.8) may appear to be artificial, but in fact it is not, at least in problems in which control enters, because, by (2.12) control problems stated for respect to the intrinsic subspace

Xl'

~

are nontrivial only with

-

29 -

R.E.Kalman

The hypothesis "constant" is by no means essential for Proposition (2.11), but we must forego further comments here. For later purposes, we state some facts here for discretetime, constant linear systems analogous to those already developed for their continuous-time counterparts.

The proofs are straight-

forward and therefore omitted (or given later, for illustrative purposes). (2.14)

PROPOSITION.

A state

n-dimensional, linear, con stant

x

of a real, discrete-time,

~~cal

system E

= (F,

G, -)

is reachable if and only if x E span (G, FG, ••• , ~-lG). Thus such a system is completely reachable if and only if (2.8) holds. (2.16)

PROPOSITION.

A state

x

of the system E

described

in Proposition (2.14) is controllable if and only if

) x E span ( F-1G, • ", F-nG, where {x:

PROPOSITION.

(2.18)

~x

column vectcr of

G}.

In a real, discrete-time, finite-dimensional,

linear, constant dynamical system E

= (F,

G, -)

a reachable state

is always controllable and the converse is always true whenever det F

f

O.

-

30 -

R. E. Kal ma n

Note also that Propositions (2.11) and its proof continue to be correct, without any modification, when "continuous-time" is replaced by "discrete-time". Now we turn to a discussion of observability. The original definition of observability by KALMAN' [1960b, Definition (5.23)] was concocted in such a way as to take advantage of vector-space duality.

The conceptual problems surround-

ing duality are easy to handle in the linear case but are still by no means fully understood in the nonlinear case (see Section 10).

In order to get at the main facts quickly, we shall consider

here only the linear case and even then we shall use the underlying idea of vector-space duality in a rather ad-hoc fashion. The reader wishing to do so can easily turn our remarks into a strictly dual treatment of facts (2.1)-(2.12) with the aid of the setup introduced in Section 10. DEFI}ilTION.

An event

("

x)

in a real, continuous-

time, finite-dimensionak linear dynamical system E

= (F(o),

-, H(·»

is unobservable iff

DEFI}ilTION. ("

x)

With respect to the same system, an event

is unconstructible* iff

*In the older literature, starting with KAl}t~~ [1960b, Definition (5.23)], it is this concept which is called "observability"o By hindsight, the present choice of words seems to be more natural to the writer.

-

31 -

R. E. Kalman

The motivation for the first

defi~ition

is obvious:

the

"occurrence" of an unobservable event cannot be detected by looking at the output of the system after time subsumes

ill

= 0,

linearity.)

T.

(The definition

but this is no 10s3 of generality because of

The motivation for the second definition is less

obvious but is in fact strongly suggested by statistical filtering theory (see Section ments Definition

10).

(2.20)

complements Definition

In any case, Definition

(2.21)

comple-

in exactly the same way as Definition

(2.1)

(2.2).

From these definitions, it is very easy to dedu ce the following criteria:

(2.21)

PROPOSITION.

In a real, continuous-time, finite-di mensional,

linear dynamical system E (a)

= (F('),

-, H('))

unobservable if and only if x for all

t E

~,

an event

(T, x)

is

E kernel M(T, t)

t > T, where

M(T, t)

(b)

unconstructible if and only if for all

s

E~,

s <

T,

where

x E kernel M( s, T)

-

PROOF.

32

R.E. Kalman

-

Part (a) follows i=ediatel,y from the observation:

x € kernel M(T, t ) ~ H(s) F(s, T)X

=

0

for all

s € [T, t l .

o

(b) follows by an analogous argument.

REMARK.

Part

Let us compare this result with Proposition (2.3),

and let us indulge (onl,y temporaril,y) in abuses of language of the following sort:*

unreacha.ble # for all

t >

x € kernel

W( T,

t)

T

and observable # for some t >

x € range

M( T,

t)

T.

From these relations we can easil,y deduce the so-called "duality rules"; that is, problems involving observability (or constructibility) are converted into problems involving reachaoility (or ~ o nt rollability) in a suitabl,y defined dual system.

See KALMAN, FALB,

and ARBIB [1969, Chapter 2, Proposition (6.12)] and the broader discussion in Section 10. We will say: by slight abuse of language, that a system is completely observable whenever

0

is the onl,y unobservable state.

Thus the Basic Lemma (2 .7) "dualizes" to the PROPOSITION.

A real, continuous-time or discrete-time,

n-dimensional, linear, constant

dynamical system E

= (F,

- , H)

*A11 this would be strictly correct if we agreed to replace "direct sum" in Pr oposition (2.11) and its counterpart (2. 25) by "orthogonal. direct sum"; but thi s would be an arbitrary convention which, whi l e conve nie ~t, h~s no natural system-theoretic justification. Rer ead Rem1i.tk (2.13).

-

33 -

R. E. Kal ma n

is completely observable if and only if (2.24)

rank (rr , F'H', ••• , (F,)n-~,)

n.

By duality, complete constructibility in a continuous-time system is equivalent to observability; in a discrete-time system this is not true in general but it is true when det F

f

O.

It is easy to see also that (2.11) "dualizes" to: PROPOSITION. time or discrete-time system r.

= (F,

The state space

Xr.

of a real,

continuous-

n-dimensional, linear, constant dynamical

-, H) may be written as a direct sum

and the equations of r. are decomposed correspondingly as dx/dt

Fllxl,

dx,jdt

F 21x l + F 22x2'

yet) PROOF.

H x (t ) . 2 2 Proceed dually to the proof of Proposition (2.11),

beginning with the definiticn of Xl states of r..

as the set of all unobservable

o

Combining Propositions (2.11) and (2.25) gives Theorem C as in KALMAN (1962].

This completes our survey of the "classical" results related

-

34 -

R. E . Kalman

to reacha bility, controllability, observapility, and constructibility. The remaining lectures wi l l be concerned exclusively with discrete-time sy stems .

The main motivation for the succeeding

developments will be the algebraic criteria (2.8) and (2.24) as well as a deeper examination of Theorems C and D of the Introduction.

-

35

-

R. E. Kalman

3.

DEFINITION OF STATES VIA NERODE EQUIVALENCE CLASSES

A classical dynamical system is essentially the action of the time set

T

(= reals)

on the states

X.

In other words} the

states are acted on by an abelian group, namely definition of addition). consequences. inputs

(~+

usual

This is a trivial fact, but it has deep

A (modern) dynamical system is the action of the

n on X;

in exact analogy ,nth the classical case, to

the abelian structure on

T there corresponds an (associative

but noncommutative) semigroup structure on

n.

The idea that

n

always admits such a structure was apparently overlooked until the late 1950's when it became fashionable in automata theory (school of SCHUTZENBERGER).

This seeClS to be the "right" way

of translating the intuitive notion of dynamics into mathematics, and it will be fundamental in our succeeding investigations. It is convenient to assume from now on, until the end of these lectures} that T

time - -set -

Z

additive (ordered) group of

integers. Since we shall be only interested in constant systems from here on} we shall adopt the following normalization convention:*

*In the discrete-time nonconstant case, we WOQld have to deal with ~ copies of n, each normalized with respect to a different particular value of T E ~.

-

36 -

R. E. Kalman No element of n is defined for

t >

In view of (3.2), we can define the "length"

max {-t E Z:

Iill I

is

ill

I!:Jt

Before defining the semigroup on fundamental notion of dynamics : defined for all

ari':

0

q~

in

n ~ n:

ill

O.

T

1(1)1

of ill

defined for any

n,

by

s < t}.

we introduce another

the (left) shift operator

an'

Z by

1-+

t ~ m(t + q).

arim:

Note that the definition of O"n

is compatible with the normaliza-

tion (3.2). If J

ill

n Jill ,

of (I) and

00'

(3.4)

v

(l)

= empty for

we define the join

ill, ill' E 0.,

as the function

(00

w'

lill'

on on

Jill' Jill'.

When n has an additive structure, then we replace

DEFINITION. o.

n X0

~

o.

0,

00 v 00'

by

ill

+ (I)'.

There is an associative operation

called concatenation, defined by

(00, v)

Note that, by

1-+

anIvl ill

v

v,

(3.2) through (3.4),

o

is well defined.

Note also that the asserted existence of concatenation rests on the fact that

0

intervals in

We might express the content of (3.5) also as:

T.

is made up of functions defined over finite

o is a semigroup with valuation, since evidently

l(I)ovl = Iwl + Ivl.

37 -

R.E.Kalman

In view of (3.5), it is natural to use an abbreviated notation* also for the transition function, as follows:

(3.6)

Iwl,

ep(o; -

Xow

w)

x,

Now we come to an important nonclassical concept in dynamical systems, whose evolution was strongly influenced by problems in communications and automata theory:

a discrete-time constant

input/output map f: 0 -+ Y: w >-+ few)

y(l)

We interpret this map as follows: system E

y(l)

is the output of some

(say, a digital computer) when E is subjected to

the (finite) input sequence w,

assuming that

E is some fixed

initial equilibrium state before the application of co,

This

definition automatically incorporates the notions of "discretetime" as well as "causal" or "dynamics" (the latter because yet)

is not defined for

t < 1).

However, (3.7) does not

clearly imply "constancy" (implicitly, however, this is clear from the normalization assumption (3.2) on more forceful, we extend

(3.8)

r:

n

-+

r

f

=

n).

To make the definition

to the map

Y X Y

(infinite cartesian product) (y(l), y(2), •••

Interpretation:

r

of the system E after

gives the output sequence t

=0

y

= (y(l),

). y(2),

resulting from the application of an

*Observe that xow is the strict analog of the notation xt customary in topological dyn?~cs. The action of w on x satisfies xo(wov) = (xom)ov in view of (1.5).

-

38 -

R. E. Kalman input

ill

which stops at

t

= o.

This definition expresses causality more forcefully and incorporates constancy, provided we define the (left) shift operator for any

~r

T

~

on

r

0, T E

so as to be compatible with let

~'

t

y( t + T)

l-t

:(y(l), y(2), ••• ) Note:

the operator

operator

~r

~n

1-4

(y(T + 1), y(T + 2), •.• )

"appends" an undefined term at

0,

the

"discards" the term y(l).

Now, dropping the bar over

(3.10)

(3.3). So,

DEFINITION.

f,

we adopt

A discrete-time, constant input/output map

(of some underlying d"vnamical system E)

is any map f

such that

the following diagram

is commutative.

f

is Hnc"r iff i t is a K-vcctor -------------_.------

§.P~c~\J..~:>m:>..r:~1.i.:s"1J!.

(3.10) as the external

It will be convenient to regard

definition of a dynamical system, in contrast to the internal definition set up in Section 1. Intuitively, we should think of kind of experimental data; namely,

f f

as a highly idealized incorporates all possible

information that could be gained by subjecting the underlying

-

39 -

R. E. Kalman

system to experiments in which only input/output data is available.

This point of view is related to experimental physics the

same way as the classical notion of a dynamical system is related to Newtonian (axiomatic) physics. The basic question which motivates much of what will follow can now be formulated as f ollows: PROBLEM OF REALIZATION. f

(but of course also of

~,

Given only the knowledge of

l1, and

r)

how can we discover,

in a mathematically consistent, rigorous, and natural

.~y,

the

properties of the system E which is supu os ed to underlie the given input/output map f? This suggests immediately the following fUndamental concept: DEFINITION.

A fixed dynamical system E

(internal

definition, as in Section 1) is a realization of a fixed input/ output map f

iff

fE' o the input/output map of Eo. o

f

o

=

that is,

f

o

is identical with

In view of the notations of Section 1 plus the special convention

(3.6),

the explicit form of the realization condition is

simply that f (m) o

for all m

l1.

~ (<11: (0; o 0 Tne symbol

brium state in which Eo application of m.

*

Iml, *, m» stands for an arbitrary equili-

remains, by definition, until the

(Later we simply take

*

to be

0.)

-

40 -

R. E. Kalman

To solve the realization problem, the critical step is to induce a definition of X (of some E)

from the given

o

f

o

•

It is rather surprising that this step turns out to be trivial,

on the abstract level.

(On the concrete level, however, there are

many unsolved problems in

actual~

computing what

Section 8, we shall solve this problem, too, but linear case.)

X h. o~

In

in the

The essential idea seems to have been published

first by NERODE [1958]:

(3.14)

DEFINITION.

Make the concatenation semigroup n into

a monoid by adjoining a neutral element defined function on ~).

Then (j) == f

--

equivalent to (j)' with respect to f«(j)'oV) There are reasons (which

rr~ny

a~e

f)

for all

¢

(which is the nowhere-

co'

(~:

(j) is Nerode

iff VE

n.

intuitive, physical, historical, and technical

scattered throughout the literature and

conce~·

trated especinl~ strong~ in KALMAN, FALB, and ARBIE [1969]) for using this as the MAIN DEFINITION. =f'

denoted as

X = ( (j))f: f input/output map f.

The set of equivalence classes under (j)

E

nl,

is the state set of the

Let us verify immediately that (3.15) makes mathematical sense :

-

41 -

R.E.Kalman PROPOSITION. f

For each linear, constant input/output maE

there exists a dynamical system (a)

~f

(b)

~

realizes

PROOF.

f;

f

We show how to induce

define the state set of ~f by (b). transition

such that

X.

=

f

~f

f\L~ction

of

~f

~f'

given

f.

We

Further, we define the

by

xov

We must check that

on the left of ~

o

o!),

two different uses of sentation of

x as

(m)f'

is well defined (note

that is, independent of the repreThis follows trivially from (3.14).

Now we define the readout map of

~f

by

(3.18) Again, this map is well defined since we can take special case in (3.14).

v =

¢

as a

Then

~ (xs v) f

and the realization condition

(3.6)

is verified.

Hence claim (a)

is correct. COMMENTS.

0 In' automata theory,

reduced form of any system which realizes

~f

f.

is known as the Clearly, any two

-

42 -

R. E. Kc l ma n

reduced forms are isomorphic, in the set-theoretic sense, since the set

X f

is intrinsically defined by

f.

(This observation

is a weak version of Theorem D of the Introduction; here "uniqueness" means "modulo a perwutation of the labels of elements in the set

X ".) f

~:ot, ice also that

since, by DefInition (3.15" is reachaole (W)f.

~a

any element

As to observability of

L

f

; s como1 etely reachable

everJ element W' ~f'

x

= (W)f

of X f

in the Nerode equivalence class see Section 10.

-

43 -

H. E. Kalman

4.

MODULES INDUCED BY LINEAR INRJTjOUTPUT MAPS

We are now ready to embark on the main topics of these lectures. It is assumed that the reader is conversant with modern algebra (especially:

abelian groups, commutative rings, fields, modules, the ring

of polynomials in one

the theory of elementary divisors),

variabl~,and

on the level of, say, VAN DER WAERDEN, lANG [1965], HU [1965] or ZARISKI and SAMUEL [1958, Vol. 1].

The material covered from here

on dates from 1965 or later. Standing assumptions until Section 10:

(4.1)

All systems

L:

(F, G, H)

are di screte-time, linear,

constant, defined over a fixed field

K

(but not necessarily

finite-dimensional).

Our immediate objective is to provide the setup and proof for the

(4.2)

FUNDAMENTAL THEOREM OF LINEAR SYSTEM THEORY.

The natural

state set X f

associated with a discrece-time, linear, constant input-

output map l'

over a fixed field

generated module over the ring z

and coefficients in

(4.3)

COMME~ITS.

to the inputs to

L:,

admits the structure of a finitely

K

K[z] of polynomials (-hi t h indeterminate

K).

Since the ring

K[z] will be s een to be related

this result has a superficial resemblance t o the

fact that in an arbitrary dynamical system L: the state set the action of a semigroup, namely

nL:

~

admit s

(see (3.6) and related footnote).

It turns out, however, that this action of from combining the concatenation product in

n on X, which results

n

with the definition of

-44R. E. Kalman

states via Nerode equivalence, is incompatible with the additive structure of

n [KALMAN, 1967, Section 3].

Our theorem asserts the

existence of an entirely different kind of structure of X. structure, that of a

This

K[z]-module, is not just a consequence of

dynamics, but depends critically on the additive structure on and on the linearity of

f.

The

rele\~nt

n

multiplication is not

(noncommutative) concatenation but (c ommutative) convolution (because convolution is the natural product in

K[z]); dynamics is thereby

restated in such a way that the tools of commutative algebra become applicable.

In a certain rather definite sense (see also Remark

(4.30)), Theorem (4.2) expresses the algebraic content of the method of the Laplace transformation, especially as regards the practices developed in electrical engineering in the U.S . during the 1950's. The proof of Theorem (4.2) consists in a long sequence of canonical constructions and the verification that everything is well defined and works as needed. In view of (4.1) and the conventions made in Section 1, be viewed as a K-vector space and and all met)

mE n .

=0

for all

(a)

n

w(t )

=0

for almost all

n

may

t E ~

By convention (3.2 ), we have assumed also that t > O.

~ ~[z]

As a result, we have that:

as a K-vector space.

Let us exhibit the i somor-

phism explicitly as follows: (4.4)

By (3.2 ), the sum in (4.4) is always finite.

The isomorphism

-

45 -

R.E.Kalman

obviously preserves the K-linear structure on

n.

In the sequel, we

shall not distinguish sharply between (I) as a function

T ~ IfI

and

(I) as an m-vector polynomial. (b)

n

is a free K[z]-module with m generators, that is,

n ~ IfI[z] also in the K[z]-module sense. action of K[z]

on n by scalar multiplication as

.,

K[z ] X n

.·m

"[Z]

where

In fact, we define the

~

n:

(7T, (I))

t-7

7T.(I)

«(I). E K[ z ], j J

1, ••. , m).

The product of 7T with the components of the vector (I) is the product in K[z].

We write the scalar product on the left, to avoid

any confusion with notation axioms are verified;

It is easy to see that the module

n is obviously free, with generators

m~

(4.6)

(3.6) .

j·th posf.ti.on, j

(c)

On

n

1, ••• , m,

the action of the shift operator

by multiplication by

z.

rrn is represented

This. of course. is the main reason for

introducing the isomorphi sm

(4.4) in the first place.

-

46 -

R. E. Kalman

(d)

(4.4)

Each element of

sUggests viewing

z

is a formal power series in

r

t

z

as an abstract representation of

-1

In fact, - t E

~;

hence we define

(4.7) By

r

(3.8)

and

(4.1),

not defined) for

yet) E

t < 1.

KP

for ea ch

t > 1

and is zero (or

In general the sum is taken ove r infinitely ~ny

nonzero terms; there is no question of convergence and the right-hand side of

(4.7)

series.

is to be interpreted stict1y algebraically as a formal power Since

reO)

is always zero (see

(3.8»),

we can say also

that (e)

r

is isomorphic to the K-vector subspace of z-l ~~th coefficients in KP)

(formal power series in of all power series with

0

first

KP[[z-l]] consisting

t er~.

The first nontrivial construction is the following : (f)

r

has the structure of a

K[z]

module, with scalar

multiplication defined as

(4.8)

.:

K[z] X r

->

r:

(n, r) H7r.y

This product may be interpreted as the ordinary product of a power series in

z-l

by a polynomial in

z,

followed by the deletion of

all terms containir~ no negative powers of the module axioms is straightforward.

z.

The verification of

-

47 -

R. E. Kalman (g)

is a

f

K[ e l

quence of the fact that cation by (h)

homomorphism. This is an immediate consef = constant (see (3.10» "and that multipli-

corresponds to the left shift operators on n and

z

The Nerode equivalence classes of

n/kernel f.

f

r.

are isomorphic with

This is an easy but highly nontrivial lemma, connecting

Nerode equivalence with the module structure on n.

The proof is an

immediate consequence of the formula w.v

=

z lvlW + V.

(4.9) implies

In fact, by K-linearity of f, f(w.V)

=

f(w'.V)

for all

v E n

if and only i f fezk .WI) for all k> 0

k

fez -oi)

in Z.

The proof of Theorem (4.2) is now complete, since the last lemma identifies module

X f

as defined by (3.15) with the

quotient

n/kernel f.

We write elements of the latter as it is clear that since

K[z]

n

Xf

[w]f

=

W

+ kernel fj

as a K[z]-module is generated by

itself is generated by

e

l, that the scalar product in n/kernel f

••• , em

then

[el]f' ••• , [em]f'

(see (4.6».

Note also

is

(4.10) The last product abov" (that in n)

has already been defined in (4.5).

The reader should verify directly that (4.10) gives a well-defined scalar product.

-

48 -

R. E. Kalman

REMARK.

(4.11) define

f.

There is a strict duality in the setup used to

From the point of view of homological algebra [MAC LANE

19631, this duality looks as follows.

Since every free module is

projective, the natural map

exhibits

X as the image of a projective module. On the other f hand, there is a bijection between the set X and the set f

'::'f

fen)

'::'f is clearly a and so

X f

X f

K[ z 1- submodu.Le of

r

(with

f( z .m) ) ,

z- f(m)

K[r..] -modules.

It is

is an injective module [MAC LANE 1963, page 95,

r

Exercise 21

1'.

'::'f are isomorphic also as

and

known that

c

So the natural Inap X ~ :;;:f: f

as a submodule of an injective module.

[m1f

H

f(m)

exhibits

This fact is basic in the f (Section 7),

construction of the "transfer function" associated with

but it s full implications are not yet understood at present. There is an easy counterpart of Theorem (4.2) which concerns a dynamical system given in "internal" form: (4.12)

PROPOSITION.

The state set

X E

of every discrete-time,

ffnite-dimensional, linear, constant dynamical system admits the structure of a PROOF. K-vector space.

E

=

(F, G, -)

K[zl-~.

By definition (see (1.10)), We make it into a

X= ~

is already a

K[zl-module by defining

-

49 -

R. E. Ka l m a n

K[ z ] X JCl ->

(4.13)

.:

(4 .14)

COMMENT.

JCl:

(7T, x)

H

7T(F)x .

o

The construction used in the proof of (4 .12) is

t he classical trickof studying the properties of a fixed linear map F:

JCl

->

JCl

via the

K[ zl-module structure that

F

induces on

JCl

by (4 .13). In view of the canonical construction of L provided by f Proposition (3.16), the state set X can be treated as a K[zl module irrespective as to whether

X is constructed from

or given a priori as part of the specification of L the

(X

f

(X

= Xf)

= ~). Thus

K[zl-module structure on X is a nice way of uniting the "external"

and the "internal" definitions of a dynamical system .

Henceforth we

shall talk about a (discrete-time, linear, constant dynamical) system

L somewhat imprecisely via properties of its ass ociated

K[zl -module~.

We shall now give some examples of using module-theoretic language to express standard facts encountered before . (4. 15)

PROPOSITION .

FE is given by PROOF.

If X is the state-module of L,

X -) X: x

H

the map

z -x ,

This is obvious from (4 .13) if X

~, f

then we find that, by (1.17), x(l)

Fx(O) + Gw(O) , F[ ~lf + Gw( O);

since

x( O) results fr om input

~,

x(l)

resuJ.ts from input

z·~

+ w(O)

- so -

R. E. Kalman

and we get [Z· E + w(0) ] f'

z'[E]f + [w(O)]f' z'[E]f + GuJ(O).

o

So the assertion is again verified.

Now we can replace Proposition (2.14) by the much more elegant (4.16)

A system E = (F, G, -)

PROPOSITION.

if and only if the columns of G generate

is completely reachable

~.

The claim is that complete reachability is equiva-

PROOF.

lent to the fact that every element

x E

~

is expressible as

m

x

1rj E K[z],

= ftl1rjgj'

G

[gl' ••• , ~].

In view of (4.15), this is the same as requiring that

x be expressible

as m

x

ftl1r/F)gj;

this last condition is equivalent to complete reachability by (2.14). (4.17)

COROLLARY.

The reachable states of E are precisely

those of the submodule of (4.18)

REMARK.

simply means that

0

~

generated by (the columns of)

The statement that X is

~

G.

"E is not completely reachable"

generated by those vectors which make up

the matrix G in the specification of the input side of the system

E.

-

51 -

R. E. Kalman

It does not follow that vectors.

X cannot be finitely generated by some other

In fact, to avoid unnecessary generality, we shall henceforth

assume that

X is always finitely generated over K[z]. From the system-theoretic point of view, the case

when we need

infinitely many generators, that is, infinitely many input channels, seems rather bizzare at present. The syst em X f

PROPOSITION. PROOF. is reached by

(4.20)

~

iff is

W

Obvious from the notation:

E

E

[O]f'

a state

x

[~]f

n.

o

PROPOSITION. PROOF.

is completely reachable.

The system X f

is completely observable.

Obvious from Lemma (h) above:

D([w]f)

= fe w) = 0

which says that the only unobservable state of X f

o

0 E X • f

Let us

g~nera!ize

the l ast r esult t o obtain a module-theoretic

for complete obs ervability. doing this.

c r it c r i ~n

There are two technically different ways of

The first depends on the observation that the "dual" of a

submodule (see Corollary

(4.17»

is a ~uotient module.

observability via the "dual" system Consider a dynamical system E K[z ]-module ~

(F', HI, -)

= (F,

The s econd defines

associated with

(F, -, H).

-, H) and the corresponding

and K-homomorphism H: ~ ~ Y = KP•

We can extend H

-

52 -

R. E. Kalman

to a K[z] -homomorphism

H:

~

--+

H

(look back at (?8)) by setting

r

x ~ (Hx, H(z'x), H(z2. x), .•• ). From Definition (2.19) we see that no nonzero element of the quotient module

~/kernel

can say that

H is unobservable. Hence, by abuse of language, we

~/kernel

H

is the module of observable states of E.

Thus we arrive at phrasing the counterparts of (4.16-17) in the following language:

(4.21)

A system E

PROPOSITION.

if anionly i f the quotient module

(4.22)

COROLLARY.

= (F,

-A

~/kernel

is compl et el y observable

TERMINOLOGY.

~/kernel

are to be identified

H.

The preceding cons i derat i ons suggest viewing

a system E as essentially the sane "thing" as a module speaking, however, knowing E

= (F,

G, H)

(see (4.13)) but also a quotient module module (that generated by

XEo =

~.

H is isomorphic with

The observable states of E

with the elements of the quotient module (4.23)

H)

G)

of ~,

~

X.

gives us not only (over kernel

H)

Strictly ~

= XF

of a sub-

that is

K[z]G/ kernel -H.

If ~ ~~ we say that

~

is canonical (relative to the given

G, H).

To be more precise, let us observe the following stronger version of (4.19-20):

-

53 -

R. E. Kalman

(4.24)

CORRESPONDENCE

between

There is a bijective correspondence

THEO~I.

K[z]-homomorphisms

f: n

r and the equivalence class of

--+

completely reachable and completely observable systems basis change in

E modulo a

~.

Detailed discussion of this result is postponed until Section A

7. stricter observation of the "duality principle" leads to

(4.25)

The K-linear dual of E

DEFINITION.

= (F, G, H) is

E* = (FI, H', G') (, = matrix transposit ion). The states of E* are called costates of E. The following fact is an immediate consequence of this definition:

(4.26)

PROPOSITION.

structure of

K[z-l]

is the dual of ~ product in

~*

The state set

of

Y~*

module, as follows:

E* may be given the

(i) as a vector space

~*

regarded as a K-vector space, (ii) the scalar

is defined by x*(Fx).

(4.26A)

REMAR.X.

We cannot define

K[z]-linear dual of domain

~,

XE*

as

because every-torsion module

D has a trivial D-dual.

equal to

M over an integral

However, the reader can verify (using

the ideas to be developed in Section 6) that morphic with

Ho~[ z ] (~, K[ z])

~*

defined above is iso-

Ho~[z](~,K(z)/K[Z]). See BOURBAKI [Algebre, Chapter

(2 e ~d.), Section

4, No.8].

7

-

54 -

R. E. halman Now we verify easily the following dual statements of (4.16-17):

(4.:27)

PROPOSITION.

if and only if (4.28)

A system E

generates

HI

COROLLARY.

generated by

-, H)

is completely observable

~*.

The observable COstates of E* are precisely

the reachable states of E*, ~*

= (F,

that is, those of the submodule of

H'.

We have eliminated the abuse of language incurred by talking about "observable states" through introduction of the new notion of "observable COstates".

The full explication of why this is necessary

(as well as natural) is postponed until Section 10. The preceding simple facts depend only on the notion of a module and are immediate once we recognize the fact that

F may be eliminated

from statements such as (2.8) by passing to the module induced by via (4.13).

F

But module theory yields many other, less obvious results

as well, which derive mainly from the fact that

K[z]

is a principa1-

ideal domain. We recall:

an element

m of an

R-modu1e M (R

= arbitrary

commutative ring) has torsion iff there is a r E R such that r·m

= O.

If this is not the case,

m is free.

Similarly,

said to be a torsion module iff every element of

M has torsion.

M is a free module if no nonzero element has torsion. is any subset of M, ~

=

(r;

the annihilator r·j,

it follows immediately that

o ~

of

~

for all

j,

M is

If

LC M

L is the set

E L);

is an ideal in

R.

Note also that

-

55 -

R. E. Kalman

the statement that

"M

is a torsion module" does not imply in general

is nontrivial, that is,

~

~

f. o.

(Counterexample:

take

an M which is not finitely generated.) Coupling these notions with the spe cial fact that, for us, R

= K[z),

we get a number of interesting

(4.29)

PROPOSITION.

is a torsion

PROOF.

">S:

is finite-dimensional i f and only i f

I:

If

>s:

q

is infinite dimensional.

"I: = finite-dimensional" is defined

Xl' ••• , x q

G).

of XI:

deg Y

j

Hence

with Y E K[z).

Yl[z)

= nj >

0

j

for all

is either zero (and then a unit which implies

See (l.18).

(which are not·

is a principal-ideal domain, each of the

K[z}

>s:

By assumption X is. finitely generated

nonzero elements

pal ideal, say, then

I:

= finite-dimensional as a K-vector space".

necessarily the columns of

Since

is free,

We recall that

Sufficiency. by, say,

results:

K[z)-~.

COROLlARY.

to be

syste~theoretic

x

replace each expression

j

x. J

=0

j

If

1, ••• , q.

JS:

A

x

is a princij

is a torsion module, For otherwise

Y

j

is free, which is a contradiction) or contr

y to assumption.

Hence we can

-

56 -

R. E. Kalman by the simpler· one

XL,

which shows that

as a K-module, is generated by the finite set

Necessity. x

F:

1-+

z.-x,

If

Let

XL

~F

be the minimal polynomial of the map

is finite-dimensional as a K-module,

deg

> O.

~F

This means (by the usual definition of the minimal polynomial in matrix theory or more generally in linear algebra) that x E

XL

so that

y~

is a torsion

~F

annihilates every

o

K[z]-module.

Notice, from the second half of the proof, that the notion of a minimal polynomial can be extended from K-linear algebra to

K[z]-modules.

In fact, the same argument gives us also the well-known (~030)

PROPOSITION.

Every finitely generated torsion module

over a principal-ideal domain ~M

given by

~

=

R has e nontrivial minimal pynomial

~~.

COROLLARY. q

If a

K[z]-module

generators and minimal polynomial

f

~X'

X is finitely generated with then

dim X (as K-vector space)

~

REMARK.

is completely reachable and is

The fact that

therefore generated by of L

M

L

f

q.deg ~X'

m vectors allows us to estimate the dimension

by (4.31) knowi.ng only

deg

but without having computed

~X

f

-

57 -

R. E. Kalman

X

itself.

(Knowing X explicitly means knowing F: x ~ z·x, etc.) f In other words, the module-theoretic setup considerably enhances the f

content of Proposition (3.16).

Guided by these observations, we shall

develop in Section 8 explicit algorithms for calculating from

f

without first having to compute PROPOSITION.

E

If

XL

f

directly

F.

is a free

K[z]-module, no sta.te of

can be simultaneously reachable and controllable. PROOF.

We recall that

"XL = free"

simplicity that

XE = K[z].

for some 5 E K[z]. zlwl. x +

00.1

=0

This shows that WI

Similarly,

for some

1

Then

00

x

XL

means that

(isomorphic to) a finite sum of copies of K[z].

by

dim E

= reachable

is

Suppose for means that

x

= 5'1

x = controllable means that

E K[z].

is annihilated by

Hence if x has both properties,

~ow,

which contradicts the assumption that

the input ~

5 followed

is free.

o

The most important consequence of Theorem (4.2) is due to the fact that through it we can apply to linear dynamical systems the well-known FUNDAMENTAL Sl'RUCTURE THEOREM FOR FINITELY GENERATED MODULES OVER A PRINCIPAL IDEAL DOr1Allf R (Invariant Factor Theorem for Modules).

Every such module M

wi~h

~

generators is isomorphic to

-

58 -

R. E. Kalman

where the the

El

Vi

R/ViR are quotient rings of

R viewed as modules over

(called the invariant factors of M)

M up to units in

denotes the free

Vi Iw .. , i l

R,

R-module with

s

R,

are uniquely determined

i = 2, ••• , q,

and, as usual, RS

generators; finally,

r + s

~

m.

Various proofs of this theorem are referenced in KALMAN, FALE, and ARBIB [1969, page 270], and one is given later in Section 6. Note:

The divisibility conditions imply that

module iff

s = 0

and then

M is a torsion

VM = VI.

One important consequence of this theorem (others in Section is that it gives us the most general situation when torsion module

E.

~

7)

is not a

(4.33) with (4.34), we

For instance, combining

get PROPOSITION.

A system cannot be simultaneously completely

reachable and completely controllable if its oo-dimensional components (i.e.,

(4.37 )

REMARK.

s >0

in

K[z]-module

X has any

(4.35».

Although our entire development in this section may

be regarded as a deep examination of Proposition (2.14), most of our comments apply equally well to (2.7), since both statements rest on the ~ algebraic condition (2.8).

In fact, the only remaining

thing to be "algebraized" is the notion of "cont i nuous- t ime " . shall not do this here.

We

Once this last step is taken, the algebraization

of the Laplace transform (as related to ordinary linear differential equations) will be complete.

-

59 -

R. E. Ka I ma n

5.

CYCLICITY AND REIATED QUESTIONS

We recall that an R-module

element

th~t

M = Hm.

m E M such that

iff there is an element better to say

(R = arbitrary ring) is cyclic

M

such a module is monogenic:

[It would be

generated by one

m.]

If M is cyclic, the map R and has kernel

Am'

loI: r

~

r'm

H

is an epimorphism

the annihilatir-g ideal of m.

This plus the

homomorphism theorem gives t he well-known PROPOSITION.

Every cyclic

R-~J ::J:lle

RIA:n

is isomorphic with the quotient ring

r-,

with ge::e!'at::>!' :n

vie~ed a s an

~-~Jdule.

This result is much m::>re interesting when, as in our case,

R

is not only commutative and a principal-ideal domain, but specifically the polynomial ring

X be a cyclic

So let A

g

g.

=

'I' g K(z],

where

K(z] -module ·H.ith generator

X "" X[ z l/vK[ z l. (i)

(ii)

and

l~t

X.

Write

~

g

Hence

= ~ X =~.

'I' g is a minimal

In view of (5.1),

Let us r ecs.Ll some f'eabur es of the ring

K[ z ]hx[ z }:

Its elements are the residue classe s of polyno~als ~ ( mod V) ,

rr E K[z]. (rr]-[cr]

g

is the minimal or annihilating polynomial of

By commutativity and cyclicity,

polynomial also for

(rr]

K[z] .

W!'ite these as

[~)

or

[rrlo/.

Multiplication i s def ined as

= [rrcr). Each

[rr]

is either a

is a unit iff (n, 'f)

tL~it

= greatest

or a divisor of zero.

In fact,

common divisor of u, V is a

-

60 -

R. E. Kalman

unit in

K[z)

(that is,

cnr + Tljr so that

unit in K[z),

divisors since (iii)

(0",

1

If

T

[71").[ljr/Q] ljr

Then

E K[z])

is the inverse of

[0")

=0 f

(71", ljr)

(71", \if) E K).

[71").

On the other hand, if

then both

[71")

and

[ljr/Q) are zero

= [(71"/Q)ljr] = o.

is a prime in K[z)

(that is, an irreducible poly-

nomial with re spe ct to coefficients over the ground field by (ii)

K[z ]/ljrJ([ z ]

i s a field.

K),

then

This is a very standard construction

in algebraic number theory. Since it is awkward to compute with equivalence classes

[71"],

shall often prefer to work with the standard representative of namely a polynomial mined by

[71"]

1i- of least degree in

and the condition

[ 71"] •

deg 7i- < deg ljr.

we

[71"),

7i- is uniquely deterHenceforth

-

will

always be used in this sense. The next two assertions are immediate: (5.2) to the

PROPOSITION .

K[z]/fK[z)

K-vector space CEJ( n)

K[z)/ljrK[ z ]

=

~

a E K[z l : deg l' < n

is also isomorphic to lJ1(n) as a

we define the scalar product in ®(n) PROPOSITION. then

K-vector space is isomoruhic

dim E = deg ljr .

If

=

deg \' } •

K[ z I-mcdul,e, provided

E.l (71".1')

r+

7i1.

XE is cyclic ,d th minimal poJ.y:lomial

~,

-

61 -

R. E. Kalman

(4.34), we see that the most general

Looking back at Theorem

K(z]-module is a direct sum of cyclic

(5.3) and

(4.3~

K(z]-modules.

By combining

and using the fact that dimension is additive under

direct summing, we can replace (4.31) by the followiEg exact result: PROPOSITION. factors

If X is a torsion module with invariant E

W , ••• , W then l q -dim E

A simple but highly useful consequence of cyclicity is the so-called control canonical form [KALMAN, FALB, and ARBIB, 1969,

44] for a completely reachable pair (F, g) wher e g is an

page

matrix.

n X1

We shall now

Observe first that lent to

"g

generates

procee~to

"(F, g) XF,

deduce this result.

completely reachable" is equiva-

the module induced by

F via (1+ .13) ."

Let

det (zI - F), n

z + al Z then X F•

~

n-l

+ ••• + an'

~ E K;

is the characteristic (and also the) minimal polynomial for

[This is a well-known fact of module theory.

See for example

KAlMAN, FALB, and ARBIB [1969, Chapter 10, Section 7] for detailed discussion.]

As in KALMAN [1962], consider the vectors

-

62 -

R . E. Kalman

en e

in~.

=

n_l

g

=

=

l.g

=

{l)(z).g,

~.g =

z.g +

[ For consistency,

{2)(z)'g,

xin+l)(z) F

= X(z).J F These vectors are

easily seen to be linearly independent over since

~

'" ®n)

as a

K.

They generate

K-vector space (Proposition (5 .2}).

••• , en are a basis for ~ as a K-vector space. l, respect to this basis, the K-homomorphism e

z:

is represented by the matrix

(5. 6)

0

1

0

0

0

0

0

1

0

0

0

0

0

0

1

F

-0:

r

-exn-1

-0:

n-2

[This is proved by direct computation. necessary to use the fact that

-0:

2

Hence

With

z -x

X H

-~

In particular, it is

~

-

63 -

R. E. Kalman

z.e

1

z~n)(z).g, (~(z) - an) 'g,

Note that the last row of

By definition,

F

of

~.

~

has the representation

(5.7 )

g

in

(5.6) consists of the coefficients

= en' Hence g as a column vector in

g

Conversely, suppose

W,

~

have the matrix representation

with respect to some basis in

~.

(5. 6-7)

Then (by direct computation)

the rank condition (2 .8) is satisfied and therefore

(F, g) is

completely reachable in both the continuous-time and discretetime cases (Propositions (2 .7) and (2.16)). We have now proved:

(5.8)

PROPOSITION.

The pair

(F, g)

is completely reachable

if and only if there is a basis relative to which

COROLLARY. A(Z)

= zn + tll zn-l + ... + tln

exists an ~

Given an arbitrary

n-vector

(F, g)

£

in

such that

K[ zJ,

n-th K

is,given by

degree polynomial

= arbitrary

A = ~_g£'

is completely reachable.

F

field.

There

if and only if the

-

64 -

R. E . Kalman

PROOF.

Suppose that

With respect to the same basis

(5.6-1),

forms

(F, g)

(5.5)

is completely reachable.

which exhibits the canonical

define

Then verifY by direct computation that Conversely, suppose that reachable.

(F,

A = ~_gtl' g)

is not completely

Then, recalling Proposition (2.12) (which is an

algebraic consequence of (2.8) and hence equally valid for both continuous-time and discrete-time), deg ~

•

~

Since

22

the polynomial

KU

and so is also

F-invariant subspace of X = ~,

is independent of the choicp of basis in

~

II

~ = XP/X • (In F 22 11 does not depend on the arbitrary choice of

and the same is true then also for

particular, X 2

is an

dim X > 0 2

~

22

in satisfYing the condition X =

we have for all

n-vectors

~ EB X

2.)

t, deg

This contradicts the claim that with suitable choice of

In view of (2.12),

~

22

A-X - · F- gt ·

> O.

is true for any

t.

In view of the importance of this last result, we shall

rephrase it in purely module theoretic terms:

A

o

-

65 -

R. E. Kalman THEOREM.

Let

K be an arbitrary field and

K[z]-module with generator n.

g and minimal polynomial

There is a bijection between n-th

= zn + 131 zn-l + .e: If' -+ If': x(j) .g ~

degree polynomials

(5.5»

J

such that

-

"A is the minimal polynomial for the

new module structure induced on X by the map Note that in (5 .11) The map l

z

X of degree

..• + 13 in K[ z l and K-homomorphisms n H l .• g (j = 1, " " nand x(j) defined

"A( e)

E

X a cyclic

(F, g, -) to

z*

l(x) .

z*: x H z -x -

lex) corresponds to gl'x in (5.10).

in (5.11) defines a control law for the system corresponding to the module X.

The passage from

is the module-theoretic form of the well-known open-loop

to closed-loop transformation used in classical linear control theory. PROOF.

If',

basis for treat

l

l

represents the equivalence class is never a

l

that this choi ce of

= 1,

••• , n + 1.

"A(l)(z _

13 j

.e

- O:j'

implies

We

(that is, an operator

l'x = l(~ 'g), where

= (s:

[s]

s·g

= x).

Unless

K[zl-homomorphism and therefore

does not commute with nonunits in K[z]. Define

j

form a

is clearly a well-defined K-homomorphism.

K-vector space), by writing

identically zero,

.e

x(l) .g, ••• , x(n)'g

formally as an element of K[z]

on X is a ~

Since the vectors

j

= 1,

.•• , n.

"A(j)(z -

Use induction on

j.

We prove first

l) = x(j)(z) for By definition,

l) = x(l)(z). f I n the general case,

-

66 -

R. E. Kalman

(inductive hypothesis), (def . of .£), (def. of .£ .), J

(def. of x(j+l)).

j = n + 1)

It follows (case regarded as a

K[z*]-module.

A(l)(z*).g, ••• , A(n)(Z*)'g space since

F=~~asitions

to the

A annihilates

g

X

On the other hand, the is a basis for

X as a

K-vector

X(l)(z).g : .• , x(n)(z).g was such a basis.

is cyclic with generator by

that

also as a

K[z*]-module.

(5.1-2) the annihilating ideal of

So X

Hence

g" with respect

K[z*)-module structure cannot be generated by a polynomial

of degree less than

n,

nomial with respect to

that is, z*.

A is indeed the minimal poly-

The correspondence

A

f-'

.£ is obviously

o

bijective. The proof immediately implies the following COROLLARY. ~

K[z]-module.

respect to the are related as

Hz)

~

Then

x x

=

~. g

be any element of X viewed

has the representation

K[z*]-module structure on

X,

where

~*.g

S

with

~

s*

-

67 -

R. E. Kalman

So the open-loop/closed-loop transformation is essentially a change in the canonical basis, provided X is cyclic.

X(j)

It is interesting that the

have long been known in

Algebra (they are related to the Tschirnhausen transformation discussed extensively by WEBER [1898, §46, 54, 74, 85, 96]), but their present (very natural) use in module theory seems to be new. **Theorem (5.l1} may be viewed as the central special case of Theorem A of the Introduction.

Let us restate the latter in

precise form as follows: THEOREM. n

;>.(z) = z + I\Z There exists an if and only if

n-l

Given an arbitrary . + ••• + I3n E! K[z],

n X m matrix (F, G)

Lover

n-th

degree polynomial

K = arbitrary field. K such that

~-GL'

=A

is completely reachable.

For some time, this result had the st a t us of a well-known folk theorem, considered to be a straightfoniard consequence of (5.9). has been discovered independently by many pe ople .

The latter

(I first he ard

of it in 1958, proposed as a conjecture by J. E. Bertram and proved soon afterwards by the so-called root-locus method.)

Indeed, the

passage from (5.11) to (5.13) is primarily a tecnnical problem.

A

proof of (5.13) was given by LAIiGEliliOP [1964) and subsequent ly simplified by WON¥JU~ [1967).

Tne first proof was (~n_~ecessarily)

very long, but the second proof is also unsatisfactory; since it depends on arguments using a splitti ng field of

K

**The material between these marks was added after the Summer School.

-

68 -

R. E. Kalman

and fail when K is a finite field.

We shall use this situation

as an excuse to illustrate the power of the module-theoretic approach and to give a proof of (5.13) valid for arbitrary fields. The procedure of LANGENHOP and WONHAM rests on the following fact, of which we give a module-theoretic proof: LEMMA.

Let

F be cyclic* and

!.!! m-vector

a E

K be an arbitrary but infinite field.

(F, G)

Ifl

completely reachable.

such that

(F, Ga)

Let

Then there is

is also completeq

reachable. We begin with a simple remark, which is also useful in reducing the proof of (5.13) to Lemma (5.18). SUBLEMMA.

Every submodule of a cyclic module over a

principal-ideal domain is cyclic. PROOF OF (5.14). m= 1

is trivial.

m.

The case

The general case amounts to the following.

Consider the submodule gl' ••• , ~-l

We use induction on

of G.

Y of X =

~

generated by the columns

In view of (5.15),

Y is cyclic.

By the

inductive hypothesis, we are given the existence of a cyclic generator of Y of the form

gy

We must prove:

a, J3 E K the vector

for suitable

is a cyclic generator for

=

a i gl + ••• + am_I· ~-l' a a.~

+

i

E K.

J3.~

X.

*Of course, this means that the is cyclic.

K[z]-module

X F

(see (4.13))

-

69 -

R . E. Ka l ma n

By hypothesis,

Sx'

X has an (abstract) cyclic generator

By cyclicity we have the representations

=

gy

and

TJ'~

Eim

Tj,

~,~,

~ E K[ e l-

Hence our problem is reduced to proving the following:

ex, tl

E

K the polynomial

aT)

~

+

is a unit in

K[

for suitable This,

Z]/~K[ z ] .

in turn, is equivalent to proving

(5.16) where

aT)

classes zero.

-

mod gi'

K[z]

are the unique prime factors of

Then no pair

(~i' ~i)'

X,

reachable.

= 1.

values of

X'

(F, G)

is completely ~

and

gy

the condition

tl from con sideration.

can be

is a proper sub-

are zero, then every ~ .

K[Z]/~K[z],

Then

.•• , r

that is, ~gi annihilates

whence

contradicting the fact that

I f all the

is a unit in

ex

X' = K[z]gy + K[z]9m'

= 1,

i

For if one is, then gil (~, TJ, ~),

module of

r

in

1, ... , r

i

~

mean the representative of least degree of equivalence

the submodule

So let

° (mod g.)

f-

gl' .,., gr Let

~.

+ ~

f-

0,

~. + ~ . ~

Since

~

= 0 eliminates at most K is infinite by

(5.16).

An essential part of the lemm~ is the stipulation that

"F

= cyclic

+ (F, G)

TJ

is already a cyclic generator.

hypothesis, there are always some tl which sati sfy

The hypothesis

so

0

a E ~.

= completely reachable" means that

-

70 -

H. E . Kalman

that is, the le~~ i s trivially true for some a E ~[z]

sx = Ga.

But since we want

a E K,

since

there must be interaction

between vector-space structure and module structure, and for this reason the lemma is nontrivial. when K = finite field.

As a matter of fact, the lemma is false

The simplest counterexample is provided

when (5.12) rules out a single nonzero value of 13, out all

thereby ruling

13. COUNTEREXAMPLE.

Let

integers modulo the prime ideal

Notice that

K = y~, ~.

that is, the ring of

Consider

~ = Xl e X e ~

(as a K[z]-module), where the 2 minimal polynomials of the direct sumrrands are

').(z) X 2(z) X (Z)

3

z2 + z + I, z 2, z + 1. (Xl' X X = 1, hence 2, 3) gl generates Xl eX while

All these factors are relatively prime, X is cyclic. generates

Notice also that

X ex • A cyclic generator for 2 3

3

X is

-

71 -

R. E. Kalman

A simple calculation gives

(z

4

2

+ Z

+ l)'~'

Conditions (5.16) are here a-I + f3'0

f

0

(mod Xl)'

+ f3.1

f

0

(mod X

a-I + f3-1

f

0

(mod X ) .

a-O

2),

3

These conditions have no solution in

g/~.

At this point, the following is the situation concerning Theorem (5.13): (1)

Its counterpart, Theorem A of the Introduction, was

claimed to be true in the continuous-time case under the hype

.~esis

of complete controllability. (2)

In the discrete-time case (5.13) with the preceding

hypothesis Theorem A is false, because of the counterexample: (F

= nilpotent,

~-GL'

G

= 0)

the pair

is completely controllable, but evidently

1s independent of L.

However, in view of (5.11),.Theorem

(5_13) might be true also in the discrete-time case if "complete controllability" is replaced by "complete reachability", this modification being immaterial in the continuous-time case. (3)

Because of (5.17), we might expect that a theorem like (5.13)

1s false for an arbitrary field

K.

-72R. E. Kalman

(4)

If our general claim that reachability properties are

reflected in module-theoretic properties is true, then (5.13) should hold without assumptions concerning module-theoretic fact, that

K,

= principal

K[z]

independent of the specific choice of

because the principal ideal domain, is

K.

We now proceed to establish Theorem (5.13). hypotheses on

K will turn out to be irrelevant.

PROOF OF (5.13).

Necessity is proved exactly as in (5.8).

Sufficiency will follow by induction on m,

~~.

once we have proved it

m = 2:

in the special case

(5.18)

Let

K be an arbitrary field and let

K[z]-module generated by

gl' g2.

K[z*]-module structure on

Let

Case 1.

z*

=z

£ - £

£(x)

will change the

serve that on

o

or

x E Z.

on

Thus there exist polynomials

£

In (5.11)

Replacing

K[z]-module structure on

t.. on

z

Y but pre-

is prime to the unchanged minimal polynomial

y +

Z

by

so that the new minimal poly-

V,

a

such that

B.r hypothesis, every x E X has the representation x

induces a

g2·

X=YEllZ.

for all

nomial Z.

gl + g2

that is,

Z. Further, choose Y

z - £

Y = K[z]gl and Z = K[z]g2.

ynZ=O,

such that

=

z*

X then X is cyclic with respect to this

structure and is generated by either

PROOF.

X be a

There is a K-homomorphism £

(of the tyPe defined in (5.11] such that if

take an

That is, special

vt.. + o X

~Z

= 1.

X

-

73 -

R.E. Kalman

Now verify that x

= (T]crX + svA)·(gl + g2)'

T]crX'g

l

+ SVA·g 2,

T](l - VA)·gl + s(l - crX)'g2' Tj'gl + s 'g2'

K[z*]-module.

ynz=wf o.

C2.s e2.

there is ag E K[z] cyclicity of Take same w Tj

-1

T]

g'g2

f

on

Then if

O.

generates

unit (mod

w

there is also a

Y,

f

su ch that

1Sc).

To show:

X such that

g' g2

Z = X.

3y ;lypotlle s i s,

and therefore, by

Tj E K[z]

such that

1Sc)

g'g2 = w = Tj'gl'

we are done because

In the nontrivial case,

there is a suitable new module structure

~ = unit (mod X* ) ,

nomial of X as a

'lE W.

T] = u,'.it (mod

and so

Y,

kt

X*

being the minimal poly-

K[ z* ]-moduLe,

The main facts we need are the following: SUB~~~.

deg X = n,

Let

X be a fixed element of

FX the companion matrix of

the cyclic module induced by X F• X

Then

Tj E K[z]

F)? and

is a unit modulo

X given by g

K[z]

,nth

(5.6),

X FX

a cyclic generator of

X if and only if

~'g

is

also a cyclic gener at or of X . FX PROOF.

Obvious.

o

-

74 -

R. E. Kalman

.Jl-l )

f

( dety, FXY' ••. , .1"X Y

where

y

(5.19).

Same notations as in

SUB~~~.

(5.20)

Write

0,

is the column vector Tin

PROOF.

Since

X(1), ••• , x(n)

is the basis for the

K-vector space of all polynomials of degree (~l' ••• , ~n)

is uniquely determined by

< n,

By definition

~.

is the matrix representing the module operator to the special basis

e

l,

••• , en

in

~ X

the n-tuple

z: x

given by

~

z·x

FX relative

(5.5).

Similarly,

using one of the module axioms, we verifY that

£

J=l

[rt.x(j)(Z)]'g "J

'

Jl'iij[x(j)(z).gJ,

in other words, the numerical vector (5.22) represents the abstract vector

Ti·g

in

X relative to the same basis FX

e

l,

.•• , en'

Recall

-

75 -

R. E. Kalman

that By

generates

Tj'g

(2.7)

~X

(F x, ll(FX) g)

is complete reachable.

the latter condition is equivalent to

follows from

(5.21)

Same notations as in

(5.19)

and

(5.20).

Given

n-vector (5.22), there exists a polynomial

X

is satisfied.

PROOF.

Let

11 1 , Ti 2 , X(z )

The rest

o

any nonzero nwnerical such that

(5.21).

(5.19).

SUBLEMVA.

numbers

iff

Ti r be the first member of the sequence of which is nonzero.

n +

Z

~z

and determine the first ll r

'i'ir+l

o

Tjr

o

o

n-l r

Write

+ •.. + an' coefficients of

X by the rule

~:J

:J

T}r

an

o

o

1

(Since all numbers belong to a field, the required values of a

r,

..• , an

exist.)

reduce the matrix in

Now check, by computation, that these conditions

(5.21)

to the direct sum of two triangular

matrices, each with nonzero elements on its diagonal . In view of always choose a new

(5.12), Xy = Xt

it follows from these facts that we can such that

Tjt

= unit

mod Xt •

o

-

76 -

R. E. Kalman

The proof of Case 2 is not yet complete, however, because we must still extend the is easy .

Write first

Z

K[z*]-module structure from

= W$

Z·

and then

direct sum is now wi t h r espect to the

t

from Y to X

"by

£i Z'

s '.:ttins

polynomial

X*

(5.12),

is replaced by some

(5.24 )

~

defined over

K-~odule

O.

=

X Since ~*

X

Y to X. This

Y $ Z',

where the

structure of X.

Extend

;;o',{ we have a n(;w mi nima.L z*

= Zt on Y,

~*

= ~t .

By

such that

w

that is, our previous representation of

w~ 0

in W induces a

similar representation with respect to the new K[z*]-module structure on X. Since

~

Xr,

is a unit modul o

By (5.24), we have, with re sp ect t o the cy.

(~* ·g2)'

c-

(~* ·gl)'

we can

~T it e

K[z*]-s tructure,

(1 + TXt) ·gl'

gl· This proves that

52 generates both Y and Z; that is,

a cyclic generator f or

X end owed

~~ th

proof of Lemma ( 5 . 18 ) is now complete.

the

K[z*]-structure.

is The

o

-

77 -

R. E. Kal ma n It should be clear that Theorem (5.13) is not a purely moduletheoretic result, but depends on the interplay between module theory, vector-spaces, and elimination theory (via (5.21)). the fact that

£

ca~

be extended from

For instance,

Y to X, which was needed

in the proof of Case 2, is a typical vector-space argument.** There are many open (or forgotten) results concerning cyclic modules which are of interest in system theory. is easy to show that an

n Xn

real matrix is cyclic iff a certain is nonzero at

~

For instance, it

is roughly analogous to the polynomial

det

,

F'

the polynomial

in the same ring,

but, unlike in the latter case, the general form of

~

does not seem

to be known. We must not terminate this discussion without pointing out another consequence of cyclicity which work.

Since

K[z]jXg K[z], co~~tative

X = cyclic with generator it is clear that

Xg

g

the module frame-

is isomorphic with

X also has the structure of this

ring, that is, the product is defined as

xXy If

tra~scends

(~Tj) 'g.

irreducible, then

X has a galois group.

No one has

tion of this galois group. facts in the theory of

X is even a field. eve~

Hence, in particular,

given a dynamical

interpret~-

In other words, there are obvious algebraic

dyr~nical

from the dynamical point of view.

systems which have never been examined For some related comments in the

setting of topological semi groups, see DAY and WALLACE [1967].

-

78 -

R. E. Kalman

6.

(6.0)

PREAMBLE.

TRANSFER FUNCTIONS

There has been a vigorous tradition in engineer-

ing (especially in electrical engineering in the United States during 1940-1960) that seeks to phrase all results of the theory of linear constant dynamical systems in the language of the Laplace transform. Textbooks in this area often try to motivate their biased point of view by claiming that "the Laplace transform reduces the analytical problem of solving a differential equation to an algebraic problem". When directed to a mathematician, such claims are highly misleading because the mathematical ideas of the Laplace transform are never in fact used.

The ideas which are

complex function theory:

actu~lly

used belong to classical

properties of rational functions, the

partial-fraction expansion, residue calculus, etc.

More importantly,

the word "algebraic" is used in engineering in an archaic sense and the actual (modern) algebraic content of engineering education and practice as related to linear sy stems

i~

very meager.

For

eXfu~ple,

the crucial concept of the transfer function is usually introduced via heuristic arguments based on linearity or "defined" purely formally as "the ratio of Laplace transforms of the output over the input". do the job

~~

To

and to recognize the transfer function as a natural

and purely algebraic gadget, requires a drastically new point of view, which is now at hand as the machinery set up in Sections 3-5. essential idea of our present treatment was first published in KALMAN [1965b l.

The

-

79 -

R. E. Kalman

The first purpose of this section i s to give an intrinsically algebraic definition of the transfer function associated with a discrete-time, constant, linear input/output map (see Definition (3.10)). Since the applications of transfer functions are standard, we shall not develop them in detail, but we do want to emphasize their role in relating the classical invariant factor theorem for polynomial matrices to the corresponding module theorem (4. 34). Consider an arbitrary

K[zl-homomorphism

(g) following Theorem (4.2)) . equivalent to the set

(f(e

j),

n~ r

f:

(see lemma

Then as a "mathematical object" i

1, ... , m,

e

j

f

is

defined by (4.6)),

since (6.1) (The scalar product on the right is that in the defined in Section 4.) power series in

z

-1

By definition of with vani shing

fir~t

r,

K[zl-module

each

term.

f(e .) J

r,

as

is a formal

We shall try to

represent these formal power series by ratios of polynomials (Which we shall call transfer functions~) and then we ca n replace formula (6.1) by a certain specially defined product of a ratio of polynomials by a polynomial .

Some algebraic sophistication will be needed to find the

correct rules of calculations.

These "rules" will consititute a

rigorous (and simple) version of Heaviside 's so-called "calculus". There are no conceptual complications of any sort.

(However, we are

dodging some difficulties by working solely in discrete-time.) *This entrenched terminology is rather unenlightening in the present algebraic context.

-

80 -

R. E. Kalman

X = n/kernel f be the state set of f regarded as f K[zl-module. We assume that X is a torsion module with nontrivial f Let

a

minimal polynomial

ljr.

=

ljr·f(e.)

(6.2)

J

Then, for each f(ljr·e.) J

=

j = 1,

ordinary product of the power series

no dot

O.

~([ljr.e.l) J

By definition of the module structure on

a (vector) polynomial.

•.. , m we have

r,

(6.2) means that the

f(e j )

by the polynomial

Hence (6.2) is equivalent to

ljr

is

(notation:

ordinary product) 1, ... , m.

!ntuit.i'y-e}:.y.:, we can solve this equat.Lon by writing

fee .) J

There are two vmys of making this idea rigorous. Method 1.

(6.3)

Define

=

f(e.) J

G./ljr J

as the formal division of

G.

by

1jr

Check that the coefficient of

ZO

is always

J

into ascending powers of O.

*(z-l)

Multiply both sides of (6.2 1 ) by

= z-nljr(z)

and

Q.(z-l) ~ z-nQ(z). J

Then

-1

Verify by computation

that the power series so obtained satisfies (6.2 1 ) Method 2.

z

.

z-m.

Write

~ E K[z-ll C K[[z-lJl

and (6.2 1 ) becomes (6.2")

~f( e .)

Moreover, the

J

O-th

coefficient of

~

is

1

(because of the convention

-

81 -

R.E. Kalman

W

that the leading coefficient of K[[z-l]]

is

1),

hence

t

is a unit in

and therefore

(6.3' )

f(e.) J

Note that tions of

(6.3) and (6.3')

f(e.),

give slightly different defini-

depending on whether we use a transfer function with

J

z

respect to the variable

or

in the engineering literature.) preferable.

actu~lly

z

-1

(Both notations have been used

For us the form~lisffi of Method 1 is

(The calculations of Method 1 can be reduced by Method 2

to the better-known calculations of the inverse in the ring

K[[z-l]].)

Summarizing, we have the easy but fundamental result:

(6.4)

EXIS~~CE

OF

TRP~SFER

correspondence beblcen polynomial

~Ihere

Q

yuNCTIONS.

K[ z j-homomorpht er,s

wand transfer function

j E KP[z], deg

den ominator of

Q

j <
There is a bijcctive f: n

~trices

and

->

I'

with minimal

of the type

W is the lea.st common

Z.

In many contexts, it is preferable to deal with the ponding to

f

rat.he r t.han \,ith

f

itself.

Zf

dim Zf /',.

W z

and conversely. dim f

fare well-

Thus, for instan ce,

~ dim X

f;

least common denominator of minimal polynomial of

corre s-

Because the cor r e sponde nce

is bijective, it is clear that all objects induced by defined also for

Zf

fZ'

Z,

-

82 -

R.E.Kalman

(6.5)

REMARK.

realization of

In view of Propositions (4.20-21), the natural

Z,

namely

D.

X = X z f, Z

well as completely observable. has caused a great confusion ,

is completely reachable as

Not having this fact available before 1960 Questions such as thoscresolved by Theorem (5.13)

tended to be attacked algorithmically, using special tricks amounting to elementary algebraic manipulations of elements of

Z.

Very few

theoretical results could be conclusively established by this route until the conceptual foundations of the theory of reachability and observability were developed. The preceding results may be restated as "rules" whereby the values of

f

may be computed using

Z.

We have in fact,

fern) = Z· rn,

(6.6)

wZ

multiply the polynomial matrix consisting of the numerators of Z with rn, reduce to minimaldegree polynomials modulo and then divide formally by W as in ~lethod 1 above.

*

We can also compute the entire output of the system E

Z

(that is,

all output values following the application of the first nonzero input value) by the rule

same as above, but do not reduce modulo

W.

In this second case, the output sequence will begin with a positive power of

z.

(The coefficients of the positive powers of

thrown away in the definition of

f

(see (3.7»

z

are

and in the definition

vhere

-

83 -

R. E. Kalman

r,

of the scalar product in for

X f

= n/kernel

in order to secure a simple formula

f.)

Many other applications of transfer functions may be found in KAl1~, FALB, and ARBIB [1969, Chapter 10, Section 10].

It is easy to show that the transfer function associated with

= (F,

the system L f

G, H)

is given by

Zf

= H(zI

- F)-lG.

(This is

just the formal Laplace transform computed from the constant version of (1.12) by setting

= zx(t).)

x(t + 1)

z

= d/dt

or from (1.17) by setting

Probably the simplest way of computing

Z

is

via the formula

6.8)

q

where

1/I

F

is the minimal polynomial of the matrix

script denotes the special polynomials defined in identity

(6.8)

deg .1/I, F and the super-

(5.5).

The matrix

follows at once from the classical scalar identity

[WEBER, 1898, §4]

ttl . ( L) (z - w) .L. zJ;; q-a, (w),

7T(Z) - 7T( w) upon setting

w

= F,

7T

J= l

= 1/IF'

q

deg 7T,

and invoking the Cayley-Hamilton theorem.

Much of classical linear system theory was concerned with computing Zr

In the modern context, this problem "factors" into first solving

the realization problem

f ~ L f

a~d

then applying formula

(6.8).

See

Sections 8 and 9. One of the mysterious features of Rule (6.6) (as contrasted with the conventional rule (6.7)) is the necessity of reducing mowllo The simplest way of understanding the importance of this

1/1.

-

84 -

R. E. Kalman

aspect of the problem is to show how to relate the module invariant factors occuring in the structure theorem (4 .34) to the classical facts concerning the invariant factors of a polynomial matrix. INVARIANT FACTOR THEOREM FOR MATRICES.

Let

P be a

matrix with elements in an arbitrary principal-ideal domain p

(6.10) where

A and

Bare

p X P

diag

IT

= rank

P.

The

II. 1

and

Rand

Then

m X m matrices (not necessarily det A, det B units in

<\' ..., "-q'

is unique (u p to units in q

R.

AlIB,

unique) with elements in

(6.11)

p Xm

with

0, ... , 0)

R) with

R,

II. E R 1

= 1, ... ,

i

whEe

are called the invariant factors of

and

q - 1,

P.

As anyone would expect, there is a correspondence between the module structure theorem (~.34) and the matrix structure theorem (6.9) and, in particular, between the respective invariant factors and

Ill' .•• , IIq.

t l'

... ,

Let us sketch the standard proof of this fact follow-

ing CURTIS and REINER [1962, §13.3] who also give a proof of (6.9). PROOF OF (4.34). onto

M given by

basis elements of M ~ RSjN,

Clearly,

~:

e.

Consider the R-h omomorphism from where the

H

1

m R (recall where

N

(4.6))

elements.

Write each basis element

1

and the

= kernel

is a free sutmodule of

e.

~.

are the standard gi

generate

M.

It can be proved that

with a basis of at most fj

Rm

of

N as

L Pij'e i,

.e < m Pij E R.

r

-

85 -

R.E.Ko.lman

(6.9)

Apply

to the R-matrix

= L aij·e i•

~j

P.

f j =L

f k = A.g i i'

(6.10-11),

~

Define

cij'fi,

C

= B-1,

Hence

Then, by "direct sum", M

~

Let

THEOREM.

given by

(6.9),

i

=r

r

o

r = rank P = ,e.

=0

..• , Aq be the invariant fact ors of

Xz

(\' W) = Qi'

Then the

are

wi \

Ccn c Lde'r the ;:[z]-~pimorphism

ill E [O]Z = kernel (mod

i = 1, ... , q.

for

CJ. = !'a;Jl: \jIZ.

m OO?

(WZ)ill

and

is the smallest integer su ch that

+ 1, . • . ,

Clearly,

'J.'

and let

invariant f a ctors of

where

~

the same type of calculations, we can prove also

(6.12)

wZ

r

(4.34) holds with W. = A.

That is, ~

R/AREIl

""

w).

I-l

iff

Z'ill = 0

(see

I-l:

n

-7

(6.6».

Xz:

ill

-7

[ill]Z'

Equivalently,

Using the representation whose existence is claimed

R. E. Kalman

86 -

by

(6.9),

write

-1

W = D !,

o/Z

Define

where diag (0/1' 1lr 2, ••• , t r , 1, ""

l'

M = 0, (1lrZ)W = 0,

Then

(C, J\ D = matrices over K[z].)

CAD

and W has clearly maximal rank among K[z]So the columns of the matrix W consti-

matrices with this property. tute a basis for

1).

kernel~.

The rest follows easily, as in the proof

of (4.34).

0

(6.13)

~~K.

The preceding proof remains correct, without any

modification, if the representation 1jrZ is taken in the ring

K[z]/o/K[z],

= CAD,

det C, det D

rather than in K[z].

= units

The former

representation follows trivially from the latter but may be easier to compute.

(6.14)

REMARK.

factors of Xz factors of

Theorem (6.12) shows how to compute the invariant

from those of 1j:Z.

must define the invariant

vIe

Z to be the same as those of X

z

bijective corre spondence

Z H

(because of the

Xz), Consistency with (6.12) demands

that we write

(6.15) where

Q.

1.

/

is defined as in

(6.3).

In other words, the -

the denominators of the scalar transfer function

A./o/ 1.

t.1.

are

a ~ ~~r cancellation

-

- -

of all common factors. Theorems (4.34) and (6.12) do not fully reveal the significance of invariant factors in dynamical systems. deduce all properties of

~trix-invariant

Nor is it convenient to factors from the representation

-

87 -

R. E. Kalman theorem (6.9).

It is interesting that the sharpened results we present

below are much in the spirit of the original work of WEIERSTRASS, H. J. S. SNITH, KRONECKER, FROBENIUS, and HENSEL, as summarized in the well-known monograph of (6 .16)

[1899].

~IDTH

DEFllUTION.

orization domain V, W (over

R,

R.

Let A, B rects.ngular matrices over a unique factAlB

(read:

A divides

of appropriate sizes)

B)

such that

iff there are matrices B

=

VAW.

This is of course just the usual definition of "divide" in a ring, specialized to the noncommutative ring of matrice s. The following result [~H 1899, Theorems IIIa-b, p. 52] shows that in case of principal-ideal domains the correspondence between matrices and their invariant factors preserves the divide relation (is "functcrial" with respect to "divide"): ( 6.17)

THEOREM.

if and O:lJ.y i f PROOF.

Let

R be a principal-ideal domain.

A. (A)I /,. (B) 1.

Sufficiency.

AlB

all .i .

Write the representation (6.10) as

B =

A

By hypothesis, there is a B

fc~

1.

Then

~

(diagonal) such that

V2~~W2'

V2ViiAVl~WlW~1~W2' (V2Vil)A(W~1~W2)·

~~ =~.

Hence

-

88 -

R. E. Kalman

Necessity.

(6.18)

LEMMA.

domain

R,

This is just the following

For an arbitrary

A. (A) I A. (B) •

A!B implies PROOF.

~~igue-factorization

l.

l.

By elementary determinant manipulations, as in

o

MUTH [1899, Theorem II, p, 16-17].

o

This completes the proof of Theorem (6.17)

(6.19)

REMARK.

Since (6.9) does not apply (why?) to unique factori-

zation domains, for purposes of using Lemma (6.18) we need WEIERSTRASS's if tJ..(A)

definition of invariant factors: all

j Xj

A. (A) = l.

minors of a matrix A,

c:l. (A)/tJ..l.- l(A).

=

J

greatest common factor of

with tJ. (A) o

= 1,

then

Of course, this definition can be shown to be

equivalent (over principal-ideal domains) to that implied by (6.9). In analogy with Definition (6.16), let us agree (note inversionl) on

(6.20) Zl'Z2

DEFINITION. (read:

such that

Zl

Zl

divides

= VZ 2W.

PROOF.

Let

Zl' Z2 be transfer-function matrices Z2)

(Note that

iff there are matrices Zl'Z2

This is the natural

V, ~1

implies at once:

cOlL~terpart

over

K[z]

*Z i*Z .) 1 2

of Theorem (6.16),

and follows from it by a simple calculation using the definition of ~i(Z)

given by (6.15).

o

-

89 -

R. E. Kalman

(6.22) iff

~ I~,

that is, iff XE

X E2

[or isomorphic to a quotient module of X ]. E 2

121

is isomorphic to a submodule of

This definition is also functorially related to the definition of "divide" over a principal ideal domain

R because of the following

standard result:

(6.23)

THEOREM.

R-modules.

Then

Let

R be a principal-ideal domain and

X, Y

Y is (isomorphic) to a submodule or quotient module

of X i f and only i f w.(Y)llJr.(x), ~ ~ PROOF.

1, • • •, r(Y)

i

Sufficiency.

< r(X).

Take both X and

Y in canonical

form

(4.34), with xl' ••• , Xr(X) generating the cyclic pieces of X,

and

Yl' ••• , Yr(X) (with

assignment

y.

~

is, exhibits assignment

H

Yi

=0

(lJr.(x)/v.(Y)}x. ~

~

1

if

Y as (isomorphic to) a submodule of X. xi

H

Yi

Necessity

and

Y.

The that

Similarly, the

defines an epimorphism X --+ Y exhibiting

Y as

X.

(follovring BOURBAKI [Algebre, Chapter 7 (2 e ed.),

4, Exercise 8]). Let Y be a submodule of X.

X ~ LIN where theorem,

those of

defines a monomorphism Y --+ X,

(isomorphic to) a quotient module of

Section

i > r(Y))

L, N are free R-modules.

By

(4.34),

By a classical isomorphism

Y is isomorphic to a quotient module

MIN,

where

M is free (since submodules of a free module are free).

L:J M :J N

-90-

R. E.Kalman From the last relation, that, for any R-module

r(Y) ~ reX). X and any

Now observe, again using (4.34)

7f E R,

and therefore ideal generated by Since

7fY

is a submodule of

R1I'k (X) J R!V (Y), k

7fX

(7f:

for all

< k},

r(7fX)

7f E R,

it follows that

and the proof is complete for the case when

a submodule of X.

Y is

The proof of the other case is similar.

o

(6.24) Immediate from the fact that

PROOF. of

E (see Section Now

(6.25)

is a submodule

7).

o

we can summa.rize main results of this section as the PRD-lE DECOMFOSITION THEOREM FOR LINEAR DYNAMICAL SYSTEMS.

The following conditions are e 0uivalent: (i)

Zl

~i(ZI)

(ii) (iii)

E Z

PROOF. (6.23), since

divides

1

Z2·

divides

~i(Z2)

can be simulated by

for all E

Z

2

i.

•

This follows by combining Theorem (6.21) with Theorem

~.(Z) J.

= ~J..(EZ)

by definition.

o

-

91 -

R.E.Kalman

INTERPRETATION.

(6.26)

The definition of Zl'Z2 means, in

syst~

theoretic terms, that the inputs and outputs of the machine whose transfer function is an input

Ul

2

Z2 are to be "recoded":

the original input

= B(z)wl

r 2 is replaced by an output

and the output

r 1 = A( z)r 2; with these "coding" operations, a machine with transfer function transfer function, the equation A, B are replaced by

A, B

Zl. Zl

L

Ul

2

is replaced by

wj.ll act like

2

In view of the definition of a

= AZ 2B

(reduced modulo

is

al~~ys

tz

2

).

satisfied whenever

This means that the

coding operations can be carried out physically given a delay of d = deg t

z2

units of' time (or more). No feedback is involved in coding,

it is merely necessary to store the

d

last elements of the input and

Hence, in view of Theorem (6.25) and Corollary (6.24),

output sequences.

we can say that it is possible to alter the dynamical behavior of a system L

2

arbitrarily by external coding involving delay but not

feedback if and only if the invariant factors of the desired external behavior

(Zl)

behavior

(ZL;)

called the

are divisors of invariant factors of the exter~al of the given system.

2 PRll~S

of linear systems:

The invariant factors may be they represent the atoms of system

behavior which cannot be simulated from smaller units using arbitrary but feedback-free coding.

In fact, there is a close (bot not isomorphic)

relationship between the Krohn-Rhodes primes of automata theory (see KAIMAN, FALE, and ARBIB [1969, Chapters 7-9]) and ours.

A full treat-

ment of this part of' linear system theory will be published elsewhere.

-

92

-

R. E. Kalman

7.

ABSTRACT THEORY OF REALIZATIONS

The purpose of this short section is to review and expand those portions of the previous discussion which are relevant to the detailed theory of realizations to be presented in Sections 8 and 9.

The same

issues are examined (from a different point of view) also in KALMAN, FALB, and ARBIE [1969]. Let

f:

n~ r

construction of

X f,

(Sections 3 and 4). I-l :

f

n

be a fixed input/output map.

->

as a set and as carrying a It is clear that

X : m f

(i) f

=

Let us recall the K[z]-module structure

Lfo~f'

where

[to},

H

'f: X ~ r: [m]f 4 f

f(m)

(ii)

are K[z]-homomorphisms, and

I-l

f

= epimorphism while

L

f

= mononorphi.sm.

We have also seen that

(7.1)

C'

'f

=

epimorphism monomorphism

<=> Xf

is completely reachable;

< > Xf

is completely observable.

These facts set up a "functor" between system-theoretic notions and algebra which characterize

X f

uniquely.

Consequently, it is desirable

to replace also our system-theoretic definition of a r 2alization (3.12) by a purely algebraic one: DEFINITION. is any factoriz ation

A realization of a f

Kl z j-homomor-phd sm f: n

that is, any commutative di8§ram

->

r

-

93 -

R. E. Kalman of

K[z]-homomorphisms.

The

module of the realization. co~letely

A

K[z]-module

X is called the state

realization is canonical iff it is

reachable and completely observable, that is,

surjective and

= P,

(or X

(7.3)

REMARK.

~

= f,

X

= n,

E

G, H) by

F:

~

X:

~

restricted to the submodule

G

H

ln'

It is clear that a realization in the sense of (3.12)

= (F, X

~

= lp).

L

can always be obtained from a realization given by (7.2). define

is

is injective.

A realization always exists because we can take f

~

x

In fact,

z·x,

H

followed by the projection Y

(w:

Iw]

H

Y(l).

lJ.

It is easily verified that these rules will define a system with f, x

= f.

Given any such E, X

=

it is also clear that the rules

J1:,

~: w ~ t~ F~tGEw(t), V:

x

l->

(~x, ~FEx, •••

define a factorization of

f.

Hence the correspondence between (3.12)

~ (7.2) is bijective.

The quickest way to exploit the algebraic consequences of our definition (7.2) is via the following arrow-theoretic fact:

-

94 -

R.E.Kalman

ZEIGER FILL-IN LEMMA. and

5

~

A, B, C, D be sets and ex,

s, r,

set maps for which the following diagram commutes: ex

4

>

B

./

./

r ./

VJi/

~

~

5

is surjective and

t3

./

C

If ex

./

./

;>

W D

5 . i s injective, there exists a unique set

corresponding to the dashed arrow which preserves commutativity.

This follows by straightforward "diagram-chasing", which proves at the same time the COROLLARY.

The claim of the lemma remains valid if "sets"

are replaced by "R-modules" and "set maps" by "R-homomorphisms". Applying the module version of the lemma twice, we get

(7.6)

PROPOSITION.

fixed

f:

Consider any two canonical realizations of a

the corresponding state-sets are isomorphic as K[z]-modyles.

Since every K[z]-module is automatically also a K-vector space, (7.6) shows that the two state sets are K-isomorphic, that is, have the same dimension as vector spaces.

The fact that they are also K[z]-isomorphic

implies, via Theorem (4.34), that they have the same invariant factors. We have already employed the convention that (in view of the bijection between

f

and l:f)' the invariant factors of

f

and X f

are to be

-

95 -

R. E. Kalman

identified.

In view of

(7.6),

this is now a general fact, not dependent

on the special construction used to get

(7.6)

x. f

We can therefore restate

as the

(7.7)

ISOHORPHISM THEOREM FOR CANONICAL REALIZATIONS.

canonical realizations of a fixed

f

Any two

have isomorphic state module s.

The state module of a canonical realization is uniquely characterized (up to isom orphism) by its invariant factors, which may be also viewed as those of

f.

A simple exercise proves also

(7.8)

PROPOSITION.

realization

f,

then

If

X is the state module of a canonical

dim X (as a vector space) is minimum in the

class of all realizations of

f.

This result has been used in some of the literature to justify the terminology "minimal realization" as equivalent to "canonical realization".

'-Ie shall see in Section 9 that the two notions are

not aD~Ys equivalent; we prefer to view (7.2) as the basic definition and

(7.8)

as a derived fact.

REMARK. claimed (4.24).

2 = (F, G, H)

(7.7)

Theorem

constitutes a proof of the previously

To be more explicit:

if

E

(F, G, H)

and

are two triples of matrices defining canonical realiza-

tions of the same

f,

then

space isomorphism A: X -)

(7.7)

X

implies the existence of a vector-

such that

-

96 -

R . E. Kalman F

(7.10)

'" G

AG,

1\

If we identify X and X then A is simply a basis change and it follows that the class of all matrix triples which are canonical realizations of a fixed grOUp over

f

is isomorphic with the general linear

X. The actual computation of a canonical realization, that is,

of the abstract Nerode equivalence classes

[m]f'

require a consider-

able amount of applied-mathematical machinery, which will be developed in the next section. a factorization of

The critical hypthesis is the existence of f

such that

expressed by saying that

f

dim X

<

(this is sometimes

00.

has finite rank.)

Given any such reali-

zation, it is possible to obtain a canonical one by a process of reduction.

(7.n)

More precisely, we have THEOREM.

Every realization of

f

with state module

X

contains a subquotient (a quotient of a submodule, or equivalently, a submodule of a quotient)

X* of X which is the state-module of

a canonical realization of

f.

PROOF.

The reachable states

X

r

of X and so are the unobservable states X*

R<

X/Xr

n Xo

is a subquotient of X.

X* is a canonical state-module for

f.

=

ima ge

a r e a submodule

X = kernel r , o

Hence

It f'o.l.Lows immediately that

[The proof may be visualized

via the following commutative diagram, where the canonical injections and projections.]

~

j

IS

and

pI s

are

o

-

97 -

R. E. Kalman

REMARK.

Since any subquotient of X is isomorphic to a

submodule (or a quotient module) of X, that

it follows from Theorem (6.23)

X can be state-state module of a realization only if ~i(f)l~i(X)

for all

i

(recall also Corollary (6.24)).

not enough since the

~i

This condition, however, is

are invariants of module isomorphisms and not

isomorphisms of the commutative diagram (7.2). The preceding discussion should be kept in mind to gain an overview of the algorithms to be developed in the next sections.

-

8.

98 -

R . E. Ka l m a n

CONSTRUCTION OF REALIZATIONS

Now we shall develop and generalize the basic algorithm, originally due to B. L. Ho (see HO and KALMAN [1966]), for computing a canonical E = (F, G, H)

realization

of a given input/output map f.

Most of

thp. discussion will be in the language of matrix algebra. Here and in Section 9 boldface capital letters*

Notations.

will

denote block matrices or sequences of matrices; finite block matrices will be denoted by small Greek subscripts on boldface capitals; the elements of such matrices will be denoted by ordinary capitals.

This

is intended to make the practical aspects of the computations selfevident; no further explanations will be made. Let

f:

n~ r

the K-linearity of

be a given, fixed K[z]-homomorphism. f

Using only

we have that

f(oo) (1)

(8.1) where the

~

(k > 0)

a re

p X m matrices over the fixed field

K.

We denote the totality of these matrices by

Then it is clear that the spe cification of a

K[z]-ho ~omorphism

is equivalent to the specification of its matrix sequence over, if L

(8.2)

reali zes

f(oo) (1)

*Note to Printer:

f

~ (f).

(8.1) can be written explicitly as

t~ HF-tChJ( t) .

=

Indicated by double underline.

f More-

-

99 -

R. E. Kalman

Comparing (8.1) and (8.2) we can translate (3.12) into an equivalent matrix-language DEFINITION. A dynamical system

~G,

realizes a

A iff the relation

(matrix) infinite seguence

~+l

L = (F, G, H)

0, 1, 2, ...

k

is satisfi ed, Let us now try to obtain sequence

A

also a matrix criterion for an infinite

to have a finite-dimensional realization.

The simplest

way to do that is to first write dO\{ll a matrix representation for the map f: n

->

r,

So let

r~l

A 2

R(A)

::: =

C

and verifY that ~

A 2 A 3 A4

A 3 A4 A 5

represents

~(~(f»

column vector ~~th elements

Classically, with A.

~(~)

... ,

when w E n

is ,~ewed as an

(wl(O), •.. , wm(o), Wl ( l ) , . .. ).

is known as the (infinite) Hankel matrix associated

We denote by

H

the

=~,v

~

ing in the upper left-hand corner of

(8.4)

f

X V block submatrix of H.

E be any realization of A.

PROPOSITION.

Let

rank ~~, v(~)

< dim

E

H appear-

for all

>1,

v > 1.

Then

-

100 -

R. E. Kalman

(8.5)

COROLLARY.

realization only if

An infinite sequence

rank

has a finite-dimensional

~

is constant for all

~~,V(~)

~, V sufficiently

large. PROOF.

If

dim

E

=

00,

the claim of the proposition is

vacuous (although formally correct!).

Assume therefo:e that

dim E <

00

E the finite block matrices

and define from ~V

[G, FG, ••• , F

V-l G ]

and

Then O'R

=~=V

=

by the definition

and

rank 0

=~

H

=~,

(A)

V =

(8.3) of a realization.

are at most

n

=

dim E.

I t is clear that

rank R

=V

Thus our claim is reduced to

the standard matrix fact rank (AB)

o

< min (rank A, rank B}.

Our next obj ective is the proof of the converse of the corollary. This can be done in several ways.

The original proof is due to HO and

similar results were obtained independently and and TISSI [1966] as well as by SILVE~~ [1966]. are analyzed and compared in Section 11].

KAh~,

FALB, and

~f

concurre~tly

[1966];

by YOULA

Two different proofs

JL~IB

[1969, Chapter 10,

All proofudepend on certain finiteness argument s.

We

shall give here a variant of the proof developed in HO and KALMAN [1 969].

-

101-

R. E. Kalman

(8.6)

DEFINITION.

the sequence

~

The infinite Hankel matrix H associated with A = (A', A")

has finite length

iff one of the follow-

ing two equivalent conditions holds: min {.e': rank

A" A'

(min

!!o, v =rank !io, v for all -~ , -~ +K,

.e": rarik!!-11,~0"

is the row length of H and

rank H 0"+K =j.4,~ A"

K,

for all

v

K,

1, 2,

... }

1, 2,

11

is the column length of H.

The equivalence of the two conditions is immediate from the equality of the row rank and column rank of a finite matrix.

The proof

of the following result (not needed in the sequel) is left for the reader as an exercise in familiarizing himself with the special pattern of the elements of a Hankel matrix: PROPOSITION. either both true

[~

For any has finite

g,

the following inequalities are

le~]

or both false [otherwise]:

< rank ~mA", A" < mA", A" < rank H pA', =71.' ,pA' < A'

The most direct consequence of the finiteness condition given by

(8.6) is the existence of a finite-dimensional representation Z of the shift operator

CIA

acting on a sequence

A.

will be the Hankel matrix associated with a given A.

~

and

The "operand" As we shall see

soon, this representation of the shift operator induces a rule for

< ee

.•• }<

co ,

-

102 -

R. E. Kalman

computing the matrix we would expect:

F of a realization of ~.

This is exactly what

module theory tells us that, loosely speaking,

DEFINITIOX~

The shift ope=ator

~A

on an infinite sequence

A is given by

the corresponding shift ouerator on Hankel matrices is then

(Of course,

~H

is well-defined also on submatrices of a Hankel matrix.)

(8.8)

MAIN LEMMA.

seguence

~

A Hankel matrix

H associated with an infinite

has finite length if and only if the shift operator

has finite-dimensional left and right matrix representations. H has finite length and

l" X £11

A = (A', A")

block matrices

Sand

and

f,.

(8.9) is

A" X A".

PROOF. which satisfies

Sufficiency.

Ta.1{e any

X £.

such that

and furthermore the minimum size of these matrices satisfying A' X A'

Precisely:

if and only if there exist Z

cr H

£11 X £tI

(8.9). Compute the last column of

block matrix ~J.l,£ "~:

Z

-

103 -

R. E. Kalman

(8.10)

= 0,

(where

j

of ~).

Relation (8.10) proves that

1, ...

Z

>Iv

rank ~K+l,£"

rank ~K+l,£"

(>I, v)th

is the

for all

for all

element block

0, 1, ...

K

the general case follows by repetition of the same argument. existence of the claimed

Z

cannot exceed the size of of the smallest

implies that the col umn length

Z.

If actually

Z which works in

the necessity part of the proof.

A"

Hence the A"

of

H

is smaller than the size

(8.9), we get a contradiction from

The claims concerning

S

are proved

by a strictly dual argument. Necessity. (A" + 1)

th

By the definition of

block column of

~>I, A"+l

exist

(8.U)

m X m matrices

Zl' .• . , ZA"

Aj+lZA" + Aj+2Z A"+l

holds identically for all

j

~>I,

= 0,

A"+l;

moreover, this

no matter how l arge.

So there

su ch that the relation

+ • • • + A O+' Z J "" 1

A" X A" block c ompanion mat r Lx of just defined:

>I,

each column of the

is linearly dependent on the

columns of the precedi ng block c olumns of property is true f or all intege rs

A",

1, ..••

=

A

JO+I+"'" 1\

Now define

Z t o be a n

m X m block made up from the

Zo ~

-

104 -

R. E. Ka lman

0

0

0

0

ZA"

I

0

0

0

Z""_l

0

I

0

0

Z""_2

o

o

o

o

o

o

o

I

Z

The verification of (8.9) is immediate, using (8.11) . of

A' X A'

block matrix

S

The existence

verifying (8.9) follows by a strictly

o

dual argument.

Now we have enough material on hand to prove the strong version of Corollary (8.12)

(8.5):

THEOREM.

An infinite s eguence

realization of dimension

n

if and only if the as sociated Hankel

matrix H has finite length PROOF.

A has a finite-dimensional

Sufficiency.

A=

o.I,

Let

A").

~AII, 1

be a

column matrix whose first block element is an the other blocks are

m X m zero matrices.

define

(8.13)

~AIl,l'

!!l -

1. 11 •

, F\

A" X 1

block

m X m unit matrix and

Using (8.9) with

.e"

=A",

-

105-

R. E. Kalman Then, for all

k

~

0,

comput ~

~l, A'l~A", l~ (J~l, A"~A", 1;

mXG

(8.9).

the second step uses

By definition of

(JA and ~, the last k ~«(JA(~))' namely A1+k'

matrix is just the

(1, l)th element of

Hence the given

is a realization of A.

E

Necessity.

This is immediate from Cor :

;a r y (8.5).

0

Now we want to attack the problem of finding a canonical realization of ~,

since the realization given by (8.13) is u~ually very far

from canoirl.cal.

Our succeeding consideratiorn here and in Section

9

are made more transparent if we digress for a moment to establish another consequence of

(8.8).

By outrageous abuse of language, we shall say that length iff (8.14) order ~

=

has finite length.

1i(~)

DEFINITION.

We note

An infinite sequence B is an extension of

N of (the initial part of) an infinite seguence B k

(8.15)

for

k

THEOREM.

= 1,

N of ~,

By

(8.8),

A iff

••• , N.

No infinite seauence of finite length

has distinct length-preserving extensions of any order PROOF.

A has finite

Suppose

(A', A")

N > A' + A".

B is a length-preserving extension of order

the length of both sequences being both sequences satisfy relation

(A', N'),

(8.9),

with

with suitable

N > A' + N'. ~ and

~B'

-

106-

R. E . Kalman

The sequence

A is uniquely determined by

from the left and the sequence acting on the matrix

N.

acting on

~AI, 7\"(~)

B is uniquely determined by from the right .

~A', A"(~)

are equal by hyp othesis on

~

~B

The two matrices

Moreover,

and

are also equal, since the matrices on the right-hand side depend only on the

2nd, •.• , N-th

member of ea ch sequence.

Using only this fact

and the associativity of the matrix product 11:-1

~AI, A"~~B ;:

So

'

k-l

~~AI, N'~B

'

o

B.

A

Now we can hope for a realization algorithm which uses only the first

A' + A"

terms of a sequence of finite length.

In fact, we have

(8.16)

B. L. HO' s REALIZATION AIDORITHM.

seguence

A of finite length with associated Hankel matrix

Consider any i nfinit e

following steps will lead to a canonical realization of

A:

H.

The

-

107 -

R . E. Kalman (i)

Determine

(ii)

Compute

nonsingular

pA'

X

pN

A', A". n = rank ~A'I A"; and

mA"

X'

mA"

in doing so, determine

matrices

P, Q su ch that

(8.17)

(iii)

(8.18)

Compute

Rn P!!" ,,,~, - /\ ,/\

G

H = are idempot ent "editing" matrices c orre spondi ng to the operations "r et a i n onl y the first

p

rows" and "retain only the first

m columns". We claim the (8.19)

REALIZATION THEOREl·! FOR INFINITE SEQUENCES.

seguence

~

(A', N'),

whos e a ssociat ed Hankel mat r i x

~

For any infinite

ha s f inite length

B. L. Ho's f or mula s (8.17-18) yi el d a canonical r ealization. PROOF.

If E

defined by (8.17-18 ) is a realization of ~,

then it is certainly cano ni ca l : the class of all realizations of

by ~

(8.4)

L

ha s minimal dimension in

and so it i s canonical by (7. 8) .

The required verification is int eresting. subscripts.

Observe that

l!

H

n

= QCRP

First, drop all

is a pseudo-inverse of

~,

that

-

108 -

R.E.Kalman is,

~~ =~.

Then, by definition of

~G

F, G, H,

II

.'m d

~,

(~Q.C)(RP[(J"r&]Q.C)k(~C),

~(~II[(J"~])~~C; by repeated application of (8.9),

~(~I1~)~~C ~~(~II~)k-~~C,

RS~~C,

~~C, R[(J"~]C. The last equation calls for picking out the first first (8.20)

m columns of COt~NT.

(J"~,

which is just

A+ l k,

p

rows and the

as required.

0

This is a considerably sharper result than Theorem

(8.12), in two respects: (i) use the matrix (ii) form:

It is no longer necessary to compute ~", , ,," «(J"At;;) ,

~:

we simply

which is part of the data of the problem.

Formulas (8.18) give the desired realization in minimal

there is no need to reduce (8.13) to a minimal realization (recall

here (7.11». Notice also that the proof of (8.19) does not re~uire (8.12) but depends (just like the latter) on direct use of (8.8).

-

109 -

R. E. Ka l ma n

An apparently serious limitation of the algorithm (8.16) is the

necessity to verify abstractly that

has finite length".

"~

Of

course, this can be done only on the basis of certain special hypotheses on ~'

given in advance.

(ii) ~

= coefficients

(Examples:

=0

(i) ~

for all

k > q;

of the T~lor expansion of a rational function.)

Fortunately, the difficulty is only apparent, for the preceding developments can be sharpened further: F1JNDA.MEN'rAL THEOREM OF LINEAR REALIZATION THEORY.

(8.21)

any infinite sequence

~

and the corresponding Hankel matrix H.

Suppose there exist integers (8.22)

1,1, 1,"

such that

rank

u., +,.r, 1 n,,(~), _

rank

~£ I, 1,"+1 q~) .

_.r,

'" of Then there exists unique extension A

such that with

A'

<

~=

1,1

i\' = 1, I, i\"

PROOF.

and

= 1,"

~

of order

I ,

1,1

+

1,"

moreover, applying formulas (8.17-18) gives a canonical realization of

A.

Exactly as in the necessity part of the proof of

(8.8), condition (8.22) implies the existence of ~

crJ£.e

Consider

1,11 (~)

'" of Define an extension A

~

of order

t

I

+ t"

k> 1.

by

and

Z such that

-

110-

R. E. Kalman By repeated application of (8.23), it follows that we have also

k > O.

Now i t is clear, from (8.8), that

A~

<

A""

£'

and

~

<

A""

£11.

ness of the extension follows immediately from (8.15). Theorem (8.19) is still valid, even though

(£', £11)

The uni.que-

Moreover, is not necessarily

minimal, because the proof of (8.19) depended only on (8.9) and not on theminimalityof

o

(£', £11).

Theorem (8.21) says, in effect, that a canonical realization of some extension of ~

is always possible as scon as (8.22) is satisfied.

Moreover, (8.22) can be used as a practical criterion for constructing by trial and error a canonical realization of any A known to have finite length (but without being given (8.24)

EXAMPLES.

(i)

A', A").

There is no scalar infinite seCJ.uence

(p

m "" 1)

A for which (8.22) is never satisfied.

(ii)

If ~£I,£11

is squar-e and has full rank (for instance,

in the scalar case), then (8.22) is automatically satisfied. (iii)

If the algorithm (8.16) is applied without any informa-

tion concerning condition (8.22), the system always realize some extension of

~,

E defined by (8.18) will

at least of order

1.

It is not

known, however', hO\'T to get a simple formula which would determine the maximal order of this extension of A. The remaining interesting CJ.uestion is then:

What can be said if

(8.22) is not satisfied for a finite amount of data

AI' ••• , ~

and

-

111 -

R.E.Kalman

any

£ I , t"

satisf'ying

£ I + £"

N.

This problem is the topic of

the next section.

(8.25)

FINAL COlt.l1Elf:'.

An essential feature of B. L.Ho's algorithm

is that is preserves the block structure of the data of the problem. course, one can obtain pa"allel r€'sults by treating

~£"£"

ordinary matrix, disregarding its block-Hankel structure. procedure requires looking at a minor of

~

Of

as an

Such a

of maximum rank, and was

described explicitly by SILVERl/AN [1966] and SILVERl'.AN and MEADOHS [1969]. There does not seem to be any obvious computational advantage associated with the second method.

-

112 -

R . E . Kalman

9.

THEORY OF PARTIAL REALIZATIONS

In one obvious r e sp ect the theory of realizati ons developed in the previous se ction is r ather un satisfactory : with infinite sequenc e s.

it is concerned

Fr om here on we cal l a sy stem satisfying

(8.3) a complete reali zation, t o di stinguish it from the practically more interest i ng ca se gi ven by DEFINITION. sequence of system A

Let

A = (A , A

=

1

2,

be an i nfi ni t e

••• )

K. A dynami cal

p x m matrice s ove r a fixed fi eld

2: = ( F, G, H)

is a partial realization of order

r

of

iff

~+l

~G for

k

0, 1,

...,

r•

We shall us e t he same ter :ninology if, Ln st.e a d of a n i nfinit e se quence s

~

r.

!';, we are given merely a f i nite s equence The re a son f or

t~i s

A

=s

convent ion will be cl ea r fr om the di s-

cussion to f ollow.

We sh all call the firs t

sequence (o f orde r

r).

r

terms of

A a partial

The con c epts of ca non ical par tial r eal ization a nd minima l partial reali za tion wi l l be under stood in exact ly the same sense as for a complet e reali zation .

We warn t he r ea der, bowever, that now the s e

two notions wi l l turn out t o be i nequivalent, in that minimal partial

=?

ca nonical partial

but not c onvers el y .

Our mai n intere st wi l l be t o determi ne a l l equivalence clas s es of mi nimal pa r t i al realizat i ons; i n gene ra l , a given sequence wi ll.

-

113 -

R. E. Kalman

have infinitely many inequivalent minimal partial r ealizations if r

is sufficiently small. According to the Main Theorem (8. 21) of the theory of realiza-

tions, the minimal partial realization problem has a unique solution whenever the rank condition (8.22) is satisfied.

If the length

r

of the

partial sequence is prescribed a pr i ori, it may well happen that (8. 22) does not hold.

vThat to do?

realization

(F, G, H)

sequence of

~r

Clearly, if we hav e a minimal partial

of order

r

we can extend the partial

on which this realization is based to an infinite

sequence ca noni ca l ly r ealized by

(F, G, H)

simply by setting

Consegu'ntly, we have the preliminary PROPOSITIor.. realization f or

~r

The

de ter~ inat io n

is e quivalent t o t he

extensions of a partial sequence

A

=:c

of a

mini ~~l

dete rminati ~n

partial of a l l

such t hat the extended

sequence i s (i) finite-dh ensj. =::?l .;:J.G, ,"ore st r ong' Y,

(ii) it" dimension is minimal in t he class of all ext.ensi.ons . It is trivial to prove that finite-d imensional exte nsi ons exi st for any pa rtial sequence ( of finit e length). reduced t o determining

extensi on~

Hence the problem i s

whi ch have mini mal dimen sion.

solution of this latter problem c onsists of t wo step s.

i ~e d i a tely

The

First, we show

by a trivial a r gument that the min imal dimensi on can be bounded fr om

-

114-

R.E.Kalman below by an examination of the Hankel array defined by the partial sequence.

Second, and this is rather surprising, we show that the

lower bound can be actually attained.

For further details, especially

the characterization of equivalence classes of the minimal partial realizations, see KALMAN [1969c and 1970b). DEFINITION.

By the Hankel array

sequence

~r we mean that

block is

A + j_ i l

if

r Xr

i + j - 1

of a partial

~ (Ar>

block Hankel matrix whose

~

r

(i, j)th

and undefined otherwise.

In other words, the Hankel array of a partial sequence

~r

consists of block rows and columns made up of subsequences Ap' ... , Ar

(1 ~ P ~ r)

above them.

~r

and blank spaces.

n (A )

b~ the number of rows of the o =r which are linearly independent of the rows

PROPOSITION. Hankel array of

of ~r

Then the dimension of a realization of A =r

is at least

n (A ). o =r

PROOF. sequence of ~,

~

The rank of

~

Hankel matrix of an infinite

is a lower bound on the dimension of

by Proposition

(8.4).

~

of

This implies "filling

~r'

in" the blank spaces in the Hankel array of =:l'"

~r'

is filled in, the rank of the resulting

=r

matrix is bounded from below by By

realization

By Proposition (9.2), it suffices

to consider a suitable extension

H(A)

~

Regardless of how r Xr

block Hankel

n (A ). o =r

o

the block symmetry of the Hankel matrix, we would expect

to be able to determine

n (A) o =r

by an analogous examination of the

-

115 -

R. E. Kalman

columns of the Hankel array of lower bound.

fir'

thereby obtaining the

This is indeed true.

~

We prefer not to give a direct

proof, since the result will follow as a corollary of the Main Theorem

(9.7).

The critical fact is given by the

MAIN LEMMA.

fir

For a partial seguence

~:

smallest integer such that for row of H(A) - - - = =r

k'> A'

every

is linearly dependent on the

rows above it. AJ'(A ) =r

smallest integer such that for column in the

k-th

k" > A"

every

block column of H(A) = =r

is linearly dependent on the columns to the left of it. Every partial sequence seguence

~

may be extended to an infinite

A in at least one way such that the condition n (A) o =r

for all

~

> A' (A ), v > A" (A ) =r =r

is satisfied. PROOF.

The existence of the numbers

It suffices to show, for arbitrary such a way that the numbers

A', A",

and

Consider the first row of Ar+l

n

r,

is trivial.

how to select

Ar+l

remain constant.

and examine in turn all the

first rows of the first, second, third, ••. ,

!! U ). - -r

o

A'. A"

ALth

block rows in

If the first row of the first block row is linearly depen-

dent on the rows above it (that is,

0), we fill in the first row

in

-

116-

R. E. Kalman

of Ar+l

using this linear dependence (that is, we make the first

row of Ar+l

all zeros).

This choice of the first row of Ar+l

will preserve linear dependencies for the first row of every block row below the second block row, by the definition of the Hankel pattern.

If the first row in the first block row is linearly

independent of those above (that is, contributes

I

to

n (A

o =r

we pass to the second block row ana repeat the procedure.

»,

Eventually

the first row of some block row will become linearly dependent on those above it, except when

A' = r; in that case, choose the first

row of Ar+l

to be linearly dependent of the first rows of

••• , A r•

Repeating this process for the second, third,

~,

of each block row*, eventually ing

At

or

Ar+l

rows

is determined without increas-

n. o

To complete the proof, we must show that the above definition of Ar+l

also preserves the value of

~~

That is, we must show

that no new independent columns are produced in the Hankel array of ~r

when Ar+l

is filled in.

that the definition of Ar+l rank H =r, I rank I]-r- 1 , 2

rank HI = ,r

This is verified immediately by noting implies the conditions

rank!! -r+I , l' rank ~r, 2'

rank ~2, r

rank ~l,r+l.

*Of course, ::0-., Li nea,r dep endence in t.he first step does :1Qt that the corresponding row of Ar+l will be ~ll zeros.

in~ly

o

-

117 -

R. E. Kalman

With

th~

a.id of this simple but subtle observation, the problem

is reduced to that covered by the V~in Theorem

(8.21) of Section 8. We have:

MAIN THEORD1 FOR MINIMAL PARTIAL REALIZATIONS.* be a partial sequence.

flr

Let

Then:

(i) Every minimal realization of ~r

has dimension

n (A ). o =r

(ii) All minimal realizations may be determined with the aid of B. L. Ho's formulas as given by Lemma (iii) If -is unique.

(8.17-18) vdth

r> A'(A ) + A"(A) = =r =r

there are extensions of

~r

then the minimal realization

~~ny

satiSfying

By the Main Lemma

minima'

r=alizcti~ns

o

So we can apply the

as

(9.6).

(9.5),

every partial sequence

has at least one infinite extension "hich preserves n.

A" = A"(A ) =r

(9.5).

Othen,ise there are ss

PROOF.

and

A', A"

~r

and

(8.21) of the preceding section.

It fo.l Lovs that the minimal partial realization is uni que if (the A' (A ) + A"(A ) + 1 Hankel matrix can be =r =r = =r =r filled in completely with the available data); in the contrary case, the

r

> At (A ) + A" (A )

minimal extensions will depend on the

mar~er

in which the matrices

Ar+l' •••, AA'+ 1\' have been determined (subject to the requirement

o

(9.6) ).

In view of the theorem, we are justified in calling the integer

A• =or *A similar result was obtained sDT.lutaneously and independently by T. Tether (Stanford dissertation, 19c9).

-

(9.8)

REMARK.

R.E.Kalman

118-

The essential point is that the quantities

no'

A', and AU are uniquely determined already from partial data, irrespective of the possible nonuniqueness of the minimal extensions of the partial sequence.

We warn, however, that this result does

not generalize to all invariants of the minimal realization. instance, one cannot determine from

For

how many cyclic pieces a

~r

minimal realization of A will have: some minimal realizations =r may be cyclic and others may not [KALMAN 1970b). Finally, let us note also a second consequence of the Main Theorem: COROLLARY.

Suppose

nl(~r)

columns of the Hankel array of ~r

no(~r))· Then

dim ~r

PROOF.

If

is the number of independent

(defined analogously with

= nl(~r)· "l(~r)

>

no(~r)

then, using the Main Theorem,

we get a contradiction to the fact that the rank of any Hankel matrix of an infinite sequence is lower bound f0r the dimension of any realization (Proposition to any

~Al+~~l

equal to

(8.4)). If

nl(~r)

<

no(~r)

we contradict the fact that rank

then extending ~r ~A"N'

is at least

o

n (A ).

o =r

In other words, the characteristic property of rank, that counting rank by row or column dependence yielcs identical results, is preserved even for incomplete Hankel arrays. It is useful to check a simple case which illustrates some of the technicalities of the proof of the Main Lemma. EXAMPLE. r X p,

where

The dimension of (0, 0, ... , 0, A)

p = rank A r

and

At = A"

= r,

is precisely

-

119 -

R. E. Kalman 10.

GENERAL THEORY OF OBSERVABILITY

In this concluding section, we wish to discuss the problem of observability in a rather general setting: linearity, at least in the beginning .

we will not assume

This is an ambitious program

and leads to many more problems than results.

Still, I think it is

interesting to give some indication of the difficulties which are conceptual as well as mathematical.

This discussion can also

serve as an introduction to very recent research [KALMAN 1969a, 1970a] on the observability problem in certain classes of nonlinear systems. The motivation for this section, as indeed for the whole theory of observability, stems from the writer's discovery [KALMAN 1960a) that the problem of (linear) statistical prediction and filtering can be formulated and r esolved very effectively by consistent use of dynamical concepts and methods, and that this whole theory is a strict dual of the theory of optimal control of linear systems with quadratic Lagrangian.

For those who are familiar with the standard

classical theory of statistical filtering (see, for instance, YAGLOM [1962]), we can summarize the situation very simply by saying that Wiener-Kolmogorov filter

+ theory of finite-dimensional linear dynamical systems Kalman filter. For the latter, the original papers are [KALMAN 1960a, 1963a] and [KAlMAN and BUey 1961).

-

120 -

R. E. Kalman The reade r int ere sted in further details and a

m ~dern

exposition is

referred especially t o the monograph of KALM.t'N [:1.969b). We shall exaoi ne here only one a spect of this theory (which does not involve a ny stochastic elements):

the strict formulation

of the "duality r;rinciple" between reachability and o'.Js er vabi lit y . This principle was f ormally stated f or the first time '.Jy KA~~N [1960c l, but the pertinent dis cu s sion in this paper is limited t o the linear case and is somewhat ad-hoc.

Aided by research progress since 19&1, it is

now possible t o develop a completely general approach to the "duality principle " .

We shall do thi s and, as a by-product, we shall obtain

a new and strictly deductive proof of the principle in the now classical linear case. We shall introduce a ge neral notion of the "dual" system, arid use it to replace the problem of observability by an equivalent problem of reachability.

In keeping with the point of view of the

earlier lectures, we shall view a sys t em i n terms of its input/output map f

and dualize

f

(rather than

L).

The constructibility

problem will not be of direct interest, since its theory is similar to that of the obs er vabi l i t y problem. Let

n, r

from then on. (k

be the sa me set s as defined in Section 4 and used We assume that both

nand

rare K-vector spaces

arbitrary fi eld) and recall the definiti on of the shift

ope rators

n and

Cf

Cf ~

!

both shift op erators by module structure on

n

on

z and

n

and

r

(see

(3.10)).

We denote

but ignore, until later, the r.

K[z)-

-

121 -

R . E. Kal m an

By a constant (not necessarily linear) input/output map f:

n

~r

we shall mean

~

map f

which commutes with the shift

dPerators, that is, z·(f(oo)).

f( z·oo)

Let us now formulate the general problem of this section:

(10.1)

PROB~l OF OBSERVABILITY.

its canoni cal realization after

= o.

t

~,

Given an input/output map f,

and an input sequence

Determine the state

x

the knowledge of the output sequence of

of ~

~

after

This problem cannot be solved in general: that the state set

since

Giving

00'

X f

of

f

at

v E n applied

o

t t

from

O.

To see this, recall

may be viewed as a set of functions

is Nerode-equivalent to

00

iff

v E n and the corresponding output sequence amount s to

giving various values of to the sequences

¢,

vI"

f(ooo.)(l) ZV

r

(namely those corresponding

+ v •• •, v, z v, z2 v, ••• ), r_ l'

and

it may happen that these substitutions do not yield enough values of the function

f(ooo·)(l)

to determine the function itself.

This

situation has been recognized for a long time in automata theory,

-

122 -

R. E. Kalman

where, in an almost self-explanatory terminology, one says that "l:

is initial-state determinable by an infinite multiple experiment

(possibly infinitely many diff=rent single experiment (single

v

VIS)

but not necessarily by a See MOORE (1956].

chosen at will)."

The problem is further complicated by the fact that it may make a difference whether or not we have a free choice of

v.

KALMAN,

FALB, and ARBIB (1969, Section 6.3)] give some related comments. A further difficulty inherent in the preceding discussion is that the problem is posed on a purely set-theoretic level and does not lend itself to the introduction of more refined structural assumptions.

We shall therefore reformulate the problem in such

a way as to focus attention on determining those properties of the initial state which can be

comput~d

from the combined knowledge of

the input and output sequence occurring after For simplicity, we shall fix the value of generality, since

f

resulting from

after

x

x

is not linear). t

0

t

O. V at . 0

(no loss of

Then the output sequence

is given simply as

f(ill) ,

where

(ill]f' We shall use the circumflex to denote certain classes of

functions from a set into the field

K.

class will be the class of all functions.

f An element

(all functions

r

of

r

For the moment, this Thus

I' --> K) •

is simply a "rule" (in practice, a computing

algorithm) which assisns to each possible output seqDtn~e Y

in

r

-

123 -

R. E. Kalman

a number in the field

K.

If y

resulted from the state

x

then

y(y)

Y(f(w))

(rof) (00)

" and, by definition of gives the value of a certain function in n the state, also the value of a certain function in

X.

This suggests

the DEFiNITION.

(10.2)

iff there is a

An element

y"x E?

~ E

X is

an c:se~vable costate

such that we have identically for all

ooEn

In other words, no matter what the initial state the value of ~

y"x

rule

at

x

x

=

[oolf

is,

can always be determined by applying the

to the output sequence

f(oo)

resulting from

x.

Note,

carefully, that this definition subsumes (i) a fixed choice of the class of functions denoted by the circumflex, and (ii) a fixed input sequence after

t

=

0

(here

v

=

0).

For certain purposes, it

may be necessary to generalize the definition in various ways (KALMAN 1970 al, but here we wish to avoid all unessential complications. According to Definition (10.2), we shall see that a system is COmpletely observable iff every costate is observable.

This agrees

with the point of view adopted earlier (see Section 4) in an ad-hoc fashion.

Also, the vague requirement to "determine

x"

used in

-

124 -

R. E . Kalman

(10.1) is now replaced by a precise notion which can be manipulated (via the actual definition of the circumflex) to express limitations on the algorithms that we may apply to the output sequence of the system. The requirement "every costate is observable" can be often replaced by a much simpler one.

For instance, if

X is a vector

space, it is enough to know that "every linear costate is observable" or even just that "every element of some dual basis is an observable costate"; if X is an algebraic variety, it is natural to interpret "complete observability" as "every element of the coordinate ring of X is an observable costate" [KALMAN 1970a]. We can now carry out a straightforward "dualization" of the

n ~r.

setup involved in the definitior. of the input/output map f:

First, we adopt (again with respect to a fixed interpretation of the circumflex) : DEFINITION.

The dual of an input/output map f:

n

~r

is the map

Note that

f

is well-defined, since the circumflex means the class

of all functions. As to the next step, we wish to prove that constancy is inherited under dualization. spift operator on obvious ones:

To do this, wo have to induce a definition of the rand

n.

The only possible definitions are the

-

125 -

R. E. Kalman

'" r

--+ '" r:

Both of these new shi f t operators will be den oted by

z

-1

The reason for this notation will become clear later. Now it is easy to verify:

(10.4)

PROPOSITION. PROOF.

f

is constant, so is

'" f.

We apply the definitions in suitable sequence:

fez -l·r)(w)

and so we see that

If

'" f

(z-l·r)(f(w))

(de t'. of

r),

Y(z.f(w))

(def. of

(ff'),

Y(f(z.w))

(f

f(r)(z. w)

(de r , of

r) ,

(z-l·1'(r))(w)

(def'. of

(fn),

c ommutes with

z

At this stage, we cannot as yet view

wheneve r

f

f

is constant),

does.

0

as the input/ output map

of a dynamical system because concatenation is not yet defined on and therefore

r

'"n "

is not yet a properly defi ned "input set".

In other words, it is necessary t o chec k that the notion of ti me i s also inherited under dualization. to be

po ~sible

In gen eral , this doe s not appe ar

wi t hout some str ong limitation on the cla s s

we shall look only at the simpl e s t

'"P.

Here

-

126 -

R. E. Kalman

HYPOTHESIS. finiteness condi t i on : such that for all

Every function

y

There is an integer

y, 0 E

r

satisfies the

ly"'l

(dependent on

in

y)

the condition

r

I, ••• ,

IrI

implies

Yeo).

r(y)

In other words, we assume that the value of each "y

at

y

is uniquely determined by some finite portion of the output sequence y.

Assuming (10.5), it is immediate that

f admits a concatenation

multiplication which corresponds (at least intuitively) to the usual

n:

one defined on (10.6)

We can now prove the expected theorem, which may be regarded as the precise form of the "duality" principle: THEOREM. map and

f

Let

its dual.

f

be an arbitrary constant input/output

Suppose further that (10. 5 ) holds.

each observable costate of

f

(relative to

may be viewed as a reachable state of '"f, PROOF.

r

induced by

f.

r

Then

satiSfYing (10.5))

and conversely.

First we determine the Nerode equivalence classes on By definition

-

127 -

R. E.Y.:alman

'"€ E P. '"

for all

Now "r is linear

f

the definition of

and

(!);

in fact, direct use of

(10.6) gives (50f)(W), wEn.

So rof

and

are equal as plements ~l

50f

same observable Gostate.

~:

chey define the

Tn fancier language, the assignment

{lo.B) is well defined and constitutes a bijection between the reachable states of '" f

and those costates of

f

which are observable

o

relative to the function class Thus ~o

hold.

(10.5) is a sufficient condition for Ghe

d~lity

principle

However, the fact that the canonical realization 0f '" f

is

completely reachable is not quite the same as saying that the canonical realization of

f

is completely observable because the latter depends

on the choice of

r

Moreover, Theorem

(10.7)

and therefore is not an intrinsic property of does not give any indicati~n how "big"

and it may certainly happen that the observability problem for ~~ch

more difficult than the reachability problem.

f.

X

is

f

f

is

These matters will

be illustrated later by some examples. Now we deduce the original form of the duality principle from Theorem

(10.7).

The essential point is that (10.5) holds automati-

cally as a result of linearity. New definition of the function class: the class of all K-linear ~xnctions.

let the circumflex denote

(All the underlyin~ bets with the

K-vector spaces, so the definition makes sense.)

-

128 -

R.E.Kalman The following facts are well known: PROPOSITION. K-vector spaces .

Let

*

denote duality in the sense of

Then:

r {).

(KP[[z-ll])*

n {).

(JCD'[ z])*

KP[z-ll,

JCD'[ [z l l.

Now we can state the (10.10)

MAIN THEOREM.

dimensional. (i)

Suppose

Suupose further that

f

PROOF.

f

f,

A

~

hence every costate of

The fact that

by Proposition (10.4).

r

Then:

K[z~ll-homomorphism

f,

isomorphic with the X f

is observable.

is K-linear implies, by (10.3),

(Caution:

K[zl-homomorphism

cannot be simplified.

are

f*

is K-linear; the constancy of

dual of the

K-linear duality.

and finite-dimensional.

The reachable states of

K-linear dual of X f;

that

is K-linear, con stant, finite-

is K-linear and constant, that is, a

(and therefore written~ f*) (ii)

f

f

f

always implies that of is not the K[zl-linear

and the construction given here

See Remark (4.26A).)

To prove the second part, we note that by Proposition (10. 9) Hypothesis (10.5) holds and thus map of a dynamical system. of

f*

are isomorphic with

f = f*

is a well-defined input/output

We must prove that the reachable states

X;,

the K-linear dual of X f•

amounts t o proving that the K-vector spac e of functions

This

-

129-

R. E. Kalman is isomorphic with the K-vector space

X;.

It suffices to prove

that the K-vector space generated by the K-linear functions (10.1l) is isomorphic with Then by

x f

0, 1, •••

i

= 0,

X;.

Suppose that, for fixed

and x,

j

1, ••• , m]

'"

every

A(x)

= O.

by definition of the Nerode equivalence relation induced

(recall here the discussion from Section

3).

X is f finite-dimensional by hypothesis, it follows from this property of

the functions

(A)

that they generate

X* f•

Since

Obviously,

din:

x;

=

so that everything is proved.

[J

In other terms, the fact that

f

with the appropriate definition of

A

is a

f

K[z-l]-homomorphism.

= K[z]-homomorphism

t

=-

k

Since (10.5) holds, we can interpret

due to input

Y

In fact, we have

y(y)

f(y)( m), (Yof)(w) , ~(f(Y)(-

k»(Wk).

the output of the dual

is given by the assignment

which is a linear function defined on the sequence.

together

implies that

in a system-theoretic 'iay, as follc~s:

system at

dim Xf'

k-th

term of the input

-

130 -

H.E.Kalman

(10.12) that

"f

REMARK.

It is essentially a consequence of Proposition (10.9)

turns out to be the same kind of algebraic object as

f.

Note,

however, that under duality the input and output terminals are interchanged and ~

t

is replaced by

-t

(hence

z

z -1) •

In terms of the pictorial definition of a system, this statement simply amounts to "reversing the directions of the arrows", which is the "right" way to define duality in the most general mathem~tical

context, namely in category theory.

We would expect

that the duality principles of system theory will eventually become a part of this very general

du~lity

theory.

yet because the correct categories to

b~

This has not happened

considered in the study of

dynamical systems have not yet been determined.

It is likely that

eventually many different categories wi]l have to be looked at in studying dynamical problems. We shall now present an example the previous results.

whi~h

should help to interpret

We emphasize, however, that the theory sketched

here is still in a very rudi.mentary form. (10.13)

EXAMPLE. x(t + 1)

y(t)

Consider the system

L

defined by

2x(t) + u(t), y(t)

=( 1

if

0;;

if

1/2 ~ x(t) < 1,

x(t) < 1/2,

x(t), t E ~;

-

131 -

R. E. Kalman

X = U = Y = ~ mod 1, i.e., the interval [0, 1).

with

be thought of as identified with 0 . ) x

We let

u(t)

o

1.

(1

= O.

is to

We view

through its binary representation or

It is clear from the definition of the sy stem that the output sequence due to any

If it.

x

x

is precisely

is irrational, infinitely many terms are needed to identify

Consequently, the

x's

lence classes induced by Relative to

are isomorphic with the Nerode equiva-

f[.

So [

cannot be reduced.

".... = functions", every co stat e of

f[

is

observable, provided that Hypothesis (10. 5) is not satisfied.

If

it is, then only those c ostates defined on fi xed-length rationals are observable (more precisely, these on a fixed finite subset of the not define a

dyn~ic al

functions which depend only .... gk(x)ls). Thus: either f does ~re

sy st em or not all co st ates are obse r vabl e .

Now let us replace the set

[0, 1)

by its inters ection

with the rationals .

It is clear that there is now a finite algorithm

for dete rmining

we simply apply the re sult s of partial realiza-

x:

tion theory of the previous se ction. problem is to express of polynomials in is rational.)

x

from

~2[2]--which

However,

x

(We take

K

= ~2

(gl(x), ••• , g2(x) 0

and the

as a ratio

i s always pos sible sinc e each

x

i s not "effecti vely computable" in the

-

132 -

R. E. Kalman

strict sense since there is no way of knowing when the algorithm has stopped. no

~

~(x)

rule

for all

In other words, given an arbitrary costate

,.,

y"

x

x.

such that the application of "y" x

to

On the other hand, substituting into

,.,

x

there exists

Yx gives

,.,

x

the

results of the partial-realization algorithm will give an approxi~tion to the value of

~(x)

which always converges in a finite

(but a priori unknown) number of steps as more values of the output sequen~e

are observed.

In short, the costate-determination algorithm

has certain pseudo-random elements in it and therefore cannot be described through the machinery of deterministic dynamical systems. (Is there some relation here to the conceptual difficulties of Quantum Mechanics?)

-

133 -

R. E. Kalman

11.

HISTORICAL COMMENTS

It is not an exaggeration to say that the entire theory of linear, constant (and here, discrete-time) dynamical systems can be viewed as a systematic development of the equivalent algebraic conditions (2.8) and (2.15). Of course, the use of modules (over

K[z])

to study a constant

square matrix (see (4.13)) has been " st andar d" since the 1920's under the influence of E. NOETHER and especially after the publication of the Modern Algebra of VAN DER WAERDEN. must be also quite old.

Condition (2.15), by itself,

For instance, GANTMAKHER [1959, Vol. 1, p. 203]

attributes to KRYLOV [1931] the idea of computing the characteristic polynomial of a square matrix A by choosing a random vector computing successively b, Ab,

A2b, ...

band

until linear dependence is

obtained, which yields the coefficients of det (zI - A). will succeed iff X is cyclic with generator A

g.)

(The method

However, the

merger of (4.13) with (2.15), which is the essential idea in the algebraic theory of linear systems, was done explicitly first in KALMAN [1965b]. We shall direct our remarks here mainly to the history of conditions (2.8) and (2.15) as related to controllability.

See also earlier

comments in KALMAN [1960c, pp , 481, 483, 484] and in KAWAN, HO, and NARENDRA [1963, pp. 210-212].

We will have to bear in mind that the

development of modern control theory cannot be separated from the development of the concept of controllability; moreover, the technological problems of the 1950's and even earlier had a major influence on the genesis of mathematical ideas (just as the latter have led to many new technological applications of control in the 1960's).

-

134 -

R.E. Kalman

The writer developed the mathematical definition of controllability with applications to control theory, during the first part of 1959. (Unpublished course notes at Johns Hopkins University, 1958/59.) first definitions were in the form of (2.17) and (2.3).

These

Formal presenta-

tions of the results were made in Mexico City (September, 1959, see KALMAN [1960b]), University of California at Berkeley (April, 1969, see KALMAN [1960d]), and Moskva (June, 1960, see KALMAN [1960c]), and in scientific lectures on many other concurrent occasions in the U.S.

As

far as the writer is aware, a conscious and explicit definition of controllability which combines a control-theoretic wording

~th

a

precise mathematical criterion was first given in the above references. There are of course many instances of similar ideas arising in related contexts.

Perhaps the comments below can be used as the starting point

of a more detailed examination of the situation in a seminar in the history of ideas. The following is the chain of the writer's own ideas culminating in the publications mentioned above: (1)

In KALMAN [1954] it is pointed out (using transform methods)

that continuous-time linear systems can be controlled by a linear discrete-time (sampled-data) controller in finite time.* *It is sometimes claimed in the mathematical literature of optimal control theory that this cannot be done with a linear system. This is false; the correct statement is "cannot be done with a linear controller producing control functions which are continuous (and not merely piecewise continuousl) in time." Such a restriction is completely 'irrelevant from the technological point of view. As a matter of fact, computer-controlled systems have been proposed and built for many years on the basis of linear, time-optimal control.

-

135-

R. E. Kalman

(2)

Transposing the result of KALMAN [1954] from transfer functions

to state variables, an algorithm was sketched for the solution of the discrete-time time-optimal control of systems with bounded control and linear continuous-time dynamics. (3)

[KALMAN, 1957]

As a popularization of the results of the preceding work, the

same technique was applied to give a general method for the design of linear sampled-data systems by

~~

and BERTRAM [1958].

Some background comments concerning these papers are appropriate: (1)

The ideas and method presented in KALMAN [1954] descend

directly from earlier (and very well known) engineering research on time-optimal control.

(The main references in KALMAN [1954] are:

McDONALD [1950], HOPKIN [1951], BOGNER and KAZDA [1954], as well as a research report included in

~~l

[1955].)

Although the results of

KALMAN [1954] on linear time-optimal control were considered to be new when published, it became clear later that similar ideas were at least implicit in OLDENBOURG and SARTORIUS [1951, §90, p. 219] and in TSYPKIN's work in the early 1950's.

The engineering idea of nonlinear time-optimal

control goes back, at least, to DOLL [1943] and to OLDENBURGER in 1944, although the latter's work was unfortunately not widely known before 1957. During the same time, there was much interest in the same problems in other countries; see, for instance, FELDBAUM [1953] and UTTLEY and HAMMOND [1953].

Mathematical work in these problems probably began with BUSHAW's

dissertation [1952] in which, to quote from

~·WL~

[1955, before equation

(40»), " ••• [it was] rigorously proved that the intuition which led to the formulation of the [engineering] theory [quoted above] was indeed correct."

TSIEN's survey [1 954] contains a lengthy account of this state

-

136 -

R.E.Kalman

of affairs and was ready by many• . We emphasize:

none of this

extensive literature contains even a hint of the algebraic considerations related to controllability. (2-3)

The critical insight gained and recorded in KAU~ [1957] is

the following:

the solution of the discrete-time time-optimal control

problem is equivalent to expressing the state as a linear combination of a certain vector sequence (related to control and dynamics) with coefficients bounded by 1

in absolute value, the coefficients being

the values of the optimal control sequence. of the first

n

The l inear independence

vectors of the sequence guarantees that every point

in a neighborhood of zero can be moved to the origin in at most

n

steps (hence the terminology of "complete controllability"); and the condition for this is identical with (2 .17) (stated in KALMAN [1 957] and KALMAN and BERTRAM [1958] only for the case

det F of 0

and m = 1).

A thorough discussion of these matters is found in KALMAN [1960c; see especially Theorem I, p. 485].

A serious conceptual error in KALMAN

[1957] occurred, however, in that complete controllability was not assumed, as a hypothesis for the existence of time-optimal control law, but an attempt was made to show that the controllability is almost always com.plete [Lem:na 1].

In fact, this lemma is true, with a small

technical modification in the condition.

Only much later did it become

clear (see the discussion of Theorem D in the Introduction), however, that a dynamical system is always completely controllable (in the nonconstant case, completely reachable) if it is derived from an external description. this difficulty, very

~sterious

in 1957, which led to the development

It was

-

137 -

R.E. Kalman Of a formal machinery for the definition of controllability during the next two years .

The changing point of view is already apparent in

KALMAN and BERTRAM [1958]; the unpublished paper promised there was delayed precisely because the algebraic machinery to prove Theorem D was out of reach in 1957-8.

Consult also the findings of the biblio-

grapher RUDOLF [1969].

IN

S~~Y:

under the stimulation of the engineering problems

of minimal-time optimal control, the researches begun by KALMAN [1954,

1957] and KAlilAN and BERTRAM [1958] eventually evolved intoiwhat has come to be called the mathematical theory of controllability (of linear systems). Beginning about 1955, Ind stimulated by the same engineering problems, FONTRYAGIN .and h i,s school in the USSR developed their mathematical theory of optimal control around the celebrated "Maximum Principle". mentioned

(They were well aware of the survey of TSIEN [1954] acove J and referenced it both in English and in the Russian

translation of 1956.)

We now know that ~ theory of control, regard-

less of its particular mathematical style, must contain ingredients related to controllability.

So it is interesting to examine how

explicitly the controllability condition appears in the work of PONTRYAGIN and related research. GAMKRELIDZE [1957, §2; 195e §lJ §2] calls the time optimal control problem associated with the system

(11.1)

dx/dt

Ax

+ bu(t)

-

138 -

R. E. Kalman "nondegenerate" iff subspace of (11.2)

n R •

b

is not contained in a proper A-invariant

He notes immediately that this is equivalent to

~ ) det ( b, Ab, ••. , An- [)

f.

(i.e., the special case of (2.8) for

0

m = 1).

He then proves:

in

the "degenerate" case the problem either reduces to a simpler one or the motion cannot be influenced by the control function

u(·).

~

this is very close to an explicit definition of controllability. However, in discussing the general case

m > 1,

GAMKRELIDZE [1958,

§3, Section 1] defines "nondegeneracy" of the system

=

dx/dt

Ax + Bu(t)

as the condition (11.4)

det (b., Ab., ••• , An-~.) ~

~

~

f.

0

for every column

b~

.

E B,

but he does not show that this generalized condition of "nondegeneracy" for (11.3) inherits the interesting characterization proved for "nondegeneracy" in the case of (11.1).

In fact, condition (11.4) is much too strong

to prove this; the correct condition is (2.8), that is, complete controllability.

In other w0rds, in GPJ~IDZE's work (11.4) plays

the role of a technical condition for eliminating "degener a cy" (actually, lack of uniqueness) from a particular optimal control problem and is not ; explicitly related to the more baEic notion of complete controllability. Neither GAMKRELIDZE nor PONTRYAGIN [1958] give an interpretation of (11.4) as a property of the dynamical system (11.3) , but employ (11.4) only in relation to the particular problem of time-optimal control.

See

-

139 -

R.E.Kalman also KALMAN [l960c, p. 484].

A siaular point of view is taken by

USALLE [1960]; he calls a dynamical system (11.3) satisfying (2.8) "proper" but then goes on to require (11.4) (to assure the uniqueness of the time-optimal controls) and calls such systems "normal". The assumption of some kind of "nondegeneracy" condition ·...as apparently unavoidable in the early phases of research on the timeoptimal control problem.

For example, ROSE [1953, pp . 39-58] examines

this problem for (11.1); by defining "nondegeneracy" [po 41] by a condition equivalent ot (11.2), he obtains most of GAMKRELIDZE's results in the special case when A has real eigenvalues [Theorem 12].

ROSE

uses determinants closely related to the now familiar lemmas in controllability theory but he, too, fails to formulate controllability as a concept independent of the time-optimal control problem. A similar situation exists in the calculus of variations.

The

so-called Caratheodory classes (after CARATHEODORY [1933]) correspond to a kind of classification of controllability properties of nonconstant systems.

In fact, the standard notion of a normal family of extremals

of the calculus of variations is closely related to condition (11.4), suitably generalized via (2.5) to nonconstant systems.*

Normality is

used in the calculus of variations mainly as a'hondegeneracy'condition. It is importan':. to note that the "nondegeneracy" condit loons employed in opt Ime.l c orrt r o., ",nd the calculus role of eliminating

annoyin~

01

var a.at a.ons play mainly the

;,echnicalities and simplifying proofs.

*The use of the word "normal" by IaSALLE [1960] t'or (.11.4) is only accidentally coincident with the earlier use of the "normal" in the calculus of variations.

-

140-

R. E. Kalman With suitable formulation, however, the basic results of time-optimal control theory continue to hold without the assumption of complete controllability.

The same is not true,

howeve~,

of the four kinds of

theorems mentioned in the Intorduction, and therefore these results are more relevant to the story of controllability than the time-optimal control discussed above. There is a considerable body of literature relevant to controllability theory which is quite independent of control theory.

For instance, the

treatment of a reachability condition in partial differential equations goes back at least to CHOW [1940] but perhaps it is fairer to attribute it to Caratheodory's well-known approach to entropy via the nonintegrability condition.

The current status of these ideas as related to

controllability is reviewed by WEISS [1969, Section 9].

An independent

and very explicit study of reachability is due to ROXIN [1960]; unfortunately, his examples were purely geometric and therefore the paper did r.ot help in clarifying the celebrated condition (2.8).

The

Wronskian determinant of the classical theory of ordinary differential equations with variable coefficients also has intersections with controllability theory, as pointed out recently with considerable success by SILVERMAN [1966].

Vany

problems in control theory were misunderstood

or even incorrectly solved before the advent of controllability theory. Some of these are mentioned in KALMAN [1963b, Section 9].

For relations

with automata theory, see ARBIB [1965]. Let us conclude by stating the writer's own current position as to the significance of controllability as a subject in mathematics:

-

141-

R. E. Kalman

(1)

Controllability is basically an algebraic concept.

(This

claim applies of course also to the nonlinear controllability results obtained via the Pfaffian method.) (2)

The historical development of controllability was heavily

influenced by the interest prevailing in the 1950·s in optimal control theory.

Ultimately, however, controllability is seen as a relatively

minor component of that theory .

(3)

Controllability as a conceptual tool is indispensable in

the discussion of the relationship between transfer functions and differential equations and in questiohs relating to the four theorems of the Introduction.

(4)

The chief current problem in controllability theory is the

extension to more elaborate algebraic structures. For a survey of the historical background of observability, which would take us too far afield here, the reader should consult KALMAN [1969b].

-

142 -

R. E. Kalman

12. Sec~ion

A:

REFERENCES

General References

M. A. ARBIB

A common framework for automata theory and control theory, SIAM J. Contr., 2:206-222. C. W. CURTIS and 1. REINER Representation Theory of Finite Groups and Associative Algebras, Interscience-Wiley. E. M. DAY and A. D. WALIACE [1967]

Multiplication induced in the state space of an act, Math. System Theory; 1:305-314.

C. A. DESOEH and P. VABAlYA [1967]

The minimal realization of a nonanticipative impulse response matrix, SIAM J. Appl. Math., 15:754-764.

E. G. GILBERT Controllability and observability in multivariable control systeffi3, SIAM J. ContrOl, 1:128-151. B. L. HO and R. E. KAIJlAN [1966]

Effective construction of linear state-variable models from input/output functions, Rege1ungstechnik, 14:545-548. The realization of linear, constant input/output maps, I. Complete realizations, SIAM J. Contr., to appear.

S. T. HU [1965 ]

Elements of Modern Algebra, Holden-Day.

R. E. KALMAN

[1960a]

A new approach to linear filtering and prediction problems, J. Basic Engr. (Trans. ASME), 82D:35-45.

[1960b]

Contributions to the theory of optimal control, Bol. Soc. Mat. Mexicana, L:I02-119.

-

[1960c]

143 -

On the general theory of control systems, Proc. 1st IFAC Congress, Moscow; Butterworths, London. Canonical structure of linear dynamical systems, Proc. Nat. Acad. of Sci. (USA), 48:596-600. New methods in Wiener filtering theory, Proc. 1st Symp. on Engineering Applications of Random Function Theory and Probability, Purdue University, November 1960, pp 270-388, Wiley. (Abridged from RIAS Technical Report 61-1.)

[1963b]

Mathematical description of linear dynamical systems, SIAM J. Contr., 1:152-192.

[1965a]

Irreducible realizations and the degree of a rational matrix, SIAM J. Contr., 13:520-544. Algebraic structure of linear dynamical systems. I. The Module of E, Proc. Nat. Acad. Sci. (USA), 54:1503-1508.

[1967]

[1969a]

On multilinear machines, J. Compo and System Sci., to appear.

[1969b]

pynamic Prediction and Filtering Theory, Springer, to appear.

[1969c]

On partial realizations of a linear input/output map, Guillemin Anniversary Volume, Holt, Winston and Rinehart.

[1970a]

Observability in multilinear systems, to appear.

[1970b]

The realization of linear, constant, input/output maps. II. Partial realizations, SIAM J. Control, to appear.

R. E. KAWAN and R. S. BUCY

New results in linear prediction and filtering theory, J. Basic Engr. (Trans. ASME, Sere D), 83D:95-100. R. E. KALMAN, P. L. FALB and M. A. ARBIB Topics in

~~thematical

System Theory, McGraw-Hill.

R. E. KALMAN, Y. C. HO and K. NARENDRA [1963]

Controllability of linear dynamical systems, Contr. to Diff. Equations, 1:189-213.

C. E. LANGENHOP

[1964]

On the stabilization of linear systems, Proc. Am. Soc., 15:735-742.

~~th.

-

S. LANG

[1965]

144

R. E. Kalman

Algebra, Addison-Wesley.

S. MAC LANE

[1963]

Homology, Springer.

L. A. MARKUS

[1965 ]

Controllability of nonlinear processes, SIAM J. Control, J:78-9O.

E. F. MOORE [1956]

Gedanken-experiments on sequential machines, in Automata Studies, C. E. Shannon and J. McCarthy (eds.), pp. 129-153, Princeton University Press.

P. MUTH [1899]

Theorie und Anwendung der Elementarthei1er, Teubner, Leipzig.

A. NERODE [1958]

Linear automaton transformations, Proc. Amer. Math. Soc.,

2:5 41-544 .

L. SILVERMAN [1966]

Representation and realization of time-variable linear systems, Doctoral dissertation, Columbia University.

L. M. SILVERMAN and H. E. MEADOWS Equivalent realizations of linear systems, J. Control, to appear. H.

S~l

WEBER [1898]

Lehrbuch der Algebra, Vol. 1, 2nd Edition, reprinted by Chelsea, New York.

L. WEISS Lectures on Controllability and Observability, C.I.M.E . Seminar. L. WEISS and R. E. KALMAN [1965 ]

Contributions to linear system theory, Intern. J. Engr. ScL, J:141-171.

W. M. WONHAM [1967]

On pole assignment in multi-input controllable linear systems, IEEE Trans. Auto. Contr., AC-12:6oo-665.

-

145 -

A. M. YAGLOM

An Introduction to the Theory of Stationary Random Functions, Prentice-Hall.

D. C. YOUIA

[1966]

The synthesis of linear dynamical systems from prescribed weighting patterns, SIAM J. Appl. Math., 14:527-549.

D. C. YOUIA and P. TISSI

[1966]

n-port synthesis via reactance extraction, Part I, IEEE Intern. Convention Record.

O. ZARISKI and P. SAMUEL [1958]

Commutative Algebra, Vol. 1, Van Nostrand.

-

Section B:

146-

References for Section 11

M. A. ARBIB

A common framework for automata theory and control theory, ~IAM.J. Contr., 1:206-222. I. BOGNER and L. F. KAZDA

[1954 ]

An investigation of the switching criteria for higher order contactor servomechanisms, Trans. AlEE, 11 11:118-127.

D. W. BUSHAW Differential equations with a discontinuous forcing term, doctoral dissertation, Princeton University.

[1952]

C. CARATHEODORY [1933 ]

Uber die Einteilung der Variationsprobleme von Lagrange nach Klassen, Comm, Mat. Relv., 2:1-19.

W. L. CHCM

[1940]

Uber Systeme von linearen partiellen Differentialgleichungen erster Ordnung, Math. Annalen, :98-105.

H. G. DOLL

[ 1943]

Automatic control system for vehicles, US Patent 2,463,362.

A. A. FELDBAUM

[1953 ]

Avtomatika i Telemekhanika, 14 :712-728.

R. V. <W-lKRELIDZE the theory of optimal processes in linear systems (in Russian), Dokl. Akad. Nauk SSSR, 116:9-11.

[1957]

On

[1958]

The theory of optimal processes in linear systems (in Russian), Izvestia Akad. Nauk SSSR, ~:449-474.

F. R. GANTMAKHER

[1959]

The Theory of Matrices, 2 vols., Chelsea.

-

147 -

A. M. HOPKIN [1951]

A phase-plane approach to the compensation of saturating servomechanisms, Trans. AlEE, 70:631-639.

R. E. KALMAN

[1954 ]

D~scussion of a paper by Bergen and Ragazzini, Trans. AIEE, 73 II: 245-246.

[1955]

Analysis and design principles of second and higherorder saturating servomechanisms, Trans. AIEE, 74 II:29h-3l0.

[ 1957]

Optimal nonlinear control of saturating systems by intermittent control, IRE WESCON Convention Record, 1, IV:130-135.

[1960b]

Contributions to the theory of optimal control, Bol. Soc. ~~t. Mexicana, 1:102-119.

[1960c]

On the general theory of control systems, Froc. 1st IFAC Congress, Moscow; Butterworths, London. Lecture notes on control system theory (by M. Athans and G. Lendaris), Univ. of Calif. at Berkeley.

[1963b]

NathemaUcal description of linear dynamical systems, SIAM J. Contr., 1,:152-192.

[1965b]

Algebraic structure of linear dynamical systems. I. The Module of E, Proc. Nat. Acad. Sci. (USA), 54:15 03-1508 .

[1969b]

Dyna~ic

Prediction and Filtering Theory, Springer, to app ear.

R. E. YJ\l1:A1J and J. E BERTRAM

[195 8 ]

R. E. KALllAN, [1963]

General synthesi s procedure f or computer control of single and ~ulti-loop linear systems, Trans, ALEE, TI 11 I: t<'2-6 09 . Y.

C.

HO

and

K.

NA_ttENDRA

Cont ro L'lab i ld ty of linear dynamical systems, Contr. to Diff. Equations, 1,:189-213.

-

148 -

A. N. KRYLOV

On the numerical solution of the equation by which the frequency of small oscillations is determined in technical problems (in Russian), I~v. Akad. Nauk SSSR Ser. ~ix.-Mat., ~:491-539.

[1931]

J. P. LaSALLE

The time-optimal control problem, Contr. Nonlinear Oscillations, Vol. 5, Princeton Univ. Press.

[1960] D. C. McDONALD

Nonlinear techniques for improving servo performance, Proc. Nat. Electronics Conf. (USA), ~:400-421.

[1950]

R. C. OLDENBOURG and H. SARTORIUS Dynamik selbstattiger Regelungen, 2nd edition, Oldenbourg, Munchen.

[1951]

R. OLDENBURGER [1957]

Optimum nonlinear control, Trans. ASME, 12.:527-546.

[1966]

Optimal and Self-Optimizing Control, MIT Press.

L. S. FONTRYAGIN

[1958]

Optimal control processes (in Russian), Uspekhi Mat. Nauk, 14:3-20.

N. J. ROSE Theoretical aspects of limit control, Report 459, Stevens Institute of Tech., Hoboken, N. J.

[1953 ] E. ROXIN

[1960]

Reachable zones in autonomous differential systems, Bol. Soc. Mat. Mexicana, 2:125-135.

K. E. RUDOLF

[1969]

On some unpublished works of R. E. Kalman, not to be unpublished.

-

149 -

H. S. TSIEN

[19541

Engineering Cybernetics, McGraw-Hill.

A. M. UTTLEY and P. H. HAMMON!)

[19531 L.

The stabilization of on-off controlled servomechanisms, in Aut Gmatic and Manua] Control, Ac ~dernic Press.

WEISS

Lectuces on eontrollability and Observability, C:I.M.E. Seminar

CENTRO INTERNAZIONALE MATEMATICO ESTIVO (C .I.M.E.)

R. KULIKOWSKI

CONTROLLABILITY AlI:D OPTIMUM CON T RO L

C O l'S 0

t en u t

0

a

S a ss

0

M a r .: 0 n i

d .a 1 1

a1 9

lu g I i

0

19 E8

-

153-

CONTROLLABILITY AND OPTIMUM CONTROL by R. Kulikowski (Polish Academy of Sciences , Warszawa) 1. Introduction

and

Statement

of the

Problem

The intuitive notion of controllability of dynamic systems had been used for many years by control-engineers. In the case of linear stable systems, described by eqs , x = Ax + Bu

(1)

= Cx

y

(2)

,

where x = n-dimensional state-vector, u = r-dimensional control-vector, y = p-dimensional output-vector, A, B, C - matrices of the dimensions n x n, n x r, p x n,

respectively,

that notion has been formulated strictly by Kalman (see Ref. According to Kalman the system S, described

by (1), (2)

trollable if and only if: given that the system is in state then for some finite time that

T

>0

there is a control

x

o

is con-

at time t=O,

u(t), t €

[0,

T] such

x(T) = O. He has proved also that

column

Q

where

n- 1 B, ... , A

a"

S.

of

S

is

controllable if and only if the

vectors of the matrix

(3)

That

t':::,.

[B, AB,

... , A n-1

denote columns

B

means that

the rank of

there is a set n which constitute a basis for R nr

[2, 3J ) .

columns

of

Q

.,

BJ of

Q,

span the state space

Q

is

n

of n

S

among

l inear-Iy independent vectors

In control theory the notion of optimal being used. The system

or that

is optimally (time)

(time)

control is

also

controlled if there exists

-

154-

R. Kulikowski

the control function trol-set T te

(usually a convex r-dimensional

required for x

the transition

to the given final state

o

Using the well [8J),

u{t) E U, where

U

is an

polyhedron)

admissible consuch that the time

of state variables from the given initial stax{T)

(e. g.

x{T) = 0) is minimum.

known "maximum principle" of Pontryagin (see R ef.

or an equivalent optimization technique, it ; s possible to formulate

the necessary condition of optimality for system S.

That condition can be

written in the form of linear differential equations and it can be used for derivation of optimum control function others

u{t). As shown by Pontryagin and

(Ref. \:8]) the necessary condition of optimality becomes also suffi-

cient when the system is controllable. Besides, the optimum control exists and it is unique. Then the notion of c o n t r-ollarul ity has an important th eoretical and practical value. It determines conditions under which the optimum control of a linear system is generally possible.

Roughl y speak ing a controllable system is the system in which the state of

variables

can be

driven to

any pos ition with

a finite value

performance measure and an optimally controllable s ystem is

system in which the

system in which

the

the state variables can be driven to

the given position with a minimum value of performance measure. In the case of the linear systems and optimization time as

the performance measure

the controllable system can be optimally controlled.

Is

that also true if

we take as performance measure the other possible performance criteria? A

simple example will show that the answer to that question is negative. Consider the first-order system described by the eq . dx/ dt

= u(t) ,

x{O)

=0

-

155-

R. Kulikowski

Assume

that

the control force u(t)

is generated by the control 2 ler having finite energy, what can be wr itten as u ~ L [0, T]. As the performance measure we assume the so called 2

lIy_xll

E(u)

=

j

[y(t)

o where

y(t) is

"square error":

T

T

~

,2

u(?:) d1:'.;

dt,

o

a given square-integrable function.

The necessary condition of optimality

requires that

t

y(t)

fU('t')d~,tE[O,TJ.

o When that condition holds the functional bound:

E(u)

E(u)

attains its lower

= O.

Assuming timum value of

that

u(t)

y(t)

= I(t) (a unit step) we find easily that the op-

is Dirac's

b (t)

function.

However, that fun ction is

not square- integrable and the optimum solution of our optimization problem does not exist desp ite the fact that the finite evergy solutions "approximating"

~

(t) exist.

Obviously the difficulties of the present type arise in the case when some sufficient conditions of optimality (such as the generalized Weierstrass theorem)

for nonlinear functionals do not hold . In the present paper we shall deal with a "well defined" class of

optimalization problems for which the optimum control exists and an optimally controlled system is also a controllable system (at least in certain of state space). It will be use gull to introduce the following definition.

We shall say that a 'system is optimally controllable if the system state-variables can be derive to any (given) position with minimum value of the performance measure and the system constraints

are not violated.

-

156-

R. Kulikowski We shall ti ons of

strive to find c o nd iti o ns under which the optimum solu -

concrete optimization probl ems exist and to determine the regions

of controllability in the space of system and constraint parameters. We shall be interested mainly in complex optimalization problems including energy and amplitude inequality constraints, constraints of phase c o o r d i na t e s , nonlinear systems etc. Dealing with that cl ass of problems it is convenient to employ a few simple notions of functional analysis. Then the main optim ization problem which is investigated in the present paper can be formulated as follows. Let a nonlinear functional be given. Find the point

x£ X

F(x) . x € X o

X is a Banach space)

such that max

(4)

(where

F(x)

xEn

ncX

where

is the set of feasible solutions, specified by

2. 0

G(x)

(5)

where

is a nonlinear operator

G

space). It is also assumed that

F

the condition

(G : X and

G

-t

Z

and Z

is another Banach

are concave and strongly

differentiable. In the most practical applications the assumption that Z

are Banach spaces (i. e.

X

the linear, normed and complete

and spa ces).

hold s • In particular w e shall deal with the space of all continuous funct ions C [0, T] , and with the space of all p-power integrable fun ctions L P [0 , T], P ? 1 . In since

G

function

these is

an

cases the element

x is a function

operator the element

of tim e (z(t)). The in equality

nonnegative for a ll

t I: [0 , T]

all te-ro, T] - in the case We shall wr it e

also

z = G(x),

of time (x(t)) and z € Z

is

another

(5) means that the values

- in the cas e

Z:::C

zit) are

, and for almost

Z ~LP . z >if 1'" z 2

z l - z 2 ). O.

The inequal ities d efi-

ned in s uc h a wa y have the kn own prop erties o f inequalit ies for numb ers

-

157-

R. Kulik owski

(i. e . o ne can multiply them by non negati ve numbers, sum them up and pass

to th e limits on both sides). c o nv e x, closed cone

(i. e.

Generally, one can say that

Z

the set closed with respect to the multiplication

by real nonnegative numbers). The closed c o ne induces in -order relation denoted by the sign

a(t)

where

a(t),

form (5) if

b(t)

~

Z a partial-

~

One should observe that the c o n s t r a i nt (6)

includes a

of the form

x(t):S b(t) ,

= given functions, can be represented in the general

we introduce the operators: G (x) = x - a , 1

G (x ) = b - x , 2

and writ e

Us ing that notation we assume that for an ordered pair

..-: z 1 lities

J

z2 >

zl 2: 0,

the inequality

z2 :::: O.

z ;;: 0

=

Z

is equivalent to

=

is equivalent to the pair of inequa-

In the similar way for the Z

the inequal ity

z20

Z

n

n

ordered set

>

zi 2: 0, i = I, •.• , n •

The space of all ordered pairs is c a lle d the Cartesian product of

< zl' z2 > , where ZI and

Z2'

zl€ZI

and

It is denoted by

• In t.he abo ve m ention ed e xa m ple the domain and range of operators is

X

(i. e. G

: X ~X, G X~X) and G(x) E Z = XxX . 2: 1 It should be noted th at if for a function x two ine qua lity cons t r a int s h old a nd G (x ) < 0 , o -

-158 -

R. Kul ikow s ki

then the equality constraint

G (x) = 0 is also valid. Then the equality o constraint is a special case of (5), where G(x) = < G (x}, - G (x) > .

o

As can be seen the constraint

0

(5) may also express the equality

or inequality constraints imposed on the state and output coordinates of a dynamic system (1),

(2).

In order to obtain an explicite relation of that type one may integrate eq. (1) and express the state and output coordinates as a Volterra operator of control vector. The functional x

may describe the control

F

cost. If, for example,

denotes a vector-function, with components:

the energy cost of control forces is proportional to

T

r

o

i=1

T

r

S L.

[u.(t)] 2 dt

,

1

and

(7)

F(x)= -

J ., o

[uP)]

2 dt.

i=1

In the present case the optimization time

T is fixed.

seen later it will be also possible to solve problems in

which

As can be T

is m i-

ni m i z ed ,

Before we formulate the sufficient and necessary cond it ion s of optimality it is necessary to introduce the notion of weak and strong differentials. Then a method based on the notion of Lagrange-functional will be presented. Hurwicz

[IJ

General idea of that method is based on the paper of

L.

dealing with nonlinear programming in topological spaces.

As shown in Ref.

[4,

5, 7J

found to be very useful

the method of Lagrange-functionals has been

in the solution of optimization problems with

-

159-

R. Kulikowski

operator inequality constraints.

Let spaces,

G(x) be a nonlinear operator G: X

and x, h be elements of X. The operator

r e nt iaol e

Y, where

X, Yare Banach

G is called weakly diffe-

if the limit 1 ' -\G(x+ fh)-G(x) }

lim

(1)

=dG(x,h) ,

YL

;r-+o where

~

is a number, exists.

~

The differential dG(x, h) is a homogeneous operator with respect to h, i , e. dG(x,

r h)

r. dG(x, h) .

=

When dG(x, h) exists and is continuous at

it is also an additive operator

(see Ref.

x

[9J ).

As an example find the weak differential of the operator T

J K[t, t' ,

G(x)

(2)

He[o, T] ,

x( 7:)] dC',

U

where the functions with

respect to We

(3)

K' [t, T, x] = ~ K[t, L, x] x ox and xEX.

K [t, 1:, x],

t,1'E[O, T]

are continuous

get formally

d G(x, h) = dG{x + "t h) d

r

IJ

T =0

K~ [t,

f

1;' ,

X(7:")] h(-r-) d T

•

°

Since the function K is uniformly continuous the differentiation the integral

sign

under

is admissible.

Besides the weak differential the strong (or Frechet) differential is also being used. If at the point

we have

G(x + h) - G(x) = dG(x, h) + r2(x, h) ,

(4)

where

X€X

dG(x, h)

is a

linear operator with respect to hEX

and

-160 -

R. Kulikowski II

lim

nix, h)/i

we call

dG(x, h) When

Y,

o

II h II

iJ hI/ -+ 0

the strong differential of

dG(x, h)

G(x)

is a linear operator acting from the space

it is also an element of the Banach space

from

X

into

Y

by

into

of all linear operators acting

and it is called the derivative of G(x)

Denoting that operator

X

at

x.

the point

G'(x) we can write d(G(x, h)

(5)

= G'(x)(h)

In that formula G'(x) is an operator acting on the element hEX . As follows from the definition of strong differential if it exists it is equal to the weak differential. It is possible to show (see Ref.

(9])

that the continuity and existence of weak derivative G'(x) at the vicinity of

x is sufficient for the existence of strong derivative and that these

two derivatives are equal. Now we shall consider relations between the differentials and derivatives

of differentiable funct ional s , Denote the weak linear differential of

the functional

F'[x},

X€

nCx

ctional with respect to

h

dF(x, h).

X~

dF(x, h)

is a linear fun-

dF(x, h) = (y, h) ,where

adjoint to

as a result of an operation i , e. Consider,

Since

one can write

an element of the space also

by

X.

T

f

KG

y = f(x) , f: X

(t-),'t"J d'l',

7

X~

XEL

P

[0,

TJ

o where

K'

x

[x,tJ,

t'E[O,T] ,

are continuous functions. We get by (3)

T

T

dF(x,h) =

f o

K~

[x,1:Jh(t)dl:'

f o

is

That element can be treated

for example, the functional

F(x)

y

Y (1:") h (1") d't"

•

-

161-

R. Kulikowski

+q

-1

1,

J

y('t') € L q

y = f(x)

= K'

x, h € L P [0, T then

Since

[0,

TJ, where

P

-1

+

and the operator

(6)

L P [0, T]

is a cting from

The operator

f

into is

x

[x, 'f:;' ]

Lq[O,T]

being c all e d the gradient

of the functional

F:

f(x) = grad F'[x] In the ly denoted by

case of the finite dimensional space

R

n

the gradient is usual-

V F(x) •

By Lagrange functional we call the expression

p (x, ).

(1)

where operator

A

)

= F(x) + A[G(x)]

is a linear functional defined over th e space

Z

(of the range of

G(x)). The form of t h e functional

tical applications

Z

).

depends on the space Z. In pra cP is usually the space L [0, TJ or e[o, T]. F or

t h e s e spaces there one knows the general forms

of linear fun ctionals (

[6] ).

However we shall be mainly interested in the non-negative fun ctionals. We call a fun ctional X(z) non-ne gative, i , e .

non-negative if for all the non-negative

II (z)

~ 0 .

The ge n e r a l form of a linear non-negative functional in spa ce is T (2)

z ~ 0 it is

J o

z (t )

A(t)

dt ,

L P [0, T]

-

162 -

R. K ulikowski

whe re

is a lmos t every -where non-ne gati ve f u nc tio n

A (t )

al m ost e v ery

t € [O, T ] )

~(t)f L q, q = p/(P-l).

a nd

Th e non-n e g ati v e fu nc t io nal s ove r the s pace

(A(t) ?Ofor

i». TJ

C

assume the

foll owing for m T

J

( 3)

wher e

z (t ) d). (t)

,

o

A(t)

is a non-de cr easing,

c ontin u o u s from th e right

side, fun ction

ha v i ng b ounded variation. In the ; eneral c a se the co n s t r ai n t p onent s,

G{x) ~ 0

co n s is t s o f s e veral co m -

i , e. 1, . .. , n,

where

G . : X .... Z., i = 1, • .• , n, 1

and

1

the fun ctional

).

is d efined o v e r

th e Ca r t he s ia n produ ct

co nsis ts

It

wh er e

A

d enot e s

i

c o m p o nents

i , e.

t he line ar fun ctional

ove r

n

of

Z. • 1

Wh e n we w r ite

A~

T he L ag ra nge

fun ctional in th e p res e nt case c a n

0

it mea n s th at

a ll

'\ . a re no n - ne gativ e 1

b e wr itten

n


(x,

Sinc e

A)

L x

= F {x ) +

F(x),

a c o nc ave fun ctional

i= 1

A[G{ x)] of

x

1

[G .(X)] ,

ar e c o ncave fun ctionals of a nd

a

linear fun ctional

F or c o ncave d iffer entia bl e fu nc ti o n s hold s (4)

), 1. c

where

1

F{x)

Z .~ 1

x, of

p(x,).)

is

>.

the foll owing inequality

-

163-

R. Kulidowski

It

follows froml the definition of the differential and the definition

of a concave function: (5)

°<

a<:

<1,

xl' x

- arbitrary points of the domain 2 It can be easily proved that the inequality

of

F'(x)

(4)

holds also

for

conca ve and differentiable functionals.

Theorem 1.

F

Let the functional

and

the operator

concave and strongly differentiable over there exists gative

such

functional

a

dx'ff.x, )J,x) =

(2)

C(x) > 0,

X[C(x)]

l;:

X

and

a

A that for every

(1)

(3)

x

be

C

X.

If

linear non-nex E: X

°

= 0,

(4)

then the functional

F(x)

attains

at

mum value subject to the c o n s t r a i nt

X the C(x) :::'0.

Proof 1) . Since

F,

). C

are

concave functionals we ha ve

F(x ) < F(x) + dF(x, x o -

).. [C(X

o)]::;).

" 0

- x)

,

[C(X)J +ldC(X, X - x) o

1)

The proof

of

a

similar

theorem

is

given

in

Ref.

[1]

.

maxi-

-164 -

R. Kulikowski

x

where

= arbitrary element of

o

X.

Summing up these inequalities one

gets F(x

+

o)

~[G(Xo)J

Taking into account

Since

~ 2:. 0

Since

x

o

dx~[(X').

:::: F(x) + >-[G(X)] + (1)

and

(3)

), X o

xl

one obtains

2: 0 we get F(x) 2:. F(x o) o) arbitrary the theorem has been proved.

and is

G(x

Remark When

the constraint

x

2. 0

is distinghished explicitly i , e.

when

< G 1(x),

G(x)

where

G: X .. Z,

x

> ,

Z = ZI)( X,

one can write

i£ (x,). ) where

A.

=

< ), 1' ) ' 2> .

Then the conditions

(1) - (4)

can be written in the following

equivalent form (5)

d

d

(6)

x

~ 1 [(X, \),

x

x]

=

0

~1 L(X, ~ 1)' xJ 5 0, for

every

PI l(X, ~'1)' 1 1J = 0, [(x, ,\), ), IJ 2. 0 for every

x

2.

0 ,

d).

(7)

d~ ~

(8)

1

Indeed, the condition

(1)

dx~[(3"}.)'

(9)

Since

),2(X) = 0,

for

x]

can

0

be written

= dX~I[(X,

x =x

~1~

II)'

x],.\(X)

=0

one gets (5). According to

(4) for

-

165-

R. Kulikowski

XI [G I (x)]

Since in

.x 2(x) ;:: 0

x ~ 0 the inequality

every

= d;\ 1 ~

hol ds , Then by (9) one gets

[(x, ~ 1)' AI]

for every

0

(3) can

G 1(x) ? 0

the form of (7) • Taking into account that

AIL G 1 (x)] ?

then

\;:: 0 , the relation

(6).

be written

if and only if

(2) can be written in the form

of (8) • Remark 2: It should be noted that when

such

a pair

(x,5.), that

F and

G

x c X the

for every

are convex and there exists conditions

d ~(x,:x.; x) = 0,

(10)

x

G(x)

(11)

:s

0,

~[GC>()]= 0,

( 12) (13 ) hold then F'[x )

attains

The formulae (5) - (8)

at

x

its minimum value; subject to

preserve their form,

except

G'(-x) $ O.

(6) and (8), which c ha n -

ge the i n equality signs, i.e .:

~I[(x,),)(l2:0,

(14)

d

(15)

-r-O:; - I d A<£ 1 L(x , " 1)';' r''5. 0, for every

Re mark

x

for every

x

, II

~O, ~

0,

:~ .

In the c a s e when the expli cit form

Of

the functional ~ (x,), ) is g i v e n

the opt imality conditions i nc l u d i n g differentials c a n be replaced by c o n d iti o n s in the gradient form • Let fo r

example, F'[x} : be the integral operator T

F(x) =

J

K [x(

~),:,J d r

o ha vi ng the

gradient f

[x;1:"]

' KI r , x ( '!:'),::J, x -

-

166 -

R . Ku likowski

(see (6) o f s e c.

2 ). Ass ume t hat

G (x ) be a d ifferentia bl e o pe rato r an d

G: X ~ L P [ 0, TJ T aking into account t he ge ne r a l for m o f line ar fun ctional s in LP[O , T ] (s ee (2)

o f s e c.

3)

o ne can writ e T

J ).Cd

G(x )

G

ex)

;\ ("e ) E: L q [0, T]

di,

o Den ot e th e g ra d ient of t ha t fun ctio nal g ra d and t he g ra d i e nt of For

a

is a f unc tion

h x , \.)

fi xed

of

by

A [ G(X)] by

'f [x,

).(~) g [x,,] , i , e.

)('t) g [x ,

). ,I::

r:J '

J.

x =x

r E. [0, TJ and

d 1! [X,\ ; xJ = (gra d x x

o ne ca n wr it e

~(x, ~),

x]

=

T

_

f~rx,

A:r]

x('C"') d c",

o T he co ndi tio ns

(I), (10) r educ e t o th e r equirement th at a l mos t eve ry -

wh e r e (1 6)

In a simila r wa y th e co nd itio ns

(5),

(6) a re equi val ent t o the follo-

wing: I)

if

g rad

X(T ) = 0

II)

if x(r)

x

~ 1 (x, \.) < 0 fo r a l mos t a lmos t e ve ry- whe re in P

> 0 for a l mos t

a l mo st e ve ry - w he re i n wh ere

all 1: E P -C [0, TJ, then

a ll 't ER C [0, T J ,

then

gr a d

T he co nd it io n s ( 3) ,

(4)

PI (x, ')")

= 0

R,

P, R = a r b it ra ry s et s of po s iti ve m e a sure o f the interval

d ient form:

x

[0,

TJ

(and (7), (8)) c a n b e a lso written i n th e g r a -

-

167-

R. K ulik ow s ki

III)

~ g r a d >. 'f(X, ",\ )

= G(x)

> 0 for a l m o s t all C" E P C [0, T] then

), ('t) = 0 almost every-where in P, IV) if

"5:(-::) > 0

g r a d .l.

1? (x, ~

Co n d it i o n s

:=

for almost all 'e'ER

[O,T] , then

) = 0 almost every-wher e in R.

III-IV h a v e a simple physical interpretation: a t th e p oints

where the c o n s t r a i nt s are not active the L a grange-functi on vanishes and wh en the L a gran g e - function is positive the

co n s t ra i nt s must be a ctive .

It i s also p ossible to write down the g ra d i e n t form of conditions o f

optimality in th e case of minimali zation o f Wh en th e operator c tio n s ,

F'(x ) •

G(x) is a cting into th e space o f c o nt i n uo us fu n -

G: X -,. C [0, T] , one c a n w r ite

i. c ,

T ) G[x] d), ("d

\ " .\ LG(x) '1J

o where

). (~)

d ). (r) ~ 0 small

is a non-in creasing fun ction, what c an b e als o written a s

vi c inity of 1:' is non -ne gative). Wh en

A'( z )

d ~\ (1:") =

de',

;l.(?:")

to

d). (<:)

ned in th e g e ne ralize d s e n s e (e . g . as the ).'(1:") c a n also include

Dira c's

~

A' (1:) 2:

0

0 if the d ifferentiation is defi-

Schwart z's

'b (t)

in the a r b it r a ry

is differ entiable

and the above c o n d iti o n 'can b e written

The l ast inequality is equivalent

ca s e

>. ("l:")

(that notation m e ans that the increas e of

distribu tion). In th a t

- fun ctions a t th e dis c ontinuity-

- p o i nt s o f .:\ (1: ) The co n d itio n

( 3)

in th e pr-e s e nt c a se c a n b e written a s

0, or I) i f = 0

II)

if

It is

grad/.

~ (x'\) = G Lx] > 0

.r o r

()..(1:") = c o n s t ) at the point d\(;;) > 0, "t"l:P

th en

"r

[0, TJ

't" E-P C [0 , T ]

then

d

A( co)

T or v i c i n i t y of ""t' ,

= 0,

tEP .

gr'a d i " n ~

10r m

G [ x]

also po s .si bl e to write th e

€

of 0 ;.'1. i ma l i ' y co n d i -

-

168-

R. Kulikowski

tions for the remaining formulae leave that as an exercise The conditions

(1) - (4), (5) - (8), (10) - (1:3).

We shall

for the readers. (5) - (8)

can be called the quasi-saddle-point condi-

tions and they can be treated as a generalization of well differential conditions of optimality, which

known Kuhn-Tucker

were for mulai ed originally for

nonlinear functions in finite -dimensional spaces

~~~~~~~~~~X_~~~j2~~~~~Y!_~2~~~~~~~~ When an optimization problem is being solved it is also important to know that the functions x(t) which do not satisfy the cond itions (1)-(4) or (5) - (8)

can not be optimal. That problem requires to prove that the

conditions (1)-(4) are also necessary for optimum. In order to prove the necessary conditions we shall impose certain regularity conditions on G but Shall not assume any more that We shall call ble variation

x

x € X o at the point

o

,which

G

if

is defined

for every admiss iby the condition

G [x ] + dG(x , x) ~ 0 , o 0

(I)

there e xi s t s e curve emanating of admissible solutions

n .

generally speaking, a function i , e.

F and G are concave .

a regular point of x

F and

y:

from

x, tangent to x and lying in the set o 0 By a curve in the Banach space we understand,

r of real variable

s

with

the range in

X ,

R't X • According to definition that function should satisfy the follow-

ing conditions: (2)

't (s)E n , We shall

F(x)

(3)

'(0) = x O '

dt(O, 1)

show now, that if

and a re gular point of

=~.

is a maximali zing point for

G then for each admissible variation

G(x) + dG(x, x)

~

0 ,

x, i. e .

-

169-

R. Kulikowski

we get a non-positive increase of F, i , e. -dF(i, x) 2: 0.

(4)

Indeed, the real function f(s)

(5)

attains the maximum value for On the

['f(S)J

F

'1'(0) =

X, i.e. for s

= 0. Then

df(O, I)'::; 0.

other hand, according to the differentiation rule of compound. fun-

ction (5)

and formulae (2) we get df(O, I) = dF ['1-(0), d 1(0, I)] Then

dF(x, x) SO and

(4) has been

= dF(x, x) .

proved.

Introducing the notation II (x)

= -d F(x,

g(x )

xj ,

= G(x) + dG(i,

x)

the obtained result can be written as: (6)

g(x) 2:

if

°

then

II (x) ~

°.

The next step in our reasoning consists in showing that there exists such

a functional

). > 0, which will ensure the relation

where L (x) I

(7)

= dG(x, x] .

The main obstacle in showing that is the nonlinearity of g(x), whi ch consists of linear term In order to (8)

L (x) and the additive term G(x). I overcome that obstacle an auxiliary operator L < s , x>

=

< s, sG(i) + dG(x , x»,

where L: R"X'-' R"Z

s€R,

-170 -

R. Kulikowski

can be introduced. it can be proved that for

real numbers

and

o(l,,x2

Since the fun ctional Rx X

L <

S,

x> is a linear operator,

i,

e,

sl' S2€ R,

11 (x)

can

be also treated as defined over

then the following notation 1 <

x >

S,

-dF(x,

x)

can be introdu ced. Now we should che ck whether the condit ion L <s ,

x> ? 0 impli es

<s , x>

> O.

Observe th at this c o n d iti o n c a n be written as

s ? 0

(9)

and

sG(iC) + dG(i, x ,

Assuming first of all that

s >0

G(x) + dG(x, x is) Taking into ac count

? 0

and divining

?

(4) we obtain

(9) by

s

we get

0 . -dF(x, x is)? 0

and -dF(x, x)?O

or ( 10)

1 <

Then the fun ctional

<

S,

x

x> 2

o.

1 is nonnegative

> which s at i s fly c o nd itio n s Each point

(11 )

S,

s > 0,

on the set

P

of

pai r s

sG(x) + dG(x, x).2 0 .

<0 , x> for which the relation dG(x , x) ;: 0

holds can be treated as a limit of the sequence sequen ce c a n be constructed as follows.

of points from

P,

That

-171-

R. Kulikowski

Take on element

!n

(12)

x

with the property that

o

+ dG(x, x

G(x)

Summing up (11) and (12)

!n

0

In)

>0

-

one gets

G(x) + dG(x, x

In + x)

>0

0 -

Then 1 1 < -, - x n

n

1

lim n .,.

then

(9)

+x >e

0

P

• Since

1

< 0, x>

< -;;-' -;;- X o + x >

00

implies (10) for all

s

2 o.

Introducing the notation

<s, x> = w, Rx X = W the obtained relation

can be written as ( 13)

if

L(w)

2

0

then

l(w)::: 0 ,

where L = linear operator, I

L: W

= linear functional over

W.". , adjoint to

~

V = Rx Z ,

W (an element of the space

W).

We can now return back to the main problem which is the existence of nonnegative functional

l(w)

(14)

To solve that spa ce s

V Jt

satisfying the relation

=

v*[L(w)].

problem we shall need a generalization for Banach

of the well known Farkas lemma. Hirst of all it is necessary to introduce a few additional notions. We shall denote by

Q

a set of all functionals of

be represented in the form (15 )

w*+ (w) = v ....

[L(W)J '

'"

v 2:: 0,

w

which can

-

172-

R. Kulikow ski

where

*

v e- V

v

l<-

= R KZ

The sequen ce of fun ctionals ,..

•

w E. W, if the sequen ce w

e

W

w k(w),

witE W"" is called w eakly converg ent to k

k = 1,2, • . •

converges to

~

w (w)

for each

•

Th e set ther

l<

.

of functionals

Q C W

"!l'

is called w eakly clos ed

with ea ch wea kly c o n ve rge n t sequence

if

to ge-

w: -+ w it c o nt a i ns also

their

limits, i. e. The g e ne r a lized Farkas)

states that

function al

W -It

if

Farkas lemma (called the lemma of Minkowski

Q

is a weakly closed set then

... v~0

In other words there exists such

and

it contains each that (14) holds

r1 J ) .

(see Ref.

Now we are able to formulate a nd prove the following n eces sary cond itions of optimality Theorem 2. Let 1.) at the point

xi murn , 2) 3)

the functi onal

F(x)

subject to the constraint

the point the set

x

2 0,

G(x) ,

is weakly closed.

Then ther e e x is t s such a fun ctional condit ions

G(x)

x is a re gular point

Q

attains the conditional ma-

~ :::: 0

that the quasi-s addle-point

(1) - (4) hold.

Proof

Ii

It was shown already that there exists such a functional (16)

1 <s , x> = v"'(L < s,x » Taking i nt o a cc ount (8) one can write

1) The proof of a similar theorem is given in R ef.

[1

~

.

_..

v

~

? 0,

th at

-

173-

R . Kulikowski

il""<S, x > = ~s +I[sG(x) + dG(i, x)] , where

u

is a real number

and ·~ E Z -Ii-

•

v"~ 0 can be written in the form

The condition

""~O,.\~O

(17)

Hence (4) follows. The relation (16) (18)

can be rewritten as

-dF(i, x) = Setting

s =0

1 [dG(X,

and grad

x

(18)

x)]

=di [(x, ~),

! [i, >: J = 0

xJ = 0

•

the relation (1) follows.

Setting

x = 0,

X[G(i)] = 0

yields

+ ~ (sG(i) + dG(x, x)] •

one gets from

dF(x, x] +

Then

fS

t<- + 1[G(X)] = 0, what by (17)

s = 1 one gets

and (3). The condition (2) must hold by

assumption,

Q.E.D. The theorem ples

2 is valid under two regularity conditions. In the exam-

which are considered below the operator

G(x) = A(x) + a, where element of

X.

G(x) assumes the form

A(x) is a linear operator over

One c a n easily check

each admissible variation

that

X, and

a - given

G(x) i s a regular operator. For

x, defined by

G(X) + dG(x, x) = A(x) + a + A(x) ~ 0 , and the function t(s)

and the c ur ve

r

t(s) = x + sx , one obtains

= x+sxefl,

't(O)=x,

dy-

(0,1)=x

is lying within the set of admissible solutions .

It is possible to check that the same property have the operators

G(x.),

which consist

of several components

(constraints)

Ai(x) t a ' A j i

-174 -

R. Kulikowski

linear,

a € X, i = 1, ••• , n ; i In the case of nonlinear operators

the space of continuous functions measurable,

bounded functions

(Z = C[O, TJ)

(Z = L

x,

such that the function

00

or into

into

the space of

[0, T]) the regularity c ond itio n

[7J )

boils down (see in that respect Ref. tion

G(x) , which are acting

to the existence of adm issible varia -

z(t)

z(t) = G [x] + dG(x,

x),

is positive. In the case of the space of continuous functions it means that min

z (t ) > 0,

0-:; tg L 00 [0, T]

and in the case of the space z(t)

it means that the minimum

of

is positive almost every-where. As an example consider the inequality t

G(x) = a(t) -

(20)

J
d'l:' >

0,

o where

r

(x)

is increasing

= nonne gative,

G(x)

~

0

and having continuous derivative

continuous function. That op erator is regular

'f I(X);

a(t) =

Indeed, since

and t

dG(x, x)

ifl [x

)

('0)]

x('lf)

d z , '("(x)

> 0,

o

one c a n set

x(t')

= - 1 and obta in z(t) > O.

As shown in Ref. dition

3 . of theorem

an element (21 )

[7] in order

to check whether the re gularity c on -

2 holds it is sufficient to show that there exists such

w-Ii E W, that L(w'''') > 0 •

-175 -

R. Kulikowski

For example, in the case of the

L(w)

= < s,

operator

t

J If' [x{~)J x('t')d"t'

(20)

one obtains

t

- Sr [XC~)} d t'} > ,

+ s [a(t)

°st:ST.

o

o t

Since

~ If[xCI:)]

a(t) -

there exists such a parr

d 1;' ~ 0 , then

< s,* x· >,

it can be easily proved that

s'" > 0

x~(t) > 0,

and

t

e [0, T],

that

L(w*) > 0 • It should be noted that the theorem

of variational

2 generalizes certain theorem

calculus in Banach spaces and, in particular,

the following

theorem of Luster-nik, Theorem 3. Let the functionals

If grad

X E.X

and

F'(x},

subject

H(x)

II > O.

If

to the constraint

x

is

a conditional

H(x) = c ,

grad F(x)

(22) and

F, H be strongly differentiable at the point

= p

where grad

extremum point of

c = H(x) , then

H(x) ,

/"- is a number • The proof of that theorem is given in

Consider a controlled input

u(t)

Ref.

[9] .

linear dynamic system, shown in Fig. 1; having one and n+I outputs, which

are described by Volterra

operators: (1)

Yi(t)

J kp,1:") u(1:')

d1:' ,

o where ki (t, 1:' ) - linearly independent transient functions of the system, i = 0, 1, .•• , n •

-

176-

R. Kulikowski

A typical optimization problem can be formulated as follows; Find the function u(t) € L P [0, TJ, which minimalizes T

II

(2)

u 1/

=( J

p

ju(t)1 p

o

,) 1/p

d~

, p Co 1

subject to the constraints T

J

y/T) =

(3)

k.(T,'t' 1

u(-r) d z-

= x .; 1

i = 0,

1, ••• , n

o where

T,

x . - given real numers, 1

In other words, for the given outputs

it is required to minimalize the control cost (2)

x . attained at the time 1

t = T •

In certain cases additional conditions of the form (4) (~,

M ~ u(t) M

M

given numbers) or t J.(t) = k.(t, z ) u(?") d z < x .(t), J 0 J J

f

(5)

S

= 0,1, ... , n

(x .(t) = given time functions) are being imp osed. J The constraint (5) is c a ll e d "restriction of phase coordinates". There exist, of course, many known optimization techniques, such as : va r ia t io na l cal culus,

maximum principle, dynamic programming etc. whi ch

c an be applied for the solution of the optimization problems formulated above. In the present se ction we should like to demonstrate that the m ethod based on theorems

I,

2 of sections

4, 5 , is very c o n ve nie nt for the solution of

problems incl uding restri ction o f ph ase c o o r d i na te s . Instead of de alin g w ith a g e ne r a l n-dim ensional s ystem we shall confine o u r anal ysis to a s e cond order s ystem, whi ch is fr equently e nc o u nt e r e d in th e

en gine ering pra cti ce (e. g. in s ervom e ch ani sms etc .) . The r esult o f that

anal ysis w ill be us eful for th e in vestigation of a class of c ontrollability probl e rn s ,

-

177-

R. Kulikowski

Example I. Consider a system described by the differential equa tio n dYI dt = u(t),

(6)

with zero i nitia l conditions:

y 0(0) = Y1(0) = 0,

shown in Fig. 2 .

It is r equired to find such a control function

u(t)

which min imali ze s

th e " energy cost": I

T

="2 j

E(u)

(7)

[u('()

J

2

dt,

o s ub ject to the constraints T (8)

YO(T) =

J

(T -1:') u(;:-) d r = x ' O

(x

O

> 0)

0 T

YI (T) =

J

u( ·~)

dr

=0 •

0

The c o n s t r a i nts (8), (9) mean th at the deflection of the output c o o r dinat e of the s ystem for of that coordinate

at

t =T

t =T

is equal x 0

a nd the c o r re s po n d i ng velo city

is equal ze r o . The c o ns t r a i nt s of that kind are

typi cal for operatio n of controlled motors

and se r vo m ec ha nis m s .

The Lagrangean of present pr obl em is e q ua l

~ (u, f ) (10)

1 =2

T 2 \ [u ( 1:' )] d t- +

o

T

( T -'t') u(r) d r -

xo~+ /'1-2 J o

wh ere

r-2 = La grange multipliers. Th E' ne cess ary, a nd at th e sa m e t im e s uff icie nt co nditi o n (due t o t he

1~I'

co nvexi ty of

E (u )) , o f o p t ima l it y acco r d in g t o th e or em

3 becomes :

-178 -

R. Kulikowski

(ll ) where

grad f'l'

u

~(u, t<-)"'. u{~)

+ ""l{T - L) + /"'2

can be computed by

«'2

12x = ___0 1 T3

~

and (12)

(a) ,

(9) •

6x

,

~

2

= T

=

0 ,

We get then

0

2

6x =-f(1- ~~), O:S~:s T. T Now we can solve a more complicated problem when in addition u{t')=u{'r)

to constraints

(a), (9)

the amplitude-constraints of control force: u{ '1:') - M :s 0

(13) -M - u{'I:')

where

M

= given

number, should be taken into account. These constraints

are typical for the operation Since linear,

<0

of electrical motors in servo-systems.

is a square-integrable function the general form of the 2 non-negative functional L{z) in the space L [0, T (according

to (2) of section

u{r)

J

3) becomes T

L{z)

! ) (~)

=

z{'t') d't'

,

o where the function

A(-e-)

is non-negative and square-integrable.

The Lagrangean of present problem becomes

J (U{t')J 2 d e

1 T

P{u, /"-, ~) = "2

+ ~1

A1 (r ),

~ 2{1:)

=

~ o)'

J

T

T

+ { ). ('t')

o where

(T -1:') u ('I:') di:- x

0

o

ucn d e

(fT

1

[u ('t')

-

Lagrange functions.

M] dt'+

'\2('t') [- M - u('I:')] d r ,

o

-

179-

R. Kulikowsk i

The necessary and sufficient condition of optimality, accordin g to formulae (10) - (13) of sec. 4, grad

u

p(u,

fL, ) )

become

= u("1:')

+

(15)

r-1 (T - ~) + r.2

u( '1:) - M.:::O,

( 16) T (17)

J

A 1('~)

[U(....) -

1"-1'

f-2

(C')

+

0,

T M] d e

J

>

° \

"1

-M - u('/:'):s.0,

A2 ( "t) [-M

°

( 18) where

=

), 2 (~)

+

(r )

~2(L) ~

.2 0,

- u ('t->]dt' =

°

°,

can be determined by (8), (9) •

,\ . (L), 1 become zero. That correspond to the nonactive constraints. When the

As can be seen these condition will hold for all "L

c o n s t r a i nt s become active

the functions

values which satisfy the condition the interval

[0, TJ

1 (-1:'), 1

, when

). 2(~) should take such

(15). When the constraints are not active in

the optimum solution should be the same as

(12).

Then the optimum solut ion becomes

M,

u(t)

(19)

0 < t < T -

- [t"-;1 (T-t) - M,

+

0

r-2] = M l-1 - ~] T-2T

T-T

o

T

< t < T-T 0 -

-

-

T

T

T

(T - t) li(t) dt

°

=

T-T

Ml J (T - t)dt + J

°

0

< t < T

0-

can be derived from the equation obtained by setting o which yields :

where (8),

-

0

(T-t)

[2(t - T ) 1_ 0

T

-vr,

(19)

JJ.t

into

-

180-

R. Kulikowski

..... I

(T _ t) dt} =

M T - 2T

T -T

'= x

o

o

o

Typical form of that solution has been shown in

11 (t),

The correspondig optimum values o f - t"l(T - t) -

{

r, -

~ 2(t) become:

(t-T ) o 2M =-4M T-2T o'

0 st

'5. To

O,To StsT

~ 0,

0:S t :S T-T 0

LI'Ll (T -

t+T -T t)

+

P:

o f the relation

2

- 2M = 4M

o

T-2T

T-T o

< t <- T

0-

[x ,

T

The pl ot

F i g. 3.

_9= f[--2..-] has been shown T MT2

It c a n b e obse r ve d that th e optimum s olution,

in

Fig. 4.

satisfying c o n s t r a i nt s (8), (9),

exi sts only if j x i < M( T/2)2 • It means that wh en M is less that o 2 4 f x {/ T it is i rnpos s i bl e to a t t a i n the output x in time T using optimurr o 0 T2 I x , < M(-) (or non optimum) contro1. In other words, when the system o 2 is optimally c ontrollable i n the sense formulated in sec. 1. (12)

Exar::ple

~

Consider a gain - coris tr -a ints

(1 3)

the problem of example 1 but replace the amplitude-

by the " velocity- constraint"

(20)

G(u) =

j

u('t') d't'

'5.

V

,

o whe r e

V - given p ositi ve number corresponding to the maximum admissible

v e loci ty of the output c o o r di na t e . Sin ce C [O, T ] (i.e.

u",L G : L

2

2

(0, T] and the ~

C),

,

10

whi ch

operator

G(Il) is acting into the space

the g e n e r a l form of a

nonnegative linear

-

181-

R. Ku l ikow ski

fu ncti on al is des c ribed

by (3) of s e c.

3,

blem become s 1 2

T

/'-1 (

j

-~

(T

th e La grang e an of th e pr esent proT

I o

) u( t" ) d ~ - x ) o·

0

J

[u('t")

2

d r' T

+

' 2

T

J

+

d

>. (t)

S

[

.\ (t)

is a

u( c ) d

i

0

t

0

where

J

i.

u(

d~

~)

- V

+

J

dt ,

0

nonde creasing fu nction with bounded va ria ti o n , co nti nuo u s

from th e right s ide. Si.nce T

d

t

S

dl'

S [u('e-)

d -\ (t) {

0

J h( 't") J

o ne g e t s

u

wh e r e th e fu nc tio n T he n fun cl io nal (7)

t

J dArt) [ J o

i

t

d ), (t)

u( 7:")

d~ -

0

d~(t),

t'

v]

T

S

d A.(t)

0

T 1(t;):J

d), (t)

= ;\( T ) - ).('t:)

is non-incre as in g.

~

the ne ce ssary and suffic ient c on dii ion for th e mi nim um of the sub ject to th e c o ns t r aint s (8), (9), (20) is acco r d i ng to (10) -

- ( I:l)

(21 )

g rad

u

! (u,

~, A. )

= u(

~) + t""1 (T - -r ) + t'-2 + 1 ( ~ )

t

( 22)

1h("t') d ~

T

0

T

T 0

0

T

gr a d

- v}=

+ 0 h("t')J de'

S o

ut e ) dl: ~ V ,

0,

-

T

J 7:

J

(23)

182-

d

A(t')

[

°

u(s) ds -

R. Kulikowski

V]

0,

°

(24)

d ). ( ~)

where small

vicinity

2

of

In order

J and

~ (1: ")

denotes the increase of

in an arbitrarily

't' • to satisfy

active, we split [ T 2' T

°

(21) - (24), in the general case when (22) is

[O,T] into three subintervals

[O,T

I],

(T

I,T 2

J,

assume

tilt)

= 0,

as illustrated by Fig. 5. Then

the condition (21) can be written as

(25)

(26)

f'-I(T - t)

(27)

+

/-t- + let) 2

u(t) + 1"-1 (T - t) + 1-'-2 Since

let)

= 0,

= 0,

should be continuous

t

at

e (T2'

T l ' T2

T]

one obtain fr-om

these equations t€[O,T (28)

u(t)

I],

t ,,[,-. ,I... ]

t E"[O, TIl,

(29)

let)

tE [T

I,

•

T

2],

-

183-

R. Kuli kowsk i

In o r d e r

to

(9)

T Then from

be va lid it should b e

-

T

2

for

(26)

T

1

t = T 2 and

l( T ) 2

0

o ne g e ts

f2~

- t'-l T 1 • By

and

(20)

T

I

we obtain

(8)

T

1

\1("1:') dt"

J

=

0

T

J

1

r- 1 (t -

0

I'-

T 1 )dt

2 lT1

T

u('t') dz- =

J

0

T (T - t) f

(t - T ) dt + 1 1

0

T

V

2

J

T- T -T

f-l -i1 1

2

T2 2

J=

(T- t)

t:

1

(t -T+T )dt 1

1

x 0

From th es e e q ua ti o ns o ne fi n d s T1

In o r d e r

=

to get

~

x (T - -9), V

T1

8V x

1"-1 9

> 0 it must

be

h- ;J

~v > 1.

2

In o t he r w o rds

t he s y-

stem is op t i rr.a l Iy co nt rolla bl e, in the s ens e o f s~c . 1, i f th e velocity c o ns t r ai nt Xo i s g re a te r th en V T t In F ig . 5 a t ypi c al plot o f u(t), 1ft) and th e " velo city" v (t ) = u (~ ) d eO ha s b e en s ho wn .

I

Example 3 . It i s requir ed to find su ch a cont rol

u(t) o f t he s y st e m

minimiz es the fun ct ional T (30)

IU

F [ u]

o

('t')

I d 't

,

( 6),

wh ich

-184 -

R. Kulikowski

subject to the constraints (13), (9),

(13).

Since the derivative of the function under the integral sign

of (30)

is discontinuous we can not use the formula dF

eu d

+

r

hJ }

5 for the derivation of the gradient u(t),

of

(= 0

t: u J .

F

For that reason we represent

as a difference of two nonne gattve functions, i , e.

wher-e

"i (t) = max [u(t) ,

0]

'

u

2(t)

= max (-u(t), 0

In the pre sent case the Lagrangean takes the following form T

S: Cu,r ,iI] = J o

CUl(~)

+

U2(~)Jd7:+ (T

-~)[u l (c) T

T

(31 )

\+

- u ( t' ) 1 dj- - x 2 ' 0)

J CU 1 ( ::- )

- u2(L)]d~

.I .\ 1( ~,) [u /1:' )

+

o

-

M] de- +

o T

+

\

'2(t') [ u 2 ( t-)

- Ml di:

0 where

\("c),

\2(r)E:L

oo

[0, T].

Before we write down the conditions of optimality we should de r ive the differentials of

(31) T

(32)

S [1 + r- 1 (T-"t") o

+

I<. I 2

+), (1:')J 1

h(T) d1;' ,

-

185-

R. Kuliko ws k i

( 33)

d

.p [u' u 2

t"- ..) '.

T

h

i

\ ~ I -

=

.J

I~ 2 + .\ 2 ( z- ) J h (l:') dr- : ,

f<- I (T - ""t ) -

°

T

( eu I ( ?") -

( 34)

M

J

dt ,

°

T

I [u2 ( 1:')

(35)

Jh (e)

- MJ h( L)d '" •

°

Now w e can show th at the o p ti m um sol ution c o n s is ts of tw o p ulses with th e h e ight equa l

M (s e e Fig. 6)

~

, ..M,

( 36)

\11 (t) = ) ( 37)

( 38)

r u (t ) -= ,

t

2

( 39)

O
I


0,

T

0,

°:s

M, T-T

T -T

t <

I

< t4' I - -

an d _

i - I- r- I (T - t ) -

~ (t)

(40)

I

{--<2

2:

0,

°< t < T -

-

I

=

°

I

O
(41 )

=1°'-I T he va l ue

-

1

+

of

TI

ca n be deter mined by s e t ting

u(t) i nt o (8)

wh i ch y ie lds T

(42)

J

°

T

(T-t)Mdt-

J

(T-t)Mdt= MT

1(

T-T

x I)= o·

-

186-

R. Kulikowski

fA 1'

The value of

A 2 (T

\(T ) = 0 , 1

r2

can be determined using the relations

- T ) = 0, 1

whichyield

°,

~ 1(T - T 1) - /"'-2 +>-<-T +1"-:2 1 1

0.

Then 1"'-1 =

~2

T 2

Using formulae (32) - (41) it is possible to check d

u

1>

[ii,

1

,\ ~ [u,

d

I"-

\

f'- , A

1

and d

u

d

1> ( ii,

r- ,\

l

Al

1?[u,~,-\

d

~J

uJ

d

~O,

A] ::: 0,

u

[u, r ,): ; u] = ° f> Cu, ,..,~ ; :x ] = 0, iJ?

2

x2

u]:::

d):?[U,!,-,); d').

P [li, r

2

; ~ J .:::

-

,~

0,

u ~ 0,

0,

2

which indicate that the solution In Fig. 7

ti]

that

(36)

is optimum. T1 [_IXo1 ]

- (39)

the plot of the relation

MT 2

T

shown.

has been

41 X o I

M ~ It can be observed that the optimum solution exists only if 4x o the system is optiM In other words, when is greater than

~

mally

T

controllable in the sense of section 1.

2

It should be observed that the problems considered in the examples

and

3

can be easily extended for the case when the constraints of the

control force are given time functions

In a similar way the quantity

V

M (t) 1

,

M

in the example

i , e.

2(t),

2

can

be

treated as a time function. It is also possible to

sist

consider minimum-time problems, which con-

in finding such a control force

to the constraints

(8),

(9)

u(t)

(10) and

which

minimizes

T

subject

-

187-

R. Kulikowski T

J I u( 1:') I p

d't' -:s

u ,

p

> 1.

o

where

U

= given positive number.

If for example

p

=1

from

(36) -

(39) one obtains

T

(43)

U =

J I Ii (1:') I dr

= 2MT 1

o By elimination of

T 1 from (42).

(43)

one obtains

I. x 0'! M

In Fig. 8. given. from

the plot

of that function

For a given numerical values of that plot

for

,,(, and

0(

= const has been

U/ M

a correspondig minimum time value

one can read T=T

which deter-

mines the optimum solution. Then using (42) the corresponding value of T1

can be derived.

-

188 -

;

ute)

~---+'

--+-

•

Y (t) 0

y .( t ) 1

--.....;. Yn (t )

Fig. 1

ut e ) ~

)

Fig. 2

u(t),

-A(t)

2M

M +---\--

.....

T

o +---~---4,c----;:::-~-----~

-M

Fig. 3

t

-

t;

T o/

189-

T

I

0.5

0.2

0 .2

O. 1

Fig. 4

- - - - ...... ~ l(t)

"

-

"--,

, 0

,

-,

o

T

u(t)

Fig. 5

t\j(tl_ \

, ," ' -'- ) I

"i (t)

T/ 2 0

T

1

I

T-T

I

U

1

2

(t )

Fig. 6

'"

z,L-

T

-190 -

0 •.-

o. 0.3

0.2

0.1 0 .3 Fig. 7

0(=9

2

«=4 Fig. 8

2

-191 -

R. Kulikowski R ef er en ces 1.

Hurwicz L. H. L zawa:

2.

Pr-ogr-arnrru ng in linear spaces, i n K. 1. Arrow, L . Hurwi c z , Studies in linear and nonlinear programming)Stanford 1958.

Ka lman R . E. : On ' he g eneral theo ry of control s ystems. Pr o c.. IFAC Congr. Mos c ow 1960 vol , 1 pp . 481-49 3. London 196 1.

3.

Kalman R. E. , Ho Y . C ' I Narendra K. S. : Controllability of linear dynamica l s ystems, in Contribution to di·fferential equations. Vol. L New York 1962.

4.

Kulikowski R . : On optimal control w ith integral and ma gnit ude type of constraints. Wars zawa 19 67 Prace l ns t y t utu Automatykl PAN z , 67.

5.

Kulikows ki R . : On optimum control of nonlinear , dynamic indust rial pro cess es. Ar r hiwum Automatyk i i Telemechaniki 19 6 7

6.

z, L

Lusternik L.A. , Sobol e v W .1. : Elements of functiona l anal ysis . Mos c ow 19 5 1 ( i n Russian , English trans lation available).

7.

Maj erc zyk -G6mulka J . , Makowski K: Wyznac zanie optymalne go sterowania proc es am i dyna m ic z nymi m etoda; funkcjon alow Lagrange ' a . Archiwum Auto matyki i Te le me c ha ni k i 1968 z , 2, 3.

8.

Pontryagin L. S., Boltianski i V. G .

, Gamkrelid ze R. V. , Mishchenko

E. F. : The mathematical theory of opt i m a l processes . New Yo rk 196 2 . English translation by K. N . Triro goff. 9.

Weinberg M . M . : Variationa l methods o r investigation of nonl m e a r operators.

Moscow 19 5 6 (in Russsian, En g lish translation availabl e ) .

CENTRO INTERNAZIONALE lVIATEMAl1ICO ESTIVO (C. ,I. JVl. E.)

A. STRASZAK

SlJPER VISOR Y

Corso t e n u t o a

S asso

CONTROLLABILI TY

Mar con i

dal

1 a l 9

1u gl io

1968

-

SUPER VISOR Y

195-

CONTROLLABILITY by

A . Straszak (Institu te fo r Au tomatic Control - Polish Academy o f Sciences, Warsaw-) l.In troduct i o n Multilevel control systems are o f increas j ng importance in t he ap plication of complex automatic control in ind ustrial and non -industrial fie ld . The multileve l approach to the synthesis or design of the multivariable control sys tem is the on ly one acceptable for real large -scale systems . A mul tilevel structu re arises rather naturally in practice. However. the theo reti cal foundation of this concept is still on the ea rly stage of the research, since conventional mult ivariable optimization and control theories can not be used d irectly. II.

[1] [4] [5] [6]

The . P r o b l e m Let us co nsi de l' a set of optimal control systems.

i = 1,2, . .. , k . :

where x.

(x

1

. , Xl i' .... x n .i)

01

1

u.

(u l i ' u 2 i ' . . .

1

,.J\ 01 .

J

u

m. i ) 1

t

o.

1

of performance of the c o n t r ol system u, ~ 1

U.

1

Each of the optimal control systems is op timal due- to s ome f ix ed resources (for example: fue l,

energy) or another factor (for example: a p r ice

-

196-

A. Straszak

of the control given to the systeII]). Suppose that the set of the optimal control systems have common sources of this resources or resource - like factors . Now, we may formulate the following problem. Firstly, can we improve the optimality of the optimal control system which belongs to the given set of the optimal control systems by using the multilevel control procedure. Secondly, can we improve the overall optimality (in the sense of the global index of performance) of the set of the optimal control system by us ing the multilevel control procedure. However, we can not answer these questions before the study of controllability (coordinability) of the optimal control system. Therefore, first of all we must know i f it is possible to control the optimal control system and how to do it.

~~_~~£~~~~~~~~_~~~~~~~~~i~~~_ The optimal

control law

is optimal only for the given dynamic process dx .

1

dt and given constraints u.

1

and /

or


1 . 1

T.

So

1

(u .(?;'» 1

2

d~ <

2

r.

1

and/or

and so on. Therefore the dynam ic process f with the controller i

-

197-

A. Straszak

r., r~) 1 1

u . = c .(x ., 1

1

1

must be controllable in the working domain of the state

space

Di~X

due

j

to the given resources

ri .

Now, we can formulate the supervisory controllability: We say that the dynamic process if for any given number

"2.

in the working domain

Di

f is a supervisory controllable i > 0, the dynamic process f . is controllable 1

or working subdomain

j ", r and the interval (. i

resources

point for different

<

X

.

(11) >

01

7.,

D~ t: D. 1

1

due to given

consists of the more than one

"

Example. Let us consider the dynamic process

~~

=

with the working domain x

2(t=T) and

=x

x

2

g ~1x +[~]u <xl(t=O) = 0,

x

xl(t= T) = 0,

2(t=O)=O,

>

5 T

X

o

=

dt = T - minimum time index of performance.

o

Using the functional analysis methods for this optimal control problem

[ 3] , we obtain that for

lu k r ,r

for

~O

IU(tz;)

=

I,

I d"l:;~

S

T

T =

for

o

[u

r = I,

(~)

J

2

dr~

r =1 .

-

198-

A. Stras zak

Therefore this dynam ic proc ess w ith f

o

I has th e supervisory con -

t r olla b il ity . Contr ol. Assume that we have a set of the supervisory co nt r oll a bl e opt imal co nt r ol s ystems , th erefore we have relations

where min

x . 01

x . 01

u.

1

and ve ctor index of pe rforman ce x

og

=

'" '"x , · · · , "..x (x o l' o Z o k)

By introdu cing the g l o ba l index of performance I

g

"-

max

or

x . 01

k

I

g

r:

A

X .

01

i =I

we c a n fo r m ul a t e the o pt i mi z a tio n problem for a supe rvisory c o nt r olle r : Minimize I

g

/'0

x .

max i

0 1

subje ct t o

or Minimi ze

k I

g

L: i =I

A

X .

01

-

199-

A. Straszak

subject to

which can be solved by the supervisory controller by using the mathematicla programming machinery

2

7

References 1.

Mesarovic,

M. D . : Advances in multilevel control Proc . IFAC Tokyo Symposium on system Engine.=ring, Tokyo 1965.

2.

Karlin,

Mathematical Methods and Theory in Games, Programming and Economics . Pergamon Press. London 1959.

3.

Kulikowski,

R .

Optimal Control as a Function of P lant Parameters . Arch . Aut. i Tel. n , 2 1961 . Warsaw (Polish).

4.

Kulikowski,

R .

Optimum control of aggregated multilevel system , Proc. III IFAC Congress, 19 6 6. London 196?

5.

Straszak,

A.

On the structure synthes is problem in multilevel control systems. Proc. IFAC Tokyo Symposium on System Engineering . Tokyo 1965.

6.

Straszak,

A.

Multilayer and Multilevel control Structures. Proc. on Neural Network Springer - Verlag . Heidelberg 1968.

7.

Straszak A .

S:

Suboptimal supervisory control. Functional analysis and aptimizationNew York. Academic Press 1966.

CENTRO Ir-
LECTURES ON CONTROLLABILITY AND OBS.ERVABILlTY

L. WEISS (University of Maryland)

Cor-so tenuto a Sasso Marconi (Bologna) daI I al 9 Lu g l io

1968

-

203-

CONTENTS Section

1.

Introduction

205

2.

Existence and Uniqueness of Solutions to Delay-Differential Equations

207

3.

Representation of Solutions to Linear Delay-Differential Equations

209

4.

Definitions of Controllability

2\2

5.

Controllability of Linear Delay-Differential

213

~yS:tems

6.

Local Controllability of Nonlinear DelayDifferential Systems

2\5

7.

Controllability and Observability for Ordinary Linear and Nonlinear Differential Systems

2\9

8.

9.

n Algebraic Criteria for R - Controllability of Linear Time-Varying Delay-Differential and Ordinary-Differential Systems

232

The Pfaffian System Approach to Controllability

244

10.

Structure Theory for Linear Differential Systems

25\

11.

Weighting Patterns, Impulse Responses, Minimal Realizations, and Controllability Theory

272

-

205-

L. Weiss

1.

INTRODUCTION These lecture notes are devoted to a detailed exami na t i on

of the fundamental system-theoretic concepts of Controllability, Observability, Reachabili ty and Determinability, and of the roles they play in certain specific areas of research in modern system cheory.

The mathematical models employed in this study range in

sophistication from linear, constant coefficient, differential equations to nonlinear, time-varying functional-differential Much of the material, especially that dealing'~ith

equations.

functional-differential systems is of very recent origin, and in many cases enables well known older results in controllability theory to be embedded within newer more general ones.

An overall

objective has been to incorporate a certain amount of self-containment and breadth in the presentation.

Nonetheless, various aspe cts of the

subject have not been covered (it might be well to point out the obvious fact that there are as many types of problems one could consider as there are different types of system models) .

Some notabl e

omissions which a prospective lecturer on the subject may wish to fill in are :

(1) Controllability for part ial differential equations

and differential equations on Banach spaces.

(2) The relationship

of controllability to the problem of system stabilization. A series of seven lectures bases on the material in these notes presented by the author at the Centro Intemazionale Matemat i co

-

206-

L. Weiss Estivo at Pontecchio Marconi, Italy, in July, 1968.

am indebted

to Professors E.Bompiani, R. Conti, and G. Evangelisti for the privilege of participating in the C.I.M.E . course on Controllability and Observability.

-

207-

L . Weiss

2.

EXISTENCE AND UNIQUENESS OF SOLUTIONS TO DELAY-DlrFERENTI AL EQUATJONS Alth ough our concern i s with a r es t r ic ted c l ass o f del ay-

differenti al equations, it i s instructive t o present an exis tenc e theorem for a more general class of equations.

The re s ult s, who3e

p roo fs a r e not reproduced he re, are due to Driver [10].

Notat ion i s

as follows.

D

open connected set in

If

x = co l( x ,· . , , x l n)

If

[a,b]

£

n

R

n

,

R

is an interval in

11~II[a,b]

then and

R

max i

Ilxll = ~

:

Ix I 1

n [a ,b] ... R

IIHt)1I a't :Gb C([a,b],K) = class of continuous function s mappin g

,

t hen

= sup

[a ,b]

i nto

Cons ider the de lay-differential s ystem

dx dt = f(t ,x( '»

(2.1)

where

f(t,H '»

n e R

, t c (to' y) , Y (.

t c (to' y), ~ c C([CI,t] , D)

for

Definition 2 . 1-

(i)

i s a cont i nuous function of

t

( Lf )

fo r every con stant

S

£

[to' y)

f for f

is continuous in t

0

(.

t

(.

Y

t

for any

f or some

if

f(t, ~( · » ~ £

is locally lipsch i tzian i n

and evpry compact s et

KS,uC such that

'0

SeD

C([ CI , y] ,D) . ~

if

th ere c xI s t s a

-

208-

L. Weiss

for all

t

E:

[to'S), all

4>1' 4>2

Definition 2.2. 4>(') to

E:

C([a,t].S) .

(i) Given an initial function

C ([a,to],D) , a solution to (1) is a function

< S ~ y , such that

x(t)

E:

x(t) = <jl(t)

satisfies (1) on

for all

t

E:

[Cl,t

x(t;t , 4» o

•

] O

C ([ Cl, rl) ,D)

E:

and

(to'S) (ii) The solution at time

from initial time

x(·)

to

and initial function

4>

t

generated

is denoted by y(t;t , 4» o

This solution is unique if any other solution

is identical to it as far as both are defined. Theorem 2.2. be continuous in

l

Consider the system (2.1) and let

and locally lipschitzian in

W.

Let

Then there exists a unique solution on

[a,S), to < S

~

y,

then for any compact set numbers

to < t

i.e., as

t

< t

l

+ ~

x(t)

2

t

and

such that

Let

D

ljI, and linear in

W

[a,y) .

S

=

x(t;t , 4» o

cannot be increased,

x(t

k)

E:

comes arbitrarily close to

there exists a unique solution interval

S < Y and

x(t)

G ~ D there exists a sequence of real

< •• + S

Corollary 2.3. in

and if

f(t,ljI(·»

Rn

x(t)

and let

D - G, k = 1,2, •.. ,

D or is unbounded. f(t,W('»

be continuous

Then for every =

x(t;t , 4» o

on the entire

-

209-

L. Weiss

3.

REPRESENTATION OF SOLUTION S FOR LI NEAR DELAY- DIFFERENTI AL SYS TH1 ~

In th is s e cti on, whi ch i s b as e d he avi l y on th e work o f Hale and Meyer [12] , we cons i der t he equati ons o f t he f orm

dx dt = f(t,x('»

(3.1)

with in itial function sp ace is linear in

x(')

t - h ::s::t f or a l l

~ £

It

B , all

The con t ro l funct ion

C([t

+ u(t)

o

- h,t o],R

n)

=

and de pends on ly on values of

u(')

L(')

x (s )

f(t, x( '» for

II f( t, ¢(.» II

i s furthe r a ssumed that t . where

B whe r e

s L( t)

II