Advent, Advent, 1 Monat weihnachtliche Laufzeit geschenkt.

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

Jacobi-Verfahren 10:39 min

Textversion des Videos

Transkript Jacobi-Verfahren

Hallo, ich bin Christoph, und ihr seht gerade den ersten Teil einer Videoreihe zu iterativen Verfahren zur Lösung linearer Gleichungssysteme und deren Konvergenz. In diesem Video werden wir uns ausschließlich mit dem Gesamtschrittverfahren auseinandersetzen, das gelegentlich auch Jacobi-Verfahren genannt wird. Bei diesen iterativen Verfahren haben wir immer ein Gleichungssystem Ax=b und einen Startvektor x0, der eine Näherungslösung für die exakte Lösung x darstellt. Aus diesem Vektor x0 berechnen wir nun eine neue Näherungslösung für x, die besser ist als unser Startvektor. Dieses Verfahren können wir dann beliebig oft wiederholen, sodass sich unsere Näherungslösung immer mehr der realen Lösung x annähert. Die Aufgabenstellung lautet nun also, eine Näherung der exakten Lösung x zu berechnen, und zwar mit Hilfe des Gesamtschrittverfahrens. Dazu haben wir eine Formel gegeben, die auf den ersten Blick wieder furchtbar kompliziert aussieht. Sie lautet: xi(K+1)=(1/aii)×(bi-(∑((aij)×((xj)(K)) für j von 1 bis n,j≠i). Ein paar Worte zur Notation. x hat hier 2 Indices, einen unten und einen eingeklammerten oben. Der Index oben sagt uns an, nach dem wievielten Iterationsschritt wir uns gerade befinden, also im wievielten Iterationsschritt dieses x berechnet wurde. Der Index unten gibt uns an, die wievielte Komponente des Vektors i wir betrachten. Kommen wir nun gleich zu einem Beispiel. Gegeben haben wir eine quadratische Matrix A und einen Vektor b, diese bilden zusammen das Gleichungssystem Ax=b. Außerdem haben wir eine Näherungslösung x0 gegeben, die 0 steht hier dafür, dass wir uns nach dem 0-ten Iterationsschritt befinden, also noch keinen einzigen Schritt gerechnet haben. Außerdem haben wir die Anzahl der Iterationsschritte gegeben, die wir berechnen sollen. Um die Rechnung, die gleich kommt, zahlenmäßig mitverfolgen zu können, solltet ihr euch A, b und x0 nun notieren oder einen Screenshot machen und in einem anderen Fenster einblenden. Auch die Formel werde ich gleich nicht noch mal anschreiben. Im 1. Iterationsschritt berechnen wir nun den Vektor x1, da in der Formel der obere Index (K+1) lautet, ist (K) in diesem Fall 0. Als erstes berechnen wir die 1. Komponente des Vektors x1, also x1(1). i ist hier also 1. Damit erhalten wir die Formel (1/a11)×(b1-(diese Summe)). In dieser Summe ist i die ganze Zeit fest 1 und (K) die ganze Zeit fest 0. j läuft von 1 bis n, in diesem Fall also von 1 bis 4. j soll zusätzlich aber ≠i sein, in diesem Fall also ≠1. Somit nimmt j nur die Werte 2,3 und 4 an. Wie wir sehen, verwenden wir für die Berechnung des Vektors x1 Komponenten des Vektors x0, also des vorangegangenen Iterationsschrittes. Beim Berechnen von x2(1) ist i=2. Somit wird in der Formel aus a11 a22 und aus b1 wird b2. In der Summe ändert sich, dass j ja immer ≠i sein muss, in diesem Fall also nicht 2 sein darf. j nimmt also diesmal die Werte 1,3 und 4 an. Dasselbe nun noch für x3(1) und x4(1). Bei x3(1) ist i=3, somit nimmt j nur die Werte 1,2 und 4 an. Für i=4 nimmt j nur die Werte 1,2 und 3 an. Dadurch, dass alle Komponenten des Startvektors 0 waren, vereinfachten sich hier die Formeln natürlich total, da die ganzen Summen zu 0 wurden. Für die Näherungslösung von x nach dem 1. Iterationsschritt, also x1, erhalten wir den Vektor ((11/2),(-4),(-7),(-1/2)). Kommen wir nun zum nächsten Iterationsschritt, also dem 2. Hierbei berechnen wir x2. (K) ist in diesem Fall also 1. Das Einzige, was sich an unseren Formeln jetzt ändert, ist das (K). Dies ist nicht mehr 0, sondern 1. Dadurch, dass (K) nun =1 ist, sind die x,j,(K) nicht mehr die Komponenten des Startvektors x0, sondern die Komponenten des Vektors x1, also des Vektors, den wir im 1. Iterationsschritt berechnet haben. Ihr könnt die Formeln aus dem 1. Iterationsschritt also fast 1:1 übernehmen und müsst nur die Werte von x ändern. Wir erhalten schließlich den Vektor x2, ((-2),(57,5),(-7,5),(-18,5)). Dies ist die gesuchte Näherung von x nach 2 Iterationsschritten. Und wir sind fertig. Wären in der Aufgabenstellung noch mehr Iterationsschritte gefordert gewesen, müssten wir nun einen weiteren Schritt machen, bei dem wir die gleichen Formeln wieder benutzen, nur jetzt die Lösungen von x2 einsetzen für x. Ich möchte nun an demselben Beispiel noch einmal die Formel veranschaulichen. Hat man dieses Prinzip einmal verstanden, muss man sich nicht mit den Indices rumschlagen, sondern kann direkt anschaulich anhand der Matrix A und der Vektoren b und x(K) die neuen Werte xi(K+1) berechnen. Ich habe hier mal die Komponenten von A, b und und x(K) mit ihren Indices aufgeschrieben. In der Formel für xi steht als erstes 1/aii. Dies ist das i-te Hauptdiagonalelement von A. Als Nächstes folgt bi. Dies ist die i-te Komponente des Vektors b. In der Summe steht aij. Wir befinden uns also in der i-ten Zeile von A und müssen dort alle Elemente bis auf das Hauptdiagonalelement durchlaufen. Das Hauptdiagonalelement ist nämlich das Element, bei dem j=i gilt. Diese Elemente aij müssen nun mit der j-ten Komponente des Vektors x(K) multipliziert werden. x(K) ist dabei die Näherungslösung, die wir im vorangegangenen Iterationsschritt erhalten haben. Wollen wir beispielsweise x2 berechnen, benötigen wir das 2. Hauptdiagonalelement von A und den 2. Eintrag des Vektors b. Nun durchlaufen wir die 2. Zeile von A und multiplizieren das 1. Element in dieser Zeile mit dem 1. Element des Vektors x(K). Wir lassen das 2. Element aus, da es Hauptdiagonalelement ist, multiplizieren das 3. Element mit dem 3. Element von x(K) und das 4. Element mit dem 4. Element von x(K). Dann addieren wir dieses alles zusammen. Wie das in der Praxis aussieht, möchte ich euch zeigen, indem wir das Beispiel von eben noch einmal aufgreifen. Gehen wir davon aus, dass wir x1 schon berechnet haben und nun den 2. Iterationsschritt ausführen wollen. Um x1(2) zu berechnen müssen wir nun also nehmen 1 durch das 1. Hauptelement von A, also 2 × das 1. Element von b, 11, minus, und nun gehen wir die erste Zeile von A durch. Wir multiplizieren das 2. Element mit dem 2. Element von x1, das dritte Element mit dem dritten Element von x1 und das 4. Element mit dem 4. Element von x1. Ich möchte dies jetzt nicht für jede Zeile zeigen, aber noch einmal beispielhaft für die 3. Um also x3 zu berechnen, müssen wir nun das 3. Hauptdiagonalelement, die -10, nehmen, den 3. Eintrag von b, also die 70 und anschließend wieder die 3. Zeile durchlaufen. Den 1. Eintrag × den 1. Eintrag von x1, den 2. Eintrag × den 2. Eintrag von x1, den dritten Eintrag nicht, da er Hauptdiagonalelement ist, und den 4. Eintrag der 3. Zeile von A × den 4. Eintrag von x1. Hier sind noch einmal die 3 Näherungslösungen für x, die wir gefunden haben, aufgelistet. Die exakte Lösung des Gleichungssystems lautet x=(1,2,3,4). Dieser Lösung wollten wir uns ja mit dem Iterationsverfahren annähern. Wie wir sehen, scheinen sich die Werte aber eher davon zu entfernen. Also kommt die Frage auf, konvergiert unser Iterationsverfahren überhaupt gegen die exakte Lösung x? Der Frage, nach welchen Kriterien wir entscheiden können, ob unser Verfahren konvergiert oder nicht, werde ich in einem anderen Video nachgehen. Am Ende wie immer eine kurze Zusammenfassung. Wir haben ein Gleichungssystem Ax=b und einen Startvektor x0. Nun können wir durch eine Formel iterativ Näherungslösungen für die exakte Lösung x bestimmen. Im Idealfall nähert sich diese Lösung mit jedem Iterationsschritt weiter der realen Lösung an. Soviel zum Gesamtschrittverfahren, weitere iterative Verfahren zum Bestimmen der Lösung eines linearen Gleichungssystems könnt ihr in meinen nächsten Videos sehen. Bis dahin tschüss, euer Christoph!

Informationen zum Video
1 Kommentar
  1. Default

    und wieso konvergiert das verfahren den nun nicht? blende doch wenigstens das video ein, indem du es erwähnst. danke

    Von Jasmin Jat, vor mehr als 2 Jahren