Jacobi-Verfahren - Universität Münster

 Documents

 30 views
of 46
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Description
Westfälische Wilhelms-Universität WIRTSCHAFTS Münster INFORMATIK Nummerisches Lösen partieller WIRTSCHAFTSINFORMATIK Differentialgleichungen Im Rahmen des…
Share
Transcript
Westfälische Wilhelms-Universität WIRTSCHAFTS Münster INFORMATIK Nummerisches Lösen partieller WIRTSCHAFTSINFORMATIK Differentialgleichungen Im Rahmen des Seminars „Verteilte und parallele Systeme“ Nial Moore Lehrstuhl für praktische Informatik in der Wirtschaft Prof. Dr. Herbert Kuchen WIRTSCHAFTS Gliederung INFORMATIK 1. Einleitung 2. Differentialgleichungen  Partielle Differentialgleichungen  Diskretisierung 3. Numerische Lösungsverfahren  Direkte Verfahren - Gauß-Elimination  Iterative Verfahren  Jacobi-Verfahren  Gauß-Seidel-Verfahren 4. Zusammenfassung 2 WIRTSCHAFTS Gliederung INFORMATIK 1. Einleitung 2. Differentialgleichungen  Partielle Differentialgleichungen  Diskretisierung 3. Numerische Lösungsverfahren  Direkte Verfahren - Gauß-Elimination  Iterative Verfahren  Jacobi-Verfahren  Gauß-Seidel-Verfahren 4. Zusammenfassung 3 WIRTSCHAFTS Einleitung INFORMATIK  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 - Crashtest Simulation - 3D-CAD Modellierungen 4 WIRTSCHAFTS Einleitung INFORMATIK  Partielle Differentialgleichungen zur werden oft zur Modellierung herangezogen  Modelle sind recht komplex Benötigen Unterstützung durch Rechner 5 WIRTSCHAFTS Gliederung INFORMATIK 1. Einleitung 2. Differentialgleichungen  Partielle Differentialgleichungen  Diskretisierung 3. Numerische Lösungsverfahren  Direkte Verfahren - Gauß-Elimination  Iterative Verfahren  Jacobi-Verfahren  Gauß-Seidel-Verfahren 4. Zusammenfassung 6 WIRTSCHAFTS Partielle Differentialgleichungen INFORMATIK  Differentialgleichungen: - Beschreiben Verhalten realer Systeme - Gesucht: Funktion y, die die Funktion F ( x, y, Dy , D 2 y,..., D n y)  0 für x = (x1,…,xn) G, wobei G  Rn erfüllt, dabei sei Dky die k-te Ableitung der Funktion y - y ist stetig und differenzierbar Bsp.: - Beschreibung einer Flugkurve durch eine Parabel 7 WIRTSCHAFTS Partielle Differentialgleichungen INFORMATIK  Partielle Differentialgleichungen - Mehrdimensional - Von mehreren Variablen abhängig - Komplexe Berechnungen erforderlich - Unterstützung durch Rechner wünschenswert Bsp.: - Modellierung eines Trampolintuchs beim Einsprung  Rechnerunterstützung - Nur bei endlichen Problemen möglich  Deskritisierung nötig 8 WIRTSCHAFTS Gliederung INFORMATIK 1. Einleitung 2. Differentialgleichungen  Partielle Differentialgleichungen  Diskretisierung 3. Numerische Lösungsverfahren  Direkte Verfahren - Gauß-Elimination  Iterative Verfahren  Jacobi-Verfahren  Gauß-Seidel-Verfahren 4. Zusammenfassung 9 WIRTSCHAFTS Diskretisierung INFORMATIK  Bsp.: Temperaturverlauf in einem Metallstab stetiges Modell: diskretes Modell: - Einteilung in endlich viele Intervalle - Informationsverlust entsteht - Anzahl der Intervalle bestimmt Höhe des Informationsverlusts - Intervallanzahl regelt Komplexität der entstehenden linearen Gleichungssysteme (LGS) 10 WIRTSCHAFTS Diskretisierung INFORMATIK  Diskretisierung: - Temperaturen T1 und T2 bekannt - Gesucht sind die Temperaturen x1,…,x4 - Temperaturen x1,…,x4 ergeben sich aus dem Durchschnitt der umgebenden Temperaturen - Entstehendes LGS: +x1 - 0,5x2 = 0,5T1 - 0,5x1 + x2 - 0,5x3 =0 - 0,5x2 + x3 - 0,5x4 =0 - 0,5x3 + x4 = 0,5T2 - Matrixschreibweise Ax = b:  1  0,5 0 0   x1   0,5T1          0,5 1  0 ,5 0   2  x 0  *     0  0,5 1  0,5  x3 0         0  0,5  1   x 4   0,5T2      0 11 WIRTSCHAFTS Gliederung INFORMATIK 1. Einleitung 2. Differentialgleichungen  Partielle Differentialgleichungen  Diskretisierung 3. Numerische Lösungsverfahren  Direkte Verfahren - Gauß-Elimination  Iterative Verfahren  Jacobi-Verfahren  Gauß-Seidel-Verfahren 4. Zusammenfassung 12 WIRTSCHAFTS Numerische Lösungsverfahren INFORMATIK  Bezeichnet Verfahren, die Lösungen ‚zahlenmäßig‘ herbeiführen  Durch Algorithmen automatisierbar Zwei Verfahrenstypen:  Direkte Verfahren - Exakte Lösungen - Z.B. Gauß-Elimination, zyklische Reduktion  Iterative Verfahren - Erzeugen Folgen von Vektoren - Näherung der exakten Lösung - Z.B. Jacobi-Verfahren, Gauß-Seidel-Verfahren 13 WIRTSCHAFTS Gliederung INFORMATIK 1. Einleitung 2. Differentialgleichungen  Partielle Differentialgleichungen  Diskretisierung 3. Numerische Lösungsverfahren  Direkte Verfahren - Gauß-Elimination  Iterative Verfahren  Jacobi-Verfahren  Gauß-Seidel-Verfahren 4. Zusammenfassung 14 WIRTSCHAFTS Gauß-Elimination INFORMATIK Vorgehen ausgehend von dem LGS der Form Ax = b:  1  0,5 0 0   x1   0,5T1          0,5 1  0,5 0   x2   0  *   0  0,5 1  0,5   x3   0         0  0,5 1   x4   0,5T2   0  Schritt 1: LGS transformieren, so dass Matrix A die Form einer oberen Dreieckmatrix A annimmt Ax  b  Ax  b Bsp.:  1  0,5 0 0   x1   0,5T1   1  0,5 0 0   x1   0,5T1                   2       2    0,5 1 0 ,5 0 x 0 0 0,75 0 ,5 0 x 0 , 25T *    *    1  0  0,5 1  0,5  x3 0  0 0 0, 6  0,5  x3 0,1 6T1               0  0,5  1   x 4   0,5T2     0  0,625   x4   0,5T2  0,125T1      0  0 0 15 WIRTSCHAFTS Gauß-Elimination INFORMATIK  Transformation benötigt n-1 Schritte  In jedem Schritt k: A( k 1) und b ( k 1) aus A(k ) und b ( k ) errechnen: - Eliminationsfaktoren l berechnen: aik( k ) lik  ( k ) , i  k  1,..., n (k ) akk - Matrix A(k+1) und Vektor b(k+1) neu berechnen: ( k 1) (k ) (k ) a  a  l * a ij ij ik kj ( k 1)  bi  l ik * bk (k ) (k ) b i 16 WIRTSCHAFTS Gauß-Elimination INFORMATIK  Schritt 2: Durch Rückwärtseinsetzen LGS lösen Bsp.:  1  0,5 0 0   x1   0,5T1  1 0 0 0   x1   0,8T1  0,2T2               0 0,75  0,5 0   x2   0,25T1  0 1 0 0   x2   0,6T1  0,4T2  0 0 *  0, 6  0,5   x3   0,1 6T1   0 *  0 1 0   x3   0,4T1  0,6T2              0   x   0,5T  0,125T  0 0 0 1   x4   0,2T1  0,8T2   0 0 0,625   4  2 1  Rechenvorschrift: 1  (n) n  xk  ( n )  bk   akj x j , k  n, n  1,...,1 (n) akk  j  k 1  17 WIRTSCHAFTS Gauß-Elimination INFORMATIK  Problem: - Sollte ein Element der Hauptdiagonalen der Matrix A Null sein bricht der Algorithmus ab (Division durch Null ) Partielle Pivotisierung Erfordert mehr Kommunikation/Rechenaufwand i i+1 n Koeffizienten, die sich nicht verändern Pivot-Zeile i i i+1 Koeffizienten, die bereits Koeffizienten, die sich verändern den Wert Null haben werden n Koeffizienten, die den Wert Null erhalten sollen 18 WIRTSCHAFTS Gauß-Elimination INFORMATIK  Sequentielle Implementierung: - 3 ineinander geschachtelte Schleifen  Θ(n3)  Parallele Implementierung: - Erfordert wesentlich mehr Kommunikation - Geringer ‚speed-up‘  a11 a12  a1,k 1 a1k  a1n     0 a22  a2,k 1 a2 k  a2 n            A     ak 1,k 1 ak 1,k  ak 1,n    0 akk  akn             0   0 0  ann  19 WIRTSCHAFTS Gauß-Elimination INFORMATIK  Vorteile: - Vorhersagbarkeit der Laufzeit - Vorhersagbarkeit des Speicherbedarfs - exakte Lösung (sofern vorhanden) - Auf jedes LGS anwendbar  Nachteile: - Schlecht parallelisierbar - Bei dünnbesetzten Matrizen entsteht ‚fill-in‘ 20 WIRTSCHAFTS Gliederung INFORMATIK 1. Einleitung 2. Differentialgleichungen  Partielle Differentialgleichungen  Diskretisierung 3. Numerische Lösungsverfahren  Direkte Verfahren - Gauß-Elimination  Iterative Verfahren  Jacobi-Verfahren  Gauß-Seidel-Verfahren 4. Zusammenfassung 21 WIRTSCHAFTS Iterative Verfahren INFORMATIK  Liefern nur Näherungen  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 22 WIRTSCHAFTS Gliederung INFORMATIK 1. Einleitung 2. Differentialgleichungen  Partielle Differentialgleichungen  Diskretisierung 3. Numerische Lösungsverfahren  Direkte Verfahren - Gauß-Elimination  Iterative Verfahren  Jacobi-Verfahren  Gauß-Seidel-Verfahren 4. Zusammenfassung 23 WIRTSCHAFTS Jacobi-Verfahren INFORMATIK  Idee: - Sind alle x , j  i  j, i  1,..., n bekannt, kann x durch Einsetzen der j i xj errechnet werden 1   xi   bi   aij x j  , i = 1,…,n , j = 1,…,n aii  j i    Problem: - Die x sind nicht bekannt j  Iterativer Ansatz: - Beliebigen Startvektor als vorläufiges Ergebnis betrachten ( k 1) - Vorläufige Ergebnisse x der Iteration k zur Errechnung neuer x (k ) j i einsetzen - Iterationsvorschrift: 1   , i = 1,…,n , j = 1,…,n , k = 1,2,… x ( k 1) i   bi   aij x j  (k ) aii  j i  24 WIRTSCHAFTS Jacobi-Verfahren INFORMATIK  Abbruchkriterium: - Anzahl an Iterationen - Abbruch ohne Ergebnis - Lösung ist hinreichend genau: Abbruchkriterium: relativer Fehler x ( k 1)  x ( k )   x ( k 1) ||.|| 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 25 WIRTSCHAFTS Jacobi-Verfahren INFORMATIK  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: A b x(k+1) P0 x(k+1) 0 1 2 x(0) 3 Abbruch Ausgabe P1 4 testen 5 6 7 Multibroadcastoperation Initialisierung Iteration k 26 WIRTSCHAFTS Jacobi-Verfahren INFORMATIK  1. Schritt: Jeder Prozessor Pi hat alle benötigten Daten aus der Approximation x(k) vorliegen und errechnet der Iterationsvorschrift die nächste Aproximation x(k+1) seiner n/p Elemente. A b x(k+1) P0 x(k+1) 0 1 2 x(0) 3 Abbruch Ausgabe P1 4 testen 5 6 7 Multibroadcastoperation Initialisierung Iteration k 27 WIRTSCHAFTS Jacobi-Verfahren INFORMATIK  2. Schritt: Jeder Prozessor sendet seine n/p lokal gespeicherten Elemente des Vektors x(k+1) z.B. mit einer Multibroadcastoperation an die übrigen Prozessoren A b x(k+1) P0 x(k+1) 0 1 2 x(0) 3 Abbruch Ausgabe P1 4 testen 5 6 7 Multibroadcastoperation Initialisierung Iteration k 28 WIRTSCHAFTS Jacobi-Verfahren INFORMATIK  3. Schritt: Abbruchkriterien überprüfen, ggf. Ergebnis ausgeben A b x(k+1) P0 x(k+1) 0 1 2 x(0) 3 Abbruch Ausgabe P1 4 testen 5 6 7 Multibroadcastoperation Initialisierung Iteration k 29 WIRTSCHAFTS Jacobi-Verfahren INFORMATIK  Aufwand einer Iteration: - Schritt 1: n/p Werte werden in quadratischer Zeit errechnet  Θ(n2 * (n/p)) - Schritt 2: n/p Werte an p-1 Prozessoren verschicken  Θ((p-1) * (n/p)) - Schritt 3: Ist abhängig vom Abbruchkriterium, z.B. Θ(n), wenn das globale Maximum verglichen wird 30 WIRTSCHAFTS Jacobi-Verfahren INFORMATIK  Aufwand des Algorithmus: - (Aufwand einer Iteration) * (Iterationsdurchläufe) - Anzahl der Iterationsdurchläufe abhängig vom Gleichungssystem und der Konvergenzrate - Jacobi-Verfahren hat relativ schlechte Konvergenzrate 31 WIRTSCHAFTS Gliederung INFORMATIK 1. Einleitung 2. Differentialgleichungen  Partielle Differentialgleichungen  Diskretisierung 3. Numerische Lösungsverfahren  Direkte Verfahren - Gauß-Elimination  Iterative Verfahren  Jacobi-Verfahren  Gauß-Seidel-Verfahren 4. Zusammenfassung 32 WIRTSCHAFTS Gauß-Seidel-Verfahren INFORMATIK  Iteratives Verfahren  Gleicher Ansatz wie Jacobi, jedoch: - Innerhalb einer Iteration wird auf die bereits errechneten Werte zurückgegriffen - Dadurch entsteht folgende Iterationsvorschrift 1  i 1 n  x ( k 1)   bi   aij x (jk 1)  a x (k )  i  ij j  aii  j 1 j i 1  xi von Iteration k+1 xi von Iteration k - Deutlich bessere 1  ( k 1Konvergenzrate als  ( k ) das Jacobi-Verfahren xi )   bi   aij x j   - Aber es entstehen Datenabhängigkeiten aii  j i  33 WIRTSCHAFTS Gauß-Seidel-Verfahren INFORMATIK  Datenabhängigkeiten  a11 a12 a13 a14     a21 a22 a23 a24  A a31 a32 a33 a34    a a44   41 a42 a43 1  i 1 n  x ( k 1)   bi   aij x (jk 1)  a x (k )  i  ij j  aii  j 1 j i 1  34 WIRTSCHAFTS Gauß-Seidel-Verfahren INFORMATIK  Gute Anwendbarkeit bei dünnbesetzten Matrizen  Oft bei Modellen die einer Gitterstruktur entsprechen  Bsp.: Temperaturverlauf im Wasserbad xi,j-1 xi-1,j xij xi+1,j xi,j+1 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 35 WIRTSCHAFTS Gauß-Seidel-Verfahren INFORMATIK  Bei einem 4x4 Gitter ergibt sich folgendes Bild: a) 4x4 Gitter b) schematische Darstellung der Matrix A x x x 1 2 3 4 x x x x x x x x x x x x x x x 5 6 7 8 x x x x x x x x x x x x x x x x x x x x x x x 9 10 11 12 x x x x x x x x x x x x x x x x 13 14 15 16 x x x x x x x  Relative viele Datenabhängigkeiten  Durch Rot-Schwarz-Schema in der Berechnung reduzierbar 36 WIRTSCHAFTS Gauß-Seidel-Verfahren INFORMATIK  Rot-Schwarz-Schema: - 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: a) 4x4 Gitter in rot- b) schematische Darstellung der schwarz Anordnung Matrix A´ x x x 1 9 2 10 x x x x x x x x x x x x x x x x x 11 3 12 4 x x x x x x x x x x x x x x x x x x x 5 13 6 14 x x x x x x x x x x x x x x x x x x 15 7 16 8 x x x x x x x 37 WIRTSCHAFTS Gauß-Seidel-Verfahren INFORMATIK  Nach der Umordnung: ˆA * xˆ   DR F   xˆ R   bˆ1   E  *       DS   xˆ S   bˆ2   Damit ergibt sich der Iterationsschritt:  DR 0   xR( k 1)   b1   0 F   xR( k )    *  ( k 1)        *  ( k )  E DS   xS   b2   0 0   xS   In Vektorschreibweise: ( k 1) Somit ist x R( k 1) nur noch von x S und x S nur noch (k ) DR * x R( k 1)  b1  F * x S( k ) ( k 1) von x R abhängig. - Erst x R( k 1) ausrechnen, dann x S( k 1) DS * x S( k 1)  b2  E * x R( k 1) - x R( k 1) und x S( k 1) sind unabhängig und können daher parallel ausgeführt werden 38 WIRTSCHAFTS Gauß-Seidel-Verfahren INFORMATIK  Algorithmus: 1. Schritt: Berechne x auf parallelen Prozessoren ( k 1) R 2. Schritt: Mit Multibroadcast-Operation Ergebnisse kommunizieren ( k 1) 3. Schritt: Berechne x auf parallelen Prozessoren S 4. Schritt: Mit Multibroadcast-Operation Ergebnisse kommunizieren 5. Schritt: Abbruchkriterium überprüfen ( k 1) 6. Schritt: Vektor x und x zu gemeinsamen Ergebnisvektor R ( k 1) S zusammenführen  Aufwand des Rot-Schwarz-Schemas: - Berechnungsaufwand fast identisch mit dem Jacobi-Verfahren - Eine Mulitbroadcast-Operation mehr - Nicht so gut parallelisierbar wie Jacobi - Zusätzlicher Aufwand wird jedoch durch bessere Konvergenzrate kompensiert 39 WIRTSCHAFTS Gliederung INFORMATIK 1. Einleitung 2. Differentialgleichungen  Partielle Differentialgleichungen  Diskretisierung 3. Numerische Lösungsverfahren  Direkte Verfahren - Gauß-Elimination  Iterative Verfahren  Jacobi-Verfahren  Gauß-Seidel-Verfahren 4. Zusammenfassung 40 WIRTSCHAFTS Zusammenfassung INFORMATIK  Differentialgleichungen - Können oft zur mathematischen Modellierung herangezogen werden - Sind stetig - Müssen diskretisiert werden, um numerisch gelöst zu werden  Diskretisierung - Beschreibt den Vorgang ein stetiges Problem in ein diskretes umzuwandeln - Erzeugt lineare Gleichungssysteme, die numerisch lösbar sind 41 WIRTSCHAFTS Zusammenfassung INFORMATIK Numerische Lösungsverfahren:  Gaus-Eliminations-Verfahren: - Direktes Verfahren - Exakte Lösung wird errechnet - Vorhersagbare Rechenzeit - Vorhersagbarer Speicherbedarf - Auf alle linearen Gleichungssystemen anwendbar - Fill-in kann auftreten - Schlechte Parallelisierbarkeit 42 WIRTSCHAFTS Zusammenfassung INFORMATIK Numerische Lösungsverfahren:  Jacobi-Verfahren: - Iteratives Verfahren - Kein fill-in - Für dünnbesetzte Matrizen gut geeignet - Rechenzeit nicht vorhersagbar - Laufzeit abhängig von der Komplexität des Gleichungssystem - Schlechte Konvergenzrate 43 WIRTSCHAFTS Zusammenfassung INFORMATIK Numerische Lösungsverfahren:  Gauß-Seidel-Verfahren: - Iteratives Verfahren - Kein fill-in - Datenabhängigkeiten innerhalb einer Iteration - Nicht so gut parallelisierbar - Für dünnbesetzte Matrizen in Bandstruktur gut geeignet - Rechenzeit nicht vorhersagbar - Laufzeit abhängig von der Komplexität des Gleichungssystem - bessere Konvergenzrate als Jacobi-Verfahren 44 WIRTSCHAFTS Literatur INFORMATIK  Michael J. Quinn: Parallel Computing, Theory and Practice, 2nd ed., McGraw-Hill, 1994  Thomas Rauber, Gudula Rünger: Parallele Programmierung, 2. Aufl., Springer, 2007.  Hartmut Schwandt: Parallele Numerik, Eine Einführung, 1. Aufl., Teubner 2003 45 WIRTSCHAFTS INFORMATIK Vielen dank für Ihre Aufmerksamkeit und ein erholsames Wochenende! 46
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks