Advent, Advent, 1 Monat weihnachtliche Laufzeit geschenkt.

Nicht bis zur Bescherung warten, Aktion nur gültig bis zum 18.12.2016!

Textversion des Videos

Transkript Gauß-Seidel Verfahren

Hallo, hier ist Christof mit seinem zweiten Video über iterative Verfahren zur Lösung von linearen Gleichungssystemen. In diesem Video gucken wir das Einzelschrittverfahren, auch Gauß-Seidel-Verfahren genannt, an. Wir werden dabei die Unterschiede zum Gesamtschrittverfahren sehen. Die Ausgangssituation ist genau die gleiche wie beim Gesamtschrittverfahren. Wir haben ein lineares Gleichungssystem Ax=b gegeben und einen Startvektor x(0). Außerdem wurde uns gesagt, wie viele Iterationsschritte wir machen sollen. Gesucht ist nun wieder eine Näherung der Lösung x, die dieses Mal allerdings durch das Einzelschrittverfahren berechnet werden soll. Wir haben auch hier eine Formel gegeben, um die i-te Komponente von x im k+1-ten Iterationsschritt zu berechnen. Diese Formel unterscheidet sich schon optisch von der Formel des Gesamtschrittverfahrens dadurch, dass wir hier zwei Summen haben statt einer. Nehmen wir uns wieder dasselbe Beispiel her wie im letzten Video. Wir haben ein lineares Gleichungssystem mit der Matrix A und dem Vektor b gegeben, einen Starvektor x(0) und sollen nun zwei Iterationsschritte berechnen, also x(2) berechnen. Anfangen tun wir natürlich mit dem ersten Iterationsschritt, in dem wir x(1) berechnen. Laut unserer Formel berechnen wir ja immer x(k+1). Also ist k in diesem Fall 0. Wir beginnen mit der ersten Komponente von x(1), also x1(1). Dafür setzen wir i=1 in die Formel ein. Wenn wir das tun, fällt die erste Summe weg, denn i-1 ist hier 0, und somit kleiner als der Startwert j=1. Wir erhalten die Formel: 1/a11(b1-(a12×x2(0)+a13×x3(0)+a14×x4(0)). Unser Startvektor x(0) war der Nullvektor, seine Komponenten sind also alle 0. Dadurch fallen in unserer Formel alle Terme mit einem x weg, und wir erhalten für x1(1)=5,5. Für x2(1) müssen wir i=2 in unsere Formel einsetzen. Die linke Summe geht nun von j=1 bis 1, muss also für j=1 ausgewertet werden. Dort erhalten wir also a21×x1(1). Dies ist die erste Komponente unseres Vektors x(1), die wir eben schon berechnet haben. Der Rest bleibt wie gehabt.Wir sehen also, dass wir zur Berechnung einer Komponenten des Vektors x die bereits vorher berechneten Komponenten desselben Iterationsschrittes sofort verwenden. Beim Gesamtschrittverfahren hingegen haben wir immer nur die Komponenten des vorherigen Iterationsschrittes benutzt. Genauso benutzen wir jetzt bei der Berechnung der dritten Komponente des Vektors x die beiden schon gefundenen Komponenten x1 und x2 aus diesem Iterationsschritt. Nur für x4 müssen wir natürlich x4(0) benutzen, da wir x4(1), also x4 nach dem ersten Iterationsschritt noch gar nicht berechnet haben. Bei der Berechnung von x4(1) können wir nun alle drei schon gefundenen Komponenten des Vektors x(1) benutzen. Wir brauchen also keine einzige Komponente des Startvektors mehr. Kommen wir nun zum 2. Iterationsschritt. Hier berechnen wir x(2), also ist k=1. Für i=1 fällt die linke Summe wieder weg. Wir berechnen uns x1(2) also ausschließlich aus den Komponenten des Vektors x(1). Für x2(2) benutzen wir die gerade berechnete Komponente x1 des zweiten Iterationsschrittes und für die Komponente x3 und x4 nehmen wir die aus dem ersten Iterationsschritt. Analog verwenden wir für x3 die gerade berechneten neuen Komponenten x1 und x2, und für x4 die alte Komponente, also die aus dem ersten Iterationsschritt. Für i=4 fällt in der Formel die rechte Summe weg. Somit benutzen wir nur neue Komponenten des Vektors x(2).Wie schon beim Gesamtschrittverfahren wollen wir auch hier die gefundenen Näherungslösungen mit den exakten Lösungen vergleichen. Zur Erinnerung, die exakte Lösung war x=(1; 2; 3; 4). Wir sehen hier, dass sich unsere Näherungslösung mit jedem Iterationsschritt weiter von der exakten Lösung entfernt, also schlechter wird. Wir können also auch hier davon ausgehen, dass dieses Verfahren in diesem Fall gar nicht gegen die reale Lösung konvergiert. Auf die Konvergenz des Einzelschrittverfahrens möchte ich an dieser Stelle aber nicht weiter eingehen. Ich habe ein weiteres Video gemacht, in dem die Konvergenzkriterien für alle Iterationsverfahren dargestellt werden. Als Zusammenfassung dessen, was wir in diesem Video gelernt haben, möchte ich noch mal auf die Unterschiede des Gesamtschrittverfahrens zum Einzelschrittverfahren eingehen. An den Formeln sehen wir, dass wir im Gesamtschrittverfahren nur eine Summe haben, im Einzelschrittverfahren jedoch zwei Summen. Da aber im Gesamtschrittverfahren in der Summe aber j?i gilt, kann diese Summe auch in zwei Summen aufgeteilt werden, einmal für j=1 bis i-1 und einmal von j=i+1 bis n. Dann hätten wir hier die gleichen Formeln wie beim Einzelschrittverfahren, mit dem einzigen Unterschied, dass im Bereich von j=1 bis i-1 xj(k) statt xj(k+1) benutzt wird. Beim Gesamtschrittverfahren benutzen wir in diesem Bereich also die Lösungen, die wir im letzten Iterationsschritt für x gefunden haben. Im Einzelschrittverfahren hingegen verwenden wir schon die neuen Lösungen des aktuellen Iterationsschrittes.Dies wollen wir uns noch einmal grafisch veranschaulichen. Gehen wir beispielsweise davon aus, dass wir in einem k+1-ten Iterationsschritt die dritte Komponente eines Vektors, also x3, berechnen wollen. Beim Gesamtschrittverfahren benutzen wir dafür nur den Vektor x(k), also den des letzten Iterationsschrittes und multiplizieren seine Komponenten mit den Komponenten der Zeile aus A. Beim Einzelschrittverfahren dagegen benutzen wir sowohl den Vektor des letzten Iterationsschrittes x(k) als auch die Komponenten, die wir schon von dem aktuellen Iterationsschritt  x(k+1) gefunden haben, also x(1) und x(2). Dafür multiplizieren wir die Elemente aus der Matrix A, die links von der Hauptdiagonale sind, mit unseren neuen Werten aus dem Vektor x(k+1) und die, die rechts davon sind, in diesem Fall a34, mit dem alten x4(k).Wenn ihr das so weit verstanden habt, könnt ihr euch nun das nächste Video zum SOR-Verfahren angucken. Dies ist eine Verallgemeinerung des Einzelschrittverfahrens. Bis dahin, ciao, euer Christof

Informationen zum Video