Modul 19 Aufgaben Literatur Die Module

Algorithmenkonstruktion mit dem Modell Motor-Stabilisator-Last Teil 1

Der Begriff ''deterministischer Automat'' (dA) ist entstanden als abstraktes Modell realer diskontinuierlich (zeitdiskret, getaktet) und determiniert arbeitender informationeller Systeme mit Eingabe-, Ausgabe-, Verknüpfungs- und Speicherelementen als Träger informationeller Prozesse.

Der dA ist zugleich aber auch ein Notierungssystem mit integrativem, konstruktivem und heuristischem Charakter für eine beträchtliche Anzahl von Algorithmen.

Die Einbettung von Algorithmen in das mathematische Modell dA ist ein nützliches Werkzeug für systematische Erweiterungen, Verallgemeinerungen, Kombinationen, ... von Algorithmen unter Einvernahme des theoretischen und ingenieurmäßig-pragmatischen Methodeninventars für die Analyse und Synthese von Automaten (Schaltbilddenken, Einfügen zusätzlicher Rückkopplungen, Zusammenschaltungen, Zustandskopplungen; vgl. [1], Abschn. 4 und [2], Abschn. 2.3). Vielfach ergibt sich dabei zwanglos die Hinzunahme eines zunächst nicht vorhandenen Schalt- bzw. Steuereingangs (Analogie: Diode Transistor).
Ein dA wird durch nachstehendes Blockschema Bild 1 symbolisiert.

Bild 1: Blockschaltbild des dA

Hierbei ist

	-	Eingangsvariable Eingangsmenge/Eingabealphabet	(1)
	-	Ausgangsvariable Ausgangsmenge/Ausgabealphabet	(2)
	-	Zustandsvariable Zustandsmenge/internes Alphabet	(3)
	-	Taktzeitpunkt	(4)
	-	(eindeutige)- Ergebnisabbildung,	(5)
		Elementnotation
	-	(eindeutige) Folgezustandsabbildung,	(6)
		Elementnotation
	-	Anfangszustand.	(7)

beschreibt die sequentielle, äquidistant getaktete und deterministische Umformung einer Eingangsfolge (eines Eingabewortes)

(8)

in eine Ausgangsfolge (ein Ausgabewort)

(9)

Dabei wird in jedem Taktzeitpunkt (fester aber beliebiger Zeitwert) aus dem einlaufenden Eingangswert und dem im Zeitintervall ''im dA gespeicherten'' Zustandswert

• der Ausgangswert gebildet und unmittelbar ausgegeben,
• der neue Zustandswert gebildet und der alte Zustandswert mit ''überschrieben''. bleibt danach im Intervall im dA gespeichert, Bild 2.

Arbeitsregime des dA

Beispiel:

Verzögerungselement erster Ordnung (D1), Bild 3

Bild 3: Verzögerungselement erster Ordnung

X = Y = Z	(10)
y = r (x, z) = z	(11)
z' = s (x, z) = x	(12)

Jeder Eingangswert erscheint um einen Takt verzögert als am Ausgang, er wird als Zustandswert für einen Takt in D1 gespeichert, und sind dabei vollständig entkoppelt.

Heron von Alexandria (1. Jh. n. Chr.) hat ca. 80 n. Chr. zusammen mit

einem Verfahren zur Berechnung des Flächeninhaltes eines ebenen Dreiecks aus den Seitenlängen (Heronsche Formel)

auch

einen Algorithmus zur näherungsweisen Berechnung der Quadratwurzel einer positiven reellen Zahl angegeben (Heronsches Verfahren):

''VIII. Es giebt eine allgemeine Methode, um, wenn drei Seiten eines beliebigen Dreiecks gegeben sind, den Inhalt ohne die Höhe zu finden. Beispielsweise seien die Seiten des Dreiecks =7, 8, 9.

Daraus ziehe die Wurzel, und sie wird gleich dem Inhalt des Dreiecks sein. Da nun eine rationale Wurzel nicht besitzt, so werden wir mit kleinster Differenz die Wurzel folgendermaßen ziehen. Da die nächstkommende Quadratzahl ist und die Wurzel hat, so teile durch ; es ergiebt . Es wird also die Wurzel aus annähernd sein. Denn , sodaß die Differenz nur beträgt. Wenn wir aber wünschen, daß die Differenz kleiner als wird, so werden wir anstatt den gefundenen Wert einsetzen, und wenn wir dann wieder dasselbe thun, so werden wir finden, daß die Differenz viel kleiner als wird.''
H. Schöne. Herons von Alexandria Vermessungslehre und Dioptra. Leipzig 1903, S. 19-21

Dieser Heron-Algorithmus läßt sich wie folgt als Struktogramm [3,4] notieren:

Algorithmus (A1): Heron-Algorithmus zur näherungsweisen Berechnung der Quadratwurzel einer positiven reellen Zahl

In [5], Abschn. 3.2 wurde gezeigt:

• (A1) konvergiert für alle Startwerte und liefert (Fixpunkt).

• Die "Einschwingdauer"hängt dabei von und ab, sie ist umso größer, je größer ist; (A1) konvergiert in Fixpunktnähe quadratisch.

• Bei sprungförmiger Änderung des Radikanden von auf läuft bei "Eingabe"von und dem Startwert zunächst der Berechnungsprozeß von ab, bei der "Eingabe"von beginnt mit dem zuletzt berechneten Näherungswert für als neuem Startwert der Berechnungsprozeß von . (A1) besitzt " Inputfolgeverhalten"mit einem zwischengeschalteten Einschwingvorgang.

Die Abarbeitung des Heron-Algorithmus entspricht genau dem eingangs beschriebenen dA-Umformungsprozeß einer Eingangsfolge, hier

(13)

in eine Ausgangsfolge, hier

	(14)
	(15)
	(16)

Diese Zuordnung ist als "Einbettung"des Heron-Algorithmus (A1) in das mathematische Modell dA zu interpretieren (Tabelle 1), vgl. Modul 3.

(A1)						für alle
dA						für alle

Tabelle 1: Automateneinbettung des Heron-Algorithmus

Aufgabe 19.1 Der dA nach Tabelle 1 generiert bei konstanter Eingabe unabhängig von seinem Anfangszustand nach einem Einschwingvorgang stationär die Ausgabe . (a) Untersuchen Sie durch Berechnung und Experiment die Abhängigkeit derEinschwingdauer des dA Tabelle 1 von und (vgl. [5], Abschn. 3.2, Aufgabe 6). (b) Untersuchen Sie experimentell das Verhalten von dA Tabelle 1 bei zeitveränderlicher Eingabe (sprungförmig, linear ansteigend, quadratisch ansteigend, sinusförmig, ...), insbesondere für den Fall gegenüber dem Einschwingvorgang schneller bzw. langsamer Eingabeänderung. Diskutieren Sie die Ergebnisse.

Setzt man in (A1)

(17)

und betrachtet

(18)

als Eingangsfolge eines dA, so erhält man die in Tabelle 2 dargestellte modifizierte Automateneinbettung des Heron-Algorithmus, bei der die numerische Operation Quadratwurzelberechnung herausgelöst ist.

Der so normierte dA zeigt das Verhaltensmuster "dynamischer Inputfolger"(INF):

• Bei konstanter Eingabe wird
  - nach einem kurzen Einschwingvorgang, dessen Dauer von und abhängt,
  - stationär ausgegeben.
  Eine danach in einem Taktzeitpunkt von außen aufgeprägte Änderung ("Injektion") führt über einen neu beginnenden kurzen Einschwingvorgang wieder zu der stationären Ausgabe .

• Bei einer gegenüber der Einschwingdauer langsam veränderlichen Eingabe ist stationär .

• Bei sprungförmiger Eingabe

  (19)

  folgt über zwei Einschwingvorgänge .
  In Bild 4 ist ein entsprechendes Experiment mit
  

  (20)

  
  dokumentiert. Bild 4: Verhalten des dynamischen Inputfolgers bei sprungförmiger Eingabe Gl. (20)

Aufgabe 19.2 (a)   Bearbeiten Sie die Fragestellungen von Aufgabe 19.1 für den dA INF. (b)   Untersuchen Sie analytisch und experimentell das Verhalten des INF für (21)

Der vorstehend beschriebene dA dynamischer Inputfolger realisiert offensichtlich, abgesehen von kontraktiven Einschwingvorgängen (vgl. [6,7,8]), keine eigenständige Umformung seiner Eingangsfolge, ist also für sich gesehen algorithmisch inaktiv. Er entfaltet seine Wirkung erst in geeigneten Zusammenschaltungen. Die folgenden Experimente sollen das pragmatisch ausloten.

Experiment 1

In einem ersten Experiment wird die Auswirkung einer weiteren, gewichteten Rückkopplung (Bild 5) auf das Verhalten des INF untersucht.

Bild 5: INF mit zusätzlicher Rückkopplung, Experiment 1

Für

(22)

erhält man den in Bild 6 dargestellten Verlauf von .

Bild 6:

Verlauf von Eingangs- und Ausgangsgröße des INF nach Bild 5;

Nach einem kurzen Einschwingvorgang wird stationär

(23)

ausgegeben.
Diese experimentell gefundene Beziehung läßt sich leicht aus dem Schaltbild des dA Bild 5 herleiten. Man hat hier für Ergebnis- bzw. Folgezustandsabbildung

	(24)
	(25)

Für

(26)

ist im stationären Fall daraus folgt aus Gl. (25) mit Gl. (24)

(23)

Der dA Bild 5 zeigt bei konstanter Eingabe also das Verhaltensmuster "dynamischer linearer Verstärker bzw. Abschwächer ", er löst dabei iterativ die lineare Gleichung

(27)

und liefert am Ausgang das Ergebnis

(28)

Anmerkung:

Diese Interpretationen von Experiment 1 assoziieren ein weiteres Modell aus der Elektrotechnik, das System Motor-Last (vgl. Bild 5) und damit verknüpft die Fragestellungen

- "stärkerer Motor"- kürzere Einschwingdauer

- größere Last"- längere Einschwingdauer

- Belastungskennlinie

- verschiedene Motorarten, verschiedene Lastarten

Aufgabe 19.3 Bearbeiten Sie die Fragestellungen von Aufgabe 19.1 für den dA Bild 5.

Experiment 2

Bei Experiment 2 befindet sich in dem zusätzlichen Rückkopplungszweig eine nichtlineare Last (Bild 7)

(29)

Bild 7: INF mit zusätzlicher Rückkopplung, Experiment 2

Bild 8 zeigt ein typisches Verhaltensmuster dieses dA.

Bild 8:

Verlauf der Ausgangsgröße des INF nach Bild 7;

Bei konstanter Eingabe folgt auf einen anfänglichen kurzen Einschwingvorgang (wie bei Experiment 1) ein amplitudenbegrenztes pseudostochastisches Oszillieren, in dessen Verlauf kurze auf hin konvergierende und dann wieder divergierende Abschnitte einander abwechseln.
Für kleine lassen sich diese Oszillationen bereits durch Zuschalten eines einfachen Mittelwertbildners (" Glätten"durch arithmetische Mittelwertbildung, AM) unterdrücken, man erhält so den dA Bild 9 mit den Komponenten Motor, Last und Stabilisator.

Bild 9: Iterativer Gleichungslöser für

Die Bilder 10 und 11 zeigen typische Verhaltensmuster dieses dA.

Bild 10: Verlauf der Ausgangsgröße y(t) des iterativen Gleichungslösers nach Bild 9;

Bild 11: Verlauf der Ausgangsgröße y(t) des iterativen Gleichungslösers nach Bild 9;

Bei konstanter Eingabe wird nach einem kurzen Einschwingvorgang nunmehr stationär

(30)

ausgegeben, d.h. der dA Bild 9 löst dann iterativ die Gleichung

(31)

und liefert am Ausgang das Ergebnis

(32)

Aufgabe 19.4 (a) Für größere besitzt der dA Bild 9 zunehmend längere Einschwingzeiten, dabei treten systematisch oder pseudostochastisch aufgebaute Instabilitäten im Verlauf von auf, bis schließlich stationär ausgegeben wird. Analysieren Sie diese Ausgabemuster (Zeitverlauf , Differenzenquotient , , ...). Entwerfen und erproben Sie "schaltungstechnische Maßnahmen"zur Unterdrückung der Instabilitäten und zur Verkürzung der Einschwingzeit. (b) Zeigen Sie experimentell und analytisch, daß unter den denkbar möglichen Primärrückkopplungen in Bild 9 nur den gewünschten Effekt (Beseitigung der Oszillationen) bewirkt. (c) Bearbeiten Sie die Fragestellungen von Aufgabe 19.1 für den vorliegenden Fall. (d) Diskutieren Sie alle erhaltenen Ergebnisse in Bezug auf die praktische Anwendbarkeit des vorliegenden Gleichungslösers. Vergleichen Sie mit anderen Algorithmen.

Experiment 3

(33)

Bild 12: Iterativer Gleichungslöser für die algebraische Gleichung

Die Bilder 13 und 14 zeigen für diesen dA typische Verläufe der Ausgangsgröße . Dabei wird jeweils eine positive Lösung der algebraischen Lastgleichung (33) richtig berechnet.

Bild 13:

Verlauf der Ausgangsgröße y(t) des iterativen Gleichungslösers nach Bild 12;

Bild 14:

Verlauf der Ausgangsgröße y(t) des iterativen Gleichungslösers nach Bild 12;

Besitzt die Lastgleichung (33) keine positiven Lösungen, läuft gegen 0, der dA Bild 12 berechnet dann keine Lösung der Lastgleichung: Bild 15.

Bild 15:

Verlauf der Ausgangsgröße y(t) des iterativen Gleichungslösers nach Bild 12;

Aufgabe 19.5 (a) Warum berechnet der iterative Gleichungslöser nach Bild 12 nur eine positive Lösung der Lastgleichung (33)? (b) Wie ist der dA Bild 12 durch eine äußere Beschaltung zu verändern, damit er bei konstanter Eingabe nach einem Einschwingvorgang in periodischer Abfolge alle reellen (also auch die negativen) Lösungen der Lastgleichung berechnet und sequentiell ausgibt (vgl. [5], Abschn. 3.2)?

Experiment 4

(34)

(35)

(36)

Bild 16: Iterativer Gleichungslöser für die Lastgleichungen (35) bzw. (36)

Im Falle der eindeutig umkehrbaren Lastgleichung

(35)

berechnet der iterative Gleichungslöser gemäß Bild 16 bei konstanter Eingabe nach einem kurzen Einschwingvorgang die einzige Lösung

(37)

(Bild 17), d.h. der dA erzeugt iterativ die Umkehrfunktion der Exponentialfunktion .

Bild 17:

Verlauf der Ausgangsgröße y(t) des iterativen Gleichungslösers für die Lastgleichung ;

Die Lastgleichung (die zu invertierende Funktion) (36) ist nicht eindeutig umkehrbar, die Lösung liegt hier im Intervall (Quantisierungen in der zu lösenden Gleichung führen zu einer Bandstruktur der Lösung) und wird im konkreten Falle durch die Anfangszustände und determiniert: Bilder 18 und 19.

Bild 18: Verlauf der Ausgangsgröße y(t) des iterativen Gleichungslösers für die Lastgleichung (36);

Bild 19: Verlauf der Ausgangsgröße y(t) des iterativen Gleichungslösers für die Lastgleichung (36);

Die Ergebnisse der Experimente 1, 2, 3 und 4 bilden die Basis für ein zunächst pragmatisch begründetes Modell:
Der dA dynamischer Inputfolger wird

• als leistungsfähiger Iterationsmotor ("Treiber")

• durch Einfügen eines zusätzlichen Rückkopplungszweiges, in den,

• erforderlichenfalls über eine stabilisierende Anpassungsschaltung

• eine einstellige Funktion (Gleichung)

  (38)

  als Last eingeschaltet ist,

• der bei konstanter Eingabe des Funktionswertes

• nach einem kontraktiven Einschwingvorgang

• mit erforderlicher Genauigkeit einen zugehörigen Argumentwert (eine zugehörige Lösung)

  (39)

  ausgibt.

• erfolgt nichtinvasiv (also nicht durch formales Auflösen der Gleichung nach )

• geschieht durch aufeinanderfolgende Berechnung von Funktionswerten der Lastfunktion so, daß deren Folge gegen das gegebene und deren Argumentfolge gegen das gesuchte inv konvergiert. Die Konvergenz wird durch die Kontraktionswirkung des dynamischen Inputfolgers (vgl. [6,7,8]) erzwungen.

Aufgabe 19.6 Wie ist das vorstehend eingeführte Modell Motor-Stabilisator-Last durch eine zusätzliche äußere Beschaltung zu erweitern, damit bei konstanter Eingabe nach einem Einschwingvorgang in periodischer Abfolge alle reellen Lösungen der Lastgleichung berechnet und sequentiell ausgegeben werden (vgl. Aufgabe 19.5 (b)). Erproben Sie Ihre Vorschläge experimentell.

Aufgabe 19.7 Suchen Sie nach "stärkeren" (kontraktiveren, schnelleren, ...) Iterationsmotoren. Testen Sie in diesem Zusammenhang experimentell den in Bild 20 dargestellten Schaltungsvorschlag. Bild 20: Iterationsmotor mit den Kontraktionsfunktionen (40)

Aufgabe 19.8 Entwerfen und erproben Sie im Zusammenhang mit den Aufgaben 19.6 und 19.7 wirksame schaltungstechnische Maßnahmen zur Unterdrückung von Instabilitäten und zur Verkürzung der Einschwingzeit. Studieren Sie hierzu das Methodeninventar (Filter, etc.) der Kommunikationstechnik [9] und der digitalen Bildverarbeitung [10,11,12].

Aufgabe 19.9 Diskutieren Sie alle erhaltenen Ergebnisse in Bezug auf die praktische Anwendbarkeit und Leistungsfähigkeit des vorliegenden Modells Motor-Stabilisator-Last. Vergleichen Sie mit anderen Algorithmen.