GMRES-Verfahren

Das GMRES-Verfahren (für Generalized minimal residual method) ist ein iteratives numerisches Verfahren zur Lösung großer, dünnbesetzter linearer Gleichungssysteme. Das Verfahren ist aus der Klasse der Krylow-Unterraum-Verfahren und insbesondere auch für unsymmetrische Matrizen geeignet. In exakter Arithmetik, also wenn ohne Rundungsfehler gerechnet wird, liefert das Verfahren nach endlich vielen Schritten die exakte Lösung. Interessanter ist es jedoch als näherungsweises Verfahren, da es mit einer geeigneten Vorkonditionierung auch Gleichungssysteme mit Millionen Unbekannten in wenigen Iterationen mit befriedigender Genauigkeit lösen kann. Damit stellt es eine Art Black Box-Löser für dünnbesetzte lineare Gleichungssysteme dar. Es wurde 1986 von Yousef Saad und Martin H. Schultz entwickelt.

Das Verfahren

Gegeben sei das lineare Gleichungssystem $Ax=b$ , mit einer reellen, $n\times n$ Matrix A. Das Gleichungssystem sei eindeutig lösbar, A habe also vollen Rang. Gegeben sei außerdem eine Startnäherung $x_{0}$ , etwa einfach die rechte Seite b. Dann wird das GMRES-Verfahren dadurch definiert, dass im m-ten Schritt die euklidische Norm des Residuums $\|Ax-b\|_{2}$ über den affinen Krylow-Unterraum $x_{0}+{\mathcal {K}}_{m}(A,x_{0})=x_{0}+{\mbox{span}}\{x_{0},Ax_{0},\ldots ,A^{m-1}x_{0}\}$ minimiert wird.

Hierzu wird eine orthonormale Basis $\{v_{1},...,v_{m}\}$ des Raumes mit Hilfe der Arnoldi-Prozedur iterativ berechnet. Diese erlaubt eine Darstellung der von den Basisvektoren gebildeten Matrizen $V_{m}\in \mathbb {R} ^{m\times n}$ und $V_{m+1}\in \mathbb {R} ^{(m+1)\times n}$ über eine Matrix $H_{m}\in \mathbb {R} ^{(m+1)\times m}$ , die eine obere Hessenbergmatrix ist, an die eine Zeile angehängt wurde in der nur der letzte Eintrag nicht Null ist, als

AV_{m}=V_{m+1}H_{m}

.

Damit ist eine effizient berechenbare Form des Residuums gegeben, da $V_{m+1}$ die 2-Norm erhält:

\|Ax_{m}-b\|_{2}=\|\|r_{0}\|_{2}v_{1}-V_{m+1}H_{m}y\|_{2}=\|\|r_{0}\|_{2}e_{1}-H_{m}y\|_{2}

.

Hierbei bezeichnet $e_{1}\in \mathbb {R} ^{m+1}$ den ersten Einheitsvektor. Die Hessenbergmatrix H wird in jedem Schritt aufdatiert und dann durch eine zusammengesetzte orthogonale Transformation $Q_{m}$ , meist durch Givens-Rotationen wie im unten abgegebenen Pseudo-Code, auf eine rechte obere Dreiecksmatrix ${\bar {R}}_{m}\in \mathbb {R} ^{(m+1)\times m}$ mit Nullen in der letzten Zeile, gebracht. Hier sind nur m-1 Rotationen notwendig, da jede ein Element auf der unteren Nebendiagionalen auf Null setzen kann. In manchen Fällen verlieren die berechneten Vektoren aufgrund von Rundungsfehlern ihre Orthogonalität. Dies kann meist durch Verwendung der aufwändigeren Householder-Spiegelungen statt der Drehungen behoben werden. Anwendung von $Q_{m}$ liefert in beiden Fällen

\|\|r_{0}\|_{2}e_{1}-H_{m}y\|_{2}=\|Q_{m}(\|r_{0}\|_{2}e_{1}-H_{m}y)\|_{2}=\|{\bar {g}}_{m}-{\bar {R}}_{m}y\|_{2}={\sqrt {|\gamma _{m+1}|^{2}+\|g_{m}-R_{m}y\|_{2}}}

,

wobei $g_{m}$ und $R_{m}$ aus ihren Pendants durch weglassen der letzten Zeile erhalten werden. Hier ist nun ersichtlich, an welcher Stelle das Residuum minimal wird, nämlich für den eindeutig bestimmten Vektor y, der $g_{m}=R_{m}y$ erfüllt. Das Residuum im m-tem Schritt ist damit genau $|\gamma _{m+1}|$ .

Eine Besonderheit des Verfahrens ist, dass die aktuelle Näherung $x_{m}$ im Laufe der Iteration zunächst nicht berechnet wird, sondern nur der Hilfsvektor y. Stattdessen liefert das Verfahren in jedem Schritt die Norm des Residuums. Ist diese kleiner als die gewünschte Genauigkeit wird das Verfahren üblicherweise abgebrochen. Dann wird die aktuelle Näherung als Linearkombination der Basisvektoren berechnet. Hierbei sind die Komponenten von y einfach die Koeffizienten der Basisdarstellung.

Alternativ ist die Lösung des obigen Minimierungsproblems gegeben als der Vektor $x_{m}$ des affinen Krylow-Unterraumes $x_{0}+{\mathcal {K}}_{m}(A,x_{0})$ , dessen Residuum $b-Ax_{m}$ senkrecht auf dem Raum $A{\mathcal {K}}_{m}(A,x_{0})$ steht. Damit ist GMRES eine schiefe Projektionsmethode.

Pseudocode

Gegeben $x_{0}\in \mathbb {R} ^{n}$ , berechne $r_{0}=b_{0}-Ax_{0}$ .

If $r_{0}=0$ , then END.

$v_{1}={\frac {r_{0}}{\|r_{0}\|_{2}}}$ .

For $j=1,...,n$

For

i=1,...,j

do

h_{ij}=v_{i}^{T}Av_{j}

.

w_{j}=Av_{j}-\sum _{i=1}^{j}h_{ij}v_{i},\quad h_{j+1,j}=\|w_{j}\|_{2}.

For

i=1,...,j-1

do

{\begin{pmatrix}h_{ij}\\h_{i+1,j}\end{pmatrix}}={\begin{pmatrix}c_{i+1}&s_{i+1}\\s_{i+1}&-c_{i+1}\end{pmatrix}}{\begin{pmatrix}h_{ij}\\h_{i+1,j}\end{pmatrix}}

.

\beta ={\sqrt {h_{jj}^{2}+h_{j+1,j}^{2}}};\quad s_{j+1}={\frac {h_{j+1,j}}{\beta }}

.

c_{j+1}={\frac {h_{jj}}{\beta }};\quad h_{jj}=\beta

.

\gamma _{j+1}=s_{j+1}\gamma _{j};\quad \gamma _{j}=c_{j+1}\gamma _{j}

.

if

\gamma _{j+1}\neq 0

,

v_{j+1}={\frac {w_{j}}{h_{j+1,j}}}.

else

for

i=j,...,1

do

y_{i}={\frac {1}{h_{jj}}}\left(\gamma _{j}-\sum _{k=i+1}^{j}h_{ik}y_{k}\right)

.

x=x_{0}+\sum _{i=1}^{j}y_{i}v_{i}

.

END.

Konvergenzresultate

Aufgrund der Definition des Verfahrens über das Minimierungsproblem fällt die euklidische Norm der Residuen monoton. In exakter Arithmetik ist GMRES sogar ein direktes Lösungsverfahren, was spätestens nach n Schritten die exakte Lösung liefert. Wird die Dimension des Krylow-Unterraums in jedem Schritt um Eins erhöht, ist diese Aussage klar, da dann im letzten Schritt über den kompletten $\mathbb {R} ^{n}$ minimiert wird. Ist dies nicht der Fall, so kommt es vorher zu einem Verfahrensabbruch, allerdings mit der exakten Lösung.

Für allgemeine Matrizen ist dies auch das stärkste Ergebnis, was möglich ist, denn nach einem Satz von Greenbaum, Pták und Strakoš gibt es zu jeder monoton fallenden Folge eine Matrix, so dass die Folge der durch GMRES erzeugten Residuen der gegebenen Folge entspricht. Insbesondere ist es also möglich, dass die Residuen konstant bleiben und erst im allerletzten Schritt auf Null fallen.

Für spezielle Matrizen gibt es schärfere Konvergenzresultate. Ist die Matrix positiv definit, d.h. alle ihre Eigenwerte sind größer als Null, so gilt:

\|r_{m}\|_{2}\leq (1-{\frac {\lambda _{min}({\frac {A^{T}+A}{2}})}{\lambda _{max}(A^{T}+A)}})^{m/2}\|r_{0}\|_{2}

,

wobei $\lambda _{min}$ und $\lambda _{max}$ den größten beziehungsweise kleinsten Eigenwert einer Matrix bezeichnen.

Ist die Matrix A nicht nur positiv definit, sondern auch symmetrisch, so gilt sogar mit der Konditionszahl der Matrix in euklidischer Norm $cond_{2}(A)$ :

\|r_{m}\|_{2}\leq ({\frac {cond_{2}^{2}(A)-1}{cond_{2}^{2}(A)}})^{m/2}\|r_{0}\|_{2}

.

All diese Aussagen gelten nur für die Residuen und geben damit keine Auskunft über den tatsächlichen Fehler, also den Abstand der aktuellen Näherung zur exakten Lösung. Zu diesem sind keine Aussagen bekannt.

Aufwand und Restarted GMRES

GMRES benötigt pro Iteration eine Matrix-Vektor-Multiplikation und eine Reihe von Skalarprodukten, deren Anzahl um einen pro Iterationsschritt steigt, ebenso wie die Anzahl der (vollbesetzten!) zu speichernden Basisvektoren. Dies liegt daran, dass das Verfahren nicht durch eine kurze Rekursion gegeben ist, sondern auf alle Basisvektoren in jedem Schritt zugegriffen wird.

Da der Aufwand und der Speicherplatz also linear mit der Iterationszahl steigen, ist es üblich, nach k Schritten die berechnete Basis wegzuwerfen und die Iteration mit der aktuellen Näherungslösung neu zu starten. Dieses Verfahren wird GMRES(k) genannt, übliche Restart-Längen sind 20 bis 40. Hier lässt sich allerdings nur noch für Speziallfälle Konvergenz beweisen, und es lassen sich Matrizen angeben, so dass ein Restart nicht zu Konvergenz führt.

Der Gesamtaufwand von GMRES ist wie bei allen Krylow-Unterraum-Verfahren bei dünnbesetzten Matrizen O(n) mit einer hohen Konstanten, wenn deutlich weniger Iterationen durchgeführt werden, als es Unbekannte gibt.

Vergleich mit anderen Lösern

Für symmetrische Matrizen fällt das Arnoldi-Verfahren zur Berechnung der orthogonalen Basis mit dem Lanczos-Verfahren zusammen. Das entsprechende Krlow-Unterraum-Verfahren ist das MinRes-Verfahren (für Minimal Residual Method) von Paige und Saunders. Dieses kommt im Gegensatz zur verallgemeinerten Variante mit einer Dreitermrekursion aus. Es lässt sich zeigen, dass es für allgemeine Matrizen kein Krylow-Unterraum-Verfahren gibt, welches mit kurzen Rekursionen arbeitet, aber gleichzeitig wie das GMRES-Verfahren eine Optimalitätsbedingung bezüglich der Norm des Residuums, erfüllt.

Eine andere Klasse von Verfahren baut auf dem unsymmetrischen Lanczos-Verfahren auf, insbesondere das BiCG-Verfahren. Diese zeichnen sich durch eine Dreitermrekursion aus, allerdings haben sie aufgrund der fehlenden Optimalität keine monotone Konvergenzhistorie mehr. Darüberhinaus liefern sie zwar im Konvergenzfalle die exakte Lösung, haben allerdings keine garantierte Konvergenz mehr.

Die dritte Variante sind Verfahren wie CGS und BiCGSTAB. Diese arbeiten ebenfalls mit Dreitermrekursionen ohne Optimalität und können ebenfalls vorzeitig ohne Konvergenz abbrechen. Die Idee bei diesen Verfahren ist es, die generierenden Polynome der Iterationssequenz geschickt zu wählen.

Keine der drei Gruppen ist für alle Matrizen besser, es gibt jeweils Beispiele wo eine Klasse die anderen übertrumpft. In der Praxis werden deswegen mehrere Löser ausprobiert, um für das gegebene Problem Erfahrungswerte zu sammeln.

Vorkonditionierung

Weniger entscheidend als die Auswahl des tatsächlichen Lösers ist die Wahl des Vorkonditionierers, durch den entscheidende Geschwindigkeitsverbesserungen erzielt werden können. Für sequentielle Codes bietet sich hier eine ILU-Zerlegung an, aber je nach Problem können auch andere Vorkonditionierer gut sein. Da ILU nicht parallelisierbar ist, werden in diesem Falle andere eingesetzt, beispielsweise Schwarz-Gebietszerlegungs-Verfahren.

Literatur

Yousef Saad, Martin H. Schultz: GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM Journal on Scientific and Statistical Computing, Band 7, S. 856-869. Society for Industrial and Applied Mathematics, Philadelphia 1986, ISSN 0196-5204
Andreas Meister: Numerik linearer Gleichungssysteme, 2. Auflage, Vieweg, Wiesbaden 2005, ISBN 3-528-13135-7
Yousef Saad: Iterative Methods for Sparse Linear Systems, 2nd edition, SIAM Society for Industrial & Applied Mathematics 2003, ISBN 0-898-71534-2

Dieser Artikel nimmt am Schreibwettbewerb teil. Bitte hilf mit, ihn zu verbessern!

Land Bayern

GMRES-Verfahren

Inhaltsverzeichnis

Das Verfahren

Pseudocode

Konvergenzresultate

Aufwand und Restarted GMRES

Vergleich mit anderen Lösern

Vorkonditionierung

Literatur

What are your Feelings

GMRES-Verfahren

Das Verfahren

Pseudocode

Konvergenzresultate

Aufwand und Restarted GMRES

Vergleich mit anderen Lösern

Vorkonditionierung

Literatur

What are your Feelings

Share This Article :