JacobiVerfahren

Jacobi-Verfahren, auch Jacobi-Iteration genannt, ist ein iteratives Verfahren zur Lösung linearer Gleichungssysteme Ax = b, wobei A eine quadratische Matrix, und x und b Vektoren sind. Die Grundidee besteht darin, A in eine Diagonal- und eine Restkomponente zu zerlegen: A = D + R, wobei D die Diagonalmatrix von A ist. Die Folgeiterationen verwenden ausschließlich Werte aus der vorherigen Iteration. Die Standardform lautet x^{k+1} = D^{-1}(b - R x^k). In Einzelausdrückung ergibt sich für jede Komponente i die Gleichung x_i^{k+1} = (1/a_{ii}) (b_i - sum_{j ≠ i} a_{ij} x_j^k). Die Methode ist einfach zu implementieren und lässt sich gut parallelisieren, da jedes x_i^{k+1} aus den Werten der vorherigen Iteration berechnet wird.

Konvergenz: Die Konvergenz hängt von der Eigenstruktur der Jacobi-Matrix T_J = -D^{-1}(L+U) ab, wobei A = D + L + U mit L und U den unteren bzw. oberen Dreiecksteilen von A entsprechen. Die Folge x^{k} konvergiert gegen x, wenn der Spektralradius ρ(T_J) < 1 ist. Eine hinreichende Bedingung für Konvergenz ist strikte diagonale Dominanz von A nach Zeilen (oder Spalten). Allgemein ist Jacobi konvergent nicht garantiert; bei vielen diskretisierten PDE-Systemen ist die Bedingung erfüllt.

Verwandte Verfahren: Das gewichtete Jacobi-Verfahren (mit Relaxationsparameter ω) verbessert die Konvergenz in einigen Fällen. Das Gauss-Seidel-Verfahren nutzt bei jeder Iteration bereits aktualisierte Werte, was oft zu schnellerer Konvergenz führt. In der Praxis dient Jacobi häufig als Basismethode, als Vorstufe oder als Bestandteil von Krylov- bzw. Multigrid-Verfahren.

Anwendungen und Eigenschaften: Jacobi wird häufig für große, spärliche lineare Systeme verwendet, z. B. aus diskretisierten elliptischen oder parabolischen PDEs. Die Kosten pro Iteration liegen bei dichten Matrizen bei O(n^2); bei sparsamen Matrizen entsprechen sie der Anzahl der Nichtnullen.