Direkt zum Inhalt

Lexikon der Mathematik: Gauß-Seidel-Verfahren

Einzelschrittverfahren, iteratives Verfahren zur Lösung eines linearen Gleichungssystems Ax = b mit A ∈ ℝn×n und b ∈ ℝn.

Zerlegt man die Matrix A in die Summe des unteren Dreieckes L \begin{eqnarray}L=\left (\begin{array}{ccccc}0 & 0 & \cdots & \cdots & 0\\ {a}_{21} & 0 & \cdots & \cdots & 0\\ {a}_{31} & {a}_{32} & \ddots & 0 & \\ \vdots & \vdots & \ddots & \ddots & \vdots \\ x & x & \cdots x & 0 & \end{array}\right),\end{eqnarray} des oberen Dreieckes R \begin{eqnarray}R=\left(\begin{array}{ccccc}0 & {a}_{12} & {a}_{13} & \cdots & {a}_{1n}\\ 0 & 0 & {a}_{23} & \cdots & {a}_{2n}\\ \vdots & \vdots & \ddots & \ddots & \vdots \\ \vdots & \vdots & & \ddots & {a}_{n=1,n}\\ 0 & 0 & \cdots & \cdots 0 & \end{array}\right ),\end{eqnarray} und der Diagonalmatrix \begin{eqnarray}D=\text{diag}\space \text{(}{a}_{11}\text{,}\space {a}_{22}\text{,}\ldots \text{,}{a}_{nn}\text{)}\end{eqnarray} in \begin{eqnarray}A=L+D+R,\end{eqnarray} dann lautet die Fixpunktiteration des Gauß-Seidel-Verfahrens \begin{eqnarray}(D+L){x}^{(k+1)}=-R{x}^{(k)}+b,\end{eqnarray} bzw. für i = 1, 2,…, n \begin{eqnarray}{x}_{i}^{(k+1)}=\left ({b}_{i}-\displaystyle \sum _{j=1}^{i-1}{a}_{ij}{x}_{j}^{(k+1)}-\displaystyle \sum _{j=i+1}^{n}{a}_{ij}{x}_{j}^{(k)}\right )/{a}_{ii}.\end{eqnarray}

Man verwendet hier, im Gegensatz zum Jacobi-Verfahren, bei der Berechnung einer neuen Komponente der Näherungslösung die bereits verfügbaren neuen Komponenten des Iterationsschritts. Im allgemeinen sind diese neuen Werte genauer als die der vorgehenden Iterierten. Außerdem ist dieses Vorgehen günstig in bezug auf den Speicherplatzbedarf, da man den bisherigen Wert einer Komponente der Näherungslösung direkt mit dem neu berechneten Wert überspeichern kann.

Das Gauß-Seidel-Verfahren konvergiert u. a. für symmetrische, positiv definite Matrizen A.

Zur Konvergenzbeschleunigung verwendet man häufig die Technik der Relaxation. Dieser Ansatz führt auf die Iteration \begin{eqnarray}(D+\omega L){x}^{(k+1)}=((1-\omega )D-\omega R){x}^{(k)}+\omega b.\end{eqnarray}

Man spricht dann vom Verfahren der sukzessiven Overrelaxation (SOR-Verfahren). Der maximale Bereich, aus dem ω gewählt werden kann, ist das Intervall (0, 2).

In einigen (für die Anwendungen wichtigen) Fällen ist bekannt, für welche Wahl von ω diese Iteration optimal konvergiert. Es ist im allgemeinen vorteilhaft, Relaxationsparameter ω > 1 zu betrachten.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos