Im Falle eines linearen Gleichungssystems sind die beiden Hauptklassen der iterativen Verfahren die stationären iterativen Verfahren und die allgemeineren Krylov-Unterraumverfahren.
Stationäre IterationsmethodenBearbeiten
EinführungBearbeiten
Stationäre Iterationsmethoden lösen ein lineares System mit einem Operator, der das ursprüngliche System annähert, und bilden auf der Grundlage einer Messung des Fehlers im Ergebnis (dem Residuum) eine „Korrekturgleichung“, für die dieser Prozess wiederholt wird. Während diese Methoden einfach abzuleiten, zu implementieren und zu analysieren sind, ist Konvergenz nur für eine begrenzte Klasse von Matrizen garantiert.
DefinitionBearbeiten
Eine iterative Methode ist definiert durch
x k + 1 := Ψ ( x k ) , k ≥ 0 {\displaystyle \mathbf {x} ^{k+1}:=\Psi (\mathbf {x} ^{k})\,,\quad k\geq 0}
und für ein gegebenes lineares System A x = b {\displaystyle A\mathbf {x} =\mathbf {b} }
mit exakter Lösung x ∗ {\displaystyle \mathbf {x} ^{*}}
den Fehler durch e k := x k – x ∗ , k ≥ 0 . {\displaystyle \mathbf {e} ^{k}:=\mathbf {x} ^{k}-\mathbf {x} ^{*}\,,\quad k\geq 0\,.}
Ein iteratives Verfahren heißt linear, wenn es eine Matrix C ∈ R n × n {\displaystyle C\in \mathbb {R} ^{n\times n}}
, so dass e k + 1 = C e k ∀ k ≥ 0 {\displaystyle \mathbf {e} ^{k+1}=C\mathbf {e} ^{k}\quad \forall \,k\geq 0}
und diese Matrix wird Iterationsmatrix genannt.Ein iteratives Verfahren mit einer gegebenen Iterationsmatrix C {\displaystyle C}
wird konvergent genannt, wenn gilt lim k → ∞ C k = 0 . {\displaystyle \lim _{k\rightarrow \infty }C^{k}=0\,.}
Ein wichtiges Theorem besagt, dass für eine gegebene iterative Methode und ihre Iterationsmatrix C {\displaystyle C}
dann und nur dann konvergent ist, wenn ihr Spektralradius ρ ( C ) {\displaystyle \rho (C)}
kleiner als Eins ist, d.h. ρ ( C ) < 1 . {\rho (C)} <1.
Die grundlegenden iterativen Methoden funktionieren durch Aufteilung der Matrix A {\displaystyle A}
in A = M – N {\displaystyle A=M-N}
und hier die Matrix M {\displaystyle M}
leicht invertierbar sein sollte.Die Iterationsverfahren sind nun definiert als M x k + 1 = N x k + b , k ≥ 0 . {\displaystyle M\mathbf {x} ^{k+1}=N\mathbf {x} ^{k}+b\,,\quad k\geq 0\,.}
Daraus folgt, dass die Iterationsmatrix gegeben ist durch
C = I – M – 1 A = M – 1 N . {\displaystyle C=I-M^{-1}A=M^{-1}N\,.}
BeispieleBearbeiten
Grundlegende Beispiele für stationäre iterative Verfahren verwenden eine Aufteilung der Matrix A {\displaystyle A}
wie A = D + L + U , D := diag ( ( a i i ) i ) {\displaystyle A=D+L+U\,,\quad D:={\text{diag}}((a_{ii})_{i})}
wobei D {\displaystyle D}
ist nur der diagonale Teil von A {\displaystyle A}
, und L {\displaystyle L}
ist der strenge untere dreieckige Teil von A {\displaystyle A}
, bzw. U {\displaystyle U}
ist der strenge obere dreieckige Teil von A {\displaystyle A}
.
- Richardson-Verfahren: M := 1 ω I ( ω ≠ 0 ) {\displaystyle M:={\frac {1}{\omega }}I\quad (\omega \neq 0)}
- Jacobi-Methode: M := D {\displaystyle M:=D}
- Gedämpftes Jacobi-Verfahren: M := 1 ω D ( ω ≠ 0 ) {\displaystyle M:={\frac {1}{\omega }}D\quad (\omega \neq 0)}
- Gauß-Seidel-Verfahren: M := D + L {\displaystyle M:=D+L}
- Sukzessive Überrelaxationsmethode (SOR): M := 1 ω D + L ( ω ≠ 0 ) {\displaystyle M:={\frac {1}{\omega }}D+L\quad (\omega \neq 0)}
- Symmetrische sukzessive Überrelaxation (SSOR): M := 1 ω ( 2 – ω ) ( D + ω L ) D – 1 ( D + ω U ) ( ω ≠ { 0 , 2 } ) {\displaystyle M:={\frac {1}{\omega (2-\omega )}}(D+\omega L)D^{-1}(D+\omega U)\quad (\omega \neq \{0,2\})}
Lineare stationäre Iterationsverfahren werden auch als Relaxationsverfahren bezeichnet.
Krylov-UnterraumverfahrenBearbeiten
Krylov-Unterraumverfahren arbeiten, indem sie eine Basis der Folge aufeinanderfolgender Matrixpotenzen mal dem anfänglichen Residuum (der Krylov-Folge) bilden. Die Annäherungen an die Lösung werden dann durch Minimierung des Residuums über den gebildeten Unterraum gebildet. Die prototypische Methode in dieser Klasse ist die konjugierte Gradientenmethode (CG), die davon ausgeht, dass die Systemmatrix A {\displaystyle A}
symmetrisch und positiv-definit ist, für symmetrische (und möglicherweise unbestimmte) A {\displaystyle A}
arbeitet man mit der Minimal-Residual-Methode (MINRES).Für nicht-symmetrische Matrizen wurden Methoden wie die verallgemeinerte Minimal-Residual-Methode (GMRES) und die bikonjugierte Gradientenmethode (BiCG) abgeleitet.
Konvergenz von Krylov-UnterraummethodenEdit
Da diese Methoden eine Basis bilden, ist es offensichtlich, dass die Methode in N Iterationen konvergiert, wobei N die Systemgröße ist. Bei Vorhandensein von Rundungsfehlern gilt diese Aussage jedoch nicht; außerdem kann N in der Praxis sehr groß sein, und der iterative Prozess erreicht schon viel früher eine ausreichende Genauigkeit. Die Analyse dieser Methoden ist schwierig und hängt von einer komplizierten Funktion des Spektrums des Operators ab.
VorkonditioniererBearbeiten
Der Approximationsoperator, der in stationären iterativen Methoden auftritt, kann auch in Krylov-Unterraummethoden wie GMRES integriert werden (alternativ können vorkonditionierte Krylov-Methoden als Beschleunigungen stationärer iterativer Methoden betrachtet werden), wo sie zu Transformationen des ursprünglichen Operators in einen vermutlich besser konditionierten werden. Die Konstruktion von Vorkonditionierern ist ein großes Forschungsgebiet.
GeschichteBearbeiten
Wahrscheinlich erschien die erste iterative Methode zur Lösung eines linearen Systems in einem Brief von Gauß an einen seiner Schüler. Er schlug vor, ein 4-mal-4-Gleichungssystem durch wiederholtes Lösen der Komponente zu lösen, in der das Residuum am größten war.
Die Theorie der stationären iterativen Methoden wurde mit der Arbeit von D.M. Young ab den 1950er Jahren solide etabliert. Die Conjugate-Gradient-Methode wurde ebenfalls in den 1950er Jahren mit unabhängigen Entwicklungen von Cornelius Lanczos, Magnus Hestenes und Eduard Stiefel erfunden, aber ihre Natur und Anwendbarkeit wurden zu dieser Zeit nicht verstanden. Erst in den 1970er Jahren wurde erkannt, dass auf Konjugation basierende Methoden sehr gut für partielle Differentialgleichungen, insbesondere vom elliptischen Typ, funktionieren.