-, 

NASA Conmctoc Rep 178260 

ICASE REPORT NO. 87-11 

ICASE 

PIECEWISE LINEAR APPROXIMATION FOR 

HEREDITARY CONTROL PROBLEMS 

Georg Propst 

1 .. 

(EASA-CR- 178260) PlECECISE LlbEAR 

AEP8CXI8AIICP PC5 hlRED1'IABP CCIISCL 

€&GELEMS Final Beport (NASA) 15 p CSCL 12A 

N87-2 C7 78 

Unclas 

G3/64 45174 

contracts No. NAS1-17070, NASI-18107 

February 1987 

INSTITUTE FOR COMPUTER APPLICATIONS IN SCIENCE AND ENGINEERING 

WASA Langley Research Center, Hampton. Virginia 23665 

Operated by the Universities Space Research Association 

National Aeronautics and 

Space Administration 

Ln0kY-c-a 

Hampton,Virginia 23665 
PIECEWISE LINEAR APPROXIMATION FOR REREDITARY CONTROL PROBLEMS 

Georg Propst 

Institute €or Computer Applications in Science and Engineering 

ABSTRACT 

This paper presents finite dimensional approximations for linear retarded 

functional differential equations by use of discontinuous piecewise linear 

€unctions. The approximation scheme is applied to optimal control problems, 

when a quadratic cost integral has to be minimized subject to the controlled 

retarded system. It is shown that the approximate optimal feedback operators 

converge to the true ones both in case the cost integral ranges over a finite 

time interval as well as in the case it ranges over an infintte time interval. The arguments in the latter case rely on the fact that the piecewise 

linear approximations to stable systems are stable in a uniform sense. This 

feature is established using a vector-component stability criterion in the 

state space and the favorable eigenvalue behavior of the piecewise 

linear approximations. 

If x L2 

This research was supported in part by the National Aeronautics and Space 

Administration under NASA Contracts No. NAS1-17070 and NAS1-18107 while the 

author was in residence at ICASE, NASA Langley Research Center, Hampton, VA 

23665 and in part by the Fonds zur Foerderung der wissenschaftlichen Forschung 

(Austria) under Grant No. 53206 while in residence at the Universitaet Graz, 

Graz, Austria in connection with his Ph.D. Thesis. 

i 
1. INTRODUCTION 

1 Given $'E IF? and 4 :[-h,O]+ IF? consider the retarded functional 

differential equation with constant coefficients 

P 0 

k(t) = %x(t-hk) + I Ao1(S)x(t+s)ds, t - > 0 

k=O -h 

0 2 x(0) = $ , x = 9' in L (-h,O;P). 

01 An equivalent abstract Cauchy problem 

in the space M2 = IF!" x L (-h,O; If) generates a strongly continuous 

semigroup. Approximations are constructed by restricting the problem to 

finite dimensional subspaces ZN = IF!" x YN C - M2, defining appropriate 

generators on zN. 

;(t) = Az(t), t L 0; z(0) = (4 , 4 ) 

2 

Ranks and Burns [l] used subspaces YN which consist of functions that 

are piecewise constant on the delay interval [-h,O]. This is the well-known 

averaging approximation scheme. As an extension, Burns and Cliff (51 enlarged 

the subspaces to piecewise linear functions. In both papers, the approximating generators were constructed by forward difference methods. In [31 the 

approximations were obtained by projections onto subspaces of continuous 

splines being contained in the domain of A. Then Kappel and Salamon [141 

introduced 6-type operators in order to define generators for a spline scheme 

whose adjoint semigroups converge strongly. These 6-type operators are 

specially constructed to approximate the differential operator A at the 

discrete delays, where the splines may be discontinuous, as are the functions 

in the domain of A*. 
-2- 

In this paper, a new scheme is presented employing again subspaces of 

orthogonal piecewise linear functions as in [51, but using &-type operators 

for the construction of the approximating generators. These operators are 

needed at each meshpoint, where the subspace functions may be discontinuous. 

In fact, the number of discontinuities increases with the order of the approximation, in contrast to the spline case. The resulting generators are 

completely different from those given in [SI. 

An application of the approximation schemes is the optimal control problem, when an integral ranging over [O,T), quadratic in the trajectory and in 

the control, is LO be minimized subject to the controlled delay equation. It 

was shown by J. S. Gibson [91 that, if T < a, the strong convergence of 

the semigroups and their adjoints yields convergence in norm of the optimal 

feedback operators. In this present work, strong convergence of the 

semigroups and their adjoints is proved ustng the Trotter-Kat0 Theorem as in 

[l], [9]. Thereby, it is not necessary to assume absolute continuity OE AOl, 

as did the proofs in [121, [131, [141. 

In the case of the so-called infinite time horizon T = , Gibson’s 

approach relies on the assumption that a stable system is approximated by 

systems that are stable in a uniform sense. For the averaging scheme, this 

stability preservation property was established in [191, and in [12] for the 

Legendre-tau methods. Tn contrast, the spline schemes do not have this quality (see 1141). This is due to extraneous eigenvalues close to the imaginary 

axis. It is shown below that the eigenvalues of the present scheme converge 

to those of the delay equation and that exponential stabilty of our approximations is dominated by their nP-components. Thus, uniform preservation of 

exponential stability is proved with decay rates arbitrarily close to the 

decay rate of the hereditary system. 
-3- 

The matrices corresponding to the piecewise linear functions are banded 

and sparse, in contrast to the Legendre and spline methods. While the 

Legendre schemes ill], [13] exhibit high accuracy even for low order of 

approximation, the numerical efficiency of the present scheme is about the 

same as that of the first order splines in [141, and superior to the averaging 

methods [l] as well as those in [5]. 

Preliminarily, Section 2 collects some facts on the semigroup generated 

by the uncontrolled system and on the linear quadratic hereditary control 

problem (see [61, [8J, [9J). Section 3 presents an approximation framework 

suited to Chapter 4, where the piecewise linear scheme is developed. In Section 4.1, the &-type operators are defined and the projections onto the subspaces of piecewise linear functions are investigated. In Section 4.2, the 

approximating generators and their adjoints are constructed and convergence 

results for the finite time horizon problem are proved. In 4.3, the matrix 

representations are given and an @-component stab€lity criterion is 

established. Section 4.4 investigates the eigenvalue behavior of the approximate systems when the order of approximation increases. In Section 4.5, the 

uniform stability preservation is proved. Finally, €n 4.6 there is a brief 

discussion of the numerical tools needed for the implementation of the scheme 

on a computer and the results of three examples are tabulated. 

2. THE LINEAR QUADRATIC OPTIMAL CONTROL PROBLEM FOR HEREDITARY SYSTEMS 

I We are concerned with the linear retarded functional differential 

I equation 
-4- 

in @, where for some fixed finite delay is defined 

by xt(s) = x(t+s), Bo is a real nxm-matrix and u(t) E @. The bounded 

linear functional L: C(-h,O; s) + I&' is given by 

h > 0, xt: [-h,O]+ IF!' 

with 0 = ho < *e. < h = h, % E flxn, k = O,.**,p and AOl E L 2 (-h,O; 

Given $ = ($ 01 ,$ ) E !I2 = Iff' x L2(-h,0; @) and u E L 

P 

ex"). 

loc (0,w; lm, 

there exists a unique solution x(t;$,u), which is absolutely continuous 

with L2-derivative on every interval [O,T], and satisfies (2.1;l) for almost 

all t - > 0, and the init€al condition 

(2.1 ;2) x(O;$,u) = (I 0 , x(*;$,u) = $l in L 2 (-h,O; IF!'). 

Def€n€ng the state at time t by 

system (2.1) is converted to an abstract Cauchy problem in M2, which is a 

Hilbert space with the inner product <(I$', $'I, (J, 01 ,J, >> = $ OT J, 0 + <$ 11 ,J, >2. 

Let S(t), t 2 0 be the Co-sem€group corresponding to the €ree motion of 

(2.11, i.e., 

2 

S(t)$ = (x(t;$,O), xt($,O)), t - > 0, $ E M 
~ 

- 5- 

and define the input operator B:$ -f M2 by 

BU = (Bou,O), u E I€!". 

Then the evolution of z(t;+,u) in time is governed by the variation of 

constants formula 

t 

(2.3) z(t;+,u) = S(t)$ + I S(t-s)Bu(s)ds, t - > 0. 

0 

The infinitesimal generator A o€ S(*) is given by 

dom A = {$ E: M2 $l 8 W1'2(-h,0;p), +'(O) = $'}, 

1 -1 

A$ = 04 94) 1, 

where Wj ,p(a,b; IF?) denotes the space of *-valued absolutely continuous 

functions on [ a,b] possessing j-1 continuous derivatives and j-th derivatives that are in LP(a,b; IF?). The function z(t; $,u) in (2.3) is a 

mild solution of the abstract system 

(1) i(t) = Az(t) + Bu(t), t - > 0, z(0) = $. 

Weighting the past history by the step function 
-6- 

we have an equivalent norm corresponding to the inner product 

If 

(2.4) 

the operator A-wI is dissipative in M2 that is 

g' 

<A$,$>g - < w11$1I2 g' $ E dom A. 

Therefore, by the Lumer-Phillips Theorem, there exists a constant M > 1 such 

that 

The M2-adjoint of A generates the M2-adjoint semigroup S(t)*, t - > 0 and is 

given by 
denotes the characteristic function of the interval I. The optimal con- XI n 

trol problem on a finite interval is: given 0 < T < 00 and $ E ML find 

the control u E L'(0,T; that minimizes the cost functional 

where Go = Go and Wo = Wi are nonnegative matrices and R = RT is 

positive definite. Defining the operators G: M + M2 by GI$ = (Go$ ,0) 

and W: 

2 0 

2 0 M + M2 by W$ = (WO$ ,0) we have 

The solution to the linear quadratic control problem (2.3), (2.6) in the 

Hilbert space M2 is based on the Riccati differential equation 

d 

- <J,,II(t)$> + <AJ,,n(t)$> + <n(t)+,A$> - dt 

-1 * (2.7) - <II(t)J,, BR B II(t)$> + <Jl,W$> = 0, for 0, J, E dom A, 0 -- < t < T, 

II(T) = G. 

There exists a unique, strongly continuous family of nonnegative selfadjoint 

operators lI(t), t - > 0, satisfying (2.7). The optimal control u is 

given in feedback form 

- 
-8- 

-1 * 

(2.8) z(t) = -R B II(t)z(t), 0 -- < t < T, 

where y(t) is the mild solution of 

i.e., 

The optimal cost is J(u,$,T) = <$,n(O)$>. With respect to the product 

structure of M~, we can write 

IIOo(t): + ll? and IIll(t): L2(-h,0;@) + L2(-h,0;lF?) are selfadjoint 

and nonnegative. Since IIlo(t): + L2(-h,0;@), it has a representation 

by a matrix valued function 

(lTlO(t)S)(s) = IIlO(t,s)S, 0 < t < T, 6 E IF?. 

for @' E L2(-h,O; IF?) 

2 nlo(t,*) E L (-h,O; 'Iffxn), lee., 

Using this notation, we write -- 

* TO 2 Since B $ = Bo@ , $ E M , the feedback law can be wrftten in terms of the 

delay system: 
-9- 

- 

x(t) being the solution of the closed loop system 

-1 T T 0 

+ I (Aol(”) - BOR BoIllO(t,s))x(t+s)ds, 0 -- < t < T. 

-h 

We also consider the infinite time horizon problem, that is the minimization 

of J(u,$) given by (2.6) with G z 0 and T = m, and assume that the 

system (2.1;l) is stabilizable, i.e., A - BK generates an exponentially 

. stable semigroup for some linear bounded operator Then there 

exists a nonnegative, selfadjoint operator Il E: L(M ) that maps dom A 

into dom A and satisfies the algebraic Riccati equation 

K: ML + e. 

2 

* 

* -1 * (2.9) A - Il& - IIBR B lI$ + W@ = 0, @ E dom A. 

If, in addition, system (2.1;l) and Wo have the property, that any 

admissible control drives the state to zero, that is J(u,$) < m implies 

z(t;$,u) + 0, as t + -, then II is uniquely determined. This certainly 

is true if (2.1;l) with output W0 is observable or if Wo is simply nonsingular. Using the time independent solution of (2.9) in the feedback law 

(2.8) gives the optimal control and trajectory as in the finite time horizon 

case. 

H 
-20- 

3. FINITE DIlIENSIONAL APPROXIMATIONS 

Our goal is to construct systems of ordinary dif€erential equations, such 

that their solutions approximate the solution to the hereditary control problem in Section 2. To this end, let Y , N = 1,2,*** be a sequence of finite dimensional subspaces of L (-h,O; W?) with corresponding orthogonal 

projections pl. Then ZN = li? x YN, N = 1,2,... are finite dimensional 

subspaces of M2 with corresponding orthogonal projections p + = (6 ,p1+ ), 

+ E M . Suppose there is a sequence of linear operators AN: ZN + ZN and 

let SN(t), t 2 0 be the uniformly continuous semigroups on M2 generated 

by the bounded linear operators ANpN: M2 + ZN, i.e., 

N 

2 

N 

N 0 N1 

2 

2 NN N s (t>+ = e* P t+, + E M 

Remark. We extend AN to all of M2, because we want the semigroup SN(.) 

acting on the whole space. Instead of letting the generator ANPN = 0 on 

(zN)', 

is said about the control problems in ZN and the corresponding semigroups 

SN(*) in M2 in this section, remains valid, if we take the generator of 

SN(*) to be ANpN - a(1 - pN) with some a E R For simplicity of 

exposition, we shall make use of this possibility only at the end of the proof 

OE Theorem 3.5 below. 

we equally well could choose another appropriate extension. All that 

We will use the following hypotheses in order to get the desired convergence of SN(t) to S(t), the solution of semigroup generated by A as 

defined in Section 2. 
-1 1- 

(Hl) There exists a constant w E IR such that 

N N 

<A +,+> < ~II+II~ for all + E z , N = i,2,... . R- g 

(H2) There exists a subset D Cdom A and a real number X > w, such that 

(i) (XI - A)D is dense in M2, 

(ii) for all + E D, A p + + A+ as N + a. NN 

By the Lumer-Phillips theorem, (Hl) implies 

for all + E M and some M > 1. Since (XI - A)-': M2 + dom A is continuous if X > w, (H2) (i) implies that also D is dense in M2, so that 

we have the following version of the Trotter-Kato theorem [17, 111. Th. 4.51. 

Theorem 3.1: If the sequences ZN, AN, N = 1,2,**. satisfy (Hl) and 

2N (H2), then for all E M , S (t)+ + S(t)+,N -+ 00, uniformly in t - on 

bounded intervals. 

N Observing E = (BoE,O) E Z , 5 E for all N, we take the input 

operators gN: IEP + zN as BE-BS to define finite dimensional 

control systems on zN: 

N 
-1 2- 

where u(-) E Lloc(O,m; 2 e) and I$ E M 2 . The solution to (IN) is 

given by 

NN tN N 

z (t;p 4,111 = SN(t)pNQ + 1 

0 

S (t-s)B u(s)ds. 

As a consequence of Theorem 3.1, one derives (see €or instance [14], Th. 4.2) 

convergence of z (t;p Q,u) to z(t;Q,u), the solution of (I) given in N N 

(2.3): 

Corollary 3.2, Assume (Hl), (H2) and 

2 Then for all Q E: M 

The limit is uniform in t on bounded intervals and u in bounded subsets 

2 _I of Lloc(O,m; e). 

NN N N N 

z (t;p Q,u) = (x (t),y (t)) E Z , 

N 

Writing with some xN(t) E ‘JRP, 

yN(t) E YN (3.2) implies x (t) .+ x(t;Q,u) uniformly in t on bounded 

€ntervals, where x(t;Q,u) is the solution of the hereditary system (2.1). 

Seeking approximatCons for the optimal control problem (2.31, (2.6), we 

define the costs JN(u,Q ,T) by 
-13- 

(3.3) 

From the control theory of finite dimensional systems, it is well known that 

the optimal control minimizing (3.3) is given by 

-1 N*N (3.4) ?(t) = -R (B TI (t)?(t), 0 -- < t < T 

where $(t) is the solution of 

z ON (t) = (AN - B N-1 R (B N*N ) II (t))zN(t), zN(0) = p N 4, 

N and 

Riccati dif€erential equation on ZN 

TI (t): ZN + ZN is the unique nonnegative selfadjoint solution of the 

I 

(3.5) N-1 N*N -IIN(t)B R (B ) II (t) + WN = 0, 0 < t < T, cN N 

II (T) = G . 

I N N N 

I N-N NN N 

Here G I$ = GO and W 4 = W+ for 4 E Z . The optimal costs are glven 

by J (u ,$,TI = <p 4,II (0)~ $>. 

In applications, the original system (I) is controlled by use of the 

I approximate feedback law (3.4) instead of (2.8), i.e., <(t) is replaced by 
-14- 

the so-called suboptimal control 

where iN(t) is the mild solution of 

In order to establish convergence of the optimal and suboptimal controls, we 

have to deal with the M2-adjoint semigroups SN(-)* generated by the M2- 

adjoints (ANpN)* of ANpN. The adjoint of AN: ZN -+ ZN is 

(AN)*: ZN i ZN. 

Since (Hl) implies (3.11, the estimate (3.1) is valid also for (AN)* if 

AN, N = 1,2,*** satisfy (Hl). Thus, using Theorem 3.1 and Corollary 3.2, 

beside (Hl), (H3) we need (H2) with A, AN replaced by A*, (AN)* respecTherefore, (A NN* p = (pNANpN)* = pN(AN)*pN = (A N*N p . 

tively (this will be denoted by (H2*)), to obtain S”(t)*$ + S * (t)+, 4 E M 2 , 

uniformly in t on bounded intervals. 

The following assertions were proved in [91 (also [141, Th. 4.3). 

Theorem 3.3: Let (Hl) - (H3) and (H2*) hold. Then, as N -b 

(b) For the controls and trajector€es given in (3.4), (3.6), and (2.8) 
-15- 

the limits being uniform in t, 0 < t < T. -- 

In the case of the infinite time horizon, we deal with the algebraic 

Riccati equations 

N*N "-1 N*N (3.7) (A)n +nNAN-nBR (B)n +TJN=O 

on ZN, N = 1,2,*** . If (A NN ,B ) is stabilizable, then there exists a 

nonnegative, selfadjoint solution llN of (3.7), governing the optimal feedback. 

We will establish convergence of the Riccati operators IIN again using 

Gibson's arguments [9]. However, this approach is based on the assumption 

that the stabilizability of the hereditary system implies that the systems 

(A ,B ) are stabilizable in a uniform sense with respect to N (see hypothesis (H5) below). As to the investigation of stabilizability or exponential 

stability of Co-semigroups there is a L2-stability criterion due to R. Datko 

[71. 

NN 

We state here a special version (a proof may also be found in [19]). 

Lemma 3.4: - Let S(t), t 2 0 be a Co-semigroup of bounded linear 

operators in a Banach space X satisfying 

(3.9) 

, t - > 0 - and 

2 00 

I 

0 

IS(t)xNxdt - < ~~1x11~ X' x E X 
-1 6- 

for some constants MI, al, c1 > 0. Then there exists an exponent 

a = a(cl,Ml,al) > 0 and a constant M = M(cl,Ml,al) > 0 such that 

(3.10) 

Note that if we can prove (3.9) €or the semigroups SN(*) with c1 

independent on N, then, by (Hl), (3.10) yields the exponential stability of 

SN(*) uniformly with respect to N. Moreover, observe that the estimate 

(3.9) is eqivalent to 

(3.11) 

for some constant c2 > 0, if S(-) is the solutlon semigroup on M2 as 

defined in Section 2. By Fubini’s theorem, this equivalence follows directly 

from the state concept (2.2) and is a special Eeature of the semigroup 

associated with the retarded functional differential equation (2.1;l). 

As far as we want the semigroups SN(*) to be suitable approximations 

€or S(*), it seems to he natural to demand the equivalence of (3.9) and 

(3.11) also with regard to We call this the VDP-property of the 

approximations (meaning the vector-component dominance is preserved). It 

plays an important role for our approach to stability questions in context 

with the infinite time horizon control problem. 

SN(*). 

Suppose for N sufficiently large there exists a solution IIN to the 

Nth algebraic Riccati. equation (3.7). Then with 

P=A~-BR N-1 N*N (B)II 
-17- 

-N AP generates an exponentially stable semigroup ?(e) on M2. We 

introduce the projection V: N2 + ll? 

and want the following hypothesis to be valid: 

(H4) Provided N is sufficiently large, there exists a c1 - > 0, independN ent on N, such that for all 4 E Z 

if and only if there exists a c2 1. 0, independent on N, such that 

for all 4J E: Z N 

If II is a nonnegative selfadjoint solution to the algebraic Riccati 

equation (2.9) for the hereditary control problem, define the operators 

“AN: Z + Z , N = 1,2,.** by 

NN 

-1 * xN = AN - BR B II 

-N and let S (0) be the uniformly continuous semigroup on M2 generated by 

-N N -N N -N 

A p , i.e., s (t) = e* P t, t > 0. - 

Intending to provide the existence and uniform boundedness of the operN 

ators ll , we demand: 
-18- 

(H5) If the hereditary system (C) is stabilizable, then there exist constants M, f3 > 0 such that for N sufficiently large 

Theorem 3.5: Let (H1) - (HS), (H2*) hold and assume Wg - is 

nonsingular. I€ the hereditary system is stabilizable, then 

(a) for N sufficiently large there exists a solution II to the Nth 

algebraic Riccati equation (3.7) and 

IInNpN - IIII + 0, N -f OD. 

L(M~) 

(b) The optimal and suboptimal controls and trajectories and the corresponding costs converge as in Theorem 3.3 (b), (c). 

Proof: As in [9, Th. 7.41, we first consider the Nth problem (1”) 

2 with initial value $I E M , when it is controlled by the feedback 

“u(t) = -R -1 B * IIp N z(t). 

by ;N(t) = ?!‘(t)pN$ 

(H5) : 

The evolution of the state in time is then described 

and the corresponding costs can be estimated using 

.. 

0 
-19- 

Thus, there exists a nonnegative selfadjoint solution 

braic Riccati equation for N sufficiently large and 

llN of the Nth algewith some constant c1, which does not depend on N. Therefore, there is an 

index No such that 

NN tin p II < cl, N > N~. (3.12) - - 

The convergence statement in (a) now follows from [9, Tho 6.91, once that we 

have shown 

- for some constants M, a 

Since Wg > 0 we have 

> 0. 

-1 T 6 l2 5 p 6 W&., 6 E e, where p is the minimum 

eigenvalue of Woo Following the arguments given in [9] (proof of Th. 7.5) 

let + E ZN and define z (t) = S (t)4 = (x (t),y (t)) with xN(t) E 

I@, yN(t) E yN, t - > 0. 

yN(t) so that 

-N --N N N 

-1 * " *" 

Further note that <R B ll z (t),B II z (t)> - > 0, 

IP 
-20- 

03 

applying [91, Cor. 4.2 to the semigroups SN(*). It follows / IV?(t)@12 

0 

dt < p -1 c111411 2 , N > No and, by hypothesis (H4), I ll??(t)@l12 dt < c211@l12 

- - - 

0 

-1*N N with some c2 > b. Also, because 2 is generated by (AN - BR B TI )p , 

(3.1) and (3.12) imply (e.g. [17], 111. Th. 1.1) the existence of constants 

Now Lemma 3.4 assures M1, a1 - - - such that II$(t)ll < Mle , t > 0, N > No. 

that there are constants M, a > 0 such that 

t 

Me-at, t > 0, N > No. - - 

But this proves (3.13), since, as we mentioned in the remark above, we may replace ANpN by ANpN - a(I-pN), so that lI$(t) II < e-at, while the 

finite dimensional control problems on ZN remain completely unchanged. 

Statement (b) follows from (a) in a manner similar to that in the finite time 

horizon case (see [9] or [141). 

4. TRE PIECEWISE LINEAR APPROXIMATION SCHEME 

While the foregoing statements are of rather general nature, this section 

presents a special approximation scheme using so-called piecewise linear functions. We prove via several lemmas that this scheme satisfies the hypotheses 

(H1) - (H3) and (H2"). Then we show that it has the VDP-property, so that 

(H4) is valid. Furthermore, we investigate the characteristic matrix of the 

approximate systems in order to establish results on the eigenvalue behavior 
-2 1- 

1) functions [-h,O] + ni? that are polynomials of degree one on every interval 

I IN is commonly called a space of piecewise linear functions on (-h,O]. A 

basis of KN is given, written in a sfmplifried notation, by the 2pN matrix 

k.i 

when the approximation index increases, This enables us to conclude (H5). 

Finally, we present some of our numerical findings. 

4.1 Projection onto spaces of piecewise linear functions 

Corresponding to the discrete delays hk in (2.1;1), for N = 1,2,..* 

we subdivFde the intervals Ik = [-hk,-hk-l), k = 2,000,~ and 11 = [-h1,01 

into the subintervals IN = ), k = l,***,p, 1 = l,*-*,N (with 

the exception Ill = [t,,,O]) by defining the meshpoints 

NN 

kj [tkj 'tk,j-l 

N N 

tN -h - jrk/N, j = O,*..,N, kj k- 1 

functions I 

where 1 denotes the nxn identity matrix. The following diagram illustrates the definition of the basis elements. 
-22- 

N N 

%, j-1 1 

1 

0 

-1 

a 

The pairs eo = (1,O) and = (O,eij) are a orthogonal basis of the 

n(2pN+1) dimensional product space ZN = @ x YN, N = 1,2,-** The 

orthogonal projections 

(I$ ON1 ,P1 I$ 1, where P1 is the L2-orthogonal projections from L2 onto 

YN. With 

ekj 

pN: M2 + ZN are of the form D NO1 (I$ ,I$ ) = 

we have 

(4.3) 

where the components of the coe€ficient vector a NN (p I$) are given by 
-23- 

a. = 4' and 

We frequently will use the abbreviations 4kj N = akj(pN$) N and $N = pl$ N1 . Note that 

Obviously, the spaces ZN are not contained in the domain of the generator A of the hereditary semigroup, since the elements of YN are not dif- 

€erentiable on [-h,O]. Nevertheless, the action of A and A* can be 

approximated by operators on ZN imitating, heuristically speaking, the delta 

distributions in the derivatives of discontinuous functions by operators 

in YN. Following the ideas developed in [14], we need the operators gN 

for each point, where the piecewise linear functions in 

gN 

YN may have jumps. 

We define gN- 6g: IR' + YN, N = 1,2,*** by kj ' 

N- NN +- 3N eN )[, k = 1, j = O,***,N-l 'kj'') (f- ek,2j+l r k,2j+2 

k k k = 2,...,p, j = l,***,N-l 

+-e 3N N )e, k = l,**.,p-l NN 

k+l,l rk+l k+l,2 
-24- 

and 

Proposition 4.1, (a) For any 5 E - and 4' E L2(-h,0; 

In (4.7) and throughout the paper, we use the notation 

left side limit of 

I$ N (tkj) N- for the 

+N at tkj. N 

(b) The norms of the &-operators are 

Proof: (a) Let 1 < k < p and 1 < j < N-1. TJsing (4.5) and ohserv- -- Iing that 

N N- N Ne k,2j-l(tk,j-l E ek,2j(tk,j-1) = '9 

we get 
0 

<'kj(C),+ N- 1 >2 = cT(N eN +- 3N eN >(s)+'(s)ds -h r k k,2j+l rk k,2j+2 

The proof €or k = 1,.* ,p-1, j = N and for 6;; is analogous. The 

statement on gN+ follows similarly from the fact that ek,2j-1 kJ 

and 

N (t .) = I N 

kj 

eN (fj) = -I, k = l,***,p, j = l,*..,N. 

k,2j 

(b) Since the basis of YN is an orthogonal set, we have 

The proof for gN- is analogous. kj 

by (4.2). 

B 

Next we establish convergence results for the piecewise linear projections of sufficiently smooth functions. 

II+N - $ill < ll;lll, 
-26- 

The constants c1, c2 do not depend on N - or 

Proof: The proof is based on an application of the Peano Kernel Theorem 

and define the linear funck j (see for instance [20], Th. 1.3). Let s e I 

tional Fs : W2,-(IEli; e) + by 

Fs(p) = 0 for 

(4.9) 

where 

Now 

all polynomials p of degree one, so the said theorem assures 

S-T, T c <S 

. 0 ,T>S 

Lkj Lkj 

.where 

define 

F= max(rk, k = l,-**,p). To estimate the second term in (4.9), we 

so that 
-2 7- 

But from (4.11) 

Hence, by (4.6), statement (a) follows. Similar methods for the functional 

Gs: $'a(I:j; @) + @, Gs(Q1) = D$'(s) - D+$N(s), and the fact that 

gN yield (b). D+$N = - 2N eN 

r k,2j-1 k,2j k 

As an immediate consequence from Lemma 4.2 (a), we see that the subspaces ZN defined in this section satisfy hypothesis (H3), since the set 

01 {(Q ,$ ) E M2 1 Qo E: @, Q1 E W2'"0 (Ik; @I, k = l,..~,p) is dense in 

N M2 and IIp II = 1 for all N. 

4.2 The approximating semigroups and their generators 

Definition 4.3. For Q = (Q 01 ,Q E ZN we define 

Since D+Q1 E: YN for Q1 E: YN it is clear that AN is a linear 

operator zN + zN. 
I -28- 

Lemma 4.4: The adjoint of AN is given by 

01 NO1 Proof: Evaluating <($ ,$ ),A (41 ,$I )> for $,(I E ZN we get by 

Proposition 4.1. 

and, since 411 E YN, 

Integrating by parts the term involving D++l yields 

Furthermore, 

so that 
-29- 

where A is given by 

The last two sums are transformed using (4.7). Observing 

and 

+'(o-) = +l(o) 

k = l,**-,p, then arranging A appropriately we get N- - N 

tkN tk+l ,OS 

and the result follows by applications of (4.8). 

H 

The next lemma shows that the operators AN satisfy the uniform dissipativity condition (Hl) in the space M2 

E! 

defined in Section 2. 

with N Lemma 4.5: For all N and all + E Z , <AN+,+> < wll+ll 

g- 8' - 

w given in (2.4). 
-30- 

Proof: As in Proposition 4.1, it is easy to verify that, with respect to 

the weighting function g(s) = p - k + 1, s E Ik, k = l,***,p, we have 

2 for all +l E. L (-h,O; Iff') and 6 E: JI?. From these eqiiations and the 

deftnition of AN, it follows 

N for + E Z . Using 

and the inequality 5 T 0 - < 1 (15 I 2 + 101 2 ), 6, 0 E. I?, we get 
because, due to the weights, all terms except the first three neutralize each 

other. 

m I 

Looking for appropriate sets to be used in (H2) and (H2*), we deflne 
-32- 

The following Lemma occupies (H2) (ii) and (H2*> (ii). 

Lemma 4.6: (a) There is a constant c > 0, such that for all N - and 

- all Q E D 

* 

(b) For all $ E D 

N*N * 

II(A ) p $ - A $11 + 0, as N + m. 

Proof: (a) From the definition of A and AN we have the estimate 

where 

Ry proposition 4.1 and Lemma 4.2 for Q E D this yields 

N 1/2 '3 "1 N1 ) IIQ l, + IlA (Q Ill2 2 C C NN IIA p Q - &I1 ( + + 2(T) ZTs- 1 7 
-33- 

with some constants c1, c2, c3e Since $1 is continuous on [-h,O] one 

has 

so that 

with 

ell '*** 'ep,2N 

- r = min (rk, k = l,... ,PI. Taking advantage OF the orthogonal€ty of 

2 in L , we have For 5 E -iff N N 

Hence, 

j=1, -0 ,N 

This proves (a). 

(h) From Lemma 4.4 and the definition of A* we have 
-34- 

N N- NN N+ N 

N- 1 

j=l 

+ 6; ($ (tpj) - $ (tpj>) - S,($ (-h)). 

Since 043) is valid "(Aol$ T ON- ) AOl$ T 0 ti2 + 0. 

* if $ E dom A . Hence 

1-1 1-1 N 1-1 const "1 ID+$N - D($ +$ )I2 -<(h)1/2 IID+($ +$ ) - D($ +Jl )ll, - < 7 ll$ Itoo. 

by Lemma 4.2. We arrange 

Recall, that for $ 1 E dom A "1 , $ (-h) = A)' and $ (-hk) - $l(-h;) = 

k = l,***,p-l, so that 
-35- 

Finally, A3 N* (JI) can be estimated like A: in part (a), namely 

In order to apply Theorem 3.1 to AN and (AN)* of this section, it 

remains to show (H2) (i) and (H2*) (i). 

2 ** 

Lemma 4.7: The sets (A-A)D - and (A-A )D are dense in M , if 

A > w as given in (2.4). 

- Proof: Due to basic facts in semigroup theory, we know from (2.5) that 

(A E 41 Re A > w) is contained in the resolvent sets p(A) and p(A*). 

Hence, if A > w, the operators (A-A)-' and ( A -A*) - exist. 

Therefore, given JI E @' x C1(-h,O;@') the equation (A-A)Cp = JI has a 

unique solution Cp = (Cp (O),Cp ) E dom A, which by the definition of A satisfies ACpl - 6' = JI . But this implies 6' = A$' - JI1 is continuous and 

differentiable. 

C2(-h,0;@). Hence the dense set II? x C1 is contained in 

(A-A) (II? x C2 dom A), which is a subset of (A-A)D. ~ 

1 1 

1 

In fact, i1 = A$' - $' is continuous, so that Cp E I? X 

1 

E c (I~;IEF), k = l,...,p, reveal JI llk 

The same arguments applied to 

E L (@;C1(-h,O;X?)). Let A. 1 that (A-A*)D* is dense, if 

A > w, Cp E M2, 0 < E < IICpII and Aol E ~(x~;L~(-h,o;z~)). There is a I 

I 

At1 E L (X?;C'(-h,O;@)) with corresponding generator A: satisfying 

* -1 -1 * < ~(411$11 I(A-A 1) , A E P (Ac), 

* * 

IIA - A n = IIA,,~ - Gln 

1 (M2) L (IRn;L2) 
-36- 

* -1 * -1 * 

and I(A-A C ) I1 - < 2 II(A-A ) II (cf. [151, IV. Tho 1.16). Let $c E D 

* 

such that II(X-Ac)Jlc - 411 < E. Then II(A-A~)$cII 5 211@11 and 

* -1 II(A-A )$c - ~II<II(h-Ac)$c - $11 + SAc - A II ll+cII - < E + E(4llcbll II(A-A 

* * * * 

ll)-lll$cll - 

< 2E, because I\$ I1 < iI(A-Ac) * -1 II Il(A-Ac)JlclI * - < 41I(X-A * ) -1 I1 Il4ll. This 

c- ** 

proves the density of (A-A )D . w 

The proofs OF the Lemmas 4.6, 4.7 do not use additional smoothness assumptions 

on AoZ as it is the case in 1121, [131, [14]. 

Summarizing, we can now say that the semigroups SN(*) and SN(*)* 

generated by ANpN and (AN)*pN converge to the hereditary semigroups 

S(*) and S(*)* €n the sense of Theorem 3.1. Also, Theorem 3.3 holds so 

that for the €€nite time horizon control problem we can approximate the 

Riccati operators and the optimal controls by solving the finite dimensional 

systems (3.4), (3.5). 
-37- 

4.3. Vector dominance preservation 

of ZN and the canonical ^N ^N 

'ep,2N With respect to the basis eO,ell,*** 

basis of II? the matrices [AN] and [AN*] representing AN and AN* are 

given by 

(4.12) [AN] = (QN)-lHN and [AN*] = (Q N ) -1 H NT 

with 

. , N = 1,2,*-- . 

For the computat€on of the entrles of 

basis elements are given by 

HN, observe that the derivatives of the 

k = I,.** ,p, j = l,***,N. d+ N - 2N N - = 0 and 7F ek,2j ek,2j-1' 

d+ N 

dt ek,2j-1 

- 

Written in the simplifying nxn matrix notation we get for example 
I -38- 

The inner products in 

elements and Proposition 4.1. The result is the n(2pN+1) square matrix 

HN are evaluated using the orthogonality of the basis 

whe re 

N 

= (Akl k2 Ak, 2N-2 AN k, 2N- 1 + Ak *k,2N - Ak) 

N AN ..e. 

I is a nx2nN matrix, k = 1,*** ,p, ko = f,) a 2nxn matrix and 

are 2nx 2n matrices. Xumerical algorithms 

solving high order systems with coef Eicients [AN] might take considerable 

advantage from the fact that HN has band structure (not the case for the 

Legendre methods [Ill, [12], 1131) and that QN is diagonal (not the case for 

spline methods [ 141 ). 

h = (-I I), k = ( I 'I) 

-I -1 I -1, 

In the following, we exploit the structure of the matrix [AN] in orjer 

to deduce the VDP property and (H4) for our piecewise linear approximations. 

Lemma 4.8: If there is a c > 0 independent on N such that for 2- 

m 

2 N f 

0 

llSN(t)$Il2 dt - < c1 IIc$II , 0 & z , 

for some c > 0 not depending on N 01: +. 1- 
Proof: Let + E zN and set sN(t)+ = e* p t+ = e ANt 6 = NN 

--- 

the (wO(t), N wl(t)> N E z N 9 t > 0. With wl(t) N = f 2N 1 ekj N Wkj(t) N 

- 

k=l j=l coe€ficient vector col(wo(t>,wl,(t),***,wp72N(t)) N N N is the solution of 

A view of the rows of [AN] reveals that (4. 3) implies 

Vkl(t) = - - NN avkl(t) + - NN bv *N 

(t), k = 2,***, r k-l,N k k r 

(4.14) 

(t), k = 1,*** ,PY j = 2,***,N 

*N NN NN 

v (t) = - -- av (t) + - bv 

r k,j-1 k kj ‘k kj 

N 2 4N < - 1+Il2, k = l,***,p, j = l,***,N. 

- ‘k 

(4.15) Ivkj(0)I 

To estimate the solutions of (4.14), we make use of the fact that, if 

f E L 2 (0,~; N, a > 0 then 

t 

and g(t) = 1 e -a(t-s)f(s)ds, t - > 0, 

0 
-40- 

a, -2 1 

g E L2(0,m; IR) and I g (t)dt - < I f2(t)dt (cf. for instance [lo], 

0 a0 

VI. 2.33). 

The f€rst equation in (4.14) yields 

N 

t r 

-- a(t-s) 

1 vo(s)ds, N t > 0. 

at N 

r 

-- 

N 

vll(0) + I e - 

N 1 

Vll(t> = e 

0 

-- at 

1 N 

vll(0), t > 0, we get 

r -N N 

With vll(t) = vll(t) - e - 

m 

2 2 = const I 

0 

IVSN(t)$l dt - < const ll$ll , 

by assumption, where the constants do not depend on N. Using (4.15) it 

follows 

(4.16) 2 2 03 

N J (vll(t)l dt - < const IIOS . 0 

Estimating the solutions of the other equatlons in (4.14) by the same method 

yields 

00 W 2 (t)I2dt 5 const II$II , N 2 2 N I (~~,~(t)l dt - < const ll$ll if I 1~~,~-~ 

0 0 
2 m 

2 (t)l dt < const ll$ll , k = 2,***,p. 2 2 N 03 

I IvN (t)l dt < const ll$ll if I Iv~-~,~ - 

0 kl - 

0 

So, from (4.161, we get by induction 

2 2 OD 

N I Iv (t)l dt - < const ll$ll , k = l,*.*,p, j = l,***,N. 

0 kj 

But this proves the assertion of the lemma, because by (4.3) 

where d = ( 

so that 

2 < const 11$11 - 

Corollary 4.9: The semigroups $(*) generated by 

*pN = (AN - BNR-l(BN)*IIN)pN satisfy hypothesis (H4). 

Proof: Since RN:p .+ ZN is represented by the n(2pN+l)xm matrix 

N (4.17) [B ] = col(Bo,O,.**,O), 
the matrix [?I differs from [AN] only in the first 11 rows. 

Therefore, (4.13) with [AN] replaced by [$I again yields (4.14). The 

rest of the proof remains unchanged. 

I 

Besides for (H4), the VDP-property of the piecewise linear approximations 

together with the results of the next section will be used to deduce (H5). 

4.4 The eigenvalues of the approximate systems 

It is known that the spectrum of the generator A coincides with its 

point spectrum namely a(A) = (A E $ I det A(A) = 0) where 

AS 

P -1 hk 0 

h(X) = AI - 1 Ak e - 1 AO1(s)e ds, X E 4. 

k=O -h 

The eigenvalues of the finite dimensional operators 

det(AIN - [AN]) in $. IN denotes the n(ZpN+l)-identity matrix. In order 

to calculate the determinant of the characteristic matrix 

AN(X> = AIN - [ANI in terms of rational functions of A, we transform 

AN(X) 

AN are the zeros of 

by elementary row and col.umn operations. 

First, for all k = 1,s.. ,p and j = 1,*** ,N multiply A~(A> from 

the right by the matrices 

the only nondiagonal identity matrix being at the position ((k,Zj-l), 

(k,2j)). The resulting matrix is multiplied from the left by 
-43- 

N BNPN 0) NN 

(Bo Bll 0 so that the first row of blocks now is given by 

with 

B12 0 - 

3N CN 

T3; = XI - Ao-q- 12 

k = l,***,p, j = l,***,N-l 3N CN 3N N - 

BN kj = -%,2j-1 rk kj -- ‘k, j+l ’ rk 

+- N 

k l,***,p-1 3N N 

‘k+l, 1 ’ - -- N- N 3N N 

BkN - -Ak - %,2N-1 + 5 ‘kN rk+l 

3N CN +- 

P 

N BN = -A - A 

PN p p,2N-1 r pN’ 

Then multiplying from the left with 

where the only nondiagonal block is at 

whose diagonal looks like 

0 0 

3N 

k r 

- 

N 

-p,(x) 

3N 

k r 

-- 

0 6N x +-- 

‘k 

0 

0 3N 

k r 

- 

, k = 1, ,p,j=l, *N 

0 

0 

0 

6N 

k 

1%- 

((k,2j-l),(k,2j)), yields a matrix 

@I. with 
-44- 

3N 6N)-1 

r r 

N N 

r Pk(A) = - - - X(X + - 

kk k 

(4.18) , k= 1 P. 

We define 

subirwls p1(A)Dl1 ' 

the first row of blocks to zero. Thus 

from the upper left block and sets all other entries in 

N N 6N N N N P 

(4.20) det A (A) = [ II (det qk(h)I) (det(A+ -->I) ]det Ao(X), 

k= 1 k 

where 

N (4.21) Ao(X) = XI - 
-45- 

6N X + - # 0 

k r 

Note that these transformations are possible, as far as 

6N and X # f iNL fi, k = 1,... ,p, in particular qk(X) # 0, i-e., X # - 7 r 

Ff X E (X E 4IRe X -p) and N - > 2p for some p > 0. Further note, 

and 

N 

k k k 

- 

N N if Re X 1 -p, then det A (A) = 0 iff det Ao(X) = 0, provided 

N>- 2P . -r 

From (4.19) we get by recursion 

- 

where 

UsFng this in (4.21) yields 

N N Ao(X) = AI - L (A) = XI 

with 

(4.23) 
-46- 

Proposition 4.10. (a) - With the projection - V: M2 + @ introduced in (H4) 

-- we have 

N -1 * 

[V(XI - A ) V 1 = (A;(X))-', X 8 p(AN). 

- as N + =, uniformly in X on bounded subsets of $. 

(c) If Re X - > 0, then Irk(X>I - < 1, k = l,***,p. For any p > 0 

there exists N(p) such that for all N N(p) and all X E $ with 

Re X E [-p,O] 

N 

N N 

Irk(X)I - < Irk(-P>I, k = I,*** ,P* 

Proof: Expanding the determinant of AN(X) by elementary operations, 

ve have-seen that TNAN(X)SN = UN(X). where UN(X) is a lower triangular 

block-matrix with A!(h) in the position (1,l) and SN,TN are regular 

PN N N The matrices given by SN = ll I[ SN and TN = DN IT ll T .C . 

first column of blocks in TN and the first row of blocks in (SN)-' are of 

kj k=l j=l kJ k=l j=l 

the Eorm (I 0- 0). Thus, the application of these transformations to the 

equation A~(x) (+O*- *> = (400- O)T yields 

0lT = ($ 0- 0lT NO 0 = T ($ 0- 

or 

00 (($ 0- olT for all 4 ,J, E IP. -1 0 ($O *- *IT = (UN(X)> 
-47- 

N -1 0 This implies JIo = (Ao(X)) 41 . But 

COT N -1 0 -1 0 v(AI - AN)-lV*@O = V(X1 - A ) (+ ,0) = [V](AN(X)) ($ 0 

for all $O E e, and this proves (a). 

From (4.18), (4.22) we have 

22 

1-l 

6N 2 - 2NrkX rkh -1 3 rkX 

2 22 ' N = (1 ++ (1 + 22 + 4NrkX + X rk 6N + 4NrkX - 2rkX rk(X) = -- 

6N 2 

This proves (b), because, as N + 00 

22 rX -rkX 3 rkX 

-N + 1 

2 T) and (1+ - 2 (1+ k)-N +e N 6N + 4NrkX - 2rkX 

uniformly in X on bounded subsets of 4. 

Finally, an explicit computation of Irfl(X) l2 and its derivative with 

respect to ReX shows (c). 

The properties (b) and (c) are essential €or the convergence of the 

N matrices AO(h). 
-48- 

N 

(b) If det AO(A) = 0 - and Re A - > 0, then lAl f 

k=O 

For any p > 0 there is an N(p) such that for all A - wtth 

Re A E [-p,O] and all N > N(p), det AO(A) N = 0 implies 

- 

Ph P 

k=O 

1x1 - < 1 2kePhkl~l + 20e IIA~~II~~. 

N N N Proof: Set AO(A) = AI - L1(A) - Ly(A) - L3(A) as in (4.23). 

k -r A p -hkA 

=Ce Ak i P N L1(A) -+ A. + 1 % TI e 

k= 1 i= 1 k=O 

and 

uniformly in A on bounded sets. 

To each N there is a unique jN such that s E 1 N. , k' k,jN 

Let s E I: 

thus 

jN P A 

Iim L~(A) N = 1 e -hk-l lim Aol(s)(rz(A)) ds. 

N+= k= 1 N+= I k 

From O < jN + N(hk-l+s)/rk < 1 and Proposition 4.10 (b), it follows - - 

hence 
The convergence is uniEorm in A on bounded sets and in s E Ik 

dominated with respect to S. Therefore 

For Ly(A) in (4.23) we get 

and 

- 11 

3N ((=:(A))-’ is defined if - # A, k = l,...,?), so that Ly(A) + 0 

uniformly on bounded sets. If det Ao(A) = 0 then A is an eigenvalue 

of LN(A). Therefore det Ao(A) = 0 implies 1x1 - < (Ly(A) + 

IL!(A)I + (L!(A)1. 

Proposition (4.10) (c) and the convergence of rk(-p), (rF(-p))” and 

N 

rk 

N 

So (b) is proved by similar arguments as (a) using 

N 

N jN (rk(-p)) 

For the investigation of the asymptotic behavior of the eigenvalues of 

AN, N + m, we now use the following consequence of Rouche‘s Theorem: 

Proposition 4.12. - Let f, fN, N = 1,2,.** be holornorphic inside and on a 

closed bounded contour - If f has no zeros on r and if fN -b f 

uniformly on I‘, then there exists an No E IN such that for 

N 2 No, fN - and f have the same number of zeros (counted according to their 

multiplicities) inside r. 
-soFor p > 0 define G = {A E $IRe A - > -p). Since det A(X) is 

P 

analytic on tl and its zeros lie in {A e $1- p - < Re X - < 0 and 

1x1 

P 

P 1 ihklA,l + ephllA 01 I1 L1 )C, (A E $/Re h - > 0 and 

k=O n 

1x1 5 f + llAOIHL~~, the number of eigenvalues of the generator A 

in G is finite. Similarly, from Lemma 4.11 (b) and the notes following 

(4.21) we see that, if N is sufficiently large, the eigenvalues of AN in 

G lie within 

k=O 

P 

P 

P 

k=O 

K = {A E tl- p - < Re X - < 0 and lXl 5 1 2k:hklA,l + 20ephUA 01 U Ll ) P 

Although these estimates are not accurate, they lead to rigorous results given 

in 

Lemma 4.13: (a) If hO is an eigenvalue of A with multiplicity k, 

then for any E > 0 (small enough) there is an No such that each 

AN, N - > No, possesses k eigenvalues in B(XO,c) = {A E I lh -XOl < E). 

(b) - Let p > 0 - and Xi, i = 1, ,11 be the eigenvalues of A - in 

G . For any E > 0 (small enough) there exists No such that the 

P 0 

k 

operators AN, N - > No, have no eigenvalues in GP\ (j B(Ai,E). 

i- 1 
-51- 

- Proof: Assume that Xo is the only zero of det A(X) in B(XO,Er. 

aB(XO,E) is bounded and det A;(X) + det A(X) uniformly on bounded 

sets. Thus, (a) follows at once from Proposition 4.12. 

Choose, without loss of generality, E > 0 such that det A(X) has no zero 

R 

i=l 

in aG U u 3B(Xi,E). We know from (4.20) that, if N ?-;- 2p,X~G is 

an eigenvalue of AN iff det AO(X) = 0. 

- P R 

i= 1 

Write Gp\ U B(Xi,c) = G1 u G2, N 

where 

R R 

= (GpnKp) \ B(Ai,c), G2 = (G nKC) \ U R(hi,E). 

i-1 P i= 1G1 

G1 is bounded and contains no zero of det A(A). Thus, there is 

an N1 2, 2p such that for all N - > N1 det A$3(X) has as many zeros in 

a G1 

- , G1 as det A(h), that is det A!(X) has no zero in GI. Since 

G2 K;, there is no eigenvalue of AN in G2, if N is sufficiently 

large. 

This shows that the eigenvalues of A are approximated by the eigenvalues of the operators AN. Moreover, given E > 0, let p E R and 

Xi, i = l,***,R, 

Re Xi - > p. 

in the right half plane 

provided N is sufficiently large. 

be the eigenvalues of the hereditary system with 

Then the piecewise linear approximations do not have eigenvalues 

Re X - > p outside the balls B(Xi,E), i = l,***,R, 
-52- 

4.5. Uniform stability 

From the results of the previous section, we conclude that, if S(.) 

with some M, w0 > 0, then for all -u Ot is stable, i.e., IIS(t)ll - < Me 

w < w0 there are an N and constants MN such that for all N - > Nu 

w 

(4.24) IIS N (t)ll < MNeWt. 

- 

In order to get uniformity with respect to N on the right hand side of these 

estimates, we follow an idea given by R. Ito [12] in connection with his 

Legendre-tau approximations. The idea is to establish uniformity in (4.24) 

for one special no-delay case and to interpret this special case as a 

perturbation of the general situation. 

Let us consider the equation ;(t> = -x(t), t 0, in ll? as if it 

were a functional differential equation with p delays, demanding the initial 

condition We approximate by our piecewise linear 

scheme, denoting the approximating generators by They are given in 

Definition 4.3 where A0 = -I, \ = 0, k = l,***,p and A()l(*) = 0. The 

2 (x(0) ,xO) = $ E: M . 

A:. 

representation [A:] is a lower triangular block matrix with -I in the 

[A!] t tJ left upper position. Therefore the first row of blocks in e is given 

by (e'tI 0 - 0). Hence, for all $ E ZN 

Thus, by Lemma 4.8, there is a c > 0 such that 

(4.25) 
-53- 

and by Lemma 3.4 there exist constants 

N = 1,2,*** 

Mo, uo > 0 such that for all 

-at 

II < Moe , t - > 0. N- z 

Remark: Guided by these arguments, one easily sees that the spline 

approximation scheme presented in [14] does not have the VDP-property. 

Because the first row of blocks of the matrix representing the spline generators 'A: is also of type (-I 0-0) one gets for all $ in the U sN 

Aot 0 -t spline subspace 'ZN, I(e $) I L e II$ll, as above. Thus, if a spline 

analog of Lemma 4.8 holds, then by Lemma 3.4 lsZNll - < Ke-Et, for 

some K, E > 0, independent of N. But this contradicts the peculiar 

eigenvalue behavior of the spline scheme (see [14], Prop. 5.13). 

-wet 

Lemma 4.14: - If llS(t)ll - < Me , t - > 0 for some M, wo > 0 then for 

and such that for all N > Nu - - all w < wo there exist - 

IISN(t) II < KUt, t - > 0. 

(ZN - 

Proof: Let 0 < w < wo. We have seen in Lemma 4.11 that there is a 

N 

constant c such that IL (-w+iT)l - < c, T E R, if N - > N(w). It follows 

N (det Ao(-w+iT) # 0 if N is large enough). Thus, from the uniform converWnce of A!(A) to A(A) on the set {A = 'W + irI 1x1 < c), we have 

- 
-54- 

(4.26) 

with some N E IN and y > 0. 

AN, 

w 

Define AN = wI + AN and let (P E ZN- The trajectory e 0 Q is 

w 

the solution of 

&t) 

Equivalently, 

hence 

N 

where 

2 F: M -f IF?. 

f N (*,$I: R+ IF? is given by f N (s,Q) = Fe AoS Q, s 2 0 with 

because the L 2 -component of (A: - A:)$ vanishes for all JI E ZN. From 

(4.27) and (4.25) it is clear that 

(4.28) 

for some K > 0 not depending on N. We write 
-55- 

(4.29) 

with 

nL2(%L(ZN)), if N is su€ficiently large. The calculation ?f the FO:I~<~L-- 

transform y(*) of the convolution y(*) yields [In, (21.61)1 

A 

By Plancherel's T'neorem (cf. for instance 110, (21.5311) and (4.281, we get 

Thus 
-56- 

by Proposition 4.10 (a). Therefore, from (4.26) 

and, by (4.29), (4.25) and Lemma 4.8 

N 

Lemma 3.4 thus yields constants M, E. > 0 not depending on N, such that 

So, if the hereditary semigroup S(*) is exponentially stable with 

it is approximated by piecewise linear systems with 0' some decay rate w 

decay rate arbitrarily close to wO. 

Another immedtate consequence of Lemma 4.14 is 

Corollary 4.15: The semigroups 3N(-) generated by 

-N N - A P - <AN - BR-'B*II)D~ satisfy hypothesis (H5). 

Proof: If the hereditary system is stabilizable, there exists a 

solution ll of the algebraic Riccati equation, and the closed loop semigroup s(*) generated by A = A - BR B JI is exponentially stable. The 

approximations to are actually given by S (e 1. Thus the previous 

- -1 * 

-N 
-57- 

N 

lemma yields constants M, u > 0 such that 

,for all N sufficiently large. 

Summarizing, we have proved that the convergence statements of Theorem 

3.5 are valid when the piecewise linear approximation scheme is applied to 

infinite time horizon hereditary control problems. 

4.6. Examples 

Testing the numerical performance of the approximat ion scheme developed 

in this paper, we have employed it in several examples and compared the outcomes with the results produced by other schemes. As far as these examples 

are representative, it turned out that the piecewise linear and the first 

order spline approximations [14] are of the same numerical accuracy (for the 

same approximation index N), but both are inferior to the Legendre methods 

[11,131. 

In the case of the finite time horizon the Riccati differential equation 
-58- 

NN is transformed, by taking 

differential equation 

rN(t) = Q [Il (T-t)], to a standard Riccati matrix 

NTN N N d rN(t) + [A I r + r [A 1 - 

at 

(4.30) N N -1 NTN N -r[B]R [B]I'+[W]=O, O<t<T -- 

N rN(o) = [G I. 

NN Observe that the selfadjointness of 

and hence 

component of ZN, we have 

IIN(t) implies [JIN(t)ITQN = Q [Il (t)] 

Since BN, WN, GN refer exclusively to the lE& N I"(tlT = r (t). 

N [w 1 = 

[ GN 

,p(2pN+l)xn(2pN+l) 

I 

O-I 0 

wO 

0 

I 

0 

GO 0 - 0 

0 0 

I I 

0 0 

Thus (if p = 1, 5 0) we can reduce the dimension of (4.30) introducing 

the 2nxn(2N+1) matrices 
~ 

-59 - 

f = 

, where 

0 0 GOAl - GOAl 

FO 

ATG~ o 0 

Fo is given by 

m 

Ol 

IO 

0 01-IJ 

-1 T 

F~ = A'G + G~A~ - G B R B~G~ + wo, 00 00 

in orbar to get the €actorization 

(4.31) N TN rN(t) = [GN] + L1(s) L2(s)ds, 

0 

Ly(t) being the solution of 

N N -1 NTN 

LN(t) = L,(t)([AN] - [B IR [B 1 r (t)) xi 

(4.32) 

Multiplying (4.31) from the left with [BNIT yields 
-60- 

Solving the n(4n+m)(2N+l) differential equations (4.32), (4.33) we get 

[B ] r (t). But this is all we need €or the computation of the suboptimal 

control iN(t) (see (3.6)). Denoting the mxn blocks in [B NT ] [n N (t)] 

NTN 

N N by i30(t),**.,82N(t), we have 

where iN(t) is the solution of 

(4.35) k(t) = AOx(t) + Alx(t-h) + BOu -N (t) 

in 

one of the intervals 

Iff'. In each term of the sum in (4.341, the integration ranges only over 

IN , j = ,N. I,.*. 1j 

Numerically the systems (4.34), (4.35) were solved simultaneously by an 

appropriately adjusted 4th order Runge-Kutta procedure combined with Simpson's 

rule €or the evaluation of the integrals. 

Example 4.1. Minimize 

subject to 

x(0) = XJt) = (i) , -1 -- < t < 0. 
~~ ~ 

The true solu ion 

~~ 

-6 1- 

he ptecewi e linear approximations with index N = 4,8,16 are presented in the Tables 4.1 and 4.2. The 

relatively greatest errors occur around t = 1 and t = 2, where the derivatives of x(t) and u(t) have jumps, while iN(t) and iN(t) are of 

course continuously d€f€erentiable. 

- - 

For the infinite time horizon control problem (p = 1, AO1 : 0) the 

suboptimal control and trajectory are again calculated via (4.341, (4.35) 

when llN(t) is replaced by the stationary operator iI , that is the 

solution of the algebraic Riccati equation (3.7). The transformation 

rN = Q [iI ] yields a standard Riccati matrix equation 

N 

NN 

in $(2N+1)Xn (2N+1), which was solved by the Newton-Kleinman-algorithm as 

presented in [18]. In each step of this algorithm, a Ljapunov matrix equation 

was solved using the quadratic procedure given by R. A. Smith (see also [18], 

p. 297). The time independent mxn blocks B., j = 0,.**,2N were then 

employed in (4.35). Furthermore, with 

N 

S 

N nN **a I11,2N 11 1 * N tnl= * 

we give some values of the feedback kernel 
-62- 

\\ 

0 

0.25 

0.5 

0.75 

1 .o 

1.25 

1.5 

1.75 

2 .o 

-- 

0 

0.25 

0.5 

0.75 

1.0 

1.25 

1.5 

1.75 

2 .o 

-4 

u1 (t) 

-1.0602 

-0.8419 

-0.6209 

-0.4008 

-0.2268 

-0.1743 

-0.1897 

-0.1877 

-0.1880 

.I_-II 

^4 u2W 

-0.8721 

-0.8721 

-0.8721 

-0.8721 

-0.8 720 

-0.8720 

-0.87 19 

-0.87 18 

-0.87 19 

1.4018 

-1 -0599 

-0.8419 

-0.6241 

-0.4030 

-0.2 116 

-0.1860 

-0.1878 

-0.1880 

-0.1880 

-0.8719 

-0.87 19 

-0.87 18 

-0.87 18 

1.4017 

1 

-1.0598 

-0.8419 

-0.6239 

-0.4060 

-0.2022 

-0.1884 

-0.1880 

-0.1880 

-0.1880 

+t) 

-0.8718 

-0.8718 

1.4017 

-1.0598 

-0.8419 

-0.6239 

-0.4060 

-0.1880 

-0.1880 

-- 

- u2W 

-- --- 

-0.8718 

-0.87 18 

1.4017 

-- 
0.25 

0.5 

0.75 

1 .o 

1.25 

1.5 

1.75 

2 .o 

0.76221 

0.57927 

0.45 179 

0.37519 

0.32780 

0.28219 

0.23498 

0.18799 

0.25 

0.5 

0.75 

1 .o 

1.25 

1.5 

1.75 

2 .o 

0.76227 

0.57902 

0.45050 

0.37582 

0.32910 

0.28203 

0.23503 

0.18802 

-T 

1.03205 

1.06409 

1.09614 

1.12818 

1.12934 

1.07797 

0.98755 

0.87179 

1 .O3205 

1.06410 

1.09615 

1.12821 

1.12941 

1.07799 

0.98758 

0.87 180 

1.03198 

1.06395 

1.09593 

1.12791 

1.12906 

1.07761 

0.98737 

0.87 187 

- I--

1.03203 

1.06407 

1.09610 

1.12814 

1.12933 

1.07790 

0.98748 

0.87180 

(t 1 

0.76228 

0.57905 

0.4503 1 

0.37500 

0.32905 

0.28205 

0.23504 

0.18803 

0.76229 

0.57906 

0.45032 

0.37607 

0.32906 

0.28208 

0.23504 

0.18803 

Table 4.2 
-64- 

determines the feedback law of the Nth approxima- r[oo which together with 

tion. At the mesh-points, we simply have 

Example 4.2. This is the problem of minimizing 

subject to 

;r(t) = x(t) + x(t-1) + u(t), t > 0, - 

x(0) = 0, xo(t) = sinnt, -1 < t < 0. -- 

of the 

when the original system is 

Table 4.3 gives the optimal costs JN = <(x(O),x0),n N (x(0),xo)> 

M 

approximating systems and the costs 

controlled by u . J(iN) 

^N 

N JN J (2) 

4 0.321 17 0.32143 

8 I l6 

0.32 1 38 

0.32142 

0.32143 

0.32143 

Table 4.3 
-65- 

0.6349 

0.8700 

1.2544 

1.8518 

2.7 507 

N Table 4.4 presents the feedback gains I:o and fll(s) at the meshpoints 

-- j , j = 0,...,4. 

4 

0.6365 0.6369 

0.8801 0.8838 

1.2745 1.2803 

1.8812 1.8895 

2.7930 2.8050 

2.8083 2.8092 2.8094 
-66- 

0. 

0.25 

0.5 

0.75 

1 .o 

1.25 

1.5 

1.75 

2 .o 

2.25 

2.5 

2.75 

3 .O 

,. \ X 

t. 

- , 

0.25 

0.5 

0.75 

1 .o 

1.25 

1.5 

1.75 

2 .o 

2.25 

2.5 

2.75 

0.86968 

0.64873 

0.49572 

0.36350 

0.24664 

0.16200 

0.11027 

0.08030 

0.06013 

0.04349 

0.02988 

0.02002 

0.01377 

-- 

0.11276 

0.05337 

-0.06642 

-0.10870 

-0.06170 

-0.01 396 

0.00758 

0 .OO 180 

-0.00 78 7 

-0 .O 1034 

-0.00648 

-0 .OO178 

0.86836 

0.64888 

0.49647 

0.36395 

0.24624 

0.16153 

0.10997 

0.08022 

0.0601 5 

0.04347 

0.02982 

0.01996 

0.01373 

jr8(t> 

0.1 1260 

0.05332 

-0.066 28 

-0.10849 

-0.06 160 

-0.01 396 

0.00753 

0.00178 

-0.00784 

-0.01030 

-0.00646 

-0.001 78 

! 

- - 

P(t> 

0.86818 

0.64891 

0.49657 

0.36400 

0.246 18 

0.16147 

0.10993 

0.08021 

0.06015 

0.04347 

0.02982 

0.01995 

0.01372 

-I__ 

P(t) 

0.11258 

0.05332 

-0.06626 

-0.10846 

-0.06158 

-0.01 397 

0.09752 

0 .0017&? 

-0.00784 

-0.01029 

-0.00646 

-0.001 78 

I 
-67- 

Example 4.3. A simplified model for a wind tunnel at NASA's Langley Research 

Center is given by (see [4]) 

0 

0 

2 

-w - :I 2sw 

0 ka 0 

0 0 0 

0 0 0 

x(t - 0.33) 

x(0) = col(-0.1,8.547,0) 3 xo(t), -0.33 < t < 0, where k = -0.0117, -- 

5 = 0.8, o = 6.0, -= ' 1.964. One wants to minimize 

a 

m4 2 2 J(u) = I [lo x,(t) + u(t) ]dt 

0 

subject to (4.36). 

The true solution of the problem was given in [16]. Note that the 

matrix Wo weighting the contribution of the state trajectory to the costs is 

singular in this example, in contrast to the assumptions in Theorem 3.5. However, the piecewise linear approximation scheme produced the following values 

for J(iN> and JN. 
-68- 

N JN I __ 4 136.4490 136.1785 

8 136.4490 136.2921 

16 136.4493 136.3486 

J(u) 136.4049 

Table 4.6 

N 

4 

8 

16 

00 

8677.02161 -9.81498 -0.94768 

-9.8 1498 0.0 1850 0.00186 

-0.94768 0.00186 0.00019 

8677.02502 -9.8 1503 -0.94768 

-9.81 503 0.01851 0.00186 

-0.94768 0.00186 0.00019 

8677.02551 -9.8 1504 -0,94768 

-9.8 1504 0.01851 0.00186 

-0.94768 0.00186 0.0001 9 

~~ 

8677.02405 -9.81505 -0.94768 

-9.8 1505 0.01851 0.00186 

-0.94768 0.00186 0.00019 

Table 4.7 

In Table 4.7, we compare the first block of the Riccati matrix TIN with the 

ll?-component of JT. The matrices !~,(t) and nl(t), N 
- ~ ____~ ~~_____ 

-h = -0.33 < t < 0, have -- 

-43.83755 

0.06653 

0.00641 

-43.84694 

0.06633 

0.00640 

-43.84929 

0.06631 

0.00640 

-43.85008 

0.06632 

0.0064 1 

mzero entries only in th 

-46.36726 

0.06358 

0.006 14 

- 

-46.37700 

0.06359 

0.006 14 

-46.37952 

0.06360 

0.00614 

-46.38034 

0.06360 

0.00614 

are shown in Table 4.8 for t = - 2;- jh , j = 0,---,4. 

Ry(- p) 

I 

0.00669 

-41.39710 

0.06917 

0.00668 

7- 

ill(- p) 

141.39647 

0.06917 

nl(- 1;- jh) I 0.06915 

t 41.39721 

- E) 0.06917 4 1 

0.00668 t- -41.39721 

I o*oo668 

AQCNOWLEDGEMENT 

ir second columns, w..-ch 

3 

-48.97855 

0.06095 

0.00589 

-48.98892 

0.06097 

0.00589 

-48.991 57 

0.06098 

0.00589 

-48.99246 

0.06098 

0.00589 

4 

-51.67634 

0.05845 

0.00564 

-51.68730 

0.05847 

0.00565 

-51.69010 

0.05847 

0.00565 

-51.69103 

0.05847 

0.00565 

I want to thank Professor F. Kappel for numerous discussions, valuable 

hints, and the extensive care concerning my work on this paper. 
-70- 

REFERENCES 

[l] H. T. Ranks and J. A. Burns, "Hereditary control problems: Numerical 

methods based on averaging approximation," SIAM J. Control Optim., Vol. 

16, 1978, pp. 169-208. 

[2] H. T. Banks, J. A. Burns, E. M. Cliff, and P. R. Thrift, "Numerical 

solutions OF hereditary control problems via an approximation technique," Brown University, LCDS Technical Report 15-6, 1975, Providence, 

Rhode Island. 

[3] H. T. Ranks and F. Kappel, "Spline approximations for functional 

differential equations," J. Differential Equations, Vol. 34, 1979, pp. 

496-522. 

[4] H. T. Banks, C,. I. Rosen, and K. Ito, "A spline based technique for 

computing Riccati operators and feedback controls in regulator problems 

for delay equations," SIAM J. Sci. Statist. Comput., Vol. 5, 1984, pp. 

830-855. 

[5] J. A. Burns and E. M. Cliff, "Methods for approximating solutions to 

linear hereditary quadratic optimal control problems," IEEE Trans. 

Automatic Control, Vol. 23, 1978, pp. 21-36. 

[6] R. F. Curtain and A. J. Pritchard, Infinite Dimensional JAnear Systems 
-7 1- 

Theory, Springer-Verlag, Berlin, 1978. 

[7] R. Datko, "Uniform asymptotic stability of evolutionary processes in a 

Banach space," SIAM J. Math. Anal,, - Vol. 3, 1972, pp. 428-445. 

[8] J. S. Gibson, "The Riccati integral equations for optimal control 

problems in Hilbert spaces," SIAM J. Control Opt., Vol. 17, 1979, pp. 

537-565. 

[9] J. S. Gibson, "Linear quadratic optimal control of hereditary 

differential systems: infinite dimensional Riccati equations and 

numerical approximations," SIAM J. Control Opt., Vol. 21, 1983, pp. 95- 

139. 

[lo] E. Hewitt and K. Stromberg, Real and Abstract Analysis, SpringerVerlag, Berlin, 1969. 

[ 111 K. Ito and R. Teglas, "Legendre-tau approximation for functional 

differential equations, Part 11: The linear quadratic optimal control 

problem," SIAM J. Control Opt., to appear. 

[ 121 K. Ito, "Legendre-tau approximation for functional differential equations, Part 111: Eigenvalue approximations and uniform stability," in 

Distributed Parameter Systems, F. Kappel, K. Kunisch, W. SchaPPacher 

(eds.), Springer-Verlag, Heidelberg, 1985, PP. 191-2120 
-72- 

[13] F. Kappel and G. Propst, "Approximation of feedback controls for delay 

systems using Legendre polynomials," Confer. Sem. Mat. Univ. Bari, Vol. 

201, 1984, pp. 1-36. 

[14] F. Kappel and D. Salamon, "Spline approximations for retarded systems 

and the Riccati equation," SIAM J. Control Opt., to appear. 

[ 151 T. Kato, Peturbation Theory for Linear Operators, Springer-Verlag, 

Berlin, 1980. 

[16] A. Manit€us and H. Tran, "Numerical simulation of a nonlinear feedback 

controller for a wind tunnel model involving a time delay," Optimal 

Control Appl. Methods, Vol. 7, 1986, pp. 19-39. 

[17] A. Pazy, Semigroups of Linear Operators and Applications to Partial 

Differential Equations, Springer-Verlag, New York, 1983. 

[18] D. L. Russell, Mathematics of Finite Dimensional Control Systems, 

Theory and Design, Marcel Dekker, New York, 1979. 

[19] D. Salamon, "Structure and stability of finite dimensional approximations for Eunctional differential equations," SIAM J. Control Opt., 

Vole 23, 1985, pp. 928-951. 

[20] M. H. Schultz, Spline Analysis, Prentice-Hall, Englewood Cliffs, New 

Jersey, 1973. 
Standard Bibliographic Page 

1. Report No. NASA CR-178260 

ICASE Report No. 87-11 

2. Government Accession No. 

~ 

1. Title and Subtitle 

PIECEWISE LINEAR APPROXIMATION FOR HEREDITARY 

CONTROL PROBLEMS 

17. Key Words (Suggested by Authors(s)) 

hereditary control problem, piecewise 

linear approximation, uniform stability 

7. Author(s) 

Georg Propst 

18. Distribution Statement 

64 - Numerical Analysis 

66 - Systems Analysis 

Unclassified - unlimited 

3. Performing Organization Name and Addre s 

Institute for Computer Applications in Science 

Mail Stop 132C, NASA Langley Research Center 

Hampton, VA 23665-5225 

12. Sponsoring Agency Name and Address 

and Engineering 

19. Security Classif.(of this report) 

Unc 1 as s i E ied 

National Aeronautics and Space Administration 

Washington, D.C. 20546 

15. Supplementary Notes 

20. Security Classif.(of this page) 21. No. of Pages 22. Price 

Unclassified 74 A0 4 

3. Recipient's Catalog No. 

5. Report Date 

February 1987 

6. Performing Organization Code 

8. Performing Organization Report No. 

87-1 1 

10. Work Unit No. 

11. Contr t 

N ASY- fs8w~ NRAS 1 - 1 8 1 0 7 

~ 

13. Type of Report and Period Covered 

Contractor Report 

14. Sponsoring Agency Code 

505-90-21-01 

Langley Technical Monitor: 

J. C. South 

Submitted to SIAM 3. Control 

Optim. 

Final Report 

16. Abstract 

This paper presents finite dimensional approximations for linear retarded 

functional differential equations by use of discontinuous piecewise linear 

functions. The approximation scheme is applied to optimal control problems when 

a quadratic cost integral has to be minimized subject to the controlled retarded 

system. It is shown that the approximate optimal feedback operators converge to 

the true ones both in 'case the cost integral ranges over a finite time interval 

as well as in the case it ranges over an infinite time interval. The arguments 

in the latter case rely on the fact that the piecewise linear approximations to 

stable systems are stable in a uniform sense. This feature is establ shed using 

a vector-component stability criterion in the state space x L,' and the 

favorable eigenvalue behavior of the piecewise linear approximations. 

For sale by the National Technical Information Service, Springfield, Virginia 22161 

NASA-Langley, 1987