Iterative Methoden zur Lösung von Ax = b – Jacobis Methode

Die vielleicht einfachste iterative Methode zur Lösung von Ax = b ist Jacobis Methode. Beachten Sie, dass die Einfachheit dieser Methode sowohl gut als auch schlecht ist: gut, weil sie relativ leicht zu verstehen ist und somit einen guten ersten Eindruck von iterativen Methoden vermittelt; schlecht, weil sie in der Praxis normalerweise nicht verwendet wird (obwohl ihre potenzielle Nützlichkeit mit dem Aufkommen des Parallelrechnens überdacht wurde). Dennoch ist es ein guter Ausgangspunkt, um nützlichere, aber kompliziertere iterative Methoden kennenzulernen.

Bei einer aktuellen Näherung

x(k) = (x1(k), x2(k), x3(k), …, xn(k))

Für x besteht die Strategie von Jacobis Methode darin, die erste Gleichung und die aktuellen Werte von x2 (k), x3 (k), …, xn(k) zu verwenden, um einen neuen Wert x1 (k + 1) zu finden, und in ähnlicher Weise ein neuer Wert xi(k) unter Verwendung der i-ten Gleichung und der alten Werte der anderen Variablen. Das heißt, bei gegebenen aktuellen Werten x(k) = (x1(k), x2(k), …, xn(k)) finden Sie neue Werte, indem Sie nach

x(k+1) = (x1(k+1), x2(k+1), …, xn(k+1))

in

Dieses System kann auch geschrieben werden als

Um klar zu sein, bedeutet der Index i, dass xi(k) das i-te Element des Vektors

x(k) = (x1(k), x2(k), …, xi(k), …, xn(k) ),

und hochgestellt ist k entspricht der jeweiligen Iteration (nicht der k-ten Potenz von xi).

Wenn wir D, L und U für die Diagonale schreiben, streng unteres Dreieck und streng oberes Dreieck und Teile von A,

dann kann Jacobis Methode in Matrix-Vektor-Notation als geschrieben werden

Beispiel 1

Wenden wir Jacobis Methode auf das System an

.

Bei jedem Schritt lösen wir angesichts der aktuellen Werte x1(k), x2(k), x3(k)nach x1(k+1), x2(k+1) und x3(k+ 1) in

.

Also, wenn unsere anfängliche Vermutung x(0) = (x1(0), x2(0), x3(0)) der Nullvektor 0 = (0,0,0) ist – eine häufige anfängliche Vermutung, es sei denn, wir haben einige zusätzliche Informationen, die uns dazu bringen, eine andere zu wählen – dann finden wir x(1) = (x1(1), x2(1), x3(1))

Also x (1) = (x1 (1), x2 (1), x3(1)) = (3/4, 9/6, -6/7) ≈ (0.750, 1.500, -0.857). Wir iterieren diesen Prozess, um eine Folge von immer besseren Näherungen x (0), x (1), x (2), … zu finden. Wir zeigen die Ergebnisse in der folgenden Tabelle, wobei alle Werte auf 3 Dezimalstellen gerundet sind.

Wir interessieren uns für den Fehler e bei jeder Iteration zwischen der wahren Lösung x und der Approximation x(k): e(k) = x − x(k) . Offensichtlich kennen wir normalerweise nicht die wahre Lösung x. Um das Verhalten einer iterativen Methode besser zu verstehen, ist es jedoch aufschlussreich, die Methode zum Lösen eines Systems Ax = b zu verwenden, für das wir die wahre Lösung kennen, und zu analysieren, wie schnell die Näherungen zur wahren Lösung konvergieren. In diesem Beispiel ist die wahre Lösung x = (1, 2, -1).

Die Norm eines Vektors ||x// sagt uns, wie groß der Vektor als Ganzes ist (im Gegensatz dazu, wie groß jedes Element des Vektors ist). Die in der linearen Algebra am häufigsten verwendete Vektornorm ist die l2-Norm:

Zum Beispiel, wenn x = (1, 2, -1), dann

In diesem Modul werden wir immer die l2-Norm verwenden (auch für Matrixnormen in nachfolgenden Tutorials), so dass || // immer bedeutet || ||2.

Für unsere Zwecke beobachten wir, dass ||x|| genau dann klein ist, wenn jedes der Elemente x1, x2, …, xn in x = (x1, x2, …, xn ) klein ist. In der folgenden Tabelle wird die Norm des Fehlers progressiv kleiner, wenn der Fehler in jedem der drei Elemente x1, x2, x3 kleiner wird, oder mit anderen Worten, wenn die Näherungen progressiv besser werden.