Numerik IV 001

Numerik IV Fritz Colonius 24. Juli 2006

ii

Inhaltsverzeichnis Vorwort

v

1 Einleitung

1

2 Lineare Kontrollsysteme 11 2.1 Kontrollierbarkeit bei unbeschränkten Kontrollen . . . . . . . 11 2.2 Lineare Systeme mit beschränkten Kontrollen . . . . . . . . . 18 2.3 Feedback-Stabilisierung . . . . . . . . . . . . . . . . . . . . . . 23 3 Nichtlineare Kontrollsysteme 33 3.1 Lokale Akzessibilität . . . . . . . . . . . . . . . . . . . . . . . 33 3.2 Kontrollmengen . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4 Der Kontroll‡uss 57 4.1 Der Shift auf U . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.2 Der Kontroll‡uss . . . . . . . . . . . . . . . . . . . . . . . . . 62 5 Berechnung von Erreichbarkeitsmengen 5.1 Relative Globale Attraktoren . . . . . . . . 5.2 Grundalgorithmus zur Subdivision . . . . . . 5.3 Zeitdiskretisierung . . . . . . . . . . . . . . 5.4 Zeitdiskretisierung und Kettenerreichbarkeit 5.5 Graphen-Algorithmus . . . . . . . . . . . . . 5.6 Varianten des Subdivisions-Algorithmus . . Literaturverzeichnis

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

71 71 78 81 82 83 89 93

iii

iv

INHALTSVERZEICHNIS

Vorwort Dies ist das Skript der im Sommersemester 2006 am Institut für Mathematik der Universität Augsburg gehaltenen Vorlesung. Die im Literaturverzeichnis angegebenen Quellen werden ohne weitere Kennzeichnung verwendet. Das Ziel dieser Vorlesung ist es, eine Einführung in Probleme der Mathematischen Kontrolltheorie zugeben, die zu einigen aktuellen analytischen und numerischen Problemen hinführt. Dabei stehen die Beziehungen zur Dynamik im Vordergrund.

v

vi

VORWORT

Kapitel 1 Einleitung Diese Vorlesung gibt eine Einführung in die Kontrolltheorie und damit zusammenhängende numerische Probleme. Genauer handelt es sich um Probleme der Kontrolle von Systemen, die durch gewöhnliche Di¤erentialgleichungen beschrieben werden. Eine Standardreferenz hierfür ist das Buch von Eduardo Sontag [19]; ferner D. Hinrichsen/A.J. Pritchard [10], S. Sastry [18], und speziell für nichtlineare Kontrollsysteme sind auch insbesondere die Bücher V. Jurdjevic [13], Nijmeijer/Van der Schaft [16] und Isidori [11] zu nennen. Zunächst werden wir ein einfaches und klassisches Beispiel aus der Mechanik diskutieren, das mathematische Pendel oder, moderner interpretiert, die Bewegung eines Roboterarms. Dabei treten bereits eine Reihe typischer Probleme und Konzepte der Kontrolltheorie auf. Eine schöne Herleitung der Di¤erentialgleichung für das Pendel …ndet man in Aulbach [2, Beispiel 1.3.3], vergleiche auch Sontag [19, Chapter 1]. Wir betrachten ein Pendel, das aus einer masselosen starren Stange und einem daran befestigten Massepunkt besteht. Das Pendel soll sich unter dem Ein‡uss der senkrecht nach unten wirkenden Schwerkraft be…nden. Wir bezeichnen die Winkelposition des Pendels mit ' 2 [0; 2 ), so dass '(t) _ die Winkelgeschwindigkeit und '(t) • die Winkelbeschleunigung zum Zeitpunkt t bezeichnet. Die Lage, Geschwindigkeit und Beschleunigung des Punktes M des sich auf dem Kreis mit Radius l bewegenden Punktes erhält man einfach durch Multiplikation von '(t); '(t) _ und '(t) • mit l. Zur Herleitung einer Di¤erentialgleichung für ' benutzen wir das Newtonsche Kraftgesetz: Kraft = Masse mal Beschleunigung zu jedem Zeitpunkt t. Hier ist Masse mal Beschleunigung gegeben durch ml'(t): • 1

2

KAPITEL 1. EINLEITUNG

Die zur Zeit t wirkende Kraft ist die tangentiale Komponente der (nach unten gerichteten) Schwerkraft mg, also mg sin '(t): Darüberhinaus berücksichtigen wir eine Reibungskraft, die der momentanen Geschwindigkeit proportional und entgegengesetzt ist, also k '(t) _ mit einer Proportionalitätskonstanten k (dies ist eine stark vereinfachende Annahme! Die Modellierung von Reibungskräften ist sehr schwierig). Wir erhalten nach Newton also mg sin '(t)

k '(t) _ = ml'(t) •

oder

k g '_ sin '. lm l Wir nehmen jetzt zusätzlich an, dass ein Motor am Drehpunkt angebracht ist, der eine Kraft (oder ein Drehmoment) u(t) auf den Roboterarm ausübt. Dann modi…ziert sich die Gleichung zu '(t) • =

'(t) • =

k '_ m

g sin ' + u(t). l

In dieser Gleichung entspricht ' = 0 dem senkrecht nach unten hängenden Roboterarm und ' = dem senkrecht nach oben stehenden Roboterarm. Wir interessieren uns für die Position ' = . Der Einfachheit halber normieren wir die Konstanten m = g = l = 1, so dass '(t) • = Setzen wir # = '

k '_

sin ' + u(t).

, so ändern sich die Gleichungen zu • = #(t)

_ k #(t)

sin[#(t) + ] + u(t):

Die Ruhelage in der senkrechten Position #(t) 0 mit Geschwindigkeit #_ 0 ist o¤enbar eine Lösung dieser Di¤erentialgleichung für u(t) 0. Aus o¤ensichtlichen physikalischen Gründen ist diese Ruhelage bei u = 0 “instabil”. Unser Kontrollproblem (Steuerungs- oder Regelungsproblem) besteht darin, kleine Abweichungen aus dieser Ruhelage durch geeignete Wahl von u zu korrigieren. Der Sinus-Term ist nichtlinear; wir können aber ein lineares System

3 herleiten, indem wir für “kleine” Abweichungen ' sin ' (' ) benutzen, oder für # nahe 0 sin[# + ]

die Approximation

#:

Man erhält • + k #(t) _ #(t)

#(t) = u(t):

Schreiben wir _ x1 (t) = #(t) und x2 (t) = #(t) so erhält man x_ 1 = x2 x_ 2 = kx2 + x1 + u(t) oder x_ 1 x_ 2

0 1

=

1 k

x1 x2

0 1

+

u(t):

Wir erwarten natürlich, dass diese Gleichung das Verhalten des Ausgangsystems in der Nähe der (oberen) Ruhelage annähernd beschreibt. Dieses Vorgehen (Linearisierung des Systems) werden wir später mathematisch analysieren. Jetzt beschränken wir uns auf die Analyse der linearisierten Gleichung. Unser Ziel ist es, das System durch geeignete Wahl von u für (x1 ; x2 ) 6= (0; 0) möglichst schnell und mit möglichst wenig Oszillationen wieder nach (0; 0) zu bringen. Ansatz: u= x1 mit > 0. Dies nennt man ein proportionales Feedback mit dem “Feedback-Gain” . Einsetzen liefert x_ 1 x_ 2

=

0 1

1 k

x1 x2

+

0 1

(

x1 x2

:

x1 )

oder x_ 1 x_ 2

0

=

1 k

1

Zur Vereinfachung nehmen wir jetzt an, dass k = 0 gilt. Dann x_ 1 x_ 2

=

0 1

1 0

oder #• = (1

)#:

x1 x2

4

KAPITEL 1. EINLEITUNG

Die Eigenwerte von

0

1 0

1

sind die Lösungen von

z2 + für

1 = 0;

> 1 also z1;2 =

i

p

1:

Daher sind für > 1 die Lösungen Ellipsen. Für betragsmäß ig gegen 1, auß er denen mit p x1 (0) 1

x2 (0) =

< 1 gehen alle Lösungen

:

Für = 1 sind alle Anfangswerte mit x2 (0) = 0 Ruhelagen (also '(0) _ =0 liefert '(t) _ = 0 für alle t). Wir sehen also, dass proportionales Feedback hier nicht funktioniert. Wir werden einen “Dämpfungsterm”hinzufügen: Ansatz: u(t) = x1 (t) x2 (t) mit > 1 und > 1. Dies ist ein PD-Feedback (proportional-derivative). Man beachte, dass zur Implementierung dieses Feedbacks nicht nur der momentane Zustand x1 (t) = #(t), sondern auch seine Geschwindigkeit x2 (t) = _ #(t) gemessen werden muss. Einsetzen liefert #• + #_ + ( 1)# = 0 oder x_ 1 x_ 2

0

=

1

x1 x2

1

Die zugehörigen Eigenwerte sind z1;2 =

2

1p 2

2

4(

1):

Ist 2 4( 1) 0, so ist der Realteil der Eigenwerte gleich 2 < 0, die Lösungen konvergieren dann für t ! 1 gegen 0. Will man auch Oszillationen um den Nullpunkt vermeiden, so muss 2 4( 1) > 0 gewählt werden; auch dann haben beide Eigenwerte negativen Realteil. Das PD-Feedback stabilisiert also das linearisierte System; wir werden später sehen, dass es in einer Umgebung der Ruhelage auch für das nichtli-

5 neare Systeme funktioniert. Dies ist ein Beispiel eines allgemeinen Linearisierungsprinzips in der Kontrolltheorie: Designs, die auf Linearisierung beruhen, funktionieren lokal für das nichtlineare System.

Dieses Prinzip, das jeweils unter entsprechenden Voraussetzungen zu präzisieren ist, liefert die Rechtfertigung für das intensive Studium linearer Kontrollsysteme. Unser obige PD-Kontrolle hat die Form eines Feedbacks, ist also vom augenblicklichen Zustand x des Systems abhängig. Eine Alternative sind zeitabhängige Kontrollen u, die nur von t abhängen, nicht von x. Die folgende Überlegung demonstriert, warum man bei Stabilisierungsproblemen Feedback verwenden muss. Betrachte das linearisierte System (mit k = 0) • #(t)

#(t) = u(t):

mit festem Anfangswert _ #(0) = 1; #(0) =

2:

Die Steuerung u(t) = 3 e

2t

liefert die Lösung #(t) = e

2t

;

wie man durch Einsetzen nachprüft: #_ =

2e

2t

; #• = 4e

2t

also _ #(0) = 1; #(0) =

• 2; #(t)

#(t) = 4e

2t

e

2t

= 3e

2t

= u(t):

Die Lösung konvergiert dann für t ! 1 gegen (0; 0)T . Ist der Anfangswert jedoch _ #(0) = 1; #(0) = 2 + ", mit " 6= 0; : so führt Anwendung derselben Steuerung zu unbeschränkten Lösungen.

6

KAPITEL 1. EINLEITUNG

(Übungsaufgabe! Hinweis: Beachte, dass d d sinh t = cosh t und cosh t = sinh t:) dt dt Kleine Änderungen oder Ungenauigkeiten in den Startwerten führen also dazu, dass die (vorab berechnete) Steuerung wertlos für Stabilisierung wird. Bei der PD-Regelung tritt dieses Problem, wie oben gesehen, nicht auf. Das linearisierte Kontrollsystem lässt sich in der Form x(t) _ = Ax(t) + Bu(t) mit x=

x1 x2

; A=

0 1 1 0

; B=

0 1

schreiben. Kontrollsysteme dieser Form mit konstanten Matrizen A 2 Rn n und B 2 Rn m heiß en lineare autonome (oder zeitinvariante) Kontrollsysteme von endlicher Dimension in stetiger Zeit (dies bedeutet implizit, das es auch nichtlineare und nichtautonome Kontrollsysteme und solche von unendlicher Dimension und solche in diskreter Zeit gibt). In dieser Vorlesung werden wir uns mit linearen und nichtlinearen Kontrollsystemen der Form x(t) _ = f (x(t); u(t)) von endlicher Dimension beschäftigen. Für das obige lineare Kontrollsystem haben wir ein Feedback der Form x1 x2

u = Fx =

konstruiert. Einsetzen in das open-loop System x_ = Ax + Bu ergibt das closed-loop oder Feedback-System x_ = (A + BF )x: Bei geeigneter Wahl von F haben alle Eigenwerte, also die Nullstellen des charakteristischen Polynoms A+BF (z)

= det[zI

(A + BF )];

negative Realteile. Dies garantiert, dass alle Lösungen für t ! 1 gegen 0 laufen.

7 Dies führt auf das allgemeine Problem: Gegeben seien Matrizen A 2 Rn n und B 2 Rn m ; charakterisiere die möglichen Mengen von Eigenwerten, wenn F alle Matrizen in Rm n durchläuft. Der für die lineare Systemtheorie zentrale Polverschiebungsatz, löst dieses Problem. Häu…g ist nicht der gesamte Zustand des Systems einer Messung zugänglich und damit für ein Feedback verwendbar. Während das PD-Feedback für das invertierte Pendel zum Beispiel den gesamten Zustand x = (x1 ; x2 ) = _ des Systems verwendet, benutzt das P -Feedback nur x1 = #. De…niert (#; #) man hier C : R2 ! R,

x1 x2

7! x1 , also in Matrizendarstellung C =

1 0

;

so erhält man ein lineares System mit Output x_ = Ax + Bu; y = Cx: Eine lineares Feedback der Form u = Ky = KCx mit einer Matrix K der entsprechenden Dimension, wird als statisches Output-Feedback bezeichnet. Feedbacks dieser Form sind meist nicht geeignet (wie oben gesehen), das Stabilisierungsproblem zu lösen. Stattdessen führt jedoch häu…g ein dynamisches Output-Feedback zum Erfolg: Man benutzt eine Di¤erentialgleichung (einen dynamischen Beobachter), um aus dem Output den Zustand zu schätzen, und verwendet dann diese Schätzung im Feedback. Diese Konstruktion ist sogar nützlich, wenn alle Zustandsvariablen im Feedback zur Verfügung stehen, jedoch Störungen auf das System wirken. Als Illustration soll wieder das linearisierte invertierte Pendel dienen, auf das eine konstante additive Störung (zum Beispiel Wind) d(t) e 2 R wirkt: • #(t) #(t) = u(t) + e. Eine PD-Kontrolle u=

#

_ #;

;

> 0,

stabilisiert das System für e = 0. Ist jedoch e 6= 0, so gilt für keine Lösung des Feedback-Systems • #(t)

_ = e, #(t) + #(t) + #(t)

8

KAPITEL 1. EINLEITUNG

dass #(t) ! 0 für t ! 1. Dies liest man aus der Lösungsformel für diese _ T ist Gleichung ab: Mit x = (x1 ; x2 )T = (#; #) x_ 1 (t) = x2 (t) x_ 2 (t) = (1 )x1

x2 ;

das heiß t x_ 1 x_ 2

0

=

1

x1 x2

1

e 0

+

oder x_ = Gx + e mit G=

0

1

0 e

; e=

1

Die Variation-der-Parameter-Formel liefert Z t Gt x(t) = e x(0) + eG(t

s)

:

e ds:

0

Da das obige PF-Feedback das homogene System stabilisiert, gilt eGt x(0) ! 0 für t ! 1:

Rt Weil aber die zweite Komponente von 0 eG(t s) ds für t ! 1 nicht gegen 0 geht (warum?), konvergiert auch x(t) nicht gegen 0. Zur Konstruktion eines Feedbacks, das die Störung e kompensiert, fassen wir e als eine zusätzliche (nicht messbare) Zustandsvariable auf, die durch die triviale Di¤erentialgleichung e_ = 0 beschrieben wird. Das open-loop-System hat also die Form e(t) _ = 0; x_ 1 (t) = x2 (t); x_ 2 (t) = x1 (t) + e(t) + u(t): Nach den obigen Bemerkungen liegt es dann nahe, ein dynamisches Zustandsfeedback zu verwenden. Wähle mit ; ; 2 R als Feedback u=

x1

x2

wobei x0 eine Lösung von x_ 0 = x1

x0 ;

9 ist. In der Tat gibt es Zahlen ; von

;

2 R, so dass für alle e 2 R die Lösungen

x_ 0 (t) = x1 (t); x_ 1 (t) = x2 (t); x_ 2 (t) = x0 (t) + (1

)x1 (t)

x2 (t) + e

für t ! 1 gegen ( e ; 0; 0) konvergieren. Die Komponenten x1 = # und x2 = #_ konvergieren, wie gewünscht, für t ! 1 also gegen 0. In den ursprünglichen Variablen ist die Kontrolle gegeben durch Z t _ u(t) = # # #(s) ds 0

Dies ist auch als PID-Regler (proportional-integral-derivative) bekannt, der in Anwendungen von Ingenieuren am häu…gsten verwendete Regler. Teil dieses Reglers ist die Di¤erentialgleichung x_ 0 = x1 .

10

KAPITEL 1. EINLEITUNG

Kapitel 2 Lineare Kontrollsysteme In diesem Kapitel werden Kontrollierbarkeitseigenschaften für die einfachste Klasse von Kontrollsystemen, lineare Kontrollsysteme, analysiert. Im ersten Abschnitt werden wir keine Beschränkungen an die Kontrollfunktionen fordern, so dass wir mit Hilfsmitteln der linearen Algebra auskommen. Im zweiten Abschnitt werden wir den Wertebereich der Kontrollfunktionen einschränken und den wichtigen Begri¤ der Kontrollmengen einführen. Lineare Kontrolltheorie ist ein riesiges mathematisches Gebiet, mit hoher Anwendungsrelevanz in den Ingenieurwissenschaften. Es wird im Folgenden nur gestreift. Mehr Einsicht kann man zum Beispiel in Sontag [19] gewinnen.

2.1

Kontrollierbarkeit bei unbeschränkten Kontrollen

Die einfachsten Kontrollsysteme sind lineare Systeme. Sie haben die Form x(t) _ = Ax(t) + Bu(t)

(2.1)

mit Matrizen A 2 Rn n ; B 2 Rn m ; die Funktionen u : R ! Rm heiß en Kontroll- oder Steuerfunktionen, und können frei in einer Menge U zulässiger Kontrollfunktionen gewählt werden. Von Interesse ist zunächst das Verhalten des Systems unter beliebigen Kontrollfunktionen. Die Punkte x 2 Rn werden als Zustände des Systems bezeichnet. Natürlich kann man A und B auch als lineare Abbildungen auf Rn bzw. von Rm nach Rn au¤assen. Die Lösungen '(t; t0 ; x0 ; u) von (2.1) zum Anfangswert x(t0 ) = x0 2 n R sind (nach der Variation der Konstanten-Formel oder wie man leicht 11

12

KAPITEL 2. LINEARE KONTROLLSYSTEME

nachrechnet) gegeben durch A(t t0 )

'(t; t0 ; x0 ; u) = e

x0 +

Z

t

eA(t

t0

s)

Bu(s) ds; t 2 R:

(2.2)

Dieses Integral ist natürlich nicht für alle Funktionen u : R ! Rm wohlde…niert. O¤enbar reicht es, dass sie Lebesgue-integrierbar auf jedem Intervall [0; t] sind. Dann ist auch das Produkt mit der beschränkten, stetigen Funktion eA(t s) B; s 2 [0; t], Lebesgue-integrierbar. Manchmal verlangt man auch mehr Regularität, zum Beispiel, dass sie stetig, stückweise stetig, stückweise konstant, oder unendlich oft di¤erenzierbar sind. Standardvoraussetzungen an die Kontrollfunktionen sind, dass U einer der folgenden Funktionenräume ist: L1;loc (R; Rm ) = fu : R ! Rm ; L1 (R; Rm ) = fu : R ! Rm ; L1;loc (R; Rm ) = fu : R ! Rm ; Cpc (R; Rm ) = fu : R ! Rm ;

auf jedem kompakten Intervall integrierbarg essentiell beschränktg auf jedem komp. Intervall ess. beschränktg u ist stückweise stetigg

Die Funktionen in L1;loc nennt man auch lokal integrierbar. Man beachte, dass die Wahl von U = L1 (R; Rm g bezüglich des Verhaltens für jtj ! 1 einschränkend ist. Natürlich kann man auch weitere Anforderungen an die Kontrollfunktionen stellen, zum Beispiel, dass ihre Werte in einer vorgegebenen Menge U Rm liegen, also u(t) 2 U für fast alle t 2 R (zum Beispiel ju(t)j 1). Wir werden diese Situation später diskutieren (dies führt jedoch schon über den Bereich der linearen Kontrolltheorie hinaus, die zunächst nur eine Theorie für Matrizenpaare (A; B) ist). Wir werden in diesem Kapitel, soweit nichts anderes gesagt wird, U = Cpc (R; Rm ) wählen. Es wird sich herausstellen, dass dabei nichts Wesentliches verloren geht. Ist in (2.2) die Anfangszeit t0 = 0, so bezeichnen wir die Lösung (oder Trajektorie) auch häu…g mit '(t; x0 ; u); t 2 R. O¤enbar gilt wegen (2.2) (setze im Integral s := s t0 ) Z t A(t t0 ) eA(t s) Bu(s) ds '(t; t0 ; x0 ; u) = e x0 + t Z 0t t0 eA(t s) Bu(s + t0 ) ds = eA(t t0 ) x0 + 0

= '(t

t0 ; x0 ; u( + t0 ));

2.1. KONTROLLIERBARKEIT BEI UNBESCHRÄNKTEN KONTROLLEN13 mit der verschobenen Kontrollfunktion u( + t0 ))(s) = u(s + t0 )); s0 = u (s + t0 ) ; s 2 R. Eine grundlegende Frage an Kontrollsysteme sind Kontrollierbarkeitsoder Erreichbarkeitsfragen: Gegeben ein Startpunkt x0 , welche Punkte x1 2 Rn kann man mit zulässigen Kontrollfunktionen erreichen? De…nition 1 Ein Zustand x0 2 Rn heiß t kontrollierbar (oder steuerbar) n nach x1 2 R zur Zeit T 0, falls eine Kontrolle u 2 U existiert mit '(T; x0 ; u) = x1 . Der Zustand x1 heiß t dann auch erreichbar von x0 zur Zeit T. Wir de…nieren die Menge der Punkte, die von x0 in der Zeit T erreichbar sind, als OT+ (x0 ) = fx1 2 Rn ; es gibt u 2 U mit x1 = '(t; x0 ; u)g; und die Menge der Punkte, die in der Zeit T nach x1 gesteuert (oder kontrolliert) werden können, als OT (x1 ) = fx0 2 Rn ; es gibt u 2 U mit x1 = '(t; x0 ; u)g: O¤enbar ist x 2 O+ (x0 ) äquivalent zu x0 2 OT (x). Speziell schreiben wir in diesem Kapitel auch [ R(T ) = OT+ (0) und R = R(T ); T 0

C(T ) = OT (0) und C =

[

T 0

C(T ):

Von besonderem Interesse sind Systeme, bei denen jeder Punkt erreichbar oder kontrollierbar ist. Diese werden wir jetzt charakterisieren. Zunächst zeigen wir das folgende einfache Lemma. Lemma 2 Sei S > T > 0. Dann gilt: (i) R(T ) R(S); (ii) R(S) = R(T ) ) R(T ) = R(t) für alle t T (iii) R(T ) und R sind Unterräume. Beweis. (i) Für y 2 R(T ) existiert u 2 U mit y = '(T; 0; u). De…niere v 2 U durch 0 für t 2 [0; S T ) v(t) = u(t S + T ) für t 2 [S T; S] Dann ist y = '(S; 0; v) 2 R(S). („man bleibt im Nullpunkt so lange wie nötig sitzen.”)

14

KAPITEL 2. LINEARE KONTROLLSYSTEME

(iii) Seien y1 ; y2 2 R(T ). Dann existieren Kontrollen u1 ; u2 2 U mit Z T yi = '(T; 0; u) = eA(T s) Bui (s) ds für i = 1; 2 0

und damit (wegen der Linearität in u) Z T y1 + y2 = eA(T s) B [u1 (s) + u2 (s)] ds = '(t; 0; u1 + u2 ): 0

Wegen der Linearität in u gilt für 2 R, dass y1 = '(T; y1 ; u) 2 R(T ). Daher ist R(T ) ein Untervektorraum. Seien nun y1 ; y2 2 R. Mit (i) können wir annehmen, dass y1 ; y2 2 R(T ) für ein T > 0, also y1 + y2 2 R(T ) R. (ii) Es gelte R(S) = R(T ). Für x 2 R(2S T ) existiert u 2 U mit Z 2S T x = '(2S T; 0; u) = eA(2S T s) Bu(s) ds: 0

Weil '(S; 0; u) 2 R(S) = R(T ), existiert v 2 U mit Z T eA(T s) Bv(s) ds: '(S; 0; u) = '(T; 0; v) = 0

(„wir sparen die Zeit S

T ein.”) De…niere w 2 U durch

w(t) =

v(t) für t 2 [0; T ) : u(t T + S) für t 2 [T; S]

Dann ist (wegen der Zeitinvarianz) Z T Z S A(S s) '(S; 0; w) = e Bw(s) ds + eA(S s) Bw(s) ds 0 T Z T Z S A(S T ) A(T s) =e e Bv(s) ds + eA(S s) Bu(s T + S) ds 0 T Z T Z 2S T = eA(S T ) eA(S s) Bu(s) ds + eA(2S T s) Bu(s) ds 0 S Z 2S T Z T eA(2S T s) Bu(s) ds + eA(2S T s) Bu(s) ds = S

0

= '(2S

T; 0; u) = x

(hier haben wir '(S; 0; u) = '(T; 0; v) und die Transformation s0 = s verwendet). Daher ist x 2 R(S) und es folgt R(2S

T ) = R(S).

T +S

2.1. KONTROLLIERBARKEIT BEI UNBESCHRÄNKTEN KONTROLLEN15 Durch Induktion erhält man R(nS T ) = R(S) für alle n 2 N. Mit (i) folgt R(t) = R(S) für alle t S. Weil R(T ) ein linearer Unterraum von Rn ist und (ii) in dem obigen Lemma gilt, folgt R(t) = R für alle t > 0. Ferner ist R = Rn genau dann wenn für alle x0 ; x1 2 Rn und alle t > 0 eine Kontrolle u 2 U existiert mit x1 = '(t; x0 ; u). In der Tat: Betrachte x1 '(t; x0 ; 0) 2 Rn = R(t). Dann existiert u 2 U mit x1

'(t; x0 ; 0) = '(t; 0; u);

also x1 = '(t; x0 ; 0) + '(t; 0; u) = '(t; x0 ; u):

(2.3)

Wir haben damit insbesondere gezeigt, dass hier Rn = Ot+ (x0 ) für ein x0 2 Rn ; t > 0; genau dann gilt, wenn es für alle x0 2 Rn und alle t > 0 gilt. Analoge Aussage gelten für C(T ) und C sowie Ot (x0 ). Wir werden jetzt R(t) charakterisieren. Lemma 3 Sei V Rn ein linearer Unterraum und A eine lineare Abbildung n auf R . Dann ist der kleinste A-invariante Unterraum, der V enthält, gegeben durch hA j V i = V + AV + ::: + An 1 V . Beweis. Die Menge der A-invarianten Unterräume, die V enthalten, ist nicht leer (Rn ist solch ein Unterraum) und der Durchschnitt von solchen Unterräumen ist wieder von diesem Typ, also existiert der kleinste Unterraum von diesem Typ. Wegen der A Invarianz folgt Ak V hA j V i für alle k 2 N, und daher gilt \ . Für die Umkehrung ist nur zu zeigen, dass V + AV + ::: + An 1 V A invariant ist. Das charakteristische Polynom A ist A) = z n + an 1 z n 1 + ::: + a1 z + a0 A (z) = det(zI mit Koe¢ zienten ai 2 R. Nach dem Satz von Cayley-Hamilton ist A (A)

= A n + a n 1 An

1

+ ::: + a1 A + a0 I = 0;

und daher An =

a n 1 An

1

:::

a1 A

a0 I:

Daraus folgt die A Invarianz von V + AV + ::: + An 1 V:

16

KAPITEL 2. LINEARE KONTROLLSYSTEME De…niere für t > 0 eine Matrix in Rn n durch Z t T Wt = eA BB T eA d 0

(hierbei bedeutet T Transposition einer Matrix). Diese Abbildung ist symmetrisch und positiv semide…nit, weil für x 2 Rn Z t Z t 2 T T T A T AT x Wt x = x e BB e x d = B T eA x d ; 0

0

wobei j j die euklidische Norm bezeichnet. Lemma 4 Für alle t > 0 ist hA j Im Bi = Im Wt . Beweis. Die Behauptung ist dazu äquivalent, dass für die orthogonalen Komplemente gilt: hA j Im Bi? = [Im Wt ]? . „ “: Sei x 2 hA j Im Bi? . Dann ist xT Ak B = für alle k = 0; 1; ::: und daher 1 X 1 T k T At x A B = 0 für alle t 0: x e B= k! k=0 Dann folgt xT Wt = 0, also x 2 [Im Wt ]? : „ “: Sei x 2 [Im Wt ]? für ein t > 0. Dann ist Z t 2 T T 0 = x Wt x = B T eA x d ; 0

und daher

xT eA B für alle Insbesondere ist für

(2.4)

0:

=0 xT B = 0:

Sukzessives Di¤erenzieren in (2.4) und Auswerten in

= 0 liefert

xT AB = 0 x T A2 B = 0 ::: xT An 1 B = 0: Insgesamt folgt, dass x senkrecht auf Im B + A Im B + ::: + An 1 Im B = hA j Im Bi steht. Der nächste Satz charakterisiert die Erreichbarkeitsmenge vom Ursprung.

2.1. KONTROLLIERBARKEIT BEI UNBESCHRÄNKTEN KONTROLLEN17 Satz 5 Für das System (2.1) gilt R = C = Im[B AB ::: An 1 B] = hA j Im Bi Beweis. Die letzte Gleichung folgt aus Lemma 3. Wir zeigen nur R(t) = hA j Im Bi, die Behauptung für C folgt analog. „ “: Für x 2 R gibt es u 2 U und t > 0 mit x = '(t; 0; u). Für alle 2 [0; t] ist A(T

e

)

1 X 1 k Bu( ) = A Bu( ) 2 hA j Im Bi , k! k=0

also auch (beachte die De…nition des Integrals!) Z t x= eA(T ) Bu( ) d 2 hA j Im Bi , 0

„ “: Sei x 2 hA j Im Bi. Nach Lemma 4 existiert z 2 Rn mit Z t T x = Wt z = eA BB T eA z d : 0

Für eine Kontrolle u 2 U mit T

u( ) = B T eA z für

2 [0; t]

ist dann '(t; 0; u) =

Z

0

= x;

t A

e Bu( ) d =

Z

t

T

eA BB T eA

d z

0

also x 2 R(t). Das folgende Korollar charakterisiert vollständige Kontrollierbarkeit direkt mit Hilfe der Matrizen A und B. Korollar 6 (Kalman-Kriterium) Für das System (2.1) gilt R = Rn genau dann, wenn der Rang der Erreichbarkeitsmatrix [B AB ::: An 1 B] gleich n ist. Das System (und auch das Matrizenpaar (A; B)) heiß t dann vollständig kontrollierbar. Beispiel 7 Die Gleichung des linearisierten Pendels (mit Dämpfung k ist '(t) • k '(t) _ '(t) = u(t)

0)

18

KAPITEL 2. LINEARE KONTROLLSYSTEME

oder mit x1 = ', x2 = '_ x_ 1 x_ 2

=

0 1 1 k

x1 x2

+

0 1

u(t)

Die Erreichbarkeitsmatrix mit n = 2 [B AB ] =

0 1 1

hat den Rang 2, das System ist also vollständig kontrollierbar. Bemerkung 8 Die vorangegangenen Beweise lassen sich genauso führen, wenn an Stelle von stetigen Kontrollfunktionen lokal integrierbare Kontrollfunktionen erlaubt sind. Insbesondere bleibt die Charakterisierung von Erreichbarkeitsmengen in Theorem 5 gültig.

2.2

Lineare Systeme mit beschränkten Kontrollen

In diesem Abschnitt betrachten wir lineare Systeme mit Kontrollbeschränkungen von folgendem Typ:

x_ = Ax + Bu(t) in Rn ; u 2 U = fu : R ! U; messbarg;

(2.5)

wobei U Rm konvex und kompakt ist mit 0 2 int U und A und B wie in (2.1) sind. Die Bezeichnungen für Erreichbarkeitsmengen etc. aus dem letzten Abschnitt übernehmen wir entsprechend für dieses System. Wir nehmen in diesem ganzen Abschnitt an, dass (A; B) kontrollierbar ist, das heiß t, die n 1 Kalman-Bedingung rg [B; AB; :::A B] = n gilt. Ist dies nicht erfüllt, so können wir in dem Kontrollierbarkeitsunterraum hA j Im Bi = Im [B; AB; :::An 1 B] arbeiten. Beispiel 7 (mit k > 0) überzeugt uns rasch, dass wir hier im allgemeinen keine vollständige Kontrollierbarkeit erwarten können. Stattdessen betrachten wir die folgendermaß en de…nierten Teilmengen vollständiger (approximativer) Kontrollierbarkeit.

2.2. LINEARE SYSTEME MIT BESCHRÄNKTEN KONTROLLEN

Abbildung 2.1: Phasenporträts für u = +1 und u =

19

1.

De…nition 9 Eine Teilmenge D des Zustandsraums Rn heiß t Kontrollmenge, falls gilt: (i) für alle x 2 D gibt es u 2 U mit '(t; x; u) 2 D für alle t 0; (ii) für alle x 2 D ist D clO+ (x); und D ist maximal mit diesen Eigenschaften. Die Maximalitätsbedingung bedeutet, dass jede Obermenge D0 die Eigenschaften (i) und (ii) erfüllt, mit D übereinstimmt.

D, die

Beispiel 10 Betrachte das zwei-dimensionale lineare Kontrollsystem x_ y_

=

1 0

0 1

x y

+

1 1

u(t);

u(t) 2 U = [ 1; 1]:

Die Lösungen sind x(t) y(t)

=

et x0 e t y0

+

Z

t

u(s)

0

et es

s t

ds:

Man sieht leicht (siehe Figur 2.1), dass hier eine eindeutige Kontrollmenge D existiert, und dass sie durch D = ( 1; 1) gegeben ist.

[ 1; 1]

20

KAPITEL 2. LINEARE KONTROLLSYSTEME

Wir diskutieren zunächst die folgende grundlegende Eigenschaft von Erreichbarkeitsmengen. De…nition 11 Das System (2.5) heiß t lokal akzessibel in x, falls für alle T > 0 gilt: intO+T (x) 6= ; und intO T (x) 6= ;:

Ist dies für alle x 2 Rn erfüllt, so heiß t das System lokal akzessibel.

Die folgende Proposition zeigt, dass lokale Akzessibilität schon durch die Matrizen A und B bestimmt ist. Proposition 12 Für das System (2.5) gilt intOT+ (x) 6= ; für ein T > 0 und ein x 2 Rn (und dann für alle) genau dann, wenn die Kalman-Bedingung gilt. Äquivalent dazu ist die lokale Akzessibilität. Beweis. Es gelte die Kalman-Bedingung. Betrachte für T > 0 die stetige lineare Abbildung zwischen Banachräumen, L : L1 ([0; T ]; Rm ) ! Rn : u 7 ! '(T; 0; u): Die Linearität ist klar, und die Stetigkeit folgt aus Z T j'(T; 0; u)j = eA(t s) Bu(s) ds 0 Z T eA(t s) Bu(s) ds 0

sup eAt jBj T juj1 :

t2[0;T ]

Diese Abbildung ist nach Satz 5 surjektiv. Das Open-Mapping-Theorem (siehe ein beliebiges Buch über Funktionalanalysis) besagt, dass solch eine Abbildung o¤ene Mengen auf o¤ene Mengen abbildet. Weil intU 6= ;, hat U[0;T ] := fu 2 L1 ([0; T ]; Rm ); u(t) 2 U für fast alle t 2 [0; T ]g nichtleeres Inneres. Nun ist wegen der Linearität (vgl. (2.3)) OT+ (x) = fy 2 Rn ; y = '(T; x; u) für ein u 2 Ug = fy 2 Rn ; y = '(T; x; 0) + '(T; 0; u) für ein u 2 Ug = '(T; x; 0) + fL(u); u 2 U g:

Also hat OT+ (x) nichtleeres Inneres. Analog argumentiert man für OT (x). Umgekehrt, gilt lokale Akzessibilität, so hat die Erreichbarkeitsmenge vom Ursprung nichtleeres Inneres. Daraus folgt die Kalman-Bedingung (ist sie verletzt, so ist OT+ (0) in einem echten Unterraum enthalten). Bei lokaler Akzessibilität gilt sogar exakte Kontrollierbarkeit im Innern von Kontrollmengen.

2.2. LINEARE SYSTEME MIT BESCHRÄNKTEN KONTROLLEN

21

Proposition 13 Das System (2.5) sei lokal akzessibel, und D sei eine Kontrollmenge mit nichtleerem Innern. Dann gilt intD

O+ (x) für alle x 2 D.

Beweis. Sei x 2 D. Wegen der lokalen Akzessibilität von y 2 int D und der Beschränktheit von U , …ndet man t > 0 so dass ; 6= int O t (y) int D: Wähle z 2 int O t (y) : Wegen z 2 clO+ (x) …ndet man einen Punkt z0 2 O t (y) \ O+ (x). Daher gibt es S; T > 0 und Kontrollen u; v 2 U mit '(S; x; u) = z1 und '(T; z1 ; v) = y. Die Verknüpfung w(t) =

u(t) v(t S)

für für

t 2 [0; S] t 2 (S; T + S]

liefert '(S + T; x; w) = y, also y 2 O+ (x). Wir bemerken auch die folgende Eigenschaft. Proposition 14 Das System (2.5) sei lokal akzessibel, und D sei eine Kontrollmenge mit nichtleerem Innern. Dann ist D = clO+ (x) \ O (x) für jedes x 2 intD: Beweis. Der Durchschnitt clO+ (x) \ O (x) ist in D enthalten: für jedes z 2 clO+ (x) \ O (x) existiert u 2 U und T 0 mit x = '(T; z; u), also gibt es eine Steuerung, so dass die zugehörige Trajektorie von z in D bleibt; dies zeigt zugleich, dass jeder Punkt von D approximativ von z erreichbar ist. Ferner ist z von x approximativ erreichbar, d.h. z 2 clO+ (x). Dann ist z 2 clO+ (y) für jedes y 2 D: steuere von y zunächst nach x und dann approximativ nach z: Für die umgekehrte Inklusion wähle x 2 intD und betrachte y 2 D. Dann ist y 2 clO+ (x) nach der De…nition von Kontrollmengen. Ferner folgt x 2 O+ (y) nach der vorangehenden Proposition, also y 2 O (x). Der nächste Satz charakterisiert Kontrollmengen für lineare Kontrollsysteme mit beschränkten Kontrollen. Der Vollständigkeit halber sind alle vorangegangenen Annahmen noch einmal aufgeführt. Satz 15 Für das System (2.5) sei U Rm konvex und kompakt mit 0 2 int U und (A; B) sei kontrollierbar ist, das heiß t, die Kalman-Bedingung rg [B; AB; n 1 :::A B] = n gilt. Dann gibt es genau eine Kontrollmenge D mit nichtleerem Innern; sie enthält 0 im Innern und D = clO+ (0) \ O (0). Die Kontrollmenge D ist invariant, falls A asymptotisch stabil ist; in diesem Fall ist D = clO+ (0), insbesondere ist D also abgeschlossen.

22

KAPITEL 2. LINEARE KONTROLLSYSTEME

Beweis. Die Kalman-Bedingung garantiert, dass zur Zeit T = 1 der positive und der negative Orbit des Systems ohne Kontrollbeschränkung mit Rn übereinstimmen. Wegen 0 2 int U liefert das Open-Mapping Theorem, angewendet auf die lineare Abbildung L1 ([0; 1]; Rm ) ! Rn : u 7 ! '(1; 0; u); dass 0 2 int O1+ (0). Wegen 0 = '(1; 0; 0) mit 0 2 intU und Z t n A O1 (0) = fx 2 R ; e x + eA(1 s) u(s) ds = 0 für ein u 2 Ug 0

folgt sogar 0 2 int O1+ (0) \ int O1 (0). Draus folgt leicht, dass 0 im Innern einer Kontrollmenge D liegt. Nach Proposition 14 ist die Kontrollmenge D = clO+ (0) \ O (0). Ist A asymptotisch stabil, so ist O (0) = Rn (denn Lösungen mit u = 0 von einem beliebigen Anfangspunkt erreichen für t ! 1 jede Umgebung des Ursprungs, also auch D und dann auch 0 2 intD). Es folgt, dass D = clO+ (0) und wegen 0 2 intD sieht man, dass D = clO+ (x) für alle x 2 D. Es bleibt zu zeigen, dass die Kontrollmenge eindeutig ist. Sei also D0 eine beliebige Kontrollmenge mit nichtleerem Innern und x 2 intD0 . Betrachte eine Umgebung N intD0 von x. Wegen exakter Kontrollierbarkeit im Innern von Kontrollmengen gibt es für alle y 2 N Kontrollen u; v 2 U und Zeiten S; T > 0 mit '(S; x; u) = y und '(T; y; v) = x. Die Linearität impliziert, dass auch N eine Umgebung von x ist, so dass für alle Punkte in N (die von der Form y; y 2 N sind) gilt '(S; x; u) = y und '(T; y; v) = x. Dabei sind u und v in U, weil U konvex ist mit 0 2 U . Daher sind alle Punkte x; 2 (0; 1); im Innern einer Kontrollmenge. Dann müssen diese Kontrollmengen alle mit der Kontrollmenge um den Ursprung übereinstimmen. Das ist sicherlich richtig für kleine > 0. De…niere 0 := supf > 0; x 2 intDg. Dann ist 0 x im Abschluss von D. Weil 0 x im Innern einer Kontrollmenge liegt, hat diese Kontrollmenge nichtleeren Schnitt mit D, stimmt also mit D überein. Es folgt 0 = 1. Bemerkung 16 Das wesentliche Argument im Beweis der Eindeutigkeit ist die Konstruktion einer stetigen Familie von Punkten, die jeweils im Innern einer Kontrollmenge liegen. Daraus folgt, dass diese Kontrollmengen schon übereinstimmen.

2.3. FEEDBACK-STABILISIERUNG

23

Bemerkung 17 Mit ähnlichen Argumenten wie oben kann man auch zeigen, dass es nur eine Kontrollmenge gibt (also auch keine weitere Kontrollmenge, die leeres Inneres hat).

2.3

Feedback-Stabilisierung

In diesem Abschnitt werden wir (für Systeme ohne Kontrollbeschränkungen) analysieren, wann Feedbacks existieren, unter denen ein Gleichgewicht stabil wird. Zunächst diskutieren wir die Linearisierung an einem Gleichgewicht. Dann konstruieren wir stabilisierende Feedbacks für lineare Kontrollsysteme. Aus der Theorie gewöhnlicher Di¤erentialgleichungen ist folgendes bekannt: Betrachte eine nichtlineare Di¤erentialgleichung y(t) _ = f (y(t)) mit einer C 1

Funktion f;

und nimm an, dass Lösungen 't (y0 ) zu Anfangswerten y(0) = y0 für alle Zeiten t 2 R existieren. Sei y 2 Rn ein Gleichgewicht, also f (y ) = 0. Dann @ gilt für t 2 R und A := @y f (y ) @ t ' (y )x0 = eAt x0 ; @y d.h. die Ableitung der Lösung nach dem Anfangswert in Richtung x0 ist die Lösung der linearisierten Di¤erentialgleichung x_ = Ax mit Anfangswert x(0) = x0 : Ferner ist y lokal exponentiell stabil ist, wenn das Gleichgewicht x = 0 ihrer Linearisierung global exponentiell stabil ist, also wenn alle Eigenwerte von A negativen Realteil haben; siehe dazu z.B. Aulbach [2]. Ein allgemeines nichtlineares Kontrollsystem ist gegeben durch die Di¤erentialgleichung y(t) _ = f (y(t); u(t)) (2.6) mit f : Rn Rm ! Rn . Wir nehmen an, dass für u = 0 der Punkt y = 0 ein Gleichgewicht ist, d.h., f (0; 0) = 0. Ferner sei die Abbildung f in (y ; u ) = (0; 0) sowohl nach y als auch nach u stetig di¤erenzierbar. Dann können wir die Linearisierung de…nieren als (2.7)

x(t) _ = Ax(t) + Bu(t) mit A=

@ @y

f (y; u); (y;u)=(0;0)

B=

@ @u

f (y; u): (y;u)=(0;0)

24

KAPITEL 2. LINEARE KONTROLLSYSTEME

Das folgende Lemma zeigt, wie diese Linearisierungen von Di¤erentialgleichungen und Kontrollsystemen für lineares Feedback F zusammenhängen. Lemma 18 Betrachte ein nichtlineares Kontrollsystem (2.6) und seine Linearisierung (2.7) im Gleichgewicht (0; 0). Sei F : Rn ! Rm eine lineare Abbildung. Dann ist die lineare Di¤erentialgleichung x(t) _ = (A + BF )x(t) die Linearisierung in y = 0 der nichtlinearen Di¤erentialgleichung y(t) _ = f (y(t); F y(t)): Beweis. Wir müssen nachweisen, dass d dy

f (y; F y) = A + BF y=0

gilt. Sei dazu G : Rn ! Rn Rm gegeben durch G(y) = (y; F y), wobei wir (y; F y) als (n + m)–dimensionalen Spaltenvektor interpretieren. Dann folgt nach der Kettenregel d d f (y; F y) = f (G(y)) dy dy @ @ f (y; u) + = @y (y;u)=G(y) @u

f (y; u)F: (y;u)=G(y)

Also ist in y = 0 d dy

f (y; F y) = y=0

@ @y

f (y; u) + (y;u)=(0;0)

@ @u

f (y; u)F = A + BF: (y;u)=(0;0)

Damit erhalten wir das folgende lokale Stabilisierungsresultat. Satz 19 Ein nichtlineares Kontrollsystem (2.6) ist durch ein lineares Feedback lokal exponentiell stabilisierbar , wenn seine Linearisierung (2.7) durch ein lineares Feedback global exponentiell stabilisierbar ist. Darüberhinaus ist das Gleichgewicht y = 0 der Gleichung y_ = f (y(t); F y(t)) lokal exponentiell stabil für jedes lineare Feedback F , das das Stabilisierungsproblem für das linearisierte System löst.

2.3. FEEDBACK-STABILISIERUNG

25

Aus der linearen Struktur des Feedbacks F ergibt sich also, dass wir nichtlineare Stabilisierungsprobleme lokal lösen können, indem wir lineare Stabilisierungsprobleme lösen. Wir wenden uns der Stabilisierung linearer Kontrollsysteme zu und beginnen mit einem Beispiel. Beispiel 20 Wir betrachten ein (sehr einfaches) Modell für eine Heizungsregelung. Nehmen wir an, dass wir die Temperatur x1 in einem Raum an einem festgelegten Messpunkt regeln wollen. Der Einfachheit halber sei die gewünschte Temperatur auf x1 = 0 normiert. In dem Raum be…ndet sich ein Heizkörper mit Temperatur x2 , auf die wir mit der Kontrolle u Ein‡uss nehmen können. Die Veränderung von x2 sei durch die Di¤erentialgleichung x_ 2 (t) = u(t) beschrieben, d.h. die Kontrolle u regelt die Zunahme (falls u > 0) bzw. Abnahme (falls u < 0) der Temperatur. Für die Temperatur x1 im Messpunkt nehmen wir an, dass sie der Di¤erentialgleichung x_ 1 (t) =

x1 (t) + x2 (t)

genügt, d.h. für konstante Heiztemperatur x2 ergibt sich x1 (t) = e t x1 (0) + (1

e t )x2

Mit anderen Worten, wir nehmen an, dass die Raumtemperatur x1 im Messpunkt exponentiell gegen die Temperatur des Heizkörpers konvergiert. Aus diesem Modell erhalten wir das Kontrollsystem x(t) _ =

1 1 0 0

x(t) +

0 1

u(t):

Eine naheliegende Regelstrategie ergibt sich nun wie folgt: Falls x1 > x1 = 0 ist, so vermindern wir die Temperatur in x2 , d.h., wir wählen u < 0. Im umgekehrten Fall, d.h. falls x1 < x1 = 0 ist, erhöhen wir die Temperatur und setzen u > 0. Da unser Feedback linear sein soll, lässt sich dies durch die Wahl F (x) = x1 für ein > 0 erreichen, oder, in Matrix–Schreibweise, F (x) = ( ; 0) (hier ist n = 2 und m = 1). Damit erhalten wir das rückgekoppelte System 1 1 x(t) _ = x(t): 0 Berechnet man die Eigenwerte für > 0, so sieht man, dass alle Realteile negativ sind. Wir haben also das Stabilisierungsproblem gelöst und folglich

26

KAPITEL 2. LINEARE KONTROLLSYSTEME

konvergieren x1 (t) und x2 (t) für alle Anfangswerte exponentiell schnell gegen 0, insbesondere konvergiert x1 exponentiell schnell gegen die gewünschte Temperatur x1 = 0. Falls wir die Temperatur x2 am Heizkörper messen können, so können wir auch F (x) = x2 , bzw. F = (0; ) setzen. Wiederum sieht man durch Betrachtung der Eigenwerte, dass das rückgekoppelte System für alle > 0 exponentiell stabil ist. Wir werden zunächst zwei nützliche Koordinatentransformationen für Kontrollsysteme betrachten. Beachte, dass für eine Transformationsmatrix T 2 Rn n das zu x(t) _ = Ax(t) + Bu(t) (2.8) gehörige transformierte System für z = T x ~ ~ z(t) _ = Az(t) + Bu(t)

(2.9)

e = T 1 AT und B e = T 1 B gegeben ist. Ein Feedback F für (2.8) wird durch A mittels Fe = F T in eines für (2.9) transformiert (dies folgt sofort aus T 1 (A+ e+B e Fe). Aus der Erreichbarkeitsmatrix R = [B; AB; :::; An 1 B] BF )T = A e = T 1 R für (2.9). Das für (2.8) erhält man die Erreichbarkeitsmatrix R folgende Lemma zeigt, dass man für beliebige Matrix–Paare (A; B) durch eine geeignete Koordinatentransformation erreichen kann, dass das System in einen kontrollierbaren und einen nicht–kontrollierbaren Anteil zerlegt wird. Lemma 21 Es sei (A; B) 2 Rn transformation T , so dass A~ = T mit A1 2 Rn

n

1

AT =

n

A 1 A2 0 A3

und B1 2 Rn

m

Rn

m

. Dann gibt es eine Koordinaten-

~=T und B

1

B=

B1 0

ist und (A1 ; B1 ) kontrollierbar ist.

Beweis. Dies folgt mit Standardargumenten der linearen Algebra, wenn man eine Basis des Erreichbarkeitsunterraums O+ (0) = R = hA jIm B i vom Ursprung zu einer Basis von Rn ergänzt und die Spalten von T als diese Basisvektoren de…niert. Die zweite Koordinatentransformation, die wir betrachten wollen, gilt für kontrollierbare Systeme, bei denen u eindimensional ist, also m = 1.

2.3. FEEDBACK-STABILISIERUNG

27

Lemma 22 Ein Paar (A; B) 2 Rn n Rn 1 ist genau dann kontrollierbar, wenn es eine Koordinatentransformation S in die sogenannte Regelungsnormalform gibt, 0 1 0 1 0 1 : : : 0 0 B : C B C : : : C B B : C B : B C : : : C ~ = S 1B = B : C ; C und B A~ = S 1 AS = B B : C B : C : : : C B B C @ 0 0 : : : @ 0 A 1 A 1 0 1 : : : n 1 hierbei sind die i die Koe¢ zienten des charakteristischen Polynoms n 1 A, d.h., A (z) = z n ::: n 1z 1z 0.

A

von

e der angegebenen Form Beweis. Wir zeigen zunächst, dass für Matrizen A die i gerade die Koe¢ zienten des charakteristischen Polynoms sind. Dies folgt durch Induktion über n: Für n = 1 ist die Behauptung sofort klar. Für den Induktionsschritt sei An 2 Rn n von der Form des Satzes und An+1 2 R(n+1) (n+1) gegeben durch 0 1 0 1 0 B 0 C B C An+1 = B .. C: @ . A An

Entwickeln wir nun det(zI An+1 (z)

An+1 ) nach der ersten Spalte, so ergibt sich

= z An (z) ( 1)n+1 det diag( 1; :::; 1) = z An (z) n 1 = zn ; n 2z 0z

also nach Umnumerierung der i gerade der gewünschte Ausdruck. Es existiere eine Transformation S mit den angegebenen Eigenschaften. Durch Nachrechnen sieht man leicht, dass 0 1 0 0 1 : B 0 C :: n 1e e e e e e B C (2.10) R = (B AB : : : A B) = @ A 0 1 1

gilt, wobei beliebige Werte bezeichnet. Diese Matrix hat vollen Rang, denn durch Umordnung der Zeilen erhalten wir eine obere Dreiecksmatrix mit lauter Einsen auf der Diagonalen, welche o¤enbar invertierbar ist, also vollen

28

KAPITEL 2. LINEARE KONTROLLSYSTEME

e B) e kontrollierbar und da Kontrollierbarkeit unRang besitzt. Daher ist (A; ter Koordinatentransformationen erhalten bleibt, ist auch das Paar (A; B) kontrollierbar. Sei umgekehrt (A; B) kontrollierbar. Dann ist die Erreichbarkeitsmatrix R = [B; AB; : : : ; An 1 B] invertierbar. Wir zeigen nun zunächst, dass R 1 AR eT , d.h., dass AR = RA~T ist. Dies folgt (unter Verwendung des Satzes =A von Cayley–Hamilton) aus AR = A[B; AB; :::; An 1 B] = [AB; A2 B; :::; An 1 B; 0 B B B n 1 = [B; AB; :::; A B] B B B @

n 1A

0 1 : : : 0

n 1

B + ::: +

: : : 0 : : : 0 : : : : : : 1

0 1

: : : n 1

0 B] 1

C C C C = RA~T : C C A

~ = A~T und damit ~ aus (2.10) liefert R ~ 1 A~R Eine analoge Rechnung mit R ~ A~T R ~ A~ = R

1

~ 1 ARR ~ 1: = RR

~ 0; :::; 0)T = B, ~ also Ferner ist o¤ensichtlich R(1; 0; :::; 0)T = B und R(1; 1 1 ~ ~ ~ RR B = B: Damit ist S = RR die gesuchte Tranformationsmatrix. Bemerkung 23 In der Regelungsnormalform enthält das System eine Kette von n 1 Integratoren, erst in der letzten Gleichung erscheint die Kontrolle explizit Wir werden das Stabilisierungsproblems zunächst für skalare Kontrolle, also m = 1, lösen. Der allgemeine Fall wird dann darauf zurückgeführt. Zunächst drücken wir das Stabilisierungsproblem mit Hilfe des charakteristischen Polynoms aus. Dies hängt eng mit dem Hautus-Kriterium für Kontrollierbarkeit zusammen. De…nition 24 Für ein Kontrollsystem (2.8) heiß t ein Polynom vorgebbar, falls ein lineares Feedback F existiert, so dass gleich dem charakteristischen Polynom A+BF von A + BF ist. O¤enbar existiert ein stabilisierendes Feedback F genau dann, wenn ein vorgebbares Polynom existiert, dessen Nullstellen nur negative Realteile haben. Die folgende Proposition zeigt, für skalare Kontrollen, die Beziehung zwischen Kontrollierbarkeit und der Vorgebbarkeit von Polynomen.

2.3. FEEDBACK-STABILISIERUNG

29

Proposition 25 Betrachte das Kontrollsystem (2.8) mit skalarer Kontrolle, also B 2 Rn 1 . Dann sind äquivalent: (i) Das Paar (A; B) ist kontrollierbar. n 1 (ii) Jedes Polynom der Form (z) = z n ::: n 1z 1z 0 mit i 2 R ist vorgebbar. Beweis. (i) ) (ii): Sei (A; B) kontrollierbar und sei S die Koordinatentransformation aus Lemma 22. Wir setzen Fe = (

Dann gilt e+B e Fe A 0 0 B : B B : =B B : B @ 0 0

B B B =B B B @

0

1 : : : 0 1

0 : : : 0

1 : : : 0

0

1

: : : : : : : : : : : : : : : : : : : : : : : :

0;

0

n 1

n 1

0

1

0 : : : 1 0 : : : 1

1; : : : ;

1

C B C B C B C+B C B C B A @

1

0 : : : : 1

n 1)

n 1

2 R1

n

:

1

C C C C( C C A

0;

0

1

1; : : : ;

n 1

n 1)

C C C C: C C A

e+ B e Fe gleich Daher ist nach Lemma 22 das charakteristische Polynom von A . (ii) ) (i): Es sei T die Koordinatentransformation aus Lemma 21. Dann ergibt sich für jedes beliebige Feedback Fe = (F1 ; F2 ) e+B e Fe = A

A1 + B1 F1 A2 + B1 F2 0 A3

:

Das charakteristische Polynom dieser Matrix ist e B e Fe A+

=

A1 +B1 F1

A3 ;

daher sind (beachte, dass (A1 ; B1 ) kontrollierbar ist) die vorgebbaren Polynome gerade von der Form = c u , wobei c ein beliebiges normiertes Polynom vom Grad d ist und u = A3 ist. Bedingung (ii) kann o¤enbar

30

KAPITEL 2. LINEARE KONTROLLSYSTEME

nur gelten, wenn A3 = 0 ist, also das System kontrollierbar ist. Damit ist Theorem 25 bewiesen. Das Polynom u = A3 wird auch als als unkontrollierbarer Teil des charakteristischen Polynoms von A bezeichnet (vgl. Übungsaufgabe zum Hautus-Kriterium). Natürlich ist es zur Stabilisierung nicht notwendig, dass jedes Polynom vorgebbar ist, wir brauchen lediglich eines zu …nden, dessen Nullstellen nur negative Realteile haben. Der Beweis von Satz 25 zeigt, wann dies möglich ist: Man benötigt, dass der unkontrollierbare Teil des charakteristischen Polynoms nur Nullstellen mit negativem Realteil hat. Das folgende Lemma, Heymanns Lemma, erlaubt es uns, den allgemeinen Fall auf den Fall m = 1 zurückzuführen. Lemma 26 Das Paar (A; B) sei kontrollierbar. Sei v 2 Rm mit b := Bv 6= 0. Dann existiert F 2 Rn m , so dass (A + BF; b) kontrollierbar ist. Beweis. Mittels einer rekursiven Vorschrift konstruieren wir uns zunächst linear unabhängige Vektoren x1 ; : : : ; xn 2 Rn mit der folgenden Eigenschaft: Für alle i 2 f1; : : : ; n 1g gilt Axi 2 Vi+1 = hx1 ; : : : ; xi+1 i:

(2.11)

De…niere x1 := b 6= 0. Jetzt seien für k 2 f1; : : : ; n 1g linear unabhängige Vektoren x1 ; : : : ; xk gegeben, so dass für alle i = 1; :::; k 1 die (2.11) erfüllt ist. Wir konstruieren einen Vektor xk+1 , so dass x1 ; : : : ; xk ; xk+1 linear unabhängig sind und xk 2 Vk+1 = hx1 ; : : : ; xk+1 i erfüllt ist. 1. Fall: Axk 62 Vk : Setze uk := 0 2 Rm und xk+1 := Axk + Buk = Axk . O¤enbar gilt dann auch die lineare Unabhängigkeit. 2. Fall: Axk 2 Vk : Wegen (2.11) folgt dann, dass Vk ein A invarianter Unterraum ist. Weil (A; B) kontrollierbar ist, gilt für den kleinsten A–invarianten Unterraum des Rn , der das Bild von B enthält, dass Rn = hA jIm B i. Weil Vk ein A–invarianter Unterraum mit dim Vk = k < n ist, kann dieser das Bild von B also nicht enthalten. Daher gibt es ein uk 2 Rm mit Axk + Buk 62 Vk und wir setzen xk+1 = Axk + Buk . Wir konstruieren nun die gesuchte Abbildung F aus x1 ; : : : ; xn . Da die xi linear unabhängig sind, ist die Matrix X = (x1; : : : ; xn ) invertierbar, und wir können F := U X 1 für U = (u1 ; : : : ; un ) 2 Rm n de…nieren, wobei die ui für i = 1; : : : ; n 1 die in der obigen Rekursion verwendeten Kontrollvektoren

2.3. FEEDBACK-STABILISIERUNG

31

sind und un := 0 2 Rm gesetzt wird. Damit gilt F xi = ui und deswegen (A + BF )xi = xi+1 für i = 1; : : : ; n 1. Wegen b = x1 folgt somit [b; (A + BF )b; : : : ; (A + BF )n 1 b] = X; also hat diese Matrix den Rang n und (A + BF; b) ist kontrollierbar. Mit diesem Resultat lässt sich nun die Proposition 25 leicht auf beliebige Kontrolldimension verallgemeinern. Satz 27 Für das System (2.8) sind äquivalent: (i) Das Paar (A; B) ist kontrollierbar. (ii) Jedes Polynom vom Grad n ist vorgebbar. Beweis. (i) ) (ii): Sei (A; B) kontrollierbar und gegeben. Seien F1 2 Rn m und b = Bv 2 Rn 1 die in Lemma 26 konstruierten Matrizen. Dann ist das Paar (A + BF1 ; b) kontrollierbar und aus Satz 25 folgt die Existenz eines Feedbacks F2 2 R1 n , so dass A+BF1 +bF2

=

ist. Wegen A + BF1 + bF2 = A + BF1 + BvF2 = A + B(F1 + vF2 ) ist also F = F1 + vF2 das gesuchte Feedback. (ii) ) (i): Völlig analog zum Beweis von Satz 25. Satz 28 Für das System (2.8) sind die vorgebbaren Polynome gerade die Polynome der Form = c u; wobei c ein beliebiges normiertes Polynom vom Grad d = hA jIm B i ist und u der unkontrollierbare Teil des charakteristischen Polynoms von A. Insbesondere ist das Stabilisierungsproblem genau dann lösbar, wenn alle Nullstellen von u negativen Realteil haben. Beweis. Dies ergibt sich unmittelbar aus den obigen Beweisen. Dieser Satz, der zentral für die lineare Kontrolltheorie ist, wird oft als Polverschiebungssatz bezeichnet, da die Nullstellen des charakteristischen Polynoms in der Kontrolltheorie auch als Pole bezeichnet werden (dies hat seine Wurzeln in alternativen Darstellungen linearer Kontrollsystems über sogenannte Übergangsabbildungen) und der Satz angibt, wie man diese Nullstellen durch geeignete Wahl des Feedbacks verschieben kann.

32

KAPITEL 2. LINEARE KONTROLLSYSTEME

Kapitel 3 Nichtlineare Kontrollsysteme In diesem Kapitel diskutieren wir allgemeine nichtlineare Kontrollsysteme. Im ersten Abschnitt werden wir deshalb eine hinreichende Bedingung für lokale Akzessibilität herleiten, die im reell-analytischen Fall auch notwendig ist. Im C 1 -Fall ist sie nur fast hinreichend. Im zweiten Abschnitt werden wir dann grundlegende Eigenschaften von Kontrollmengen beweisen.

3.1

Lokale Akzessibilität

Zunächst beschreiben wir die allgemeine Klasse von Kontrollsystemen, die wir betrachten werden. x(t) _ = f (x(t); u(t)); t 2 R; u 2 U = fu : R!Rm ; u(t) 2 U für alle t 2 R; lokal integrierbarg ;

(3.1)

wobei f : Rn Rm ! Rn eine Lipschitz-stetige Abbildung ist; und ‚lokal integrierbar’bedeutet (Lebesgue) integrierbar auf jedem beschränkten Intervall in R. Manchmal benutzen wir für die Menge der involvierten Vektorfelder (zu konstantem u) die Notation F = ff ( ; u); u 2 U g: Wir nehmen an, dass der Kontrollwertebereich U Rm nichtleer ist, und dass für jeden Anfangswert x 2 Rn und jede Kontrollfunktion u 2 U eine eindeutige (absolut-stetige) Lösung von (3.1) in folgendem Sinn existiert: Z t x(t) = x0 + f (x( ); u( )) d für alle t 2 R. (3.2) 0

Diese Lösung wird mit '(t; x; u); t 2 R; bezeichnet und erfüllt '(0; x; u) = x: Meist reicht es, stückweise konstante Kontrollfunktionen zu betrachten, also 33

34

KAPITEL 3. NICHTLINEARE KONTROLLSYSTEME

u in U = fu : R!Rm ; u(t) 2 U für alle t 2 R, stückweise konstantg : Dann sind die zugehörigen Trajektorien '( ; x; u) stückweise C 1 Funktionen. Die De…nition von Erreichbarkeitsmengen,. lokaler Akzessibilität, und von Kontrollmengen übertragen sich wörtlich auf diese Klasse von Kontrollsystemen. Insbesondere ist das System (3.1) lokal akzessibel in x 2 Rn , falls für alle T > 0 intO+T (x) = intf'(t; x; u); 0 intO

T (x)

n

t

T und u 2 Ug 6= ; und

= intfy 2 R ; '(t; y; u) = x; 0

t

T und u 2 Ug 6= ;:

Wenn das System lokal akzessibel ist, bleiben die Aussagen der Propositionen 13 und 14 über exakte Kontrollierbarkeit im Innern von Kontrollmengen und ihre Beweise richtig, also O+ (x) für alle x 2 D

intD und

D = clO+ (x) \ O (x):

Man kann aber natürlich nicht erwarten, dass Kontrollmengen eindeutig sind. Im Unterschied zur linearen Situation haben wir zunächst kein einfaches Kriterium, um lokale Akzessibilität nachzuweisen. Wir benötigen also eine Verallgemeinerung von Kalmans Rang-Bedingung. Dies ist der Beitrag von Kreners Theorem, das wir in diesem Abschnitt beweisen. Wir folgen dabei Sontag [19]. Es wird sich herausstellen, dass diese Verallgemeinerung auch für unbeschränkte Kontrollen nicht vollständige Kontrollierbarkeit liefert, sondern nur lokale Akzessibilität. Es gibt - trotz vieler Einzelresultate - keine allgemeinen Kriterien für vollständige Kontrollierbarkeit nichtlinearer Systeme. Die folgenden Beispiele illustrieren den Unterschied zwischen Kontrollierbarkeit und lokale Akzessibilität. Beispiel 29 Betrachte in R2 x_ 1 = u(t); x_ 2 = x21 : Das System ist für keinen Kontrollwertebereich U kontrollierbar, weil der positive Orbit O+ (0; 0) in f(x1 ; x2 ) ; x2 > 0g [ f(0; 0)g enthalten ist. Das System ist aber lokal akzessibel in (0; 0): Wähle für > 0 u (t) =

0 für t 2 [0; ] : 1 für t>

Daher enthält O+ (0; 0) eine o¤ene Menge.

3.1. LOKALE AKZESSIBILITÄT

35

Beispiel 30 Betrachte in R2 x_ 1 = u1 (t); x_ 2 = u2 (t)f (x1 ); (u1 (t):u2 (t)) 2 U mit f (x1 ) = 0 für x1 0 und f (x1 ) > 0 für x1 > 0; ferner gelte 0 2 intU R2 . Dieses System ist kontrollierbar in R2 , aber nicht lokal akzessibel für (x1 ; x2 ) mit x1 < 0. Beispiel 29 deutet bereits an, wie man eine hinreichende Bedingung für lokale Akzessibilität in y 2 Rn herleiten kann. Wähle Kontrollwerte u1 ; :::; un 2 U und betrachte x(t) _ = f j (x(t)) := f (x(t); uj ); x(0) = y: j

Bezeichne die Lösung mit etf y = '(t; y; uj ) (diese Bezeichnung erinnert an die Matrix-Exponentialfunktion, die Ähnlichkeit ist aber nur formal). Betrachte dann für T > 0 die Abbildung nf n

[0; T )k ! Rn ; (t1 ; :::tn ) 7! et

1f 1

::: et

y:

Ist diese Abbildung stetig di¤erenzierbar und hat die Ableitung vollen Rang in (t1 ; :::; tn ), so folgt aus dem Inversen-Funktionen-Theorem, dass eine Umn n 1 1 gebung von et f ::: et f y von y erreichbar ist. Zur Analyse der Ableitung dieser Funktion und zur Formulierung von Kreners Theorem sind einige Vorbereitungen nötig, insbesondere Lie-Klammern von Vektorfeldern. Es seien f und g glatte (C 1 )Vektorfeldern,de…niert auf einer o¤enen Menge O Rn . Das Vektorfeld [f; g] auf O ist de…niert durch [f; g](x) =

@ g(x)f (x) @x

@ f (x)g(x); @x

@ @ wobei @x g(x) bzw. @x f (x) die jeweiligen Jacobi-Matrizen bezeichnet. Bei genügender Glattheit kann man auf die o¤ensichtliche Weise auch iterierte LieKlammern de…nieren, also zum Beispiel für Vektorfeldern f; g und h

[f; [g; h]]: Ferner ist [f; g] =

[g; f ] und [f; f ] = 0:

Man beachte, dass die Lie-Klammer o¤enbar linear in jedem Argument ist, also [f; g + h] = [f; g] + [f; h]:

36

KAPITEL 3. NICHTLINEARE KONTROLLSYSTEME

Für eine Menge F von glatten Vektorfeldern ist die von F erzeugte LieAlgebra L(F ) der kleinste lineare Raum von Vektorfeldern, der gegenüber Lie-Klammer-Bildung abgeschlossen ist, also [f; g] 2 L(F ) für alle f; g 2 L(F ). Die Berechnung von iterierten Lie-Klammern per Hand ist aufwändig und fehleranfällig, aber im Prinzip immer durchführbar. Allerdings sei betont, dass Lie-Algebren, auch wenn sie von endlich vielen Vektorfeldern erzeugt werden, im Allgemeinen keine endlich-dimensionalen Vektorräume bilden. Für eine Lie-Algebra L (einen linearen Raum von Vektorfeldern, der unter Lie-Klammern abgeschlossen ist) sei L (x)

:= fy 2 Rn ; es gibt f 2 L mit y = f (x)g:

Wir nennen L (x); x 2 O, auch die von L erzeugte Distribution (von Unterräumen im Tangentialbündel). Der folgende Satz von A. Krener [14] gibt ein hinreichendes Kriterium für lokale Akzessibilität an. Satz 31 (Krener) Für das Kontrollsystem (3.1) in Rn mit Vektorfeldern F , gelte die folgende Akzessibilitäts-Rangbedingung in x 2 Rn : dim

L(F ) (x)

= n:

(3.3)

Dann ist das System lokal akzessibel in x. Bemerkung 32 O¤enbar ist die obige Bedingung äquivalent zu L(F ) (x) = Rn . Man sagt auch, dass die Distribution in x den Rang n hat, also rang (x) = n, daher der Name. Bemerkung 33 Ist das System reell-analytisch (d.h. die rechte Seite ist in eine konvergente Potenzreihe entwickelbar) oder ist dim L(F ) (x) konstant für x 2 Rn , so gilt auch die Umkehrung. Im C 1 -Fall folgt aus der lokalen Akzessibilität nur, dass die Rang-Bedingung auf einer o¤enen und dichten Teilmenge gilt. Bevor wir uns dem Beweis zuwenden, illustrieren wir die Bedeutung dieses Resultats. Für lineare Kontrollsysteme mit unbeschränkten Kontrollen ist die Bedingung (3.3) äquivalent zur Kalman-Bedingung. Proposition 34 Für x_ = Ax + Bu in Rn gilt (3.3) in jedem x 2 Rn genau dann, wenn rang [B; AB; :::; An 1 B] = n:

3.1. LOKALE AKZESSIBILITÄT

37

Beweis. Hier ist F = fAx + Bu; u 2 Rm g. Für u = 0 erhält man das Vektorfeld Ax. Wegen der Linearität ist für u 2 Rm [Ax; Ax + Bu] = [Ax; Ax] + [Ax; Bu] = AAx AAx + [Ax; Bu] = [Ax; Bu]: Beachte nun, dass Bu ein konstantes Vektorfeld ist, wähle u als einen kanonischen Basisvektor ei in Rm , und bezeichne die i-te Spalte von B mit bi : Dann ist wegen der Linearität von L(F ) bi = (Ax + Bei )

Bei 2 L(F ).

Ferner folgt [Ax; Bei ] = 0 Ax

ABei = Abi 2 L(F ):

Entsprechend ist [Ax; [Ax; Bei ]] = A2 bi : Man erhält schließ lich , dass

L(F ) (x)

alle Vektorfeldern

Ax; b1 ; :::; bm ; Ab1 ; :::; Abm ; ::::; An 1 b1 ; :::; An 1 bm enthält. Mit Hilfe des Satzes von Cayley-Hamilton folgt, dass der davon aufgespannte Vektorraum gleich L(F ) ist. Der Unterraum L(F ) (x) von Rn stimmt für jedes x 2 Rn (also auch für x = 0) mit Rn überein, wenn Kalmans Rang-Bedingung erfüllt ist. Die umgekehrte Richtung wird etwas später bewiesen (Bemerkung 40). Eine wichtige Klasse von Kontrollsystemen sind bilineare Kontrollsysteme in Rn gegeben durch # " m X x_ = A0 + ui (t)Ai x(t) = A(u(t))x(t); (ui (t)) 2 U; i=1

mit n n Matrizen A0 ; A1 ; :::; Am und U Rm . Beachte, das hier die LieKlammer durch den Kommutator von Matrizen gegeben ist: [A(u)x; A(v)x] = (A(v)A(u)

A(u)A(v)) x = [A(u)A(v)

A(v)A(u)]x:

Man kann dies auch als Kontrollsystem auf dem Raum M = Gl(n; R) der invertierbaren n n Matrizen au¤assen oder auf der Untergruppe, die durch Multiplikation der Einheitsmatrix mit den entsprechenden Fundamental-Matrizen entsteht. Es entsteht also in Kontrollsystem auf dieser (zusammenhängenden)

38

KAPITEL 3. NICHTLINEARE KONTROLLSYSTEME

Lie-Untergruppe G (mit rechts-invarianten Vektorfeldern). Es stellt sich heraus, das die Akzessibilitäts-Rangbedingung (3.3) für das System in Rn n f0g genau dann gilt, wenn sie für das System auf G gilt. Allgemeiner kann man Kontrolltheorie für Systeme auf Liegruppen betreiben; hierzu gibt es eine gut ausgearbeitete Theorie (siehe z.B. die Monographie von V. Jurdjevic [13]). Für den Beweis von Theorem 31 benötigen wir einige Vorbereitungen. Dazu diskutieren wir zunächst, wie das Umschalten zwischen Vektorfeldern zu konstanten Kontrollen neue Richtungen generieren kann. Wir hatten den Fluss zu einem Vektorfeld f auch mit etf x = '(t; x) bezeichnet. Dann ist die Komposition zweier solcher Flüsse, die zu konstanten Kontrollen auf [0; t1 ] und (t1 ; t2 ] gehören, gegeben durch et2 g et1 f ; t1 ; t2 2 R. Im Allgemeinen ist et3 f et2 g et1 f 6= et2 g e(t1 +t3 )f ; weil die Flüsse nicht kommutieren müssen. Das folgende Beispiel zeigt, wie durch diese Komposition neue Richtungen erzeugt werden. Beispiel 35 Betrachte ein Kontrollsystem, das Rotationen im R3 um einen Punkt beschreibt (zum Beispiel für einen Satelliten). Die Kontrollen sollen Rotation um die z-Achse und um die y-Achse erlauben. Die zugehörigen Vektorfelder (für Rotation entgegen der Uhrzeigerrichtung) sind 0

1 0 1 x2 x3 f (x) = @ x1 A und g(x) = @ 0 A 0 x1

mit den Flüssen 0 10 1 0 cos t sin t 0 x1 cos t 0 tf tg @ A @ A @ sin t cos t 0 x2 0 1 e x= ,e x= 0 0 1 x3 sin t 0

10 1 sin t x1 A @ x2 A : 0 cos t x3

Die Folge von Rotationen mit f (um die z Achse) für =2 Sekunden, mit g (um die y Achse) für =2 Sekunden und mit f für =2 Sekunden (um die y Achse) hat eine andere Auswirkung als die Rotation mit g (um die

3.1. LOKALE AKZESSIBILITÄT

39

z Achse) für =2 Sekunden. Ersteres produziert eine Drehung im Uhrzeigersinn um =2 um die x Achse. Dies sieht man leicht geometrisch; algebraisch ergibt es sich aus e(

=2)f ( =2)g ( =2)f

0

e

e

x 10

10 0 1 0 0 0 1 0 = @ 1 0 0 A@ 0 1 0 A@ 1 0 0 1 1 0 0 0 0 10 1 1 0 0 x1 = @ 0 0 1 A @ x2 A : 0 1 0 x3

10 1 1 0 x1 0 0 A @ x2 A 0 1 x3

Dieses Beispiel zeigt, dass eine total neue Bewegung, verschieden von reinen Rotationen um die y oder die z Achse, aus der Kombination der ursprünglichen Flüsse entsteht. Um diese Fragen in einem angemessenen Kontext zu diskutieren, müssen wir einige Konzepte aus der Di¤erentialgeometrie einführen. Für eine stetige di¤erenzierbare Abbildung f = (f1 ; :::; fn )T : O ! Rn de…niert auf einer o¤enen Menge O Rp , bezeichnen wir mit f die Jacobi-Matrix von f , betrachtet als eine Matrix-Funktion auf O. Das heiß t, für jedes x0 2 O ist f (x0 ) 2 Rn p die in x0 ausgewertete Jacobi-Matrix, deren (i; j) ter Eintrag @fi j 0 . ist. @xj x=x Im Spezialfall p = n heiß t solch eine stetig di¤erenzierbare Funktion Vektorfeld auf O. Im Weiteren nehmen wir immer an, dass Vektorfelder C 1 sind. Die Menge aller Vektorfelder auf O Rn ist ein Vektorraum, bezeichnet mit V(O). Ist ' : O ! R di¤erenzierbar, so ist ' (x) = O'(x) ein Zeilenvektor, der Gradient von ' ausgewertet in x. Die Menge aller glatten (C 1 )Funktionen ' : O ! R ist wieder ein Vektorraum, bezeichnet mit F(O). Für jedes f 2 V(O) und jedes ' 2 F(O) ist Lf ' 2 F(O) die Richtungs-Ableitung oder Lie-Ableitung von ' entlang f , (Lf ')(x) = ' (x)f (x) (wie für Lyapunov-Funktionen). Man kann Lf als einen linearen Operator auf F(O) au¤assen. Zwei Vektorfelder f; g 2 V(O) sind genau dann gleich, wenn Lf = Lg : In der Tat, aus der letzteren Ungleichung folgt, dass für jede der n (linearen) Koordinatenfunktionen i (x) = xi gilt: fi (x) = (Lf i )(x) = (Lg i )(x) = gi (x). Beachte, dass Lf ein Di¤erential-Operator erster Ordnung ist, während die Komposition Lf Lg = Lf Lg ein Operator zweiter Ordnung

40

KAPITEL 3. NICHTLINEARE KONTROLLSYSTEME

ist: es sei H' =

@2' @xi @xj

die Hesse-Matrix. Dann folgt Lf Lg ' = Lf (' g) = g T H' f + ' g f: Weil H' symmetrisch ist, folgt Lf Lg '

L g Lf ' = Lg

f f g ':

(3.4)

Mit dieser Notation kann man die Lie-Klammer folgendermaß en de…nieren. De…nition 36 Die Lie-Klammer von f; g 2 V(O) ist [f; g] = g f V(O).

fg 2

Die Gleichung (3.4) bedeutet daher L[f;g] = Lf Lg

L g Lf :

(3.5)

Wir notieren, dass diese Operation linear in jedem ihrer Argumente ist und [f; g] = [g; f ]. Manchmal ist es bequem zu schreiben adf g = [f; g] und adf als linearen Operator auf V(O) zu betrachten. Dies ist ein „Di¤erentialOperator”bezüglich der Lie-Klammer in folgendem Sinn: adf [g; h] = [adf g; h] + [g; adf h] für alle f; g; h. Diese Formel heiß t auch Jacobi-Identität, insbesondere, wenn sie in der äquivalenten Form (man beachte die zyklische Vertauschung von f; g, und h) [f; [g; h]] + [h; [f; g]] + [g; [h; f ]] = 0 geschrieben wird. Man beweist sie, indem man (3.5) zweimal anwendet und ähnliche Ausdrücke für die anderen beiden Terme benutzt. Wir notieren die folgenden weiteren Eigenschaften. Lemma 37 Für alle f; g 2 V(O) und alle '; 2 F(O) gilt (i) Lf (' ) = Lf (') + '(Lf ); (ii) L'f ( ) = 'Lf ; (iii) ['f; g] = ' [f; g] + (Lf )'g (Lg ') f: Beweis. Übung.

3.1. LOKALE AKZESSIBILITÄT

41

De…nition 38 Eine Lie-Algebra (von Vektorfeldern auf O) ist ein linearer Unterraum S V(O), der bezüglich der Lie-Klammern abgeschlossen ist, das heiß t, [f; g] 2 S, falls f und g in S sind. Für Teilmengen A V(O) de…nieren wir die von A erzeugte Lie-Algebra L(A) als den Durchschnitt aller Lie-Algebren, die A enthalten. Dieser (nichtleere) Durchschnitt ist eine Lie-Algebra, weil Durchschnitte von Lie-Algebren wieder Lie-Algebren sind. Lemma 39 Für A

und A1

V(O) de…niere

A0 = A; Ak+1 = f[f; g]; f 2 Ak und g 2 Ag; k S = k 0 Ak . Dann L(A) = linear spanA1 .

0;

Beweis. Es ist klar, dass linear spanA1 L(A). Die Umkehrung folgt, indem man zeigt, dass linear spanA1 eine Lie-Algebra ist (der Beweis benutzt die Jacobi-Identität). Wir lassen die Details weg.. Dieses Lemma zeigt, dass L(A) der kleinste Unterraum von V(O) ist, der A enthält und unter dem Operator adf abgeschlossen ist. Bemerkung 40 Aus diesem Lemma folgt auch die noch fehlende Beweisrichtung in Proposition 34. Seien W

Rp und O

Rn o¤en. Wir nennen eine glatte Abbildung M :W !O

eine Scheibe (slice) falls ihre Jacobi-Matrix M (w) in jedem w 2 W den Rang p hat. Ein Vektorfeld f 2 V(O) heiß t tangential an M , falls für alle w 2 W das Bild f (M (w)) im Spaltenraum von M (w) ist, d.h. in dem von den Spalten aufgespannten Unterraum von Rn . Wir betrachten auch das Bild von M als eine p-dimensionale Scheibe von O. Ist M injektiv, so liefert es, di¤erentialgeometrisch ausgedrückt, eine Karte für die Untermannigfaltigkeit, die durch ihr Bild dargestellt wird. Tangentiale Vektorfelder in diesem Sinn sind genau diejenigen, die im üblichen Sinn tangential an diese Untermannigfaltigkeit sind. Proposition 41 Sei M : W ! O eine Scheibe. Dann ist die Menge der an M tangentialen Vektorfelder eine Lie-Algebra. Für den Beweis dieser Proposition benötigen wir das folgende Resultat (das mit linearer Algebra und etwas Analysis bewiesen wird; vgl. Sontag [19, Corollary 4.1.6]). Man beachte, dass die Aussage für festes w o¤ensichtlich ist.

42

KAPITEL 3. NICHTLINEARE KONTROLLSYSTEME

Lemma 42 Für eine o¤ene Teilmenge W Rp betrachte C k -Funktionen f : W ! Rn und Q : W ! Rn p , für die der Rang von Q(w) konstant auf W ist. Dann sind äquivalent: (i) Für jedes w 2 W gehört f (w) zum Spaltenraum von Q(w). (ii) Für jedes w0 2 W gibt es eine Umgebung W0 von w0 und eine C k Funktion : W0 ! Rp , so dass f (w) = Q(w) (w) für alle w 2 W . Beweis. (von Proposition 41). Natürlich ist die Menge der Vektorfelder, die tangential an M sind, ein linearer Unterraum von V(O). Anwendung von Lemma 42 auf f M zeigt, dass f genau dann tangential an M ist, wenn es für jedes w0 2 W eine Umgebung W0 und ein glattes : W0 ! Rp gibt, so dass f (M (w)) = M (w) (w) für alle w 2 W0 : Wähle tangentiale Vektorfelder f; g und ein w0 2 W0 . Wir müssen zeigen, dass [f; g](M (w0 )) im Spaltenraum von M (w0 ) liegt. Wähle eine Umgebung W0 von w0 und glatte ; : W0 ! Rp , so dass für alle w 2 W0 f (M (w)) = M (w) (w) und g(M (w)) = M (w) (w): Wir werden [f; g](M (w)) = M (w)[ ; ](w) für alle w 2 W0

(3.6)

zeigen, woraus die Behauptung folgt. Betrachte f~(w) = f (M (w)) = M (w) (w) und g~(w) = g(M (w)) = M (w) (w): Die Kettenregel liefert (f~) (w) = f (M (w))M (w); (~ g ) (w) = g (M (w))M (w):

(3.7)

Für i 2 1; :::; n sei ei der i-te kanonische Einheitsvektor; betrachte die glatte Funktion 'i = eTi M : W0 ! R. Dann ist

eTi f~ = eTi M (w) (w) = L 'i und eTi g~ = eTi M (w) (w) = L 'i ; und daher eTi (g f )(M (w)) = eTi g (M (w))M (w) (w) g ) (w) (w) = (eTi g~) (w) (w) wegen (3.7) = eTi (~ = (L 'i ) (w) (w) = (L L 'i )(w) wegen (3.8).

(3.8)

3.1. LOKALE AKZESSIBILITÄT

43

Ein analoges Argument liefert eTi (f g)(M (w)) = (L L 'i )(w). Mit L[

; ]

=L L

L L erhalten wir

eTi [f; g](M (w)) = (L[

; ] 'i )(w)

= eTi M (w)[ ; ](w).

Weil dies für alle i gilt, folgt (3.6) und der Beweis von Proposition 41 ist vollständig. Im Weiteren …xieren wir eine o¤ene Teilmenge O Rn und eine Menge A V(O) von Vektorfeldern. De…nition 43 Ein k Tupel (f1 ; :::; fk ) in A ist nichtsingular in x0 2 O, falls es t0 = (t01 ; :::; t0k ) 2 Rk 0 gibt, so dass für x0 f1 ;:::;fk

: D ! O; t = (t1 ; :::; tk ) 7! etk fk ::: et1 f1 x0 ;

de…niert auf einer o¤enen Menge D t0 den Rang k hat.

Rk mit 0 2 D, die Jacobi-Matrix in

Die Lösung t 7! etf x0 ist C 1 , weil f eine C 1 Funktion ist, daher ist auch eine C 1 Funktion. Das nächste Lemma ist entscheidend für den Beweis von Kreners Satz. Lemma 44 Wenn für die Lie-Algebra L(A) die Rang-Bedingung rangL(A)(x0 ) = n gilt, so gibt es ein nichtsingular n Tupel in x0 . Ferner gibt es für jedes " > 0 x0 ein t0 2 Rn 0 mit t0i < " für alle i und f1 ; :::; fn 2 A, so dass (t0 ) f1 ;:::;fd den Rang n hat. Beweis. Wir können annehmen, dass rangL(A)(x) = n für alle x 2 O gilt, indem wir, wenn nötig, O durch eine kleinere Umgebung von x0 ersetzen. Fixiere " > 0. Es sei k die größ te ganze Zahl für die ein k Tupel (f1 ; :::; fk ) 0 in A und ein t0 2 Rk 0 mit t0i < " existieren, so dass xf1 ;:::;fk auf einer Umgebung von [0; t01 ] ::: [0; t0k ] de…niert ist und rang

x0 f1 ;:::;fk

(t0 ) = k erfüllt. Beachte, das k

1 gilt, weil

es ein f 2 A mit f (x0 ) 6= 0 gibt (andernfalls sind alle Lie-Klammern gleich 0 null, woraus L(A)(x0 ) = 0 folgt). Für dieses 1 Tupel hat ( xf ) (0) = f (x0 )

44

KAPITEL 3. NICHTLINEARE KONTROLLSYSTEME

den Rang eins. Für den Beweis des Lemmas müssen wir k = n zeigen. Es 0 seien (f1 ; :::; fk ) und t0 2 Rk mit t0i < ", so dass rang xf1 ;:::;fk (t0 ) = k.

Wegen der Stetigkeit können wir annehmen, dass alle Einträge von t0 positiv sind. Wähle eine Umgebung W Rk 0 von t0 (enthalten in dem Gebiet D), x0 f1 ;:::;fk

so dass rang 0

(t) = k für alle t 2 W und betrachte die Scheibe

M = xf1 ;:::;fk : W ! O. Behauptung: Jedes Element von A ist tangential an M . Andernfalls gibt es f 2 A, so dass f (M (s0 )) für ein s0 2 W nicht im Spaltenraum von M (s0 ) liegt. Betrachte das (k + 1) Tupel (f1 ; :::; fk ; f ); 0

setze G = xf1 ;:::;fk ;f , und nimm s00 = (s0 ; 0) = (s01 ; :::; s0k ; 0). Beachte, dass G auf einer Umgebung von [0; s01 ]

:::

[0; s0k ]

f0g

de…niert ist. Wir berechnen die Jacobi-Matrix G (s00 ). Wegen G(t; tk+1 ) = etk+1 f M (t); ist die Jacobi-Matrix bezüglich der Variablen t gleich Q(tk+1 )M (t), wobei Q(tk+1 ) das Di¤erential von x 7! etk+1 f x ausgewertet in M (t) ist. Insbesondere erhält man M (s0 ) in (t; tk+1 ) = s00 . Die Ableitung bezüglich tk+1 ist f (etk+1 f M (t)), was ausgewertet in s00 gleich f (M (s0 )) ist. Wir schließ en daraus, dass x0 (s00 ) = [M (s0 ); f (M (s0 )]: f1 ;:::;fk ;f Dies hat den Rang k + 1, weil die ersten k Spalten eine Matrix vom Rang k bilden, denn M ist eine Scheibe und die letzte Spalte ist nicht im Aufspann der anderen. Weil alle Einträge von s00 nichtnegativ und kleiner als " sind, widerspricht dies der Maximalität von k und die Behauptung ist bewiesen. Daher sind alle Vektorfelder in A tangential an M , und Proposition 41 zeigt, dass auch alle Vektorfelder in der Lie-Algebra L(A) tangential an M sind. Wähle t 2 W . Dann liegt f (M (t)) für f 2 L(A) im Spaltenraum von M (t). Daher impliziert die Rang-Bedingung, dass rangM (t) = n, also folgt k = n wie gewünscht Jetzt können wir mit dem Beweis von Theorem 31 beginnen. Es behauptet, dass für ein Kontrollsystem, das durch die Vektorfelder F = ff ( ; u); u 2 U g die Akzessibilitäts-Rangbedingung dim

L(F ) (x

0

)=n

3.1. LOKALE AKZESSIBILITÄT

45

die lokale Akzessibilität in x0 impliziert, das heiß t, für alle T > 0 O+T (x0 ) = fy 2 Rn ; es gibt 0 < t

T und u 2 U mit y = '(t; x0 ; u)g;

und O

T (x

0

) = fy 2 Rn ; es gibt 0 < t

T und u 2 U mit x0 = '(t; y; u)g:

haben nichtleeres Inneres.. Beweis. (von Theorem 31) Nach Annahme gibt es eine endliche Teilmenge A F von Vektorfeldern, so dass L(A) (x

0

) = Rn .

Weil jedes etf in t und x stetig ist, gibt es " > 0, so dass für alle f1 ; :::fn 2 A und alle t1 ; :::; tn > 0 mit 0 ti < " der Wert etn fn :::et1 f1 de…niert ist. Wir wählen solch ein " mit " < T =n: Lemma 44 sichert, dass es Vektorfelder f1 = f ( ; u1 ); :::; fn = f ( ; un ) in A und t0 2 Rn 0 mit 0 t0i < " für alle i gibt, so dass 0 rang( xf1 ;:::;fn ) (t0 ) = n: Wegen der Stetigkeit können wir annehmen, dass alle t0i > 0 sind. Das 0 Implizite-Funktionentheorem garantiert, dass das Bild von xf1 ;:::;fn restringiert auf eine Teilmenge von f(t1 ; :::; tn ); 0 < ti < " für i = 1; :::; ng eine o¤ene Menge enthält. Wegen x0 f1 ;:::;fn (t)

= etn f ( ;ud ) ::: et1 f ( ;u1 ) x0 = '(t1 + ::: + tn ; x0 ; u);

wobei u die Kontrollfunktion ist, die den Wert u1 auf [0; t1 ]; den Wert u2 auf [t1 ; t1 + t2 ] etc. hat, ist dieses Bild in dem positiven Orbit O+T (x0 ) enthalten. Um die Behauptung für O T (x0 ) zu beweisen, betrachten wir das Zeitumgekehrte System x_ = f (x; u). Wegen L( A) = L(A) erfüllt es ebenfalls die Akzessibilitäts-Rangbedingung. Daher haben die positiven Orbits für das zeitumgekehrte System nichtleeres Inneres. Sie stimmen mit den negativen Orbits des Originalsystems überein. Damit ist der Beweis von Theorem 31 abgeschlossen. Bemerkung 45 Eine Inspektion des Beweises zeigt, dass für jede Umgebung V von x0 die im Beweis benutzten Trajektorien so gewählt werden können, dass sie V nicht verlassen. Manchmal wird lokale Akzessibilität mit Hilfe dieser Eigenschaft de…niert, also wenn für alle Umgebungen V die Menge der Punkte, die mit Trajektorien innerhalb von V erreicht werden können, nichtleeres Inneres hat. Ist der Kontrollwertebereich beschränkt, so ist dies äquivalent dazu, dass die Menge der Punkte, die von x0 bis zu einer beliebigen Zeit T > 0 erreicht werden können, nichtleeres Inneres hat.

46

KAPITEL 3. NICHTLINEARE KONTROLLSYSTEME

Bemerkung 46 Die Lie-Algebra L(F ) heiß t auch die zu dem Kontrollsystem assoziierte Akzessibilitäts-Lie-Algebra. Ein relevante Klasse von Kontrollsystemen sind kontrolla¢ ne Systeme; sie haben die folgende Form. x(t) _ = f (x(t); u(t)) = f0 (x(t)) + u1 (t)f1 (x(t)) + ::: + um (t)fm (x(t)); (3.9) u 2 U = fu = (ui ) : R ! Rm ; u(t) 2 U für t 2 Rg: Hierbei sind die fi glatte Vektorfelder auf Rn ; das Vektorfeld f0 heiß t DriftVektorfeld f1 ; :::; fm heiß en Kontroll-Vektorfelder. Manchmal schreibt man auch kurz x_ = f0 (x) + G(x)u mit G = (f1 ; :::fm ) 2 Rm n . Für kontrolla¢ ne Systems kann die AkzessibilitätsLie-Algebra durch weniger Elemente erzeugt werden als im allgemeinen Fall. Proposition 47 Betrachte ein kontrolla¢ nes System (3.9), für das der KontrollWertebereich U Rm die Null enthält und linear den Rm aufspannt. Dann ist die Lie-Algebra, die von F = ff ( ; u); u 2 U g erzeugt wird, L(F ) = L(f0 ; f1 ; :::; fm ): Beweis. Es reicht, zu zeigen, dass die linearen Hüllen von ff0 ; f1 ; :::; fm g und von F übereinstimmen. Nach De…nition ist jedes Element in F von der Form f ( ; u) = f0 +

m X

ui fi

i=1

und ist daher natürlich in der linearen Hülle der fi . Umgekehrt, mit u = 0 2 U …ndet man f0 2 F und daher ist für jedes u 2 U G(x)u = u1 f1 + ::: + um fm = f (x; u)

f (x; 0)

in der linearen Hülle von F . Um einzusehen, dass dies auch für jedes fi ; i = 1; :::; m, gilt, …xiere solch ein i, und schreibe den iten kanonischen Basisvektor von Rm als Linearkombination der Elemente von U , ei =

m X

j uj :

j=1

Dann ist fi = G(x)ei =

Pm

j=1

j G(x)uj ,

also in der linearen Hülle von F .

3.1. LOKALE AKZESSIBILITÄT

47

In Theorem 31 betrachten wir Mengen von Punkten, die in jeweils einer Zeitrichtung (in positiver Zeit oder in negativer Zeit) erreichbar sind. Die Rang-Bedingung impliziert auch Eigenschaften von Punkten, die in positiver und negativer Zeit kombiniert erreichbar sind., Dies ist eine klassische Konstruktion in der Di¤erentialgeometrie und führt zu Resultaten, die als Theoreme von Frobenius und von Chow bekannt sind. Die de…nitive Version stammt von H. Sussmann und P. Stefan und ist als Orbit-Theorem bekannt. Es stellt fest, dass alle Orbits Untermannigfaltigkeiten sind. Auch einige in Anwendungen relevante Kontrollsysteme haben die Eigenschaft, dass Gehen in positiver und negativer Zeit erlaubt ist. Betrachte driftfreie Systeme x(t) _ = u1 (t)f1 (x(t)) + ::: + um (t)fm (x(t)) mit (u1 ; :::; um ) 2 U wobei für den Kontrollwertebereich U = de…nierenden Vektorfelder

U gilt. Dann erfüllt die Menge der

F = fu1 f1 + ::: + um fm ; u 2 U g die Bedingung A = A und daher stimmt das zeitumgekehrte System mit dem Originalsystem überein. Viele Systeme aus der Mechanik, wie Satelliten oder Trailer, sind von diesem Typ. Akzessibilität ist eine viel schwächere Bedingung als vollständige Kontrollierbarkeit. Trotz intensiver Forschung und vieler Spezialresultate sind keine allgemeinen notwendigen und hinreichenden Bedingungen bekannt (nicht einmal für bilineare Systeme ohne Kontrollbeschränkungen) Sind Kontrollbeschränkungen vorhanden, so wird vollständige Kontrollierbarkeit eher die Ausnahme sein. Stattdessen sind maximale Teilmengen vollständiger Kontrollierbarkeit (also Kontrollmengen) das angemessene Konzept. Bevor wir im nächsten Abschnitt zu ihrer Analyse kommen, notieren wir noch die folgenden Resultate. Proposition 48 Es sei u 2 U eine zulässige Kontrolle und betrachte für x0 2 Rn und T 2 R den Punkt z 0 = '(T; x0 ; u). Dann gibt es eine Umgebung V von x0 , so dass die Abbildung : x 7! '(T; x; u), de…niert auf V ein Homöomorphismus auf sein Bild ist, das eine Umgebung von z 0 bildet. Beweis. Die stetige Inverse ist durch die Abbildung y 7! '( T; y; u(T + )) gegeben, weil '( T; '(T; x; u); u(T + )) = x: Für das folgende Resultat über Kontrollierbarkeit entlang von Trajektorien siehe z.B. Sontag [19, (1st ed.), Lemma/Exercise 3.6.13].

48

KAPITEL 3. NICHTLINEARE KONTROLLSYSTEME

Satz 49 Betrachte das kontrolla¢ ne System x_ = f0 (x) +

m X i=1

ui (t)fi (x); (ui )i=1;:::;m 2 U;

(3.10)

in Rn und die Trajektorie '(t; x0 ; 0); t 2 R, zum Anfangswert x0 2 Rn und zur Kontrolle u 0 2 int U . Es gebe k 2 N und T > 0, so dass die folgende Matrix ausgewertet in '(T; x0 ; 0) den Rang d hat: [f1 ; :::; fm ; adf0 f1 ; :::; adf0 fm ; :::; adkf0 f1 ; :::; adkf0 fm ]: Dann ist das linearisierte (zeitabhängige!) Kontrollsystem 0

z(t) _ = Df0 ('(t; x ; 0))z(t) +

m X

ui (t)fi ('(t; x0 ; 0))

i=1

mit Kontrollen u 2 L1 ([0; T ]; Rm ) kontrollierbar auf [0; T ] (das heiß t, die Erreichbarkeitsmenge zur Zeit T bei Start in x = 0 zur Zeit t = 0 ist Rn ) und für das nichtlineare System gilt '(T; x0 ; 0) 2 int OT+ (x). Bemerkung 50 Der Beweis dieses Resultats basiert auf einer Rang-Bedingung (ähnlich der Kalman-Bedingung) für Kontrollierbarkeit zeitabhängiger linearer Kontrollsysteme, die zur obigen Bedingung äquivalent ist. Diese Kontrollierbarkeitsbedingung bedeutet, dass die stetig di¤erenzierbare Abbildung (u; x) 7! '(T; x; u) : L1 (0; T; Rm )

R n ! Rn

eine surjektive Ableitung in (u 0; x0 ) hat. Dann impliziert das OpenMapping-Theorem die zweite Behauptung.

3.2

Kontrollmengen

Wir betrachten weiterhin das Kontrollsystem (3.1) und diskutieren in diesem Abschnitt grundlegende Eigenschaften von Kontrollmengen. Wir setzen auch voraus, dass der Kontrollwertebereich U beschränkt ist (siehe auch Bemerkung 45). Kontrollmengen sind Teilmengen D des Zustandsraums Rn , für die gilt: (i) für alle x 2 D gibt es u 2 U mit '(t; x; u) 2 D für alle t 0; (ii) für alle x 2 D ist D clO+ (x) und D ist maximal mit diesen Eigenschaften. Eine Kontrollmenge heiß t invariante Kontrollmenge, falls clC = cl O+ (x) für alle x 2 C. Alle anderen Kontrollmengen heiß en variante Kontrollmengen. Eigenschaft (i) fordert, dass man für alle positiven Zeiten in D bleiben kann. Das bedeutet, dass Kontrollmengen viabel im Sinn von J. P. Aubin

3.2. KONTROLLMENGEN

49

[1] sind, oder, wie es in der Kontrolltheorie meist heiß t, dass sie kontrolliertinvariant sind (in der Theorie dynamischer Systeme auch schwach positiv invariant). Wir werden später sehen, dass diese Bedingung automatisch erfüllt ist, wenn D die Eigenschaft (ii) hat und nichtleeres Inneres besitzt. Die folgenden Beispiele zeigen, dass Kontrollsysteme viele oder gar keine Kontrollmengen besitzen können. Beispiel 51 Betrachte in R x(t) _ = u(t);

u(t) 2 U

R1 :

Ist U (0; 1), so gibt es keine Kontrollmenge. Ist U = f0g ; so ist jede einpunktige Menge eine invariante Kontrollmenge. Daher gibt es ein Kontinuum von Kontrollmengen. Beispiel 52 Betrachte in R2 x(t) _ =

0 u(t) u(t) 0

x(t);

u(t) 2 U

R1 :

Ist U 6= f0g so sind alle Kreise um den Ursprung invariante Kontrollmengen. Wir beginnen unser systematische Studium von Kontrollmengen mit einigen einfachen Beobachtungen. Zunächst zeigen wir, dass man nicht in eine Kontrollmenge zurückkehren kann. Proposition 53 Sei D eine maximale Menge mit der Eigenschaft, dass für alle x 2 D gilt D clO+ (x). Ferner existiere für x 2 D eine Zeit T > 0 und u 2 U mit '(T; x; u) 2 D. Dann ist '(t; x; u) 2 D für alle 0 t T . Beweis. Wegen der Maximalitätseigenschaft reicht es zu zeigen, dass für 0 t T und jedes y 2 D gilt y 2 clO+ ('(t; x; u)) und '(t; x; u) 2 clO+ (y). Wegen stetiger Abhängigkeit vom Anfangswert ist y 2 clO+ ('(T; x; u)) clO+ ('(t; x; u)), und damit folgt die erste Behauptung. Um die zweite Behauptung zu sehen, betrachte eine Umgebung N ('(t; x; u)). Wegen stetiger Abhängigkeit vom Anfangswert gibt es eine Umgebung N (x) mit '(t; z; u) 2 N ('(t; x; u)) für alle z 2 N (x). Es gibt u1 2 U und t1 > 0 mit '(t1 ; y; u1 ) 2 N (x), weil x 2 D. Daher liefert die zusammengesetzte Kontrolle u2 ( ) =

u1 ( ) für u( t1 ) für

2 [0; t1 ] 2 [t1 ; t1 + t]

dass '(t1 + t; y; u2 ) 2 N ('(t; x; u)). Dies zeigt '(t; x; u) 2 clO+ (y). In der De…nition von Kontrollmengen D wird gefordert, dass man bei Start in D für alle positiven Zeiten in D bleiben kann. Die folgende Proposition zeigt, dass diese Bedingung über‡üssig ist, wenn die Kontrollmenge nichtleeres Inneres hat.

50

KAPITEL 3. NICHTLINEARE KONTROLLSYSTEME

Proposition 54 Sei D Rn eine Menge, die maximal ist mit der Eigenschaft, dass D clO+ (x) für alle x 2 D, und D habe nichtleeres Inneres. Dann ist D eine Kontrollmenge. Beweis. Es reicht zu zeigen, dass es für alle x 2 D eine Kontrolle u 2 U gibt mit '(t; x; u) 2 D für alle t 0. Wähle x 2 D. Dann gibt es T0 > 0 und u0 2 U mit y := '(T0 ; x; u0 ) 2 int D. Sei z 2 int D mit z 6= y. Wegen approximativer Kontrollierbarkeit in D und stetiger Abhängigkeit vom Anfangswert …ndet man eine Kontrolle u1 2 U, eine Zeit T1 > 0 und disjunkte o¤ene Umgebungen Vy ; Vz int D von y bzw. z, so dass '(T1 ; y 0 ; u1 ) 2 Vz 0 für alle y 2 Vy . Nun de…niere eine Trajektorie '(t; x; u); t 0, indem man zunächst mit u0 in der Zeit T0 von x nach y geht; dann geht man in der Zeit T1 mit der Kontrolle u1 von y nach Vz . Approximative Kontrollierbarkeit impliziert, dass man das System zurück nach Vy steuern kann. Dann wiederhole diesen Prozess. Jede Schleife von Vy in Vz und zurück nach Vy braucht mindestens die Zeit T1 . Daher ist diese Trajektorie auf [0; 1) de…niert und nach der vorangehenden Proposition enthalten in D. Es folgt, dass D eine Kontrollmenge ist. Die folgende Proposition zeigt, dass jede Menge approximativer Kontrollierbarkeit in einer maximalen Menge mit dieser Eigenschaft, also einer Kontrollmenge enthalten ist. Proposition 55 Sei D0 Rn eine Menge, die die Eigenschaften (i) und (ii) in der De…nition von Kontrollmengen erfüllt. Dann ist D0 enthalten in einer Kontrollmenge D. Beweis. De…niere D als die Vereinigung aller Mengen, die (i) und (ii) erfüllen und D0 enthalten: Dann ist D eine Kontrollmenge: Die Eigenschaft (i) gilt nach De…nition. Seien x; y 2 D. Dann gibt es z 2 D0 mit y 2 clO+ (z) und z 2 clO+ (x). Wegen stetiger Abhängigkeit vom Anfangswert gilt y 2 clO+ (x). Die Maximalitätseigenschaft ist trivialerweise erfüllt. Dieselben Argumente zeigen, dass Kontrollmengen paarweise disjunkt sind. Jetzt betrachten wir zunächst invariante Kontrollmengen. Proposition 56 Eine Menge C Rn ist eine invariante Kontrollmenge, falls es für alle x 2 C eine Kontrolle u 2 U gibt mit '(t; x; u) 2 C für alle t 0 und clC = clO+ (x) für alle x 2 C, und C maximal mit diesen Eigenschaften ist. Ist insbesondere C = cl O+ (x) für alle x 2 C, so ist C eine invariante Kontrollmenge. Beweis. Nach Annahme gelten die Eigenschaften (i) und (ii) in der De…nition von Kontrollmengen. Die Maximalitätseigenschaft sieht man folgendermaß en:

3.2. KONTROLLMENGEN

51

Falls für y 2 M gilt C clO+ (y) und y 2 clO+ (x) = clC für ein x 2 C, so folgt clO+ (y) = clC, also y 2 C. Die zweite Behauptung ist eine o¤ensichtliche Konsequenz. Bei lokaler Akzessibilität haben invariante Kontrollmengen eine Reihe von schönen Eigenschaften. Insbesondere sind sie positiv invariant, also '(t; x; u) 2 C für t 0; x 2 C; u 2 U. Lemma 57 Das System (3.1) sei lokal akzessibel für alle x in dem Abschluss einer invarianten Kontrollmenge C. Dann gilt (i) intC 6= ;; (ii) cl intC = C und C ist zusammenhängend; (iii) intC und C sind positiv invariant; (iv) intC O+ (x) für alle x 2 C und intC = O+ (x) für alle x 2 intC. (v) Ist das System lokal akzessibel, so gibt es höchstens abzählbar viele invariante Kontrollmengen. Beweis. Wir zeigen zunächst, dass x 2 clC impliziert clO+ (x) clC: Wenn nicht, so gibt es x 2 clC; u 2 U, und T > 0, so dass y := '(T; x; u) 2 = clC: Es gibt dann eine o¤ene Umgebung N (y) (clC)c , dem Komplement von clC; und daher eine o¤ene Umgebung V von x, so dass f'(T; z; u); z 2 V g N (y) (cl C)c . Es gibt daher einen Punkt z 2 C \ V mit '(T; z; u) 2 = cl C, ein Widerspruch, weil C nach Annahme eine invariante Kontrollmenge ist. Lokale Akzessibilität zeigt mit dem gleichen Argument, dass C abgeschlossen ist: Für x 2 cl C gilt clO+ (x) clC und int O+ (x) 6= ;. Daher gibt es ein y 2 int O+ (x) \ C: Die De…nition von invarianten Kontrollmengen zeigt, dass clC = clO+ (y) clO+ (x); d.h. clO+ (x) = clC. Wegen der Maximalität von Kontrollmengen folgt x 2 C; also clC = C: (i) Wegen lokaler Akzessibilität folgt für x 2 C, dass ; = 6 int O+ (x) C. (ii) Wir wissen bereits C = clC, und cl intC clC ist o¤ensichtlich. Für die umgekehrte Richtung wähle x 2 C. Dann ist O+ (x) C und daher int O+ (x) intC: Mann sieht leicht, dass wegen lokaler Akzessibilität int O+ (x) dicht in O+ (x) ist, und O+ (x) ist dicht in C nach De…nition invarianter Kontrollmengen. Deswegen ist int O+ (x) dicht in C, also clC = cl int O+ (x) cl intC: Um den Zusammenhang zu zeigen, nehmen wir an, dass C als disjunkte Vereinigung C = A [ B von nichtleeren o¤enen Mengen A; B geschrieben werden kann, die o¤en und abgeschlossen in C sind. Wegen clC cl intC folgt die Existenz von a 2 int A; b 2 int B: Approximative Kontrollierbarkeit in C von a nach b liefert einen Widerspruch. (iii) Natürlich ist C = clC positiv invariant. Um die positive Invarianz von intC zu sehen, wähle x 2 intC und nimm an, dass es t > 0 und u 2 U gibt mit '(t; x; u) 2 = intC. Dann gibt es eine Umgebung N C von x und

52

KAPITEL 3. NICHTLINEARE KONTROLLSYSTEME

f'(t; y; u); y 2 N g ist eine Umgebung von '(t; x; u) mit f'(t; y; u); y 2 N g \ (intC)c 6= ;. Wegen cl intC = C gibt es z 2 C c \ '(t; y; u); y 2 N g. Dies widerspricht der positiven Invarianz von C. (iv) Wähle x 2 C und y 2 intC: Wir wissen cl O + (x) = clC = C: Lokale Akzessibilität impliziert int O (y) \ intC 6= ;: Deswegen gibt es z 2 O+ (x) \ intO (y) \ intC und daher ist y 2 O+ (x). Positive Invarianz von intC; impliziert O+ (x) = intC für y 2 intC: (v) Die Anzahl der invarianten Kontrollmengen höchstens abzählbar, weil sie nichtleeres Inneres haben, und Rn eine abzählbare Basis der Topologie besitzt. Während im Allgemeinen keine Kontrollmengen existieren müssen, haben wir im kompakten Fall das folgende Existenzresultat für invariante Kontrollmengen. Satz 58 Sei K eine kompakte, positiv invariante Menge für (3.1). Dann gibt es für jedes x 2 K eine invariante Kontrollmenge Cx clO+ (x). Ist das System lokal akzessibel von jedem Punkt in K; so gibt es höchstens endlich viele invariante Kontrollmengen in K. Beweis. Für x 2 K betrachte die Familie F = fclO+ (y); y 2 clO+ (x)g. Dann ist F nichtleer und jede Menge in F ist positiv invariant. Ferner besteht F aus abgeschlossenen Teilmengen eines kompakten metrischen Raums und ist (halb-)geordnet bezüglich der Mengeninklusion (d.h., Transitivität, Re‡exivität und Antisymmetrie gelten). Für jede lineare Kette T absteigende + + fclO (xi ); i 2 Ig gilt wegen der Kompaktheit i2I clO (xi ) 6= ;. Also hat die Kette eineT untere Schranke, gegeben durch clO+ (y) für ein beliebiges Element y 2 i2I clO+ (xi ). Daher erfüllt F die Voraussetzungen von Zorns Lemma (vgl. zum Beispiel Pedersen [17, Section 1.1]), und besitzt daher ein minimales Element, das natürlich die Form Cx = clO+ (y) für ein y 2 clO+ (x) hat: Die Menge Cx ist positiv invariant und clO+ (y) = Cx für alle y 2 Cx ; weil Cx minimal ist Daher ist Cx nach Proposition 56 eine invariante Kontrollmenge. Sei jetzt, im Widerspruch zur zweiten Behauptung, fCn ; n 2 Ng eine abzählbare Kollektion von invarianten Kontrollmengen in K. Wegen der lokalen Akzessibilität gibt es xn 2 intCn . Sei x der Limes einer Teilfolge, die wir wieder mit (xn ) bezeichnen. Wähle y 2 intCx ; wobei Cx O+ (x) eine invariante Kontrollmenge ist. Dann gibt es t > 0 und u 2 U mit y = '(t; x; u) nach Lemma 57. Für eine o¤ene Umgebung U (y) int Cx gibt es eine o¤ene Umgebung V (x) so dass f'(t; z; u); z 2 V g U . Daher gibt es ein N 2 N; so dass für alle n N gilt Cn = Cx , nach Lemma 57.

3.2. KONTROLLMENGEN

53

Im allgemeinen ist es nicht wahr, dass invariante Kontrollmengen positiv invariant sind. Ferner können variante Kontrollmengen auch bei lokaler Akzessibilität leeres Inneres haben. Die Anzahl von Kontrollmengen mit nichtleerem Innern kann auch in kompakten Mengen unendlich sein. Einige Eigenschaften von invarianten Kontrollmengen gelten jedoch auch für variante Kontrollmengen. Lemma 59 Sei D eine Kontrollmenge mit nichtleerem Innern. (i) Ist das System lokal akzessibel für alle x 2 clD, so ist D zusammenhängend und cl int D = cl D. (ii) Ist y 2 int D lokal akzessibel, so ist y 2 O+ (x) für alle x 2 D. (iii) Ist das System lokal akzessibel für alle y 2 intD; so ist intD O+ (x) für alle x 2 D; und für jedes y 2 intD gilt D = clO+ (y) \ O (y) :

(3.11)

Ferner ist die Anzahl der Kontrollmengen mit nichtleerem Innern höchstens abzählbar. Beweis. (i) O¤enbar ist cl int D clD. Für die Umkehrung reicht es zu zeigen, dass D cl intD. Wähle x 2 D. Dann gibt es t > 0 und u 2 U und eine o¤ene Umgebung N von x mit f'(t; z; u); z 2 N g intD. Nun ist x 2 D clO+ (y) = cl intO+ (y) für y 2 D, also ist die o¤ene Menge intO+ (y)\N nichtleer und enthalten in D. Daher x 2 cl intD. Wie in Lemma 57 beweist man, dass D zusammenhängend ist. (ii) Sei x 2 D: Wegen lokaler Akzessibilität von y 2 intD …ndet man t > 0 so dass ; = 6 int t (y) intD: Wähle z 2 int t (y) : Wegen z 2 clO+ (x), + folgt y 2 O (x). (iii) Es ist clO+ (x) \ O (x) D nach De…nition von Kontrollmengen. Die umgekehrte Inklusion folgt nach dem obigen Beweis. Die letzte Aussage folgt, weil die Topologie von Rn eine abzählbare Basis besitzt. Bemerkung 60 Die Formel (3.11) reduziert die Berechnung von Kontrollmengen auf die von positiven und negativen Orbits Wie zeigen jetzt eine topologische Charakterisierung invarianter Kontrollmengen. Zunächst zeigt das Beispiel x_ = ux(1

x); u(t) 2 [ 1; 1];

mit den invarianten Kontrollmengen f0g; f1g; ( 1; 0); (0; 1); [1; 1), dass invariante Kontrollmengen bei fehlender lokaler Akzessibilität nicht abgeschlosssen sein müssen.

54

KAPITEL 3. NICHTLINEARE KONTROLLSYSTEME

Satz 61 Es gelte lokale Akzessibilität für alle x im Abschluss clD einer Kontrollmenge D mit nichtleerem Innern. Die Menge D ist eine invariante Kontrollmenge genau dann, wenn D abgeschlossen ist. Beweis. Ist D eine invariante Kontrollmenge, so ist D nach Lemma 57 abgeschlossen. Für die Umkehrung sei D eine variante Kontrollmenge und x 2 int D. Dann existieren t0 > 0 und eine Kontrollfunktion u mit '(t0 ; x; u) 2 = cl D. Sei T = max ft t0 ; ' (t; x; u) 2 clDg. Dann ist ' (T; x; u) 2 = D und daher ist D nicht abgeschlossen. Dies sieht man wie folgt: Ist y := '(T; x; u) 2 D, so gibt es u1 und t1 so dass ' (t1 ; y; u1 ) = x 2 int D, nach Lemma 59. Daher gibt es eine Umgebung N von y so dass ' (t1 ; z; u1 ) 2 int D für alle z 2 N . Dies gilt insbesondere für z = ' (t2 ; x; u) 2 N mit t2 T > 0, klein. Dann ist D [ fzg

eine Menge mit nichtleerem Innern, die für alle Anfangswerte x0 in ihr in clO+ (x0 ) enthalten ist, also ist sie nach Lemma 54 in einer Kontrollmenge enthalten und daher gleich D: Insbesondere ist z = '(t2 ; x; u) 2 D im Widerspruch zur De…nition von T . Jetzt analysieren wir das Kontrollierbarkeitsverhalten unter Zeitumkehr und die Feinstruktur des Randes. Das zeitumgekehrte System zu (3.1) x(t) _ =

f (x(t); u(t)); t 2 R;

(3.12)

das man erhält, indem man t durch t ersetzt. Lokale Akzessibilität in x gilt für (3.1) genau dann wenn sie für (3.12); das gleiche gilt für die AkzessibilitätRang-Bedingung (3.3): Lemma 62 Sei D eine Kontrollmenge mit nichtleerem Innern für (3.1) und es gelte lokale Akzessibilität für alle x 2 int D. Dann existiert genau eine Kontrollmenge D von (3.12) mit int D = int D . Beweis. Exakte Kontrollierbarkeit im Innern impliziert, dass es genau eine Kontrollmenge D des zeitumgekehrten Systems mit int D int D gibt. Wendet man dasselbe Argument auf D an, so erhält man die Behauptung. Dies Lemma zeigt, dass nur am Rand von Kontrollmengen interessante Dinge bei Zeitumkehr passieren können. Zur Analyse dieser Feinstruktur führen wir die folgenden Begri¤e ein. De…nition 63 Sei D eine Kontrollmenge mit nichtleerem Innern. De…niere die folgenden Teilmengen des Randes @D:

3.2. KONTROLLMENGEN

55

(D) = fx 2 @D; es gibt y 2 int D, t > 0; u 2 U mit x = '(t; y; u)g ; (D) = fx 2 @D; es gibt y 2 int D, t > 0; u 2 U mit y = '(t; x; u)g ; ~ (D) = fx 2 @D; O+ (x) \ D = ; und O (x) \ int D = ;g. Diese Mengen heiß en Austritts-, Eintritts- und tangentialer Rand von D. Lemma 64 Sei D Kontrollmenge mit nichtleerem Innern, so dass lokale Akzessibilität in clD gilt. (i) Die Mengen (D), (D), und ~ (D) bilden eine Dekomposition von @D. (ii) (D) und (D) sind o¤en in @D und ~ (D) ist abgeschlossen in @D. (iii) ~ (D) = cl (D) \ cl (D) und int@D ~ (D) = ;. Beweis. (i) Dies folgt aus der Maximalität von Kontrollmengen. (ii) Weil die Lösungsabbildungen Di¤eomorphismen sind, sind (D) und (D) o¤en in @D: Dies impliziert die Abgeschlossenheit von ~ (D) wegen der Dekompositionseigenschaft. (iii) Sei x 2 ~ (D) und wähle y 2 int+t (x) : Dann gibt es t und u 2 U und eine Umgebung V von x, so dass y 2 f'f ; x; u); x 2 V g int+t (x). Weil V Punkte in int D enthält, und O+ (x) \ D = ; und t > 0 beliebig klein gewählt werden kann, folgt x 2 cl (D). Ein ähnliches Argument gilt für O (x) und zeigt x 2 cl (D). Die umgekehrte Inklusion folgt aus (i) und (ii). Dann impliziert (ii) auch die letzte Behauptung. Die nächste Proposition klärt das Verhalten des Randes unter Zeitumkehr. Proposition 65 SeiD eine Kontrollmenge mit nichtleerem Innern für (3.1) und es gelte lokale Akzessibilität für alle x 2 clD. Dann gilt für jedes x 2 @D: (i) x 2 (D) genau dann wenn x 2 D: (ii) x 2 (D) genau dann wenn x 2 D , wobei D die Kontrollmenge des zeitumgekehrte Systems aus Lemma 62 ist. (iii) x 2 ~ (D) genau dann wenn x 2 = D[D : Beweis. (i) Wenn x 2 D, so folgt x 2 (D) direkt aus der De…nition. Umgekehrt, ist x 2 (D), so ist x 2 clO+ (y) für alle y 2 D, und D O+ (x). Also folgt x 2 D nach Proposition 54. (ii) folgt durch Zeitumkehr: O (x) der Vorwärts-Orbit des zeitumgekehrten Systems. (iii) folgt aus (i) und (ii) wegen der Zerlegungseigenschaft. Das einfache Beispiel 10 einer Kontrollmenge an einem hyperbolischen Fixpunkt illustriert die verschiedenen Teile des Randes (beachte, dass es drei Kontrollmengen in diesem Bild gibt). Dieses Beispiel regt die Frage an, wann (auch ohne Hyperbolizität) um ein Gleichgewicht des unkontrollierten Systems eine Kontrollmenge existiert.

56

KAPITEL 3. NICHTLINEARE KONTROLLSYSTEME

Proposition 66 Betrachte das System (2.8) mit 0 2 U und einen Punkt p mit f (p; 0) = 0, d.h., p ist ein Gleichgewicht des unkontrollierten Systems. Wenn p 2 intO+ (p) \ intO (p), so existiert eine Kontrollmenge D mit p 2 intD. Beweis. Es gibt Umgebungen V (p) und W (p) mit V (p) O+ (p) und W (p) O (p). Dann ist V (p) \ W (p) eine Menge vollständiger Kontrollierbarkeit mit nichtleerem Innern. Sie ist enthalten in einer maximalen Menge mit dieser Eigenschaft, die natürlich wieder nichtleeres Inneres hat. Dies ist nach Proposition 54 eine Kontrollmenge.

Kapitel 4 Der Kontroll‡uss In diesem Kapitel beschreiben wir Kontrollsysteme als dynamische Systeme. Dabei wird einem Kontrollsystem x(t) _ = f (x(t); u(t)); u 2 U;

in Rn das dynamische System, der Kontroll‡uss, t

:U

Rn ! U

Rn ; (u; x) 7! (u(t + ); '(t; x; u)); t 2 R,

(4.1)

zugeordnet. Um Stetigkeit dieses dynamischen Systems zu erhalten, führen wir im ersten Abschnitt eine angemessene Metrik auf U ein, bevor wir im zweiten Abschnitt den Kontroll‡uss diskutieren. Danach beschäftigen wir uns mit der Bedeutung von Kontrollmengen für den Kontroll‡uss. Die Konstruktion des Kontroll‡usses ist durch die folgende Überlegung geleitet: Für einen Anfangswert x 2 Rn , Zeiten t; s 2 R und eine Kontrollfunktion u erfüllt die zugehörige Trajektorie o¤enbar '(s + t; x; u) = '(s; '(t; x; u); u(t + )). Man muss also die zugehörige Kontrollfunktion verschieben. Dies wird in der ersten Komponente des Kontroll‡usses getan. Die erste Komponente von (4.1) ist unabhängig vom Anfangswert in der zweiten Komponente. Solch einen Fluss nennt man in der Theorie Dynamischer Systeme einen Schiefprodukt‡uss (skew product ‡ow). Die Betrachtung von Kontrollsystemen als dynamische Systeme ermöglicht es, Konzepte und Methoden aus der Theorie dynamischer Systeme auf Kontrollsysteme zu übertragen, insbesondere kann man so den Subdivisionsalgorithmus zur Berechnung von relativen globalen Attraktoren verallgemeinern. Wir wollen eine Metrik auf U de…nieren, so dass Trajektorien stetig von u 2 U abhängen, also xn ! x und un ! u in U =) '(t; xn ; un ) ! '(t; x; u) für jedes t 2 R. 57

58

KAPITEL 4. DER KONTROLLFLUSS

Ferner möchten wir, dass U ein kompakter metrischer Raum wird, damit jede Folge (un ) einen Häufungspunkt besitzt. Daher beschäftigen wir uns zunächst mit U. Da U in einem unendlich-dimensionalen Raum liegt, ist die Wahl einer Norm-Topologie auf U schwerlich mit der Kompaktheit vereinbar. Dies schließ t zum Beispiel die naheliegende Wahl für die Metrik mit Hilfe der L1 -Norm aus. Einen Ausweg bieten schwache Topologien: Sei Z ein Banachraum mit Dualraum Z = fz : Z ! R; z ist linear und stetigg: Die schwache Topologie auf Z ist die schwächste Topologie, für die alle z 2 Z stetig sind. Ist Z re‡exiv, also (Z ) zu Z isomorph mittels z 7! zz de…niert durch zz (z ) = z (z);

(4.2)

so ist die Einheitskugel in Z schwach kompakt. Leider bietet sich keine kanonische Wahl für einen re‡exiven Banachraum Z mit U Z an (L2 (R; Rm ) scheidet aus, weil dann konstante Kontrollfunktionen nicht in Z liegen). Eine Alternative ist folgendes: Ist U Z , also enthalten in einem dualen Banachraum, so ist nach dem Satz von Alaoglu wiederum die Einheitskugel in Z kompakt in der schwach -Topologie: Dies ist die schwächste Topologie, so dass alle linearen Abbildungen der Form (4.2) stetig werden. Speziell hat für Z = L1 (R; Rm ) der Raum Z = L1 (R; Rm ) eine schwach -kompakte Einheitskugel; die Dualität ist gegeben durch Z 1 (z ; z) = z(s)T z (s) ds für z 2 L1 (R; Rm ); z 2 L1 (R; Rm ). 1

Daraus ergibt sich unmittelbar die Forderung, dass unser Kontrollwertebereich beschränkt sein muss. Die Bedingungen, die sich aus der Forderung nach stetiger Abhängigkeit der Trajektorien von den Kontrollen ergeben, werden wir in Abschnitt 4.2 diskutieren.

4.1

Der Shift auf U

Wir setzen im Folgenden voraus, dass U Menge ist, und betrachten

Rm eine kompakte und konvexe

U = fu : R ! Rm ; u(t) 2 U für fast alle t 2 Rg = fu 2 L1 (R; Rm ); u(t) 2 U für fast alle t 2 Rg:

4.1. DER SHIFT AUF U

59

De…niere den Shift oder Verschiebe-Operator auf U durch tu

= u(t + ); t 2 R:

O¤enbar hat die dynamischen Systeme-Eigenschaften 0 = id und t+s = t s für t; s 2 R. Der nächste Satz beschreibt unsere gesuchte Topologie. Satz 67 Die Menge U ist kompakt und metrisierbar in der schwach Topologie von L1 (R;Rm ) = (L1 (R;Rm )) ; eine Metrik ist gegeben durch R 1 X 1 j R hu(t) v(t); xn (t)i dt j R d(u; v) = ; (4.3) n 1+ j 2 hu(t) v(t); xn (t)i dt j R n=1

wobei fxn ; n 2 Ng eine abzählbare dichte Teilmenge von L1 (R;Rm ) ist und h , i ein inneres Produkt in Rm bezeichnet. Mit dieser Metrik wird U ein kompakter, vollständiger, separabler metrischer Raum.

Bemerkungen zum Beweis: Der Dualraum von L1 (R;Rm ) ist L1 (R;Rm ) (siehe z.B. [3, Theorem 4.5.1] und beachte, dass das Lebesgue-Maßauf R endlich ist). Ferner ist L1 (R;Rm ) ist separabel (siehe z.B. [3, Proposition 3.4.5] und beachte, dass die Algebra der Borel-Mengen auf R abzählbar erzeugt ist). Nach dem Satz von Alaoglu hat der Dualraum eines separablen Banachraums eine kompakte, metrisierbare Einheitskugel in der schwach Topologie, und eine Metrik ist durch (4.3) gegeben (siehe z.B. [6, Theorem 4.5.1]). Ist also U schwach abgeschlossen, so ist es schwach kompakt und ein kompakter metrischer Raum; Daher ist U vollständig (siehe z.B. [7, Theorem 4.3.28]) und separabel ([7, Theorems 4.3.5 and 4.3.27]). Es bleibt zu zeigen, dass U schwach abgeschlossen in L1 (R;Rm ) ist. Dies folgt, weil für jedes kompakte Intervall I R die konvexe und Norm-abgeschlossene Menge fu j I; u 2 Ug L2 (I; Rm g schwach abgeschlossen ist. Daher ist ein schwach Limes u einer Folge (un ) U wieder in U, weil für jedes kompakte I die Restriktionen (un j I) schwach konvergent gegen u j I in L2 (I; R) sind. Im Weiteren …xieren wir der Einfachheit halber solch eine Metrik. Zunächst analysieren wir den Shift auf U. Lemma 68 Der Shift

de…niert ein stetiges dynamisches System auf U.

Beweis. Es ist nur die Stetigkeit von nachzuweisen. Betrachte tn ! t in R und un ! u in U. Dann gilt für alle z 2 L1 (R;Rm ) Z Z hun (tn + ); z( )i d hu(t + ); z( )i d R R Z Z hun (tn + ) un (t + ); z( )i d + hun (t + ) u(t + ); z( )i d R

R

60

KAPITEL 4. DER KONTROLLFLUSS =

Z

R

+

Z

hun ( ); z(

R

hun ( )

Z

tn )i d

R

u( ); z(

t)i d

hun ( ); z(

t)i d

:

(hier sind in den ersten beiden Integralen die Transformationen 0 = tn + und 0 = t + verwendet). Der zweite Summand konvergiert gegen 0, weil un ! u in U; der erste kann abgeschätzt werden durch Z sup jwj jz( tn ) z( t)j d : w2U

R

Hier konvergiert das Integral gegen 0 für tn ! t . Dieser Fakt (“Stetigkeit der Norm in L1 ”) kann folgendermaß en gesehen werden: Für ein beschränktes Intervall I R und t 2 R de…niere I(t) = I + t: Dann erfüllt die charakteristische Funktion 1; 2 I I( ) = 0; 2 =I die Beziehung Z j I(

t)

I(

)j d =

Z

d +

InI(t)

I

Z

d

I(t)nI

= (I) + (I(t))

2 (I \ I(t)):

Sei I(t2 ) \ I ::: I(tn ) \ I S1 jtn j ! 0 mit I(t1 ) \ I e n=1 I(tn ) \ I = I und wir erhalten für die Lebesgue-Maß

::: . Dann ist

lim m(I \ I(tn )) = m(I) = lim m(I(tn )):

n!1

n!1

Dies beweist die Behauptung für I in t = 0: Dann zeigt man die Behauptung für beliebiges t 2 R; für Treppenfunktionen, und dann für alle Elemente x 2 L1 . Wir haben gezeigt, dass (tn ; un ) = un (tn + ) !

(t; u) = u(t + ) in U.

Beachte, dass u 2 U genau dann eine periodische Funktion ist, wenn u ein periodischer Punkt des Flusses (U; ) ist. Man kann zeigen, dass die periodischen Funktionen, also die periodischen Punkte des Shifts, dicht in U sind. De…nition 69 Ein Fluss auf einem metrischen Raum X (also eine stetige Abbildung : R X ! X mit (0; x) = x und (t + s; x) = (t; (s; x))

4.1. DER SHIFT AUF U

61

für alle t; s und x) ist topologisch mischend, falls für je zwei o¤ene Mengen V1 ; V2 X ein T > 0 existiert, so dass ( T; V1 ) \ V2 6= ;: Proposition 70 Der Shift (U; ) ist topologisch mischend. Beweis. Es reicht, o¤ene Mengen in einer Basis der schwach Topologie zu betrachten (dann ist jede o¤ene Menge Vereinigung von Mengen aus der Basis). Daher betrachten wir nur o¤ene Mengen der Form (siehe z.B. Dunford/Schwartz [6]) Z Vj = u 2 U; huj ( ) u( ); zij ( )i d < " für i = 1; :::; kj ; R

mit uj 2 U, " > 0; kj 2 N, und zij 2 L1 (R; Rm ) für i = 1; :::; kj ; j = 1; 2: Wir müssen zeigen, dass es T0 > 0 gibt mit ( T0 ; V1 ) \ V2 6= ;: Es gibt T > 0, so dass für alle i; j Z " jzij ( )j d < : diamU Rn[ T;T ] Setze T0 := 2T und de…niere v( ) =

u2 ( + 2T ) für u1 ( ) für

Dann v 2 V1 weil für i = 1; :::; k1 Z hu1 ( ) v( ); zi1 ( )i d R

Z

2 ( 1; T ] 2 ( T; 1) :

T

jhu1 ( ) v( ); zi1 ( )ij d Z T diamU jzi1 ( )j d < ": 1

1

Andererseits ist, ( T0 ; v) 2 V2 ; weil für i = 1; :::; k2 Z Z hu2 ( ) v( T0 ); zi2 ( )i d = hu2 ( + 2T ) v( ); zi2 ( + 2T )i d R R Z 1 = hu2 ( + 2T ) u1 ( ); zi2 ( + 2T )i d T Z 1 hu2 ( ) u1 ( 2T ); zi2 ( )i d = T Z 1 diamU jzi2 ( )j d < ": T

62

KAPITEL 4. DER KONTROLLFLUSS

Bemerkung 71 Ein stetiger Fluss heiß t topologisch transitiv, falls ein x 2 X existiert mit !(x) = fy 2 X; lim

tk !1

(tk ; x) = yg = X:

Jeder topologisch mischende Fluss ist topologisch transitiv (siehe z.B. Colonius/Kliemann [4, Proposition B.2.4]).

4.2

Der Kontroll‡uss

Um die Bedingungen zu klären, die sich aus der Forderung nach stetiger Abhängigkeit der Trajektorien von den Kontrollen ergeben, betrachte zunächst Systeme der Form x(t) _ = f (u(t)); u(t) 2 =U

Rm .

Sei un ! u0 in L1 (R; Rm ) und betrachte der Einfachheit halber x(0) = 0. Dann ist Z t xn (t) = f (un (s)) ds: 0

Man erhält Konvergenz, falls die Abbildungen Z t f (u(s)) ds u 7! 0

von der Form (4.2) mit einer L1 -Funktion ist. Dies ist zum Beispiel der Fall, wenn m X f (u) = ui (s)fi : i=1

Dann ist

Z

0

t

f (u(s)) ds =

Z

1 1

u(s)T z(s) ds für u 2 L1 (R; Rm )

mit z 2 L1 (R; Rm ) de…niert durch z(s) =

T [0;t] (s)(f1 ; :::; fm ) :

Wir werden sehen, dass alle kontrolla¢ nen Systeme erlaubt sind, also Systeme der Form x(t) _ = f0 (x(t)) +

m X i=1

ui (t)fi (x(t)); u 2 U;

(4.4)

4.2. DER KONTROLLFLUSS

63

in Rn unter unseren Standard-Voraussetzungen. Für u 2 U und x 2 Rn ist die eindeutige Lösung mit '(0; x; u) = x wieder '(t; x; u); t 2 R: Der zugehörige Kontroll‡uss ist Rn ! U

U

:R

Satz 72 Die Abbildung Rn .

Rn ;

(t; u; x) = ( (t; u); '(t; x; u)):

de…niert ein stetiges dynamisches System auf U

Beweis. Die Gruppeneigenschaften gelten natürlich und der Shift ist nach Proposition 68 stetig. Für die Stetigkeit von betrachte Folgen tk ! t0 in R, uk ! u0 in U, und xk ! x0 in Rn : Kürze ab 'k (t) = '(t; xk ; uk ); t 2 R, k = 0; 1; ::: : Wir müssen 'k (tk ) ! '0 (t0 ) zeigen. Man …ndet 'n (tk )

'n (tk )

'0 (t0 )

'n (t0 ) + 'n (t0 )

'0 (t0 ) :

Der erste Summand geht gegen 0 wegen der gleichmäß igen Beschränktheit der Ableitungen, und es ist 'k (t0 ) x

k

'0 (t0 ) x

0

+

Z

t0

f0 ('k ( ))

f0 ('0 ( )) d

0

+

Z

t0

0

+

Z

0

t0

m X

i=1 m X

uki ( ) fi ('k ( )) uki ( )

fi ('0 ( )) d

u0i (t) fi ('0 ( )) d

:

i=1

Hier konvergieren der erste und der vierte Summand gegen 0 nach AnnahR t0 me; der zweite und dritte sind nach oben durch c1 0 'k ( ) '0 ( ) d beschränkt, wobei c1 von den Lipschitz-Konstanten der Vektorfelder f0 ; :::; fm und dem Kontrollwertebereich U abhängt. Dann liefert Gronwalls Lemma die Behauptung. Wir zeigen jetzt, dass der Kontroll‡uss über den Kontrollmengen die Eigenschaften des Shifts erbt. De…niere den Lift von Kontrollmengen D M (mit nichtleerem Innern) nach U Rn durch D = cl f(u; x) 2 U

M; '(t; x; u) 2 intD für alle t 2 Rg ;

Beachte, dass D und f(u; x) 2 U invariant unter

M; '(t; x; u) 2 intD für alle t 2 Rg

sind; ist D beschränkt, so ist der Lift D kompakt.

(4.5)

64

KAPITEL 4. DER KONTROLLFLUSS

Proposition 73 Es sei D Rn eine Kontrollmenge mit nichtleerem Innern und jeder Punkt im Innern von D sei lokal akzessibel. Dann hat der Lift D U Rn von D die folgenden Eigenschaften: (i) die periodischen Punkte von sind dicht in D; (ii) Die Restriktion von auf D ist topologisch mischend. Beweis. (i) Es reicht zu zeigen, dass jedes (u; x) 2 D mit '(t; x; u) 2 intD für alle t 2 R durch periodische Punkte approximiert werden kann. Wähle solch ein (u; x) und eine Umgebung W = (V N ) \ D von (u; x) mit V U und N M . Wir können annehmen, dass Z V = v 2 U; hu(t) v(t); zi (t)i dt < " für i = 1; :::; k R

mit zi 2 L1 (R; Rm ). Es gibt T > 0; so dass für i = 1; :::; k Z " jzi (t)j dt < : diamU Rn[ T;T ] Nach Annahme gilt '( T; x; u), '(T; x; u) 2 intD. Daher existieren, wegen exakter Kontrollierbarkeit in intD, eine Zeit T1 > 0 und u0 2 U mit '(T1 ; '(T; x; u); u0 ) = '( T; x; u): De…niere up (t) =

u(t); t 2 [ T; T ] u0 (t T ); t 2 [T; T + T1 ]

und setze up zu einer (2T + T1 )-periodischen Funktion auf R fort. Die zugehörige Trajektorie '(t; x; up ) ist ebenfalls periodisch mit Periode 2T + T1 und enthalten in int D, wegen der Maximalität von Kontrollmengen. Daher ist (up ; x) ein periodischer Punkt in D. Ferner gilt für i = 1; :::; k, Z Z hu(t) up (t); zi (t)i dt diamU jzi (t)j dt < ": Rn[ T;T ]

R

Also ist up 2 V und daher (up ; x) 2 W . (ii) Wir müssen zeigen, dass für jedes Paar W1 ; W2 von o¤enen Mengen in D ein T0 > 0 existiert, so dass ( T0 ; W1 ) \ W2 6= ;. Wir können wieder annehmen, dass für j = 1; 2 die Menge Wj die folgende Form hat: Wj = (Vj Nj ) \ D mit '(t; xj ; uj ) 2 intD für alle t 2 R, Nj = fy 2 Rn ; kxj yk < "g, und Z Vj = u 2 U; huj ( ) u( ); zij ( )i d < " für i = 1; :::; kj : R

4.2. DER KONTROLLFLUSS Es gibt T > 0, so dass für j = 1; 2 und i = 1; :::; kj Z " jzij ( )j d < : diamU Rn[ T;T ]

65

(4.6)

Ferner gibt es t0 > 0 und u0 2 U mit '(t0 ; '(T; x2 ; u2 ); u0 ) = '( T; x1 ; u1 ). De…niere u 2 U durch 8 u2 (t) für t 2 ( 1; T ] < u (t T ) für t 2 [T; T + t0 ) u(t) = 0 : u1 (t t0 2T ) für t 2 [T + t0 ; 1):

Mit (4.6) sieht man, dass u 2 V2 und u(t0 + 2T + ) 2 V1 : Ferner gilt nach Konstruktion '(t0 + 2T; x2 ; u) = '(t0 + T; '(T; x2 ; u2 ); u0 ) = x1 : Daher ist (u; x2 ) 2 W2 und (u(t0 + 2T + ); '(t0 + 2T; x2 ; u)) 2 W1 und die Behauptung folgt mit T0 := t0 + 2T . In der folgenden Situation erhält man ohne weiteres die Existenz einer Kontrollmenge: Sei (u; x) 2 U Rn ein periodischer Punkt. Aus den De…nitionen folgt unmittelbar, dass eine Kontrollmenge D Rn existiert mit x 2 D. Mit u 0 2 U gilt dies insbesondere für einen periodischen Punkt des unkontrollierten Systems x_ = f0 (x). Für allgemeine kompakte invariante Mengen gilt das folgende Resultat. Lemma 74 Es sei W U Rn eine kompakte invariante Menge mit Projektion Rn W in Rn . Dann gibt es eine Kontrollmenge D Rn mit Rn W \D 6= ;. Insbesondere gilt dies für kompakte ! Limesmengen !(u; x): Beweis. Jede kompakte invariante Menge enthält eine minimale abgeschlossene invariante Teilmenge, etwa W0 . Dann ist jede Trajektorie dicht in W0 und daher sind alle x; y 2 Rn W0 von einander approximativ erreichbar, also enthalten in einer Kontrollmenge. Das folgende Resultat zeigt, dass es eine 1-1-Beziehung zwischen Kontrollmengen und maximalen topologisch mischenden Mengen des Kontroll‡usses gibt. Satz 75 Es sei D Rn D

U

Rn eine kompakte Menge, so dass

= fx 2 Rn ; es gibt u 2 U mit (u; x) 2 Dg

66

KAPITEL 4. DER KONTROLLFLUSS

nichtleeres Inneres hat und aus lokal akzessiblen Punkten besteht. Die Menge D genau dann eine maximale topologisch mischend, wenn es eine Kontrollmenge D gibt, so dass D ihr Lift von der Form (4.5) ist. In diesem Fall ist D eindeutig und intD = int

Rn D

und clD =

Rn D:

(4.7)

Beweis. Wir betrachten zunächst D de…niert in (4.5). Nach Proposition 73 ist D topologisch mischend. Sie erfüllt auch die erste Gleichung in (4.7), weil cl D = cl intD und weil für jedes x 2 intD ein u 2 U existiert, so dass '( ; x; u) periodisch und enthalten in intD ist. Dann folgt auch die zweite Gleichung. Wir müssen noch die Maximalität von D zeigen: ist D0 D topologisch mischend, so auch topologisch transitiv (Übung). Also existiert (u; x) 2 D0 mit !(u; x) = D0 und daher gibt es t0 2 R, so dass '(t; x; u) 2 intD für alle t t0 : Wegen x0 = '(t0 ; x; u) 2 intD; gibt es v 2 U mit '(t; x; v) 2 intD für alle t < 0. De…niere u0 (t) =

v(t + t0 ) für t < t0 u(t) für t t0 :

Dann ist (u0 ; x0 ) 2 D und '(t; x0 ; u0 ) 2 intD für alle t 2 R; und !(u0 ; x0 ) = !(u; x) = D0 . Daher ist D0 = !(u0 ; x0 ) D, weil D abgeschlossen ist, und es folgt die Maximalität von D. Für die umgekehrte Richtung betrachte eine maximale topologisch mischende Menge D mit int( Rn D) 6= ;: Wir zeigen, dass es für x1 ; x2 2 int( Rn D) eine Kontrolle u 2 U und t > 0 gibt mit '(t; x1 ; u) = x2 : Sei y1 2 intO+ (x1 ) \ int Rn D und y2 2 intO (x2 ) \ int( Rn D). Betrachte Umgebungen V1 von y1 und V2 von y2 mit V1 intO+ (x1 ) und V2 intO (x2 ): Weil D topologisch transitiv ist, gibt es (u; x) mit !(u; x) = D. Daher kann ein Punkt in V2 von einem Punkt in V1 erreicht werden, und also kann x2 von x1 erreicht werden, wie behauptet. Dies impliziert die Existenz einer Kontrollmenge D mit int( Rn D) intD. Dann kann man D zu einer maximalen topologisch mischenden Menge D0 liften. Wir behaupten D0 D; 0 0 dann impliziert die Maximalität von D , dass D = D, wie gewünscht. Wegen !(u; x) = D und int( Rn D) intD = int( Rn D0 ); …ndet man wie im ersten Teil des Beweises (u0 ; x0 ) mit !(u0 ; x0 ) = D. Nun impliziert die Invarianz von D0 , dass D0 D: Theorem 75 zeigt, dass im lokale akzessiblen Fall die maximalen topologisch mischenden Mengen, deren Projektion auf Rn innere Punkte hat, durch Kontrollierbarkeitseigenschaften charakterisiert sind. Dieses Resultat ist der Ausgangspunkt für eine Theorie, die Kontrollsysteme als dynamische Systeme interpretiert, und die Kontrollmengen als die geeigneten Limesobjekte.

4.2. DER KONTROLLFLUSS

67

Dann kann man zum Beispiel Linearisierung, Bifurkationsfragen, etc. diskutieren. Kontrollsysteme erweisen sich damit als eine besondere Klasse von nichtautonomen Di¤erentialgleichungen, die spezielle Eigenschaften haben, so dass viele Fragen im Kontext der Theorie dynamischer Systeme, genauer der Schiefprodukt‡üsse, behandelt werden können. Bei der numerischen Lösung von Di¤erentialgleichungen kann man im Allgemeinen kleine Sprünge nicht ausschließ en. Daher ist die Forderung nach Kontrollierbarkeit von einem Punkt zum anderen sehr scharf und numerisch schwer nachprüfbar. Einen Hinweis, wie man dies umgehen kann, erhält man aus der Theorie dynamischer Systeme: Kettentransienz erlaubt (beliebig) kleine Sprünge. Der folgende Begri¤ ist eine Adaption an die Situation von Kontrollsystemen und stellt eine Abschwächung der Kontrollierbarkeitsforderung dar. Weil der Shift auf U und der Kontroll‡uss eingeschränkt auf den Lift D einer beschränkten Kontrollmenge mit nichtleerem Innern topologisch transitiv sind, folgt, dass diese Flüsse kettentransitiv sind. Wir werden jedoch sehen, dass dies nicht die einzigen kettentransitiven Mengen des Kontroll‡usses sind Dafür führen wir eine abgeschwächte Version von approximativer Kontrollierbarkeit ein, die kleine Sprünge erlaubt. De…nition 76 Es seien x; y 2 Rn und "; T > 0: Eine kontrollierte ("; T ) Kette & von x nach y ist gegeben durch k 2 N; x0 ; :::; xk 2 Rn ; u0 ; :::; uk 1 2 U und t0 ; :::; tk 1 T mit x0 = x; xk = y; und d('(tj ; xj ; uj ); xj+1 )

" für alle j = 0; :::; k

1:

Gibt es für alle "; T > 0 eine ("; T ) Kette von x nach y, so ist der Punkt x nach y kettenkontrollierbar. De…nition 77 Eine Menge E Rn heiß t Kettenkontrollmenge des Systems (4.4) falls (i) es für alle x 2 E eine Kontrolle u 2 U gibt, so dass '(t; x; u) 2 E für alle t 2 R, (ii) für alle x; y 2 E und "; T > 0 eine kontrollierte ("; T ) Kette von x nach y existiert, und E maximal mit diesen Eigenschaften ist. Man beweist leicht, dass jede Kontrollmenge mit nichtleerem Innern in einer Kettenkontrollmenge enthalten ist: Proposition 78 Es sei D eine Kontrollmenge mit nichtleerem Innern und es gelte lokale Akzessibilität in intD. Dann ist clD in einer Kettenkontrollmenge E enthalten.

68

KAPITEL 4. DER KONTROLLFLUSS

Beweis. Wir müssen zeigen, dass (i) für jedes x 2 clD eine Kontrolle u 2 U mit '(t; x; u) 2 clD für alle t 2 R existiert, und dass (ii) für jedes x 2 clD zu jedem y 2 clD kettenkontrollierbar ist. Beides ist klar für x; y 2 intD. Für x 2 clD = cl intD gibt es xn 2 intD mit xn ! x. Wähle un 2 U mit '(t; xn ; un ) 2 D für alle t 2 R. Geht man zu einer konvergenten Teilfolge in U über, so liefert die Stetigkeit des Kontroll‡usses die Behauptung. Analog sieht man, dass für x 2 @D und T > 0 eine Kontrolle u existiert mit '(T; x; u) 2 clD. Dann kann man in intD springen und so eine ("; T ) Kette nach y 2 clD …nden. Die Di¤erenz zwischen Kontrollmengen und Kettenkontrollmengen kann man in der folgenden Situation sehen. Es seien, unter den obigen Annahmen, D 6= D0 Kontrollmengen mit nichtleerem Innern, so dass clD \ clD0 6= ?. Dann gibt es eine Kettenkontrollmenge, die clD [ clD0 enthält. (Übung) Wir notieren auch das folgende Resultat. Proposition 79 Jede Kettenkontrollmenge ist abgeschlossen. Beweis. Wenn eine Folge (xk ) in einer Kettenkontrollmenge E gegen x konvergiert, so …nden man uk 2 U mit '(t; xk ; uk ) 2 E für alle t 2 R. Weil U kompakt ist, können wir annehmen, dass (uk ) gegen u 2 U konvergiert. Stetigkeit des Kontroll‡usses impliziert, dass '(t; xk ; uk ) ! '(t; x; u) für jedes t 2 R und daher ist '(t; x; u) 2 E. Ferner gilt Kettenkontrollierbarkeit für alle x; y 2 clE, und daher ist clE = E. Wie Kontrollmengen liften wir auch Kettenkontrollmengen E auf U Rn , E = f(u; x) 2 U

Rn ; '(t; x; u) 2 E für alle t 2 Rg :

(4.8)

Satz 80 Seit E Rn eine Kettenkontrollmenge des Systems (4.4). Dann ist der Lift E U Rn de…niert in (4.8) eine maximale invariante kettentransitive Menge für den Kontroll‡uss (U Rn ; ): Ist umgekehrt E U Rn eine maximale invariante kettentransitive Menge für den Kontroll‡uss, so ist Rn E eine Kettenkontrollmenge. Beweis. (i) Es seien (u; x); (v; y) 2 E und "; T > 0: Erinnere die De…nition der Metrik d auf U in (4.3) und wähle N 2 N großgenug, so dass 1 X

i=N +1

2

i

" < : 2

Für endlich viele z1 ; ::::; zN 2 L1 (R; Rm ) gibt es T0 > 0, so dass für alle i Z " jzi ( )j d < : 2 diam U Rn[ T0 ;T0 ]

4.2. DER KONTROLLFLUSS

69

O.B.d.A. können wir T > T0 annehmen. Kettenkontrollierbarkeit von '(2T; x; u) 2 E nach '( T; y; v) 2 E liefert die Existenz von k 2 N und x0 ; :::; xk 2 Rn ; u0 ; :::; uk 1 2 U; t0 ; :::; tk 1 T mit x0 = '(2T; x; u); xk = '( T; y; v); und k'(tj ; xj ; uj ) xj+1 k < " für j = 0; :::; k 1: Wir konstruieren jetzt eine ("; T ) Kette von (u; x) nach (v; y) folgendermaß en. De…niere t 2 = T; x 2 = x; v 2 = u; u(t 2 + t) für t t 1 t 1 = T; x 1 = '(T; x; u); v 1 (t) = u0 (t t 1 ) für t > t 1 und nimm die Zeiten t0 ; :::; tk 1 und die Punkte x0 ; :::; xk wie oben gegeben. Setze ferner tk = T; xk+1 = y; vk+1 = v; und de…niere für j = 0; :::; k 2 8 t 0 < vj 1 (tj 1 + t) für uj (t) für 0 < t < tj vj (t) = : uj+1 (t tj ) für t > tj ; 8 t 0 < vk 2 (tk 2 + t) für u (t) für 0 < t tk vk 1 (t) = k 1 : v(t tk 1 T ) für t > tk 1 ;

1

vk 1 (tk 1 + t) für t 0 v(t T ) für t > 0:

vk (t) =

Man sieht leicht, dass (v 2 ; x 2 ); (v 1 ; x 1 ); :::; (vk+1 ; xk+1 ) und t 2 ; t 1 ; :::; tk eine ("; T ) Kette von (u; x) nach (v; y) bilden, falls für j =

2;

d(vj (tj + ); vj+1 ) < ": Nach Wahl von T und N gilt für alle w1 ; w2 2 U R 1 X hw (t) w2 (t); zi (t)i dt i RR 1 d(w1 ; w2 ) = 2 1 + R hw1 (t) w2 (t); zi (t)i dt i=1 Z N X i 2 hw1 (t) w2 (t); zi (t)i dt Rn[ T;T ]

i=1

Z

T

" hw1 (t) w2 (t); zi (t)i dt + 2 T Z T < " + max jw1 (t) w2 (t)j jzi (t)j dt:

+

i=1;:::;N

T

T 1; :::; k

70

KAPITEL 4. DER KONTROLLFLUSS

Daher reicht es zu zeigen, dass für die betrachteten Paare von Kontrollfunktionen die Integranden verschwinden. Dies folgt unmittelbar aus der De…nition von vj ; j = 2; :::; k + 1. (ii) Es sei E eine invariante, kettentransitive Menge in U Rn . Für x 2 Rn E gibt es wegen der Invarianz u 2 U, so dass '(t; x; u) 2 E für alle t 2 R. Nun betrachte x; y 2 Rn E und wähle " > 0; T > 0. Wegen der Kettentransitivität von E können wir xj ; uj ; tj …nden, so dass die zugehörigen Trajektorien die geforderte Bedingung erfüllen. Der Beweis von (i) und (ii) wird abgeschlossen durch die Beobachtung, dass E genau dann ist maximal, wenn E maximal ist. In Lemma 74 haben wir gesehen, dass jede projizierte ! Limesmenge nichtleeren Schnitt mit einer Kontrollmenge hat. Weil ! Limesmengen kettentransitiv sind, erhalten wir als Korollar zu Theorem 80, dass ihre Projektionen in Kettenkontrollmengen enthalten sind. Korollar 81 Für das System (4.4) betrachte (u; x) 2 U Rn mit beschränkter positiver Trajektorie '(t; x; u); t 0. Dann existiert eine Kettenkontrollmenge E, so dass die projizierte ! Limesmenge in E enthalten ist, also E: M !(u; x) Beweis. Dies folgt aus Theorem 80, weil ! Limesmengen kettentransitiv sind. Bemerkung 82 Eine interessante Frage ist, wann eine Kettenkontrollmenge gleich dem Abschluss einer Kontrollmenge mit nichtleerem Innern ist. Dies gilt nicht, falls die Abschlüsse zweier Kontrollmengen einen nichtleeren Schnitt haben, die Kontrollmengen sich also berühren. Betrachtet man parameterabhängige Systeme, so entspricht dies einer „Bifurkation”von Kontrollmengen, ist also eine Ausnahmesituation. In der Tat kann man Bedingungen angeben, unter denen die Abschlüsse von Kontrollmengen mit nichtleerem Innern generisch (d.h. typischerweise) Kettenkontrollmengen sind (vgl. Gayer [8]).

Kapitel 5 Berechnung von Erreichbarkeitsmengen In diesem Kapitel werden wir numerische Verfahren präsentieren, die es erlauben, Erreichbarkeitsmengen und Kontrollmengen zu approximieren. Sie beruhen auf mengewertiger Dynamik, wie sie etwa in dem Überblicksartikel Dellnitz/Junge [5] erklärt werden. Für Kontrollsysteme beziehen wir uns insbesondere auf Szolnoki [22], [21].

5.1

Relative Globale Attraktoren

In Numerik III haben wir relative globale Attraktoren von Homöomorphismen und ihre numerische Berechnung mit Hilfe von Subdivisionsalgorithmen studiert. Analog dazu betrachten wir in diesem Abschnitt relative globale Attraktoren von Kontroll‡üssen und geben zumnächst eine Charakterisierung mit Hilfe von Kettenkontrollmengen, bevor wir im weiteren auf ihre numerische Berechnung eingehen. Wir betrachten weiterhin kontroll-a¢ ne Systeme unter den Standard-Voraussetzungen an Existenz und Eindeutigkeit von Lösungen. Allerdings legen wir eine kompakte Teilmenge Q Rn des Zustandsraums zu Grunde. De…nition 83 Für eine kompakte Menge K AK :=

\

U

Rn heiß t

(t; K)

t 0

globaler Attraktor des Kontroll‡usses 71

relativ zu K.

72

KAPITEL 5. BERECHNUNG VON ERREICHBARKEITSMENGEN

Dies ist analog zum Fall dynamischer Systeme im zeitdiskreten Fall, wo man den globalen Attraktor relativ zu K als \ AK := f j (K) j 0

de…niert. Proposition 84 Es sei Q Rn kompakt. Dann ist der globale Attraktor des Kontroll‡usses relativ zu K = U Q gegeben durch V = f(u; x) 2 U

Rn ; '(t; x; u) 2 Q für alle t

Beweis. Dies folgt leicht aus den De…nitionen: Ist (u; x) 2 folgt für jedes T 0, dass T (u; x)

2

T(

(T; K)) = K = U

Umgekehrt folgt aus (u; x) 2 V, dass für jedes T T (u; x)

= (u(T + ); '(t; x; u)) 2 U

0g: T

t 0

(t; K) so

Q.

0 Q = K:

Bemerkung 85 Die Menge ViabQ = fx 2 Rn ; es gibt u 2 U mit '(t; x; u) 2 Q für alle t

0g

heiß t auch negativer Viabilitätskern (oder Kontrollierbarkeits-Kern) von Q. Der relative globale Attraktor ist also gleich dem Lift des negativen Viabilitätskerns, und seine Projektion in Rn ist gleich dem negativen Viabilitätskern. Analog kann man auch positive Viabilitätskerne und R Viabilitätskerne (für die also '(t; x; u) 2 Q für alle t 2 R gilt) de…nieren. Man beachte, dass o¤enbar gilt ViabRQ = Viab+ Q \ ViabQ : O¤enbar ist die Komponente des relativen globalen Attraktors in U nicht von Interesse. Stattdessen interessieren wir uns für seine Rn Komponente, also den Viabilitätskern. Als nächstes charakterisieren wir relative globale Attraktoren mit Hilfe von Kontrollierbarkeitseigenschaften. Weil nur das Verhalten in der kompakten (nicht notwendigerweise invarianten) Menge Q Rn relevant ist, müssen wir die De…nition von Kettenkontrollmengen etwas verallgemeinern.

5.1. RELATIVE GLOBALE ATTRAKTOREN

73

De…nition 86 Eine Menge EQ Q heiß t Kettenkontrollmenge relativ zu Q, falls sie maximal ist mit den Eigenschaften (i) für alle x 2 EQ existiert eine Kontrolle u 2 U mit '(t; x; u) 2 EQ für alle t 2 R; (ii) für alle x; y 2 EQ und "; T > 0 existiert eine kontrollierte ("; T ) Kette von x nach y, die ganz in Q enthalten ist, für die also '(t; xj ; uj ) 2 Q für alle t 2 [0; tj ]; j = 0; 1; :::; k 1; gilt. Wir benötigen darüberhinaus den Attraktionsbereich solch einer relativen Kettenkontrollmenge. De…nition 87 Für eine Kettenkontrollmenge EQ relativ zu Q ist der positive und der negative Attraktionsbereich (relativ zu Q) de…niert durch A+ Q (EQ ) = fx 2 Q; es gibt u 2 U mit '(t; x; u) 2 Q; t

AQ (EQ ) = fx 2 Q; es gibt u 2 U mit '(t; x; u) 2 Q; t

0 und

2 !(u; x)

0 und

2

(u; x)

EQ g;

EQ g:

Der folgende Satz (Szolnoki [20]) charakterisiert Viabilitätskerne mit Hilfe von Kontrollierbarkeitseigenschaften. Rn kompakt. Dann ist [ [ Viab+ A+ (E ) und Viab AQ (EQ ); = Q Q = Q Q

Satz 88 Es sei Q

EQ

EQ

hierbei wird die Vereinigung über alle Kettenkontrollmengen EQ relativ zu Q genommen. Beweis. Wir zeigen die Behauptung nur für positive Viabilitätskerne, die für negative folgt analog. Sei zunächst x 2 Viab+ Q . Dann gibt es eine Kontrolle u 2 U mit '(t; x; u) 2 Q für alle t 0. Die Kompaktheit von U Q impliziert, dass !(u; x) U Q nicht leer ist. Ferner ist der Kontroll‡uss eingeschränkt auf eine ! Limesmenge kettentransitiv (siehe zum Beispiel [4, Appendix B.2]). Daher können je zwei Elemente in !(u; x) durch ("; T ) Ketten in !(u; x) miteinander verbunden werden. Ihre Projektion auf die Rn Komponente ist enthalten in Q. Da für jedes Element y 2 2 !(u; x) eine Kontrolle v 2 U mit '(t; y; v) 2 2 !(u; x) für alle t 0 existiert, ist !(u; x) in einer relativen Kettenkontrollmenge E enthalten. O¤enbar ist 2 Q + x 2 AQ (EQ ). Die umgekehrte Inklusion gilt, weil nach Konstruktion der relative positive Attraktionsbereich einer relativen Kettenkontrollmenge positiv viabel in Q, also enthalten in Viab+ Q ist.

74

KAPITEL 5. BERECHNUNG VON ERREICHBARKEITSMENGEN O¤enbar ergibt sich für den R Viabilitätskern [ [ ViabRQ = A+ AQ (EQ ): Q (EQ ) \ EQ

(5.1)

EQ

Stimmen die relativen Kettenkontrollmengen mit den Abschlüssen von Kontrollmengen D überein, so folgt auch [ [ (5.2) ViabRQ = (clD) \ AQ (clD); A+ Q D

D

wobei die Vereinigungen über alle Kontrollmengen D Q genommen werden. Hier wird also auch angenommen, dass die Menge Q so gewählt ist, dass eine Kontrollmenge D, die nichtleeren Schnitt mit Q hat, ganz in Q enthalten ist. Das folgende Beispiel aus der chemischen Technologie (das vereinfachte Modell eines sog. stetigen Rührkessel-Reaktors) illustriert diese Resultate. Beispiel 89 Betrachte die folgende Modellgleichung (siehe Uppal, Ray, Poore [23]) x_ = y_ =

x + B (1 y)ex y + (1 y)ex :

u(t)(x

xc )

Hier ist x die (dimensionslose) Temperatur und y die Produktkonzentration im Reaktor, die Kühlmitteltemperatur ist xc , und und B sind technische Konstanten. Die Flussrate u(t) des Kühlmittels dient als Kontrolle. Wähle = 0:05; B = 10; xc = 1: Dann stellt sich heraus, dass für das unkontrollierte System mit u = 0 zwei stabile Gleichgewichte und ein hyperbolisches Gleichgewicht existieren. (Die folgenden Bilder sind numerisch erzeugt mit dem Subdivisionsalgorithmus für Kontrollsysteme.) Wir notieren das folgende Resultat zur Approximation von Kettenkontrollmengen. Korollar 90 Sei Q Rn kompakt, und Q enthalte genau eine relative Kettenkontrollmenge EQ . Dann ist ViabR (Q) = EQ : (i) Ist EQ = clD für eine Kontrollmenge D, so ist ViabR (Q) = clD. (ii) Ist EQ = C eine invariante Kontrollmenge, so ist Viab (Q) = C.

5.1. RELATIVE GLOBALE ATTRAKTOREN

75

76

KAPITEL 5. BERECHNUNG VON ERREICHBARKEITSMENGEN

5.1. RELATIVE GLOBALE ATTRAKTOREN

77

Beweis. Die Gleichung (5.1) zeigt, dass ViabRQ = A+ Q (EQ ) \ AQ (EQ ) = EQ ; wobei die zweite Gleichung aus der Maximalität von Kettenkontrollmengen folgt. (i) ist eine unmittelbare Folgerung und (ii) ergibt sich aus der positiven Invarianz von C, und der Tatsache, dass jede Trajektorie in Q eine ! Limesmenge in EQ = C hat, also AQ (E) = Q und damit C = AQ (C) = AQ (EQ ) = ViabQ : Ist man durch geschickte Wahl von Q sicher, dass die Voraussetzungen dieses Korollars erfüllt sind, so kann man zur Berechnung einer Kontrollmenge zunächst etwa Viab+ (Q) berechnen, und dann _ fx 2 Viab+ (Q); x 2 Viab (Q)g = Viab+ (Q) \ Viab (Q) = E: Für invariante Kontrollmengen reicht es, nur Viab (Q) zu berechnen. Im weiteren werden wir drei numerische Algorithmen für die Berechnung von (Ketten-)kontrollmengen und ihrer Einzugsbereiche diskutieren: basierend auf Subdivision, Fortsetzung (continuation) und symbolischen Bildern.

78

KAPITEL 5. BERECHNUNG VON ERREICHBARKEITSMENGEN

5.2

Grundalgorithmus zur Subdivision

In Analogie zum Fall zeitdiskreter dynamischer Systeme erläutern wir hier die Grundidee des Subdivisionsalgorithmus für Kontrollsysteme, und einige der auftretenden Probleme. Betrachte ein zeitdiskretes Kontrollsystem in Rn xk+1 = f (xk ; vk ); k 2 Z. mit Kontrollen vk in einer Menge V und Trajektorien (k; x; (vm )m2Z ); k 2 Z. Wir nehmen an, dass für alle v 2 V die Abbildung fv := f ( ; v) ein Homöomorphismus auf Q ist. Approximiere den zugehörigen (zeitdiskreten) Z Viabilitätskern ViabZQ := fx 2 Rn ;

(k; x; (vm )m2Z ) 2 Q für alle k 2 Zg

(5.3)

in einer kompakten Menge Q Rn auf die folgende Weise: Starte in der trivialen Zerlegung B0 = fQg und konstruiere Familien von abgeschlossenen Teilmengen Bk aus Bk 1 in zwei rekursiven Schritten: (i) Subdivisionsschritt: Konstruiere Bk0 so dass [

B2Bk0

B=

[

B2Bk

B 1

und max diamfB 2 Bk0 g =

k diamfB

2 Bk 1 g

mit 0 < min k max < 1. (ii) Auswahlschritt: De…niere Bk0 = Bk0 und für j = 1; 2; :::setze Bkj =

B 2 Bkj 1 ;

9v1 2 V 9B1 2 Bkj 1 : fv1 (B) \ B1 6= ; und 9v2 2 V 9B2 2 Bkj 1 : fv21 (B) \ B2 6= ;

: 0

Bemerkung 91 Die Iteration im Auswahlschritt endet nach höchstens #Bk Schritten. Bemerkung 92 Will man diesen Algorithmus für die Berechnung von Viabilitätskernen von Kontrollsystemen in stetiger Zeit einsetzen, so muss man zeitliche und räumliche Diskretisierungen vornehmen und den Raum der Kontrollfunktionen diskretisieren. Wählt man für ein System der Form x_ = F (x; u(t)); u(t) 2 U;

5.2. GRUNDALGORITHMUS ZUR SUBDIVISION

79

mit Lösungen '(t; x; u) etwa die Zeitschrittweite > 0 so erhält man ein System der Form xk+1 = f (xk ; vk ) := '( ; xk ; vk ) mit vk 2 V := fv 2 L1 ([0; ]; Rm ); u(t) 2 U für fast alle t 2 [0; ]g. Der Kontrollwertebereich ist also selber unendlich-dimensional. Ferner ist es nicht klar, ob man für Kettenkontrollmengen mit Vielfachen von auskommt; und schließ lich ist die Berechnung von Bilder der Form fv (B) = f'( ; x; v); x 2 Bg schwierig. Die Konvergenz der Grundform des Subdivisionsalgorithmus ergibt sich wie für zeitdiskrete dynamische Systeme. Proposition 93 Es sei Q Rn kompakt. Dann gilt für die durch den Subdivisionsalgorithmus erzeugte Folge von Mengen [ B; Qk := BeBk

dass ViabZQ =

1 \

Qk :

k=0

Beweis. O¤enbar ist ViabZQ schwach (oder kontrolliert-) invariant in folgendem Sinn: Für jedes x 2 ViabZQ existiert eine Kontrollfolge (vm )m2Z , so dass die zugehörige Lösung für alle k 2 Z in Q bleibt. Wir zeigen zunächst ViabZQ

Qk für alle k = 0; 1; :::

(5.4)

Das ist klar für Q0 = Q. Sei jetzt ViabZQ Qk 1 und x 2 ViabZQ mit x 62 Qk . Dann existiert B 2 Bk0 mit x 2 B, und dies B wird im k ten Auswahlschritt entfernt, also gilt die Negation von 9v 2 V 9B1 2 Bk0 : fv (B) \ B1 6= ; und 9v 2 V 9B2 2 Bk0 : fv 1 (B) \ B2 6= ;, also 8v 2 V : fv (B) \ Qk

1

= ; oder 8v 2 V : fv 1 (B) \ Qk

1

Daher ist 8v 2 V : fv (x) 62 Qk

1

oder 8v 2 V : fv 1 (x) 62 Qk 1 .

= ;:

80

KAPITEL 5. BERECHNUNG VON ERREICHBARKEITSMENGEN

Dies widerspricht der oben erwähnten schwachen Invarianz von ViabQ , und damit ist (5.4) gezeigt. Ist M Q, so dass für alle x 2 M Kontrollen v + und v 2 V existieren mit fv+ (x) 2 M und fv 1 (x) 2 M; (5.5) so folgt M

ViabZQ . In der Tat: Für x 2 M gibt es v1+ ; v1 2 V mit Q und fv 1 (x) 2 M

fv1+ (x) 2 M

Q:

1

Für fv1+ (x); fv1 (x) 2 M gibt es wieder Kontrollen v2+ ; v2 2 V mit fv2+

fv1+ (x) 2 M

Q und fv

1 2

fv 1 (x) 2 M

Q:

1

Auf diese Weise de…niert man induktiv eine Kontrollfolge, so dass die zugehörige Lösung für alle Zeiten in Q bleibt, also ist x 2 ViabZQ . Es bleibt nur noch zu zeigen, dass die kompakte Teilmenge 1 \ Q1 := Qk Q k=0

die Bedingung (5.5) erfüllt, denn dann ist sie in ViabZQ enthalten. Dazu sieht man zunächst, dass Qk Qk+1 und daher ist für jedes k 2 N Qk =

k \

Ql :

l=0

Daraus folgt, dass Q1 der Limes im Hausdor¤-Sinn der Qk ist. Gibt es, im Widerspruch zur Behauptung, ein y 2 Q1 , so dass 8v 2 V : fv (y) 62 Q1 oder 8v 2 V : fv 1 (x) 62 Q1 ;

so gibt es

> 0 mit

min d(fv (y); Q1 ); v 2 V g >

oder min d(fv 1 (y); Q1 ); v 2 V g > :

Also gibt es N 2 N, so dass für alle k max d(fv (y); Qk ); v 2 V g >

N

oder max d(fv 1 (y); Qk ); v 2 V g > :

Für jedes k wähle eine Menge Bk (y) 2 Bk mit y 2 Bk (y). Weil diamBk (y) ! 0 für k ! 1, folgt aus der Stetigkeit von f , dass für k großgenug 8v 2 V : fv (Bk (y)) \ Qk = ; oder 8v 2 V : fv 1 (Bk (y)) \ Qk = ;;

im Widerspruch zu den De…nitionen. Bemerkung 94 Den gleichen Beweis kann man benutzen, um die Konvergenz eines Subdivisionsalgorithmus für den positiven und den negativen Viabilitätskern ViabQ zu zeigen.

5.3. ZEITDISKRETISIERUNG

5.3

81

Zeitdiskretisierung

In diesem Abschnitt analysieren wir, wann man zu einer festen Zeitschrittweite > 0 übergehen kann. Betrachte das zeitkontinuierliche Kontrollsystem (4.4) x(t) _ = f0 (x(t)) +

m X i=1

ui (t)fi (x(t)); u 2 U;

mit Trajektorien '(t; x; u); t 2 R, und eine kompakte Teilmenge Q Rn . Wähle eine Schrittweite > 0, und betrachte das zeitdiskrete Kontrollsystem mit t0 = 0; tk+1 = tk + ; xk+1 = '( ; xk+1 ; u(tk + )) mit Lösungen (k; x; v); vk = ( u(tk + )j [0; ]); k 2 Z. O¤enbar ist dann (k; x; v) = '(tk ; x; u); k 2 Z. Dies impliziert sofort, dass der Viabilitätskern ViabRQ des zeitkontinuierlichen Systems in dem Viabilitätskern ViabZQ des zeitdiskreten Systems enthalten ist, ViabRQ

ViabZQ :

Hier ist eine hinreichende Bedingung, die garantiert, dass die beiden übereinstimmen: Sie fordert, dass der Viabilitätskern hinreichend weit im Innern von Q liegt (oder > 0 klein genug ist). Wir bezeichnen die Kugel um x0 mit Radius r > 0 mit B(x0 ; r). Proposition 95 Es sei K > 0 eine Konstante mit f0 (x) +

m X

ui fi (x)

i=1

K für alle x 2 Rn und u 2 U:

(5.6)

Ferner sei B(x0 ; K =2) Dann folgt

Q für alle x0 2 ViabZQ :

(5.7)

ViabRQ = ViabZQ : Beweis. Für x 2 ViabZQ gibt es eine Kontrolle u 2 U, so dass xk = '(tk ; x; u) 2 ViabZQ

Q; k 2 Z.

Wir müssen also zeigen, dass auch für die Zwischenzeiten t 2 [tk ; tk+1 ] = [k ; (k + 1) ] die Trajektorie in Q liegt, d.h. x(t) = '(t; xk ; u(tk + )) 2 Q für alle t 2 [0; ].

82

KAPITEL 5. BERECHNUNG VON ERREICHBARKEITSMENGEN

Wir berechnen für t 2 [0; =2] # Z t" m X k'(t; xk ; u(tk + )) xk k f0 (x(s)) + ui (s)fi (x(s)) ds 0

K =2

i=1

und analog für t 2 [ =2; ] k'(t; xk ; u(tk + ))

xk k

K =2:

Also gilt für alle t 2 [0; ], dass '(t; xk ; u(tk + )) 2 B(xk ; K =2)[B(x+1 ; K =2) Q, weil xk ; xk+1 2 ViabZQ : Bemerkung 96 Die Bedingung (5.6) ist sehr stark, weil sie für alle x 2 Rn gelten soll. Ist der interessierende Bereich kompakt, so kann man auß erhalb davon die Vektorfelder fi abändern,.so dass die Beschränktheit gilt.

5.4

Zeitdiskretisierung und Kettenerreichbarkeit

Wir haben oben gesehen, dass, unter einer Zusatzbedingung, die Berechnung von Viabilitätskernen in stetiger Zeit auf die von solchen in diskreter Zeit zurückgeführt werden kann. Andererseits wissen wir, dass, in stetiger Zeit, Viabilitätskernen durch die in ihnen enthaltenen relativen Kettenkontrollmengen und ihre Einzugsbereiche beschrieben werden. Insbesondere kann man, wenn in der zugrundeliegenden Menge Q nur eine einzige relative Kettenkontrollmenge EQ liegt, sie beschreiben durch EQ = ViabR (Q) = Viab+ (Q) \ Viab (Q) = ViabZ (Q);

wobei die letzte Gleichheit nur unter der Zusatzbedingung gezeigt ist. Unser nächstes Ziel ist es, einen Graphen-Algorithmus für die Berechnung von Kettenkontrollmengen zu entwickeln. Dafür müssen wir zunächst diskutieren, ob man auch ohne diese Zusatzbedingung relative Kettenkontrollmengen durch das zeitdiskretisierte System beschreiben kann. Dazu führen wir zeitdiskrete Erreichbarkeits- und Kettenerreichbarkeitsmengen ein. Sei im Folgenden Q Rn kompakt. De…nition 97 Sei Q Rn kompakt und > 0. Die positive und die negative Kettenerreichbarkeitsmenge von x 2 Q ist de…niert als + OQ; (x) =

y 2 Q;

8" > 0 9 kontrollierte ("; ) Kette in Q von x nach y mit Sprungzeiten ti =

;

5.5. GRAPHEN-ALGORITHMUS OQ; (x) =

y 2 Q;

8" > 0 9 kontrollierte ("; ) Kette in Q von y nach x mit Sprungzeiten ti =

83 :

Die Beziehung zu den Kettenkontrollmengen des zeitkontinuierlichen Systems klären die folgenden Propositionen. Proposition 98 Es sei Q Rn kompakt und x; y seien in einer Kettenkontrollmenge EQ relativ zu Q: Dann existieren für alle "; > 0 kontrollierte ("; ) Ketten von x nach y in EQ mit allen Sprungzeiten gleich . Beweis. Siehe Szolnoki [22, Proposition 3.1]. + Proposition 99 Es sei Q Rn kompakt, 2 Q und x; y 2 ViabR (OQ; (x)\ OQ; (x)). Dann existiert für alle "; T > 0 eine kontrollierte ("; T ) Kette von x nach y in Q.

Beweis. Siehe Szolnoki [22, Proposition 3.2]. Als Folgerung aus diesen Propositionen und der Maximalität von Viabilitätskernen erhält man das folgende Korollar. Korollar 100 Es sei Q Rn kompakt und x sei in einer Kettenkontrollmenge EQ relativ zu Q:Dann folgt + EQ = ViabR (OQ; (x) \ OQ; (x)):

Dies Korollar zeigt, dass man Kettenkontrollmenge numerisch durch den Schnitt der Kettenerreichbarkeitsmengen in positiver und in negativer Zeit berechnen kann, sobald man einen Punkt darin kennt.

5.5

Graphen-Algorithmus

In diesem Abschnitt werden wir Kontrollsystemen bei gegebener Diskretisierung einen gerichteten Graphen (ein symbolisches Bild) zuordnen, der wesentliche Eigenschaften des Kontrollsystems widerspiegelt. Dann kann man Standardmethoden aus der Graphentheorie anwenden, um alle Kettenkontrollmengen zu berechnen; dabei ist es nicht nötig, schon ihre Anzahl oder einzelne Punkte darin zu kennen. Diese Idee (für Abbildungen) erscheint zuerst in einer Arbeit von G. Osipenko (1983) und ist insbesondere von M. Dellnitz zu einer e¢ zienten numerischen Methode ausgebaut worden. Ein gerichteter Graph G = (V; E) besteht aus einer Menge V von Knoten und einer Teilmenge E V V von gerichteten Kanten. Ein Pfad von einem Knoten v 2 V zu einem Knoten v’2 V ist gegeben durch (vi ; vi+1 ) 2 E; i =

84

KAPITEL 5. BERECHNUNG VON ERREICHBARKEITSMENGEN

0; :::; n 1; mit v0 = v und vn = v 0 . Eine starke Zusammenhangskomponente von G ist eine maximale Teilmenge S V , so dass für alle v; v 0 2 S ein Pfad in S von v nach v 0 existiert. Wir betrachten jetzt ein kontrolla¢ nes System in Rn unter unseren Standardvoraussetzungen an Existenz und Eindeutigkeit von Lösungen '(t; x; u); u 2 U. Sei > 0 eine Zeitschrittweite und Q Rn eine kompakte Menge. Ferner sei eine Folge von Partitionen Pk von Q in kompakte Mengen gegeben, so dass [ B = Q; intB \ intB 0 = ; für B 6= B 0 ; k := max diamB & 0; B2Pk

B2Pk

und für alle B 2 Pk+1 ein B 0 2 Pk mit B

B 0 existiert.

Der Graphenalgorithmus für Symbolische Bilder. Schritt1: Setze B1 = P1 = fQg; Schritt k (k = 2; 3; :::) Am Anfang von Schritt k haben wir eine Kollektion Bk 1 Pk 1 . De…niere Bk in 2 Schritten: Schritt k.1 (Subdivision): Wir gehen zu Pk über, indem wir setzen: B^k := fAk 2 Pk ; 9Ak 1 2 Bk 1 : Ak Ak 1 g;

Schritt k.2: Konstruiere den gerichteten Graphen Gk = (Vk ; Ek ) mit Vk = B^k und Ek = f(B; B 0 ) 2 B^k

B^k : B 0 \ f'( ; B; u); u 2 Ug 6= ;g:

Berechne die starken Zusammenhangskomponenten von Gk und setze Bk := fB 2 B^k ; B ist in einer starken Zus.komp.von Gk g: Wir werden zeigen, dass die Vereinigung der Boxen in Bk für k ! 1 gegen die Kettenkontrollmengen relativ zu Q konvergiert. Lemma 101 Sei EQ eine Kettenkontrollmenge relativ zu Q. Dann existiert für alle k 2 N eine starke Zusammenhangskomponente S von Gk mit [ B: EQ B2S

Beweis. Wir beweisen die Behauptung durch Induktion über k, wobei der Induktionsanfang trivial ist. Es S gebe jetzt eine starke Zusammenhangskom^ B^k mit ponente Sk 1 Bk 1 mit EQ B2Sk 1 B:Dann existiert Sk [ [ B= B EQ .: B2S^k

B2Sk

1

5.5. GRAPHEN-ALGORITHMUS

85

Nun betrachte Schritt k.2 des Algorithmus. Wir müssen zeigen, dass es eine starke Zusammenhangskomponente von S^k gibt, die EQ enthält. Seien dazu S 0 0 ^ x; y 2 EQ B2S^k B. dann gibt es B; B 2 Sk mit x 2 B und y 2 B . Wir 0 müssen einen Pfad von B nach B konstruieren. Es gibt "0 > 0, so dass für alle B1 ; B2 2 Pk gilt: B1 \ f'( ; B1 ; u); u 2 Ug 6= ; =) dH (B1 ; f'( ; B1 ; u); u 2 Ug) > "0 : Dies folgt, weil B1 ; B2 und U kompakt sind und ' stetig ist. Wähle jetzt für " < "0 eine kontrollierte " Kette (alle Sprungzeiten gleich ) in EQ von x nach y, so dass also für alle i gilt k'( ; xi ; ui )

xi+1 k < ":

Dann liegt '( ; xi ; ui ) in der Box, die xi+1 enthält. Daher gibt es einen Pfad von x0 = x nach xn = y. Der folgende Satz zeigt, dass in der Tat die im Graphen-Algorithmus erzeugte Folge von starken Zusammenhangskomponenten gegen die relativen Kettenkontrollmengen konvergiert (sie bilden eine Approximation von auß en). Satz 102 Es sei S1 :=

1 [ \

B;

k=1 B2Bk

Dann ist ViabR (S1 ) =

[

EQ ;

wobei die Vereinigung über alle Kettenkontrollmengen relativ zu Q genommen wird. S Beweis. Aus dem Lemma 102 folgt EQ S1 :Weil relative Kettenkontrollmengen viabel sind, folgt damit die eine Inklusion. Sei umgekehrt x 2 ViabR (S1 ). Für alle k 2 N gibt es eine starke Zusammenhangskomponente S~k von Gk mit x 2 S~k . Also gibt es einen Pfad von x nach x, dessen Knoten aus Boxen B besteht mit diamB k = diamPk . Daher gibt es für alle " > 0 ein k, so dass der Pfad eine kontrollierte ("; ) Kette in Q von x nach x enthält, und daher + x 2 ViabR OQ; (x) \ OQ; (x) ;

und die rechte Seite ist eine Kettenkontrollmenge relativ zu Q.

86

KAPITEL 5. BERECHNUNG VON ERREICHBARKEITSMENGEN

Wir wenden uns jetzt der Berechnung von starken Zusammenhangskomponenten in gerichteten Graphen zu. Dies geschieht mit einer doppelten Anwendung von sog. Tiefensuche , die wir zunächst erklären. Dabei werden allen Knoten in einem gerichteten Graphen G = (V; E) zwei natürliche Zahlen zugeordnet. Dafür de…nieren wir zunächst für einen Knoten v 2 V die Menge A(v) := fw 2 V; (v; w) 2 Eg der direkten Nachfolger von v. Algorithmus Tiefensuche. Schritt 1: Initialisiere (w) := 0; !(w) = 0 für alle w 2 V ; Zählvariable k := 1; Wir starten mit einem beliebigen Knoten v 2 V: Schritt 2: (a) Setze (v) := k; k := k + 1; (b) Führe Schritt 2 rekursiv für alle w 2 A(v) mit (w) = 0 aus, und kehre dann wieder hierher zurück; (c) Setze (w) := k; k := k + 1; Schritt 3: Existiert noch ein Knoten v 2 V mit (v) = 0, so starte erneut mit Schritt 2 für v. Der Algorithmus terminiert, wenn alle und ! Werte gesetzt sind. Dieser Algorithmus ist, so wie er hier rekursiv durchgeführt wird, sehr speicheraufwändig; es wird unnötig viel Arbeitsspeicher von Verwaltungsvariablen belegt, weil rekursive Funktionen sich selbst aufrufen. Dies wird bei einer hohen Anzahl von Kanten problematisch. Man kann die Rekursivität umgehen, in dem man Schritt 2 so modi…zieren, dass er immer beendet wird, bevor wir ihn neu aufrufen. Dazu müssen wir allerdings speichern, von welchem Knoten aus Schritt 2 aufgerufen wurde. Als Speicherstruktur bietet sich der sogenannte Stapel an. Ein Stapel ist eine Liste von Elementen, in unserem Fall Knoten, in der immer nur das erste (=oberste) Element gelesen oder gelöscht wird. Neue Elemente können immer nur oben eingefügt werden. Algorithmus Nichtrekursive Tiefensuche Schritt 1: Initialisiere (w) := 0; !(w) = 0 für alle w 2 V ; Zählvariable k := 1; Lege einen beliebigen Knoten v 2 V auf den Stapel; Schritt 2: v ist das oberste Element des Stapels; (a) Wenn (v) = 0; dann setze (v) := k; k := k + 1; (b) Existiert ein w 2 A(v) mit (w) = 0, dann lege w auf den Stapel und führe Schritt 2 erneut aus; (c) Setze !(v) := k; k := k + 1 und nimm v vom Stapel; ist der Stapel leer, dann gehe zu Schritt 3, starte ansonsten Schritt 2 erneut;

5.5. GRAPHEN-ALGORITHMUS

87

Schritt 3: Existiert noch ein Knoten v 2 V mit (v) = 0, so lege v auf den Stapel und starte erneut mit Schritt 2.. Der Algorithmus terminiert wieder, wenn alle und ! Werte gesetzt worden sind. Der Schritt 2 wird jedesmal beendet, bevor er erneut aufgerufen wird. Dieser Algorithmus ist von A. Marquardt in GAIO-Algorithmen für Kontrollsysteme implementiert (vgl. auch Marquardt [15]). Die beiden Algorithmen laufen, wenn die frei wählbaren Knoten identisch gewählt sind, auch identisch ab und vergeben damit auch dieselben und ! Werte. Die Berechnung der starken Zusammenhangskomponenten basiert im Wesentlichen auf der doppelten Ausführung der Tiefensuche. Im Folgenden werden Knoten, für die kein Pfad zu sich zurück existiert, als einpunktige Zusammenhangskomponenten de…niert. Sie sind von einpunktigen Zusammenhangskomponenten zu unterscheiden, für die eine Kante zu auf sich selbst existiert, und werden bei dem Graphen-Algorithmus für symbolische Bilder nicht berücksichtigt. Algorithmus Starke Zusammenhangskomponenten Wir ermitteln die starken Zusammenhangskomponenten des gerichteten Graphen G = (V; E). Die Knoten werden in eine Reihenfolge gebracht, in der die Knoten einer Komponente jeweils nebeneinander liegen. Der erste Knoten jeder Komponente, wir nennen ihn Startknoten, wird in die Menge S := ; eingefügt. Wir benutzen dabei auch den zu G invertierten Graphen H = (V; F ), wobei F = f(a; b); (b; a) 2 Eg. Schritt 1: Führe die Tiefensuche auf G aus; Lege den Knoten v 2 V mit maximalem ! Wert auf den Stapel; Schritt 2: Führe die Tiefensuche auf H aus und vergib dabei Werte für (~ ; ! ~ ). Wähle dabei jedesmal, wenn in Schritt 1 oder Schritt 3 ein Knoten frei gewählt werden kann, den Knoten s = arg maxw2F^ !(w), wobei F0 := fw 2 V; ~ (w) = 0g die Menge der noch nicht besuchten Knoten ist. Dieser Algorithmus führt in Schritt 1 die Tiefensuche aus, um die Startreihenfolge der Knoten für die zweite Tiefensuche auf dem invertierten Graphen in Schritt 2 zu erhalten. Diese setzt ausgehend von dem Startknoten s zuerst ~ (s), dann die ~ und ! ~ Werte der von s besuchten Knoten und danach ! ~ (s). Wir fassen diese Knoten in der Menge T (s) := fv 2 V; ~ (s)

~ (v) < ! ~ (v)

! ~ (s)g

(5.8)

zusammen. Der zu v 2 V gehörende Startknoten ist s(v) und die Menge aller Startknoten bezeichnen wir mit S V .

88

KAPITEL 5. BERECHNUNG VON ERREICHBARKEITSMENGEN

Aus der Konstruktion der Zählvariablen folgt sofort, dass (v) < !(v) und ~ (v) < ! ~ (v) für alle v 2 V . Wir bezeichnen mit scc(v) V die starke Zusammenhangskomponente (strongly connected component), die v enthält. Satz 103 Die von dem obigen Algorithmus berechneten Mengen T (s); s 2 S; in (5.8) sind die starken Zusammenhangskomponenten des Graphen G; scc(v) = T (s(v)) für alle v 2 V . Beweis. Sei zunächst w 2 scc(v) für w 6= v. Dann existieren in G Pfade v = v0 ; v1 ; :::; vn = w und w = w0 ; w1 ; :::; wm = v von v nach w und von w nach v. Dies liefert auch Pfade auf dem invertierten Graphen H, gegeben durch w = vn ; vn 1 ; :::; v0 = v und v = wn ; wm 1 ; :::; w0 = w. Wir nehmen an, dass v bei der Tiefensuche auf H (Schritt 2) vor w erreicht wird, d.h. ~ (v) < ~ (w). Dann existiert ein Pfad in H von s := s(v) nach v, und es gibt einen Pfad in H von s (über v) nach w. Die Tiefensuche in H läuft also von s zu v, dann zu w und wieder zurück zu s. Das heiß t w 2 T (s). Für die umgekehrte Inklusion T (s(v)) scc(v) wähle einen Startknoten s und zwei beliebige Knoten v; w 2 T (s) mit v 6= s. Dann existiert ein Pfad in H von s nach v und ein Pfad in G von v nach s Da in Schritt 2 der Knoten s und nicht v gewählt wurde, gilt !(s) > !(v). Auf Grund des Pfades in G von v nach s, muss s vor v erreicht werden, da ansonsten !(s) < !(v) gelten müsste. Damit ergibt sich (s) < (v) < !(v) < !(s). Demzufolge existiert in G ein Pfad von s nach v. Der Knoten v liegt also in derselben starken Zusammenhangskomponente wie s, das heiß t, v 2 scc(s). Analog zeigt man, dass w 2 scc(s). Folglich liegen v und w in derselben starken Zusammenhangskomponente (vgl. auch Jungnickel [12].) Die starken Zusammenhangskomponenten zerlegen die Knotenmenge in disjunkte Knotenmengen, von denen es keinen Pfad zu einem anderen Knoten und wieder zurück gibt, bilden jeweils eine einpunktige Komponente. Der Graphenalgorithmus wählt aus den starken Zusammenhangskomponenten diejenigen aus, die mehrere Knoten enthalten oder einpunktig sind und eine Kante auf sich selbst enthalten.

5.6. VARIANTEN DES SUBDIVISIONS-ALGORITHMUS

5.6

89

Varianten des Subdivisions-Algorithmus

Im Weiteren nehmen wir an, dass zeitdiskrete Viabilitätskerne berechnet werden sollen und diskutieren Varianten des Auswahlschritts, die zu Verbesserungen der Konvergenzgeschwindigkeit bzw. zu geringeren Speicheranforderungen führen. Der zweite Teil des Grundalgorithmus besteht aus dem Auswahlschritt, der zum Beispiel für die Vorwärts-Zeitrichtung die folgende Form hat. Für eine (verfeinerte) Zerlegung Bk0 de…niere Bk durch Bk = fB 2 Bk0 ; 9v1 2 V 9B1 2 Bk0 : fv1 (B) \ B1 6= ;g : Wir nehmen jetzt an, dass eine Zerlegung vorgegeben ist. Für das im vorigen Abschnitt eingeführte System müssen wir im Auswahlschritt überprüfen, ob für Mengen B1 ; B2 aus der Zerlegung f'( ; x; u); x 2 B1 und u 2 Ug \ B2 6= ;: Mit (B1 ; u) := f'( ; x; u); x 2 B1 g; u 2 U; können wir dies auch schreiben als (B1 ; u) \ B2 6= ;: Hier entsteht also zum Einen das aus der Dynamik bekannte Problem, dass für alle x aus einer Menge die Bilder berechnet werden müssen; zusätzlich müssen alle Kontrollfunktionen u : [0; ] ! U überprüft werden. Man wird genügend viele geeignete Testpunkte xi nehmen, und geeignete, zum Beispiel konstante Kontrollen oder stückweise konstante mit einer festen Zahl von …xierten Umschaltpunkten wählen. Eine rigorose Strategie, die garantiert, dass keine Mengen weggelassen werden, ist in Grüne [9] entwickelt. Hier werden wir ein anderes Problem genauer diskutieren (vgl. Szolnoki [21]). In der obigen Version wird für jede Box überprüft, ob eine Kontrolle existiert, so dass das Bild in Q bleibt. Dann folgt bereits ein Verfeinerungsschritt, also wird auf der nächsten Verfeinerungsstufe der Auswahlschritt wiederholt. Da die Anzahl der Boxen sich üblicherweise bei jeder Verfeinerung verdoppelt, wäre es o¤enbar günstiger, schon auf der gröberen Ebene die Anzahl der relevanten Boxen zu verkleinern. Einfache Beispiele (etwa Berechnung der instabilen Mannigfaltigkeit eines Fixpunktes) zeigen, dass man dies durch eine Wiederholung des Auswahlschritts (ohne Verfeinerung) erreichen kann. Dies führt zu dem folgenden

90

KAPITEL 5. BERECHNUNG VON ERREICHBARKEITSMENGEN

modi…zierten Subdivisions-Algorithmus für eine gegebene Folge (jk )k2N von natürlichen Zahlen. Starte in der trivialen Zerlegung B0 = fQg und konstruiere Familien von abgeschlossenen Teilmengen Bk aus Bk 1 in zwei rekursiven Schritten: (i) Subdivisionsschritt: Konstruiere Bk0 , so dass [ [ B= B B2Bk0

B2Bk

1

und max diamfB 2 Bk0 g =

k diamfB

2 Bk 1 g

mit 0 < min k max < 1. (ii) Auswahlschritt: De…niere Bk0 = Bk0 und für j = 1; 2; :::; jk setze Bkj = B 2 Bkj 1 ; 9v1 2 V 9B1 2 Bkj

1

: fv1 (B) \ B1 6= ; :

Weil die Anzahl der Boxen auf dem Level k jeweils endlich ist, gibt es eine Oberschranke für die Zahl jk der Schritte, die zu einer echten Verkleinerung der Anzahl der Boxen führen. Der Konvergenzbeweis überträgt sich ohne Weiteres auf diese Variante des Subdivisions-Algorithmus. Bemerkung 104 Siehe Szolnoki [21] für eine Diskussion, wieviele Schritte jk numerisch günstig sind. Er schlägt vor, zur Verfeinerung überzugehen, wenn die Anzahl der entfernten Boxen (relativ zur momentanen Gesamtzahl) unter eine vorgegebene Schranke fällt. Bemerkung 105 Entsprechende Modi…kationen des Subdivisions-Algorithmus kann man auch für die Berechnung von negativen Viabilitätsbereichen und solchen auf ganz R vornehmen Wir wenden uns jetzt einer anderen Modi…kation zu, die auf Grüne [9] zurückgeht. Es sollen beschränkte Teilmengen mit nichtleerem Innern des Rn berechnet werden. O¤enbar reicht es dafür, den (n 1) dimensionalen Rand solch einer Menge zu berechnen. Will man ihn überdecken, ist also die Anzahl der benötigten Boxen wesentlich geringer. Um einen solchen adaptiven Algorithmus (der sich auf den Rand der zu berechnenden Menge konzentriert) zu formulieren, müssen wir jeder Box B in einer Partition B k noch einen Status s(B) zuordnen. Er hat (genau) einen der folgenden Werte: IN (inside), P IN (partially inside); U N D (unde…ned), oder OU T (outside):

5.6. VARIANTEN DES SUBDIVISIONS-ALGORITHMUS Wir de…nieren die zugehörigen Punktmengen [ [ CkIN := B; CkP IN := B2Bk ;s(B)=IN

CkIN :=

[

B2Bk ;s(B)=IN

91

B;

B2Bk ;s(B)=P IN

B [ CkIN ; CkOU T :=

[

B2Bk ;s(B)=OU T

B [ Qc :

Im adaptiven Subdivisionsalgorithmus berechnen wir für eine Teilmenge S intQ den negativen relativen Ketten-Orbit. Um den Algorithmus zu starten, muss S Boxen der Anfangspartition enthalten, diese muss also insbesondere fein genug sein. Adaptiver Subdivisions-Algorithmus: Schritt 1: Wähle eine Zielmenge S intQ und setze k = 0. Setze den Status aller Boxen B 2 B0 mit s(B) :=

IN wenn B P IN sonst

S

:

Bestimme die Mengen C0IN ; C0P IN und C0OU T = Qc : Schritt 2: Führe den Subdivisions-Algorithmus folgendermaß en aus: ^ (a) Beim Übergang von Bk 1 zur feinerenSZerlegung Bk existieren für alle B 2 Bk 1 Boxen A1 ; :::Am 2 B^k mit B = m i=1 Ai . Setze im Subdivisionsschritt s(Ai ) := s(B). (b) Führe im Auswahlschritt Bk B^k die folgenden Status-Zuordnungen durch: (b1) Wiederhole für alle B 2 B^k mit s(B) = U N D oder s(B) = P IN folgende Vorschrift so oft, bis sich kein Status mehr ändert: 8 IN falls 9u 2 U : ( ; B; u) BkIN > > < OU T falls 8u 2 U : ( ; B; U BkOU T s(B) := P IN falls9u 2 U : ( ; B; u) \ BkIN 6= ; und 6 9u 2 U : ( ; B; u) > > : UND sonst Berechne jedesmal die Mengen CkIN ; CkP IN und CkOU T neu. (b2) Setze nach der Konvergenz für alle B 2 Bk : s(B) :=

OU T; falls s(B) = U N D U N D; falls s(B) = P IN

(b3) Berechne die Mengen CkIN ; CkP IN und CkOU T erneut.

Da die Boxen in BkIN und BkOU T nicht abgebildet werden, müssen sie in der Praxis auch nicht verfeinert werden. Das Verfahren bestimmt also selbst,

BkIN

:

92

KAPITEL 5. BERECHNUNG VON ERREICHBARKEITSMENGEN

welche Boxen unterteilt werden müssen und ist in diesem Sinn adaptiv. Die Mengenfolge, die nun den Rand der berechneten Menge beschreibt, ist CkU N D = B0 n BkIN [ BkOU T : für k 2 N. Satz 106 Ergebnis der adaptiven Subdivision Unter den obigen Voraussetzungen sei S0 = B0IN . Dann gilt für alle k 2 N0 : CkIN

CkOU T

@ OQ; (S0 ) [ S0

OQ; (S0 ) [ S0

OQ; (S0 ) [ S0

CkU N D :

c

CkIN [ CkU N D

CkOU T [ CkU N D

Für einen einfachen Beweis siehe Marquardt [15]. Der obige Satz enthält noch keine Konvergenz-Aussagen (nur Überdeckungs-Eigenschaften). Einen Konvergenzbeweis bei rigorosen Raumdiskretisierungen liefert Grüne [9, Theorem 7.5.5].

Literaturverzeichnis [1] J.-P. Aubin, Viability Theory, Birkhäuser, 1991. [2] B. Aulbach, Gewöhnliche Di¤erentialgleichungen, Spektrum Akademischer Verlag, 2004. Zweite Au‡age. [3] D. Cohen, Measure Theory, Birkhäuser Verlag, 1980. [4] F. Colonius and W. Kliemann, The Dynamics of Control, Birkhäuser, 2000. [5] M. Dellnitz and O. Junge, Set oriented numerical methods for dynamical systems, in Handbook of Dynamical Systems. Volume, B. Fiedler, ed., Elsevier, 2002, ch. 5, pp. 221–264. [6] N. Dunford and J. T. Schwartz, Linear Operators, Part I: General Theory, Wiley-Interscience, 1977. [7] F. Engelking, General Topology, PWN-Polish Scienti…c, Warszawa, 1977. [8] T. Gayer, Control sets and their boundaries under parameter variation, J. Di¤. Equations, 201 (2004), pp. 177–200. [9] L. Grüne, Asymptotic Behavior of Dynamical and Control Systems under Perturbation and Discretization, Springer-Verlag, 2002. [10] D. Hinrichsen and A. Pritchard, Mathematical Systems Theory, Springer-Verlag, 2005. [11] A. Isidori, Nonlinear Control Systems, Springer-Verlag, 1998. [12] D. Jungnickel, Graphs, Networks and Algorithms, Springer-Verlag, 2005. [13] V. Jurdjevic, Geometric Control Theory, Cambridge University Press, 1997. 93

94

LITERATURVERZEICHNIS

[14] A. J. Krener, A generalization of Chow’s theorem and Bang-Bang theorem for nonlinear control problems, SIAM J. Control Optim., 14 (1974), pp. 43–52. [15] A. Marquardt, Subdivisionsalgorithmen für Kontrollierbarkeitsprobleme, 2001. Diplomarbeit, Institut für Mathematik, Universität Augsburg. [16] H. Nijmeijer and A. J. van der Schaft, Nonlinear Dynamical Control Systems, Springer-Verlag, 1990. [17] G. K. Pedersen, Analysis Now, Springer-Verlag, 1988. [18] S. Sastry, Nonlinear Systems. Analysis, Stability, and Control, Springer-Verlag, 1999. [19] E. D. Sontag, Mathematical Control Theory, Springer-Verlag, 1998. Second Edition (First Edition, 1990). [20] D. Szolnoki, Viability Kernels and Control Sets, ESAIM Control, Optimisation and Calculus of Variations, 5 (2000), pp. 175–185. [21]

, Algorithms for reachability problems, 2001. Dissertation. Universität Augsburg. Shaker Verlag Aachen.

[22]

, Set oriented methods for computing reachable sets and control sets, Discrete and Continuous Dynamical Systems-Series B, 3 (2003), pp. 361– 382.

[23] A. Uppal, W. H. Ray, and A. B. Poore, On the dynamic behavior of continuous stirred tank reactors, Chem. Eng. Sci., 19 (1974), pp. 967– 985.