Lektion 9.2

Simulation dynamischer Systeme

22 min Lesezeit

Wie viele Fische darf ein Fischer jedes Jahr aus einem Teich fangen, ohne dass der Bestand zusammenbricht? Ausprobieren dauert Jahre und kann den Teich leer fischen.

Man baut stattdessen ein Modell, eine vereinfachte Nachbildung, und lässt es am Rechner ablaufen: eine Simulation. Du lernst, wie man solche Modelle aufstellt, durchrechnet und beurteilt.

Definition

Dynamisches System, Bestand und Fluss

Ein dynamisches System ändert seinen Zustand mit der Zeit, und der heutige Zustand bestimmt den nächsten (Teich, Bevölkerung, abkühlender Kaffee). Ein Flussdiagramm beschreibt es mit drei Bausteinen:

Bestand: eine Größe, die sich ansammelt, zum Beispiel die Zahl der Fische.
Fluss: die Menge pro Zeit, die in einen Bestand hinein (Zufluss) oder aus ihm heraus (Abfluss) fließt, zum Beispiel Geburten und Fang pro Jahr.
Parameter: eine feste, einstellbare Zahl, zum Beispiel die Geburtenrate.

Ein Bestand ändert sich nur durch seine Flüsse. Mit dem Zeitschritt $\Delta t$ zwischen zwei Rechnungen gilt:

B(t + \Delta t) = B(t) + \bigl(\text{Zufluss} - \text{Abfluss}\bigr) \cdot \Delta t

Definition

Wirkungsdiagramm und Rückkopplung

Ein Wirkungsdiagramm zeigt, welche Größen einander beeinflussen. Ein Pfeil von A nach B mit "+" heißt: Mehr A bewirkt mehr B. Mit "−" heißt er: Mehr A bewirkt weniger B. Beim Teich gibt es vier Pfeile: Fische nach Geburten (+), Geburten nach Fische (+), Fische nach Platz je Fisch (−), Platz je Fisch nach Geburten (+).

Ein geschlossener Kreis von Pfeilen ist eine Rückkopplung. Zähle die Minuszeichen im Kreis: Bei gerader Zahl (auch null) ist sie verstärkend, eine Änderung schaukelt sich auf. Bei ungerader Zahl ist sie ausgleichend, eine Änderung wird gedämpft. Fische, Geburten, Fische ist verstärkend. Fische, Platz je Fisch, Geburten, Fische hat ein Minuszeichen und ist ausgleichend.

Definition

Kontinuierliche und diskrete Vorgänge, Wachstumsprozesse

Kontinuierliche Größen ändern sich stetig (Wassermenge, Temperatur), diskrete nur in Schritten (Zahl der Kunden in einer Schlange). Ein Rechner arbeitet in Schritten: Er zerlegt kontinuierliche Vorgänge in kleine Zeitschritte $\Delta t$ und rechnet sie näherungsweise.

Bei Wachstumsprozessen hängt der Zuwachs pro Schritt so vom Bestand $B$ ab:

linear: konstant, zum Beispiel 5 pro Schritt, keine Rückkopplung
exponentiell: proportional zu $B$ , zum Beispiel 20 Prozent von $B$ , verstärkend
begrenzt (logistisch): $r \cdot B \cdot (1 - B/K)$ , bei kleinem $B$ verstärkend, nahe $K$ ausgleichend

Dabei ist $r$ die Wachstumsrate und $K$ die Kapazität, der größte Bestand, den die Umgebung trägt. Nahe $K$ ist $1 - B/K$ fast null, das Wachstum bremst ab.

Beispiel

Ein Teich mit begrenztem Platz

Anfangs leben 50 Fische, es gilt $r = 0{,}2$ pro Jahr und $K = 100$ . Berechne den Bestand nach einem und nach zwei Jahren mit $\Delta t = 1$ Jahr.

\begin{aligned} B(1) &= 50 + 0{,}2 \cdot 50 \cdot \left(1 - \tfrac{50}{100}\right) = 50 + 5 = 55 \\ B(2) &= 55 + 0{,}2 \cdot 55 \cdot \left(1 - \tfrac{55}{100}\right) = 55 + 4{,}95 = 59{,}95 \end{aligned}

Im ersten Jahr kommen 5 Fische hinzu, im zweiten nur 4,95, obwohl mehr Fische da sind: Der Faktor $1 - B/K$ sinkt von 0,5 auf 0,45. Das ist die ausgleichende Rückkopplung.

Definition

Implementierung mit System-Dynamics-Software

System-Dynamics-Software (zum Beispiel Vensim, Stella oder Insight Maker) setzt solche Modelle ohne Programmieren um: Du zeichnest Bestände, Flüsse und Parameter, schreibst für jede Größe eine Formel und stellst Anfangswerte, Zeitschritt und Dauer ein. Die Software rechnet Schritt für Schritt. Dahinter steckt eine Schleife wie diese:

Zeile	Einrückung	Anweisung
1	0	$\texttt{B = 50, K = 100, r = 0.2, dt = 1, t = 0}$
2	0	$\texttt{solange t < 10:}$
3	1	$\texttt{zuwachs = r * B * (1 - B / K)}$
4	1	$\texttt{B = B + zuwachs * dt}$
5	1	$\texttt{t = t + dt}$

Ändert man $r$ oder $K$ , rechnet die Software neu.

Definition

Euler-Cauchy-Verfahren

Diese Schleife ist das Euler-Cauchy-Verfahren, ein numerisches Verfahren: Es rechnet schrittweise Zahlen aus, statt eine Formel für den Verlauf zu suchen. Man kennt den Zustand $y_n$ zum Zeitpunkt $t_n$ und die Änderungsrate $f$ (wie schnell sich $y$ pro Zeiteinheit ändert, abhängig von $t_n$ und $y_n$ ) und geht einen Zeitschritt $h$ lang mit dieser Rate geradeaus weiter. Der Fehler summiert sich: Halbiert man $h$ , halbiert sich der Gesamtfehler ungefähr.

y_{n+1} = y_n + h \cdot f(t_n, y_n)

Definition

Runge-Kutta-Verfahren

Euler nutzt nur die Rate am Anfang des Schritts und läuft bei gekrümmter Kurve am Ziel vorbei. Das klassische Runge-Kutta-Verfahren (vierter Ordnung) schätzt die Rate an vier Stellen (Anfang, zweimal Mitte, Ende) und mittelt gewichtet, die Mitte zählt doppelt. Es braucht vier Auswertungen von $f$ je Schritt, ist aber viel genauer: Halbiert man $h$ , schrumpft der Fehler auf etwa ein Sechzehntel.

\begin{aligned} k_1 &= f(t_n, y_n) \\ k_2 &= f\bigl(t_n + \tfrac{h}{2},\, y_n + \tfrac{h}{2} k_1\bigr) \\ k_3 &= f\bigl(t_n + \tfrac{h}{2},\, y_n + \tfrac{h}{2} k_2\bigr) \\ k_4 &= f\bigl(t_n + h,\, y_n + h k_3\bigr) \\ y_{n+1} &= y_n + \tfrac{h}{6}\,(k_1 + 2k_2 + 2k_3 + k_4) \end{aligned}

Beispiel

Euler und Runge-Kutta im Vergleich

Ein Bestand startet bei $y(0) = 1$ mit der Änderungsrate $f = y$ (Wachstum von 100 Prozent pro Zeiteinheit). Berechne $y(1)$ mit Euler ( $h = 1$ und $h = 0{,}5$ ) und mit einem Runge-Kutta-Schritt ( $h = 1$ ). Der exakte Wert ist die Eulersche Zahl $e \approx 2{,}718$ .

Euler, $h = 1$ : $y(1) = 1 + 1 \cdot 1 = 2$ .

Euler, $h = 0{,}5$ : Erst $1 + 0{,}5 \cdot 1 = 1{,}5$ , dann $1{,}5 + 0{,}5 \cdot 1{,}5 = 2{,}25$ .

Runge-Kutta, $h = 1$ : $k_1 = 1$ , $k_2 = 1 + 0{,}5 \cdot 1 = 1{,}5$ , $k_3 = 1 + 0{,}5 \cdot 1{,}5 = 1{,}75$ , $k_4 = 1 + 1 \cdot 1{,}75 = 2{,}75$ . Damit $y(1) = 1 + \frac{1}{6}(1 + 3 + 3{,}5 + 2{,}75) = 1 + \frac{10{,}25}{6} \approx 2{,}708$ .

Runge-Kutta liegt schon nach einem Schritt etwa 0,01 neben 2,718, Euler weiter darunter.

Definition

Aussagekraft von Simulationen

Eine Simulation liefert Ergebnisse des Modells, nicht der Wirklichkeit. Ihre Aussagekraft hängt ab von:

dem Modell: Was wurde weggelassen (im Teich etwa Krankheiten)?
Parametern und Anfangswerten: Sie sind oft geschätzt. Darum rechnet man mehrere Szenarien (Was-wäre-wenn-Läufe).
der Numerik: Zeitschritt und Verfahren erzeugen Rechenfehler.

Die Verifikation fragt: Setzt das Programm das Modell richtig um? Man vergleicht mit einer Handrechnung. Die Validierung fragt: Beschreibt das Modell die Wirklichkeit gut genug? Man vergleicht mit gemessenen Daten. Eine Simulation ist eine begründete Aussage unter Annahmen, kein Beweis.

Definition

Zellulärer Automat

Ein zellulärer Automat besteht aus Zellen in einem Gitter, hier einer Zeile. Jede Zelle hat einen Zustand aus einer festen Menge. Eine Regel legt fest, wie der neue Zustand einer Zelle von ihrem eigenen Zustand und dem ihrer Nachbarzellen abhängt. Die Regel gilt in jedem Schritt für alle Zellen gleichzeitig: Alle neuen Zustände werden aus den alten berechnet. So erzeugen einfache lokale Regeln Muster im Großen, etwa die Ausbreitung von Feuer.

Beispiel

Ein Waldbrand in einer Zeile

Sieben Zellen haben die Zustände B (Baum), F (Feuer) oder L (leer, verbrannt). Regel: F wird L. B wird F, wenn links oder rechts eine Zelle im Zustand F liegt, sonst bleibt B. L bleibt L. Start (Schritt 0): B B B F B B B.

Schritt 1: B B F L F B B
Schritt 2: B F L L L F B
Schritt 3: F L L L L L F
Schritt 4: L L L L L L L

In Schritt 1 brennt die vierte Zelle ab, die dritte und fünfte fangen Feuer. Das Feuer läuft als Front nach beiden Seiten.

Definition

Ereignisorientierte Simulation

Bei einer zeitschrittorientierten Simulation rückt die Uhr um feste Schritte $\Delta t$ vor, auch wenn nichts geschieht. Bei der ereignisorientierten Simulation springt sie von einem Ereignis zum nächsten (Ankunft eines Kunden, Ende einer Bedienung), denn nur dabei ändert sich der Zustand. Eine nach Zeit sortierte Ereignisliste enthält die geplanten Ereignisse: Das Programm nimmt das früheste, setzt die Uhr auf dessen Zeit, ändert den Zustand und trägt neue Ereignisse ein.

Beispiel

Eine Kasse simulieren

Eine Kasse bedient in der Reihenfolge der Ankunft, jede Bedienung dauert 3 Minuten. Kunden kommen in den Minuten 1, 2 und 6. Bestimme die mittlere Wartezeit, also die Zeit zwischen Ankunft und Beginn der Bedienung.

Minute 1: Kunde 1 kommt, die Kasse ist frei, die Bedienung beginnt und endet in Minute 4.
Minute 2: Kunde 2 kommt und wartet.
Minute 4: Bedienung 1 endet, Kunde 2 beginnt und endet in Minute 7.
Minute 6: Kunde 3 kommt und wartet.
Minute 7: Bedienung 2 endet, Kunde 3 beginnt.

Die Uhr springt von 1 auf 2, 4, 6 und 7. Wartezeiten: 0, 4 - 2 = 2 und 7 - 6 = 1 Minute, im Mittel (0 + 2 + 1) : 3 = 1 Minute.

Häufige Fehler

Ein kleinerer Zeitschritt macht die Simulation realistischer

„Ich verkleinere den Zeitschritt, dann stimmt die Prognose besser.“

Richtig ist

Ein kleinerer Zeitschritt verringert nur den Rechenfehler. Das Ergebnis kommt näher an die exakte Lösung des Modells, nicht an die Wirklichkeit. Ob das Modell passt, zeigt erst die Validierung.

Zusammenfassung

Ein dynamisches System beschreibt man mit Beständen, Flüssen und Parametern. Ein Bestand ändert sich nur durch Zufluss und Abfluss.
Eine gerade Zahl von Minuszeichen im Kreis eines Wirkungsdiagramms ergibt eine verstärkende, eine ungerade eine ausgleichende Rückkopplung.
Wachstum kann linear, exponentiell oder begrenzt sein. Rechner zerlegen kontinuierliche Vorgänge in Zeitschritte.
Euler-Cauchy geht mit der Anfangsrate geradeaus weiter, Runge-Kutta mittelt vier Raten und ist viel genauer.
Verifikation prüft die Umsetzung, Validierung den Vergleich mit der Wirklichkeit. Eine Simulation gilt nur unter den Annahmen des Modells.
Nur im Leistungskurs: zelluläre Automaten und ereignisorientierte Simulation.

Übungen

Aufgabe 1Numerisch

Ein Bestand von 80 hat einen Zufluss von 10 Prozent des Bestands pro Jahr und einen Abfluss von konstant 5 pro Jahr. Der Zeitschritt ist 1 Jahr. Wie groß ist der Bestand nach zwei Jahren?

Aufgabe 2Multiple Choice

Mehr Räuber bewirken weniger Beute (Pfeil "−"). Mehr Beute bewirkt mehr Räuber (Pfeil "+"). Welche Rückkopplung bilden beide Pfeile?

Aufgabe 3Numerisch

Eine Größe y hat die Änderungsrate f = 3 · y und startet bei y(0) = 2. Berechne y(0,2) mit dem Euler-Verfahren und h = 0,1 (zwei Schritte).

Aufgabe 4Freitext

Ein Programm setzt das Teich-Modell fehlerfrei um, die Ergebnisse passen aber nicht zu den gezählten Fischen. Fehlt es an Verifikation oder an Validierung? Begründe.

Aufgabe 5Numerisch

Nur Leistungskurs: Eine Kasse bedient in der Reihenfolge der Ankunft, jede Bedienung dauert 3 Minuten. Kunden kommen in den Minuten 0, 1 und 5. In welcher Minute endet die Bedienung des dritten Kunden?

Lektion 9.2 · Big Data, Simulation und Internet der Dinge

Simulation dynamischer Systeme

Wie viele Fische darf ein Fischer jedes Jahr aus einem Teich fangen, ohne dass der Bestand zusammenbricht? Ausprobieren dauert Jahre und kann den Teich leer fischen.

Man baut stattdessen ein Modell, eine vereinfachte Nachbildung, und lässt es am Rechner ablaufen: eine Simulation. Du lernst, wie man solche Modelle aufstellt, durchrechnet und beurteilt.

Definition

Dynamisches System, Bestand und Fluss

Bestand: eine Größe, die sich ansammelt, zum Beispiel die Zahl der Fische.
Fluss: die Menge pro Zeit, die in einen Bestand hinein (Zufluss) oder aus ihm heraus (Abfluss) fließt, zum Beispiel Geburten und Fang pro Jahr.
Parameter: eine feste, einstellbare Zahl, zum Beispiel die Geburtenrate.

Ein Bestand ändert sich nur durch seine Flüsse. Mit dem Zeitschritt $\Delta t$ zwischen zwei Rechnungen gilt:

B(t + \Delta t) = B(t) + \bigl(\text{Zufluss} - \text{Abfluss}\bigr) \cdot \Delta t

Definition

Wirkungsdiagramm und Rückkopplung

Definition

Kontinuierliche und diskrete Vorgänge, Wachstumsprozesse

Bei Wachstumsprozessen hängt der Zuwachs pro Schritt so vom Bestand $B$ ab:

linear: konstant, zum Beispiel 5 pro Schritt, keine Rückkopplung
exponentiell: proportional zu $B$ , zum Beispiel 20 Prozent von $B$ , verstärkend
begrenzt (logistisch): $r \cdot B \cdot (1 - B/K)$ , bei kleinem $B$ verstärkend, nahe $K$ ausgleichend

Dabei ist $r$ die Wachstumsrate und $K$ die Kapazität, der größte Bestand, den die Umgebung trägt. Nahe $K$ ist $1 - B/K$ fast null, das Wachstum bremst ab.

Beispiel

Ein Teich mit begrenztem Platz

Anfangs leben 50 Fische, es gilt $r = 0{,}2$ pro Jahr und $K = 100$ . Berechne den Bestand nach einem und nach zwei Jahren mit $\Delta t = 1$ Jahr.

\begin{aligned} B(1) &= 50 + 0{,}2 \cdot 50 \cdot \left(1 - \tfrac{50}{100}\right) = 50 + 5 = 55 \\ B(2) &= 55 + 0{,}2 \cdot 55 \cdot \left(1 - \tfrac{55}{100}\right) = 55 + 4{,}95 = 59{,}95 \end{aligned}

Im ersten Jahr kommen 5 Fische hinzu, im zweiten nur 4,95, obwohl mehr Fische da sind: Der Faktor $1 - B/K$ sinkt von 0,5 auf 0,45. Das ist die ausgleichende Rückkopplung.

Definition

Implementierung mit System-Dynamics-Software

Zeile	Einrückung	Anweisung
1	0	$\texttt{B = 50, K = 100, r = 0.2, dt = 1, t = 0}$
2	0	$\texttt{solange t < 10:}$
3	1	$\texttt{zuwachs = r * B * (1 - B / K)}$
4	1	$\texttt{B = B + zuwachs * dt}$
5	1	$\texttt{t = t + dt}$

Ändert man $r$ oder $K$ , rechnet die Software neu.

Definition

Euler-Cauchy-Verfahren

y_{n+1} = y_n + h \cdot f(t_n, y_n)

Definition

Runge-Kutta-Verfahren

\begin{aligned} k_1 &= f(t_n, y_n) \\ k_2 &= f\bigl(t_n + \tfrac{h}{2},\, y_n + \tfrac{h}{2} k_1\bigr) \\ k_3 &= f\bigl(t_n + \tfrac{h}{2},\, y_n + \tfrac{h}{2} k_2\bigr) \\ k_4 &= f\bigl(t_n + h,\, y_n + h k_3\bigr) \\ y_{n+1} &= y_n + \tfrac{h}{6}\,(k_1 + 2k_2 + 2k_3 + k_4) \end{aligned}

Beispiel

Euler und Runge-Kutta im Vergleich

Euler, $h = 1$ : $y(1) = 1 + 1 \cdot 1 = 2$ .

Euler, $h = 0{,}5$ : Erst $1 + 0{,}5 \cdot 1 = 1{,}5$ , dann $1{,}5 + 0{,}5 \cdot 1{,}5 = 2{,}25$ .

Runge-Kutta liegt schon nach einem Schritt etwa 0,01 neben 2,718, Euler weiter darunter.

Definition

Aussagekraft von Simulationen

Eine Simulation liefert Ergebnisse des Modells, nicht der Wirklichkeit. Ihre Aussagekraft hängt ab von:

dem Modell: Was wurde weggelassen (im Teich etwa Krankheiten)?
Parametern und Anfangswerten: Sie sind oft geschätzt. Darum rechnet man mehrere Szenarien (Was-wäre-wenn-Läufe).
der Numerik: Zeitschritt und Verfahren erzeugen Rechenfehler.

Definition

Zellulärer Automat

Beispiel

Ein Waldbrand in einer Zeile

Schritt 1: B B F L F B B
Schritt 2: B F L L L F B
Schritt 3: F L L L L L F
Schritt 4: L L L L L L L

In Schritt 1 brennt die vierte Zelle ab, die dritte und fünfte fangen Feuer. Das Feuer läuft als Front nach beiden Seiten.

Definition

Ereignisorientierte Simulation

Beispiel

Eine Kasse simulieren

Die Uhr springt von 1 auf 2, 4, 6 und 7. Wartezeiten: 0, 4 - 2 = 2 und 7 - 6 = 1 Minute, im Mittel (0 + 2 + 1) : 3 = 1 Minute.

Häufige Fehler

Ein kleinerer Zeitschritt macht die Simulation realistischer

„Ich verkleinere den Zeitschritt, dann stimmt die Prognose besser.“

Ein kleinerer Zeitschritt verringert nur den Rechenfehler. Das Ergebnis kommt näher an die exakte Lösung des Modells, nicht an die Wirklichkeit. Ob das Modell passt, zeigt erst die Validierung.

Zusammenfassung

Ein dynamisches System beschreibt man mit Beständen, Flüssen und Parametern. Ein Bestand ändert sich nur durch Zufluss und Abfluss.
Eine gerade Zahl von Minuszeichen im Kreis eines Wirkungsdiagramms ergibt eine verstärkende, eine ungerade eine ausgleichende Rückkopplung.
Wachstum kann linear, exponentiell oder begrenzt sein. Rechner zerlegen kontinuierliche Vorgänge in Zeitschritte.
Euler-Cauchy geht mit der Anfangsrate geradeaus weiter, Runge-Kutta mittelt vier Raten und ist viel genauer.
Verifikation prüft die Umsetzung, Validierung den Vergleich mit der Wirklichkeit. Eine Simulation gilt nur unter den Annahmen des Modells.
Nur im Leistungskurs: zelluläre Automaten und ereignisorientierte Simulation.