Gauß-Seidel-Verfahren

In der numerischen Mathematik ist das Gauß-Seidel-Verfahren oder Einzelschrittverfahren, (nach Carl Friedrich Gauß und Ludwig Seidel) ein Algorithmus zur näherungsweisen Lösung von linearen Gleichungssystemen. Es ist, wie das Jacobi-Verfahren und das SOR-Verfahren, ein spezielles Splitting-Verfahren. Das Verfahren wurde zuerst von Gauß entwickelt, aber nicht veröffentlicht, später wurde es, bevor dessen Anwendung von Gauß bekannt war, von Seidel veröffentlicht.
Entwickelt wurde das Verfahren, da das Gaußsche Eliminationsverfahren, ein exakter Löser, für Rechenfehler sehr anfällig ist. Eine iterative Vorgehensweise hat diesen Nachteil nicht.

Beschreibung des Verfahrens

Gegeben ist ein lineares Gleichungssystem in nn Variablen mit nn Gleichungen.
a1;1⋅x1+⋯+a1;n⋅xn=b1a2;1⋅x1+⋯+a2;n⋅xn=b2⋮an;1⋅x1+⋯+an;n⋅xn=bn \begin{matrix} a_{1;1}\cdot x_1+\dots+a_{1;n}\cdot x_n&=&b_1\\ a_{2;1}\cdot x_1+\dots+a_{2;n}\cdot x_n&=&b_2\\ &\vdots&\\ a_{n;1}\cdot x_1+\dots+a_{n;n}\cdot x_n&=&b_n\\ \end{matrix}
Um dieses zu lösen, wird die kk-te Gleichung nach der kk-ten Variablen xkx_{k} aufgelöst, d.h. für den (m+1)-ten Iterationsschritt:
xk(m+1):=1ak;k(bk−∑i=1k−1ak;i⋅xi(m+1)−∑i=k+1nak;i⋅xi(m))x^{(m+1)}_k:=\dfrac1{a_{k;k}}\left(b_k-\sum\limits_{i=1}^{k-1} a_{k;i}\cdot x^{(m+1)}_i -\sum\limits_{i=k+1}^n a_{k;i}\cdot x^{(m)}_i\right),
wobei die vorher berechneten Werte des aktuellen Iterationsschritts mit verwendet werden, im Gegensatz zum Jacobi-Verfahren. Diese Ersetzung wird, ausgehend von einer willkürlichen Startbelegung der Variablen, sukzessive wiederholt. Als minimale Bedingung lässt sich hier festhalten, dass die Diagonalelemente ak;ka_{k;k} von Null verschieden sein müssen.
Als Algorithmusskizze mit Abbruchbedingung ergibt sich:
wiederhole
fehler:=0fehler := 0
für k=1k=1 bis nn
xk(m):=xk(m+1)x^{(m)}_k:=x^{(m+1)}_k
xk(m+1):=1ak;k(bk−∑i=1k−1ak;i⋅xi(m+1)−∑i=k+1nak;i⋅xi(m))x^{(m+1)}_k:=\dfrac1{a_{k;k}}\left(b_k-\sum\limits_{i=1}^{k-1} a_{k;i}\cdot x^{(m+1)}_i -\sum\limits_{i=k+1}^n a_{k;i}\cdot x^{(m)}_i\right)
fehler:=max⁡(fehler;∣xk(m+1)−xk(m)∣)fehler:=\max(fehler;|x^{(m+1)}_k-x^{(m)}_k|)
nächstes kk
m:=m+1m := m+1
bis fehler<fehlerschrankefehler<fehlerschranke
Dabei wurde die Erstbelegung des Variablenvektors und eine Fehlerschranke als Eingangsgrößen des Algorithmus angenommen, die Näherungslösung ist die vektorielle Rückgabegröße. Die Fehlerschranke misst hier, welche Größe die letzte Änderung des Variablenvektors hatte.

Herleitung des Verfahrens

Beschreibung des Verfahrens in Matrixschreibweise

Die Matrix A A\, des linearen Gleichungssystems A⋅x‾=b‾A \cdot \underline{x} = \underline{b} wird zur Vorbereitung in eine Diagonalmatrix D D\, , eine strikte obere Dreiecksmatrix U U\, und eine strikte untere Dreiecksmatrix L L\, zerlegt, so dass gilt:
A = L+D+UA\,=\, L+D+U
In jedem Iterationsschritt gilt dann Dx‾(neu)=b‾−Lx‾(neu)−Ux‾(alt)D \underline{x}^{(\mathrm{neu})} = \underline{b}-L \underline{x}^{(\mathrm{neu})}-U \underline{x}^{(\mathrm{alt})}. Nach Umstellen ergibt sich formal
(D+L)x‾(neu)=b‾−Ux‾(alt)(D+L) \underline{x}^{(\mathrm{neu})}=\underline{b}-U \underline{x}^{(\mathrm{alt})} und daraus x‾(neu)=(D+L) ⁣−1(b‾−Ux‾(alt))\underline{x}^{(\mathrm{neu})} =(D+L)\!^{-1}(\underline{b}-U\underline{x}^{(\mathrm{alt})}).
Man legt dann einen Startvektor x‾(0) \underline{x}^{(0)}\, fest und setzt ihn in die Iterationsvorschrift ein:
x‾(k+1)=−(D+L)−1Ux‾(k)+(D+L)−1b‾\underline{x}^{(k+1)} =-(D+L)^{-1}U \underline{x}^{(k)} + (D+L)^{-1} \underline{b}.
Da es der erste Iterationsschritt ist, hat dabei k  k\, den Wert Null. Das Ergebnis der Rechnung ist ein erster Näherungswert x‾(1) \underline{x}^{(1)}\, für den gesuchten Lösungsvektor x‾ \underline{x}\,. Diesen Näherungswert kann man seinerseits in die Iterationsvorschrift einsetzen und gewinnt einen besseren Näherungswert x‾(2) \underline{x}^{(2)}\,, den man wieder einsetzen kann. Wiederholt man diesen Vorgang, gewinnt man eine Folge von Werten, die sich dem Lösungsvektor immer mehr annähern, wenn die Konvergenzbedingungen (s. unten) erfüllt sind:
x‾(0), x‾(1), x‾(2), ⋯  →  x‾\underline{x}^{(0)},\,\underline{x}^{(1)},\,\underline{x}^{(2)},\,\cdots \; \rightarrow \; \underline{x}

Diagonaldominanz und Konvergenz

Die Konvergenzgeschwindigkeit des Verfahrens hängt sowohl vom Spektralradius der Iterationsmatrix −(D+L)−1U-(D+L)^{-1}U als auch von der Nummerierung der Unbekannten ab.
Allgemein gilt: Ist AA strikt diagonaldominant, sind also sowohl D−1UD^{-1}U als auch D−1LD^{-1}L "kleine" Matrizen im Sinne der Operatornorm (z.B. der Spektralnorm), ist also die Bedingung
∥D−1L∥+∥D−1U∥<1\|D^{-1}L\|+\|D^{-1}U\|<1
erfüllt, so ist das Verfahren konvergent. In diesem Falle ist der Fixpunktsatz von Banach anwendbar. Dabei ist die Kontraktionskonstante des Gauß-Seidel-Verfahrens kleinergleich der Kontraktionskonstante des Jabobi-Verfahrens.
Das einfachste und gebräuchlichste Kriterium für Diagonaldominanz ergibt sich in der Supremumsnorm ∥x∥:=max⁡k∣xk∣\|x\|:=\max\limits_k|x_k| der Vektoren und deren induzierter Matrixnorm ∥A∥:=max⁡k∑i∣aki∣\|A\|:=\max\limits_k\sum\limits_i|a_{ki}|. Es verlangt die Erfüllung des Zeilensummenkriteriums, also der Ungleichung
∑i=1, i≠kn∣aki∣<∣akk∣\sum\limits_{ {i=1 \text{, } i\ne k}}^n|a_{ki}|<|a_{kk}| für k=1,…,nk=1,\ldots,n.
Je größer die kleinste Differenz zwischen rechten und linken Seiten der Ungleichung ist, desto schneller konvergiert das Verfahren.

Anwendungen

Für moderne Anwendungen wie die Lösung großer dünnbesetzter Gleichungssysteme die aus der Diskretisierung partieller Differentialgleichungen stammen, ist das Verfahren ungeeignet. Es wird jedoch mit Erfolg als Vorkonditionierer in Krylow-Unterraum-Verfahren oder als Glätter in Mehrgitterverfahren eingesetzt.
 
 

So seltsam es auch klingen mag, die Stärke der Mathematik beruht auf dem Vermeiden jeder unnötigen Annahme und auf ihrer großartigen Einsparung an Denkarbeit.

Ernst Mach

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Gauß-Seidel-Verfahren aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Lineare Gleichungssysteme