of 46/46
WIRTSCHAFTSINFORMATIK Westfälische Wilhelms- Universität Münster WIRTSCHAFTS INFORMATIK Nummerisches Lösen Nummerisches Lösen partieller partieller Differentialgleichungen Differentialgleichungen Im Rahmen des Seminars „Verteilte und parallele Systeme“ Lehrstuhl für praktische Informatik in der Wirtschaft Prof. Dr. Herbert Kuchen Nial Moore

Nummerisches Lösen partieller Differentialgleichungen

  • View
    30

  • Download
    0

Embed Size (px)

DESCRIPTION

Nummerisches Lösen partieller Differentialgleichungen. Im Rahmen des Seminars „Verteilte und parallele Systeme“. Nial Moore. Lehrstuhl für praktische Informatik in der Wirtschaft Prof. Dr. Herbert Kuchen. Gliederung. Einleitung Differentialgleichungen Partielle Differentialgleichungen - PowerPoint PPT Presentation

Text of Nummerisches Lösen partieller Differentialgleichungen

Nummerisches Lösen partieller DifferentialgleichungenLehrstuhl für praktische Informatik in der Wirtschaft
Prof. Dr. Herbert Kuchen
*
*
Viele Problemstellungen in FuE lassen mit Hilfe von Simulationen lösen
Beschreibung realer Systeme durch mathematische Modelle
Mathematischen Modelle ermöglichen Simulationen von Zuständen / Ergebnissen
Beispiele:
Klimasimulation
Simulationen:
zerstörend
Modelle sind recht komplex
Benötigen Unterstützung durch Rechner
*
*
erfüllt, dabei sei Dky die k-te Ableitung der Funktion y
y ist stetig und differenzierbar
Bsp.:
Rechnerunterstützung
Deskritisierung nötig
stetiges Modell:
diskretes Modell:
Informationsverlust entsteht
*
Temperaturen x1,…,x4 ergeben sich aus dem Durchschnitt der umgebenden Temperaturen
Entstehendes LGS:
Durch Algorithmen automatisierbar
Vorgehen ausgehend von dem LGS der Form Ax = b:
Schritt 1: LGS transformieren, so dass Matrix A die Form einer oberen Dreieckmatrix annimmt
Bsp.:
*
Bsp.:
Rechenvorschrift:
Gauß-Elimination
Problem:
Sollte ein Element der Hauptdiagonalen der Matrix A Null sein bricht der Algorithmus ab (Division durch Null )
Partielle Pivotisierung
Koeffizienten, die den Wert Null erhalten sollen
Koeffizienten, die bereits den Wert Null haben
Pivot-Zeile i
Parallele Implementierung:
*
Aufbauend auf bereits errechnete Näherungen werden weitere Approximationen errechnet
Verfahren erzeugen Folgen von Vektoren {x(k)}k=1,2,…die gegen die gesuchte Lösung x* konvergieren.
Aufwand der Algorithmen nicht ausschließlich abhängig von der Größe des Systems
Für dünnbesetzte Matrizen gut geeignet
*
, i = 1,…,n , j = 1,…,n
Vorläufige Ergebnisse der Iteration k zur Errechnung neuer einsetzen
Iterationsvorschrift:
*
Lösung ist hinreichend genau:
Abbruchkriterium: relativer Fehler
||.|| Vektornorm, z.B. ||x|| = max i=1,...,n|xi| oder ||x||2=(n i=1|x|2)½ .
Eigenschaften in Hinblick auf Parallelisierbarkeit
Berechnung der einzelnen xi nur von vorherigen Iteration abhängig
Keine Datenabhängigkeiten innerhalb einer Iteration
Leicht parallelisierbar
Parallel Implementierung:
Prozessor Pi mit i = 1,…,p speichert n/p Zeilen von A und die dazu gehörigen Werte von b
Möglichkeit Vektor x entweder lokal als auch global gespeichert
Iterationsablauf:
1. Schritt:

2. Schritt:


Schritt 2:
Schritt 3:
*
Jacobi-Verfahren hat relativ schlechte Konvergenzrate
*
Innerhalb einer Iteration wird auf die bereits errechneten Werte zurückgegriffen
Dadurch entsteht folgende Iterationsvorschrift
Aber es entstehen Datenabhängigkeiten
Oft bei Modellen die einer Gitterstruktur entsprechen
Gauß-Seidel-Verfahren
Bsp.: Temperaturverlauf im Wasserbad
Der Punkt xi,j ist nur von den ihn umgebenden Punkten abhängig:
xi,j = (xi-1,j + xi+1,j + xi,j-1 + xi,j+1)/4
xi,j-1
xij
xi-1,j
Relative viele Datenabhängigkeiten
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
*
1. 16 Punkte in rote und schwarze Punkte aufteilen
2. Punkte so im Gitter angeordnet, dass alle roten Punkte nur schwarze Nachbarn haben und umgekehrt
Damit ergibt sich folgende Umordnung:
1
9
2
10
11
3
12
4
5
13
6
14
15
7
16
8
b) schematische Darstellung der Matrix A´
*
In Vektorschreibweise:
Somit ist nur noch von und nur noch von abhängig.
- Erst ausrechnen, dann
Gauß-Seidel-Verfahren
Schritt: Abbruchkriterium überprüfen
Aufwand des Rot-Schwarz-Schemas:
Eine Mulitbroadcast-Operation mehr
Zusätzlicher Aufwand wird jedoch durch bessere Konvergenzrate kompensiert
*
Sind stetig
Diskretisierung
Beschreibt den Vorgang ein stetiges Problem in ein diskretes umzuwandeln
Erzeugt lineare Gleichungssysteme, die numerisch lösbar sind
*
Fill-in kann auftreten
Rechenzeit nicht vorhersagbar
Schlechte Konvergenzrate
Rechenzeit nicht vorhersagbar
bessere Konvergenzrate als Jacobi-Verfahren
Literatur
Michael J. Quinn: Parallel Computing, Theory and Practice, 2nd ed., McGraw-Hill, 1994
Thomas Rauber, Gudula Rünger: Parallele Programmierung, 2. Aufl., Springer, 2007.
*
0
Koeffizienten, die bereits
schwarz Anordnung