Textversion des Videos

Transkript SOR-Verfahren Young Verfahren

Hallo, hier ist Christoph und in diesem Video möchte ich euch das 3. iterative Verfahren zur Lösung linearer Gleichungssysteme vorstellen. Dieses Verfahren heißt SOR-Verfahren oder auch Young-Verfahren. Es stellt eine Verallgemeinerung des Einzelschrittverfahrens, das wir im letzten Video kennengelernt haben, dar. Als Grundlage für dieses Video solltet ihr euch also das Einzelschrittverfahren angeguckt und verstanden haben. Gegeben ist wieder mit Ax=b ein lineares Gleichungssystem sowie ein Startvektor x0. Außerdem wissen wir wieder, wie viele Iterationsschritte wir machen sollen. Dieses Mal haben wir haben wir allerdings noch eine zusätzliche Variable gegeben: ω. In den meisten Anwendungen ist ω eine Zahl zwischen 1 und 2. Für ω=1 ergibt sich das Einzelschrittverfahren, das wir vorhin kennengelernt haben. Wie auch in den anderen Verfahren haben wir hier eine Formel gegeben, um xik+1 zu berechnen. Zunächst erinnern wir uns jedoch einmal an die Formel des Einzelschrittverfahrens. Ausgehend von dieser Formel kommen wir zu der Formel des SOR-Verfahrens, indem wir mit ω multiplizieren und anschließend 1-ω×xik addieren. Für ω=1 wird die Klammer (1-ω)=0 und dadurch erhalten wir, wie schon angedeutet, genau die Formel für das Einzelschrittverfahren wieder. Gucken wir uns dazu nun ein Beispiel an. Wir nehmen wieder das gleiche lineare Gleichungssystem und denselben Startvektor x0 wie in den beiden anderen Videos. Für ω=1 würden wir nun also genau das Einzelschrittverfahren erhalten, das wir in dem anderen Video gerechnet haben. Hier rechnen wir jetzt allerdings einmal mit ω=1,5. Berechnen wir also zunächst x11. Wir erhalten den Summanden (1-ω)×x10 im Gegensatz zum Einzelschrittverfahren. Außerdem gab es den Faktor ω beim Einzelschrittverfahren nicht. Der restliche Teil, insbesondere die Summe hinten, ist jedoch genauso wie beim Einzelschrittverfahren. Die Berechnung ist in unserem Beispiel wieder besonders einfach, da alle Komponenten des Startvektors 0 sind. Berechnen wir nun unsere 2. Komponente x2, sehen wir, dass sich der hintere Teil im Gegensatz zu x1 so ändert, wie im Einzelschrittverfahren. Im vorderen Teil steht nun statt x10 x20. Da diese Berechnungen nicht besonders schwierig sind, wenn man das Einzelschrittverfahren verstanden hatte, werde ich nun nur noch die Ergebnisse anschreiben und nicht weiter kommentieren. Die Ergebnisse brauchen wir gleich noch. Wir belassen es jetzt auch bei der Berechnung dieses 1. Iterationsschrittes, da ihr das Prinzip inzwischen hoffentlich verstanden habt. Wir kommen lieber zu einer weiteren wichtigen Sache beim SOR-Verfahren, der Sassenfeldzahl β(ω). Wir schreiben β(ω), da diese Sassenfeldzahl davon abhängt, welches ω wir gewählt haben. Zur Bestimmung der Sassenfeldzahl müssen wir zunächst β1(ω) bis βn(ω) berechnen. Die Formel für βi(ω) lautet dabei βi(ω)=Betrag von 1-ω+ω/Betrag von aii×Summe über Betrag von aij×βj(ω) (dabei geht j von 1 bis i-1)+Summe über Betrag von aij (wobei j hier von i+1 bis n geht). Diese Formel ist ähnlich aufgebaut, wie die Formel, die wir vorhin für die xi benutzt haben. Auch hier fällt die 1. Summe weg, wenn i=1 ist. Wir erhalten für β1 also: Betrag von 1-ω+ω/Betrag von a11×Betrag von a12+Betrag von a13+Betrag von a14. Wenn i=2 ist, wir also β2 berechnen, müssen wir die linke Summe für j=1 auswerten. Der Unterschied zwischen der linken und der rechten Summe besteht nur darin, dass in der linken Summe noch mit βj multipliziert wird. Wir müssen hier Betrag von a21, also mit dem eben schon gefundenen β1 multiplizieren. Wir können uns das so vorstellen, dass wir für j=1 bis i-1 mit βj multiplizieren können, da wir diese β schon berechnet haben. Für j=i+1 bis n haben wir diese noch nicht berechnet. Analog dazu können wir bei der Berechnung von β3 β1 und β2 schon benutzen und bei der Berechnung von β4 β1 bis β3.  Wir haben nund also β1 bis β4 berechnet. Die Sassenfeldzahl ist definiert als das Maximum der Beträge dieser βi(ω). Hier war die größte unserer βi-Zahlen die 4., β4. Daher ist unsere Sassenfeldzahl β(1,5)=205,5875 Falls ihr euch die ganze Zeit schon gefragt habt, warum wir diese Sassenfeldzahl β überhaupt berechnen, kommt hier die Antwort: Mithilfe der Sassenfeldzahl können wir eine Fehlerabschätzung durchführen. Bei einer Fehlerabschätzung geht es darum, abzuschätzen, wie groß unsere Näherungslösung maximal von der exakten Lösung noch entfernt ist. Dabei gibt es 2 Arten der Fehlerabschätzungen: Die 1. ist die A-priori-Fehlerabschätzung. Hier schätzen wir schon nach dem 1. Iterationsschritt ab, wie groß unser Fehler nach dem k. Iterationsschritt maximal sein wird. x-xk ist der Differenzvektor zwischen der realen Lösung x und unserer Näherungslösung xk. Die Doppelstriche mit dem Unendlichzeichen stehen hier für die Unendlichnorm. Die Unendlichnorm ist der betragsmäßig größte Wert eines Vektors. Die Unendlichnorm von x-xk ist also unser Fehler und diesen können wir abschätzen durch: (βk(ω))/(1-β(ω))×//x1-x0//∞ Also der Differenz des Vektors x nach dem 1. Iterationsschritt minus dem Startvektor x0. Die 2. Fehlerabschätzung ist die A-posteriori-Fehlerabschätzung. Hier schätzen wir den Fehler nach dem k. Iterationsschritt auch wirklich nach dem k. Iterationsschritt erst ab. Diese Abschätzung erfolgt durch β durch 1-β×unsere aktuelle Näherungslösung xk minus der Näherungslösung aus dem vorangegangenen Iterationsschritt x(^(k-1) in der Unendlichnorm. Da wir ja in unserem Beispiel den 1. Iterationsschritt berechnet hatten, können wir einmal eine A-priori-Fehlerabschätzung dafür machen. Das Einsetzen der Sassenfeldzahl und der Differenz zwischen x1 und x0 ergibt die folgende Ungleichung für unseren Fehler. Die Unendlichnorm eines Vektors ist, wie gesagt, die betragsmäßig größte Komponente dieses Vektors. In unserem Fall also 115,35. Im Zähler unserer Gleichung steht 205,5875k. Mit jedem weiteren Iterationsschritt, wenn k also um 1 größer wird, ver205facht sich also unser maximal möglicher Fehler. Unser eigentliches Ziel war bisher, mit jedem Iterationsschritt weiter an die exakte Lösung heranzukommen. Unsere Fehlerabschätzung zeigt uns aber, dass wir uns evtl. sogar immer weiter davon entfernen können. Wie wir an der Formel bzw. dem βk in der Formel sehen können, wird unser Fehler mit jedem Iterationsschritt kleiner, wenn unsere Sassenfeldzahl <1 ist. Nur dann können wir also sagen, dass das Verfahren konvergiert. Weitere Konvergenzkriterien werde ich in meinem nächsten Video erläutern, nicht nur zum SOR-Verfahren, sondern auch zum Einzelschritt- und Gesamtschrittverfahren. Bis dahin, euer Christoph. Tschüssi.

Informationen zum Video