Modellbildung und Simulation – Einführung

Modelle und Simulationen

wissenschaftlicher Erkenntniserwerb: Die zwei klassischen Säulen des Erkenntniserwerbs sind Theorie (analytische Berechnungen, Gedankenexperimente) und Experiment (zur Verfikation der Theorie/wo keine Theorie vorhanden). Allerdings versagen beide Methoden oft, denn die Theorie löst meist nur einfache Szenarien explizit und Experimente können unmöglich, gefährlich, unerwünscht oder zu teuer sein. Daher hat sich als 3. Säule die Simulation etabliert.

Modell: Ein Modell ist ein vereinfachendes Abbild einer partiellen Realität.
Man unterscheidet zwischen konkreten (Modellbau, Windkanal usw.) und abstrakten (formale, mathematische Beschreibung) Modellen.

mathematische Modellierung: Die Herleitung/Analyse eines math. Modells ist eine Formalisierung/Mathematisierung des Problems durch zur besseren Lösbarkeit.

informale Bescheibung des Problems in Prosaform
semiformale Beschreibung mit dem Instrumentarium der Anwendungswissenschaft
streng formale, konsistente Beschreibung

Simulation: Eine Simulation ist ein virtuelles (i. A. rechnergestütztes) Experiment am Modell. Die Simulation ist das eigentliche Ziel der Modellierung.

Modellbildung in versch. Wissenschaften:

exakte Naturwissenschaften: lange Tradition, z. B. Physik, Modellbildung i. A. anerkannt
staatliche Wirtschaftspolitik: stark umstritten, verschiedene Lager erstellen „ihre“ Modelle
Klimapolitik: stark voneinander abweichende Theorien zu Ozonloch/globaler Erwärmung
Spieltheorie: von Neumanns Min-Max-Prinzip kaum realistisch für Zocker

Ziele von Simulation:

besseres Verständnis (Erdbeben, Einsturz des WTC an 9/11)
Optimierung (Flugeinsatzplan, Wärmeabtransport, Rechensystem-Durchsatz)
Vorhersage (Klimaveränderungen, Wetter, Bevölkerungswachstum)

Simulationspipeline:

Modellierung: vereinfachende formale Beschreibung eines geeigneten Ausschnitts
Berechnung/Simulation im engeren Sinn: geeignete Aufbereitung des Modells
Implementierung: effiziente Umsetzung der Berechnungsalgorithmen
Visualierung/Datenexploration: Interpretation der Ergebnisse eines Simulationslaufs
Validierung: Abgleich von Simulationergebnissen z. B. mit Experimenten
Einbettung: Integration in Simulationskontext

Anwendungen: Physik, Chemie, Biologie, Materialwissenschaften, Klima/Wetter, Automobilindustrie, Nationalökonomie, Finanzwirtschaft, Halbleiterindustrie, Computergrafik, Logistik/Ablaufplanung, Verkehrstheorie, Strategie, Wahl-/Meinungsforschung, Codierungstheorie

Herleitung von Modellen

Fragen:

Was genau soll modelliert werden? (Wirkungsgrad eines Katalysators oder die detaillierten Reaktionsvorgänge, Bevölkerungswachstum in Afrika oder nur in Kairo, Durchsatz durch ein Rechnernetz oder die mittlere Durchlaufzeit eines Pakets)
Welche Größen spielen eine Rolle (qualitativ) und wie groß ist ihr Einfluss (quantitativ)? (Raumschiff-Flugbahn: Gravitation von Mond, Pluto, Dow Jones morgen: Äußerungen von Bernanke, uns)
In welcher Beziehung stehen die Größen zueinander? (qualitativ, quantitativ)
Mit welchem Instrumentarium lassen sich die Abhängigkeiten beschreiben?

Frühe Festlegungen bestimmen dabei spätere Simulationsergebnisse!

Instrumentarien zur Beschreibung von Beziehungen:

algebraische Gleichungen und Ungleichungen: \(E = mc^2\), \(w^\tp x \le 10\)
Systeme gewöhnlicher Diferentialgleichungen: \(\ddot {y} + y = 0\) (Oszillation eines linearen Pendels), \(\dot {y} = y\) (exponentielles Wachstum), \(\dot {x} = -mx + ay + c\), \(\dot {y} = bx - ny + d\) mit \(a, b, c, d, m, n \ge 0\) (Wettrüsten zweier Großmächte)
Systeme partieller Diferentialgleichungen: \(u_xx + u_yy = f\) für \((x, y) \in \Omega \), \(u = 0\) für \((x, y) \in \partial \Omega \) (Verformung einer am Rand eingespanntne Membran unter Last \(f\))
Automaten/Zustandsübergangsdiagramme:
Warteschlangen, Texterkennung, Wachstumsprozesse mit zellulären Automaten
Graphen: Rundreisen (TSP), Reihenfolgeprobleme, Rechensysteme, Abläufe
Wahrscheinlichkeitsverteilungen: Ankunft in Warteschlange, Zustimmung zur Politik in Abh. von Arbeitslosenquote, Kontrolltheorie (Störungen), randomisierte Heuristiken
Fuzzy Logic: Regelungen von Wasch-/Spülmaschinen, Fotoapparate
neuronale Netze
Sprachkonzepte: UML
algebraische Strukturen: Gruppen in der Quantenmechanik, endliche Körper (Kryptologie)

Simulationsaufgabe: Welche Gestalt hat die resultierende Aufgabenstellung?

Finde eine Lösung des LGS (gültige Startlösung für lineare Optimierung).
Finde die Lösung des LGS (eindeutig lösbare PDE).
Gibt es eine Lösung (Hamilton-Weg im Graphen)?
Löse eine unbeschränkte Extremalaufgabe (kürzester Weg Quelle – Senke).
Löse eine beschränkte Extramalaufgabe (Rucksackproblem, lineare Optimierung).
Ermittle den Störenfried bzw. den Flaschenhals (Komponente maximaler Auslastung).

Analyse

Beispiele zu Aussagen zur Handhab- und Lösbarkeit:

Existenz von Lösungen: Populationsdynamik (Gibt es einen stationären Grenzzustand, wenn ja, wird dieser erreicht?), Reihenfolgeproblem (Ist der Präzedenzgraph zyklenfrei?), Minimierung (Gibt es Minima oder nur Sattelpunkte?)
Eindeutigkeit von Lösungen: Minimierung (Lokales oder globales Minimierung?), Molekulardynamik (Stabile Zustände oder Oszillationen zwischen verschiedenen Lösungen?), alle Lösungen gleichwertig?
stetige Abhängigkeit der Resultate von den Eingabedaten (Eingabe enthält Anfangs- und Randwerte, Startzustände usw., entspricht Kondition/Sensitivität)

sachgemäß gestellt: Ein Problem heißt sachgemäß gestellt, wenn es stets eine eindeutige Lösung gibt und diese stetig von den Eingabedaten abhängt. Die meisten Probleme sind allerdings unsachgemäß gestellt.

inverses Problem: Bei einem inversen Problem ist ein Ergebnis vorgegeben, gesucht ist die Anfangseinstellung (z. B. Wirtschaftspolitik, Technik, Rechnernetz). Strategien zur Lösung umfassen sinnvolles Ausprobieren und Anpassen (Folge von Vorwärtsproblemen) und die Lösung eines verwandten, regularisierten Problems, das sachgemäß gestellt ist.

Eignung für weitere Verarbeitung: Ist das Modell für automatisierte Lösung geeignet?

Verfügbarkeit/Genauigkeit der Eingabedaten
Implementierungsaufwand: Verfügbarkeit notwendiger Software
erforderlicher Rechen-/Speicheraufwand absolut: NP-vollständige Probleme, Wetter
erforderlicher Rechen-/Speicheraufwand relativ: Ist das Modell kompetitiv?
Empfindlichkeit

Lösungsmöglichkeiten

analytisch: Bei einer analytischen Lösung erfolgen Existenz- und Eindeutigkeitsbeweis sowie Konstruktion direkt. Dies ist das Bestmögliche, denn es muss nichts vereinfacht/approximiert werden, allerdings geht das allermeistens nur in einfachen Spezialfällen.

heuristisch: Bei einer heuristischen Lösung führt man Versuch-und-Irrtum gemäß einer bestimmen Strategie durch, um die optimale Lösung durch eine gute Lösung anzunähern. Das ist vor allem bei Problem der diskreten Optimierung nützlich. Die Frage ist jedoch, ob die heuristisch gefundene Lösung gegen die Optimallösung konvergiert und wenn ja, wie schnell.

direkt-numerisch: Bei einer direkt-numerischen Lösung liefert ein numerischer Algorithmus eine exakte Lösung (mit Rundungsfehler). Der Vorteil gegenüber Heuristiken ist, dass die Lösung in jedem Fall erreicht wird (z. B. Simplex-Algorithmus).

approximativ-numerisch: Bei einer approximativ-numerischen Lösung führt man ein iteratives Näherungsverfahren für genäherte Gleichungen durch. Hier ist das Erreichen einer beliebig genauen Approximation sichergestellt. Allerdings ist die Frage, wie schnell das Verfahren konvergiert (z. B. CG-Verfahren für LGS-Lösungen und Newton-Verfahren für Nullstellen).

Bewertung

Validierung: Stimmt das Modell?

Vergleich mit Experimenten: Windkanal, Laborexperimente an verkleinerten Prototypen
A-posteriori-Beobachtungen: Realitätstest (Wetter, Börse), Zufriedenheitstest (Verkehr)
Plausibilitätstest: Test der Ergebnisse auf Konsistenz zu bestehenden Theorien
Modellvergleich: Vergleich mit auf anderen Modellen basierenden Simulationen

Genauigkeit: Wie präzise ist das Modell?

bzgl. der Qualität der Eingabedaten
bzgl. der Fragestellung (z. B. Bundestagswahl und 5-%-Hürde)
Sicherheit (Aussagen zu Worst-Case oder Average-Case?)

Klassifikation von Modellen

diskret vs. kontinuierlich:

diskret: diskrete/kombinatorische Beschreibung (binäre/ganzzahlige Größen, Graphen)
kontinuierlich: kontinuerliche/reellwertige Beschreibung (reelle Zahlen, physikalische Größen, algebraische Gleichungen, DGLs)

Dasselbe Phänomen kann aber sowohl diskret als auch kontinuierlich modelliert werden (z. B. Verkehrsfluss in der Stadt).

deterministisch vs. stochastisch:

deterministisch (z. B. Crash-Test)
stochastisch (z. B. Würfeln)

Auch hier kann das Phänomen sowohl deterministisch als auch stochastisch modelliert werden. Beispiele sind die Wettervorhersage und die Internet-Paketankunft an einer Bedieneinheit.

Betrachtungsebene/Hierarchie: Selten gibt es „ein korrektes Modell“. Meistens gibt es eine Modellhierarchie (Wechselspiel aus Aufwand und Genauigkeit), die man durch schrittweise Verfeinerung des Modells durchläuft. Welche Auflösung gewählt werden soll, hängt vom gewünschten Resultat und dem erforderlichen Lösungsaufwand ab. Beispiele beinhalten die Strömung durch einen Zylinder (1D/2D/3D?) und die Populationsdynamik (in den USA rein zeitabhängig als \(p(t)\) oder Ost-West-Siederstrom als \(p(x, t)\)?).

Multiskaleneigenschaft: Die auftretenden Skalen können meist nicht ohne einen inakzeptablen Genauigkeitsverlust getrennt werden. Ein Beispiel sind turbulente Strömungen: Hier müssten (abhängig von der Viskosität des Fluids) auch in einem großen Gebiet kleinste Wirbel mitberechnet werden, weil die sich zu größeren Verwirbelungen beitragen können. Abhilfe schaffen Turbulenzmodelle, die feinskalige Einflüsse in grobe Parameter packen und eine Mittelung bzgl. Raum und Zeit durchführen.