Direkt zum Inhalt

Lexikon der Mathematik: GMRES-Verfahren

iteratives Krylow-RaumVerfahren zur Lösung eines linearen Gleichungs-systems Ax = b, wobei A ε ℝn×n eine beliebige (insbesondere unsymmetrische) Matrix sei. Da im Laufe der Berechnungen lediglich Matrix-Vektor-Multiplikationen benötigt werden, ist das Verfahren besonders für große sparse Matrizen A geeignet.

Das GMRES-Verfahren ist eine Verallgemeinerung des konjugierten Gradientenverfahrens für Gleichungssysteme mit symmetrisch positiv definiten Koeffizientenmatrizen.

Es wird, ausgehend von einem (beliebigen) Start-vektor x(0), eine Folge von Näherungsvektoren x(k) an die gesuchte Lösung x gebildet. Die nächste Näherung x(k) wird so gewählt, daß \begin{eqnarray}{(b-A{x}^{(k)})}^{T}(b-A{x}^{(k)})\end{eqnarray} minimiert wird über dem verschobenen Krylow-Raum\begin{eqnarray}\{{x}^{(0)}\}+{{\mathscr{K}}}_{k}(A,{r}^{(0)})\end{eqnarray} mit\begin{eqnarray}{r}^{(0)}=b-A{x}^{(0)}\end{eqnarray} und\begin{eqnarray}{{\mathscr{K}}}_{k}(A,{r}^{(0)})=\{{r}^{(0)},A{r}^{(0)},{A}^{2}{r}^{(0)},\ldots {A}^{k-1}{r}^{(0)}\}.\end{eqnarray} Die wesentliche Idee des Algorithmus’ ist es, x(k) mittels einer orthogonalen Basis des Krylow-Raums \({{\mathscr{K}}}_{k}(A,{r}^{(0)})\) darzustellen, d. h.\begin{eqnarray}{x}^{(k)}={x}^{(0)}+{Q}_{k}{y}^{(k)},\end{eqnarray} wobei Qk = (q(1)q(2)q(k)) ε ℝn×k eine Matrix mit orthonormalen Spalten sei, deren lineare Hülle gerade der Krylow-Raum \({{\mathscr{K}}}_{k}(A,{r}^{(0)})\) ist:\begin{eqnarray}\text{Span}\{{q}^{(1)},{q}^{(2)},\ldots, {q}^{(k)}\}={{\mathscr{K}}}_{k}(A,{r}^{(0)}).\end{eqnarray} (Hieraus folgt sofort, daß q(1) = r(0)/||r(0)||2 gelten muß.) Würde man x(k) mittels einer nicht orthogonalen Basis von \({{\mathscr{K}}}_{k}(A,{r}^{(0)})\) darzustellen, erhielte man ein Verfahren, welches unter Umständen während der Berechnungen zusammenbricht und dann nicht die gesuchte Lösung des Gleichungssystems Ax = b berechnen kann.

Die gesuchte orthogonale Basis berechnet z. B. das Arnoldi-Verfahren. Nach k Schritten des Arnoldi-Verfahrens hat man die Zerlegung\begin{eqnarray}A{Q}_{k}={Q}_{k+1}{H}_{k+1,k}\end{eqnarray} berechnet mit\begin{eqnarray}{H}_{k+1,k}=\left(\begin{array}{ccccc}{h}_{11} & {h}_{12} & \ldots & \ldots & {h}_{1n}\\ {h}_{21} & {h}_{22} & \ldots & \ldots & {h}_{2n}\\ 0 & \ddots & \ddots & & \vdots \\ \vdots & & \ddots & \ddots & \vdots \\ 0 & \ldots & \ldots & {h}_{k,k-1} & {h}_{kk}\\ 0 & \ldots & \ldots & 0 & {h}_{k+1,k}\end{array}\right), {H}_{k+1,k}\in {{\mathbb{R}}}^{k+1,k}.\end{eqnarray}

Im k-ten Schritt des GMRES-Verfahren minimiert man nun\begin{eqnarray}{(b-A{x}^{(k)})}^{T}(b-Ax{y}^{(k)})\end{eqnarray} unter der Nebenbedingung, daß x(k) die Form\begin{eqnarray}{x}^{(k)}={x}^{(0)}+{Q}_{k}{y}^{(k)}\end{eqnarray} für ein y(k) ε ℝk hat. Es folgt, daß y(k) als die Lösung des linearen Ausgleichsproblems\begin{eqnarray}\mathop{\mathrm{lim}}\limits_{y\in {{\mathbb{R}}}^{k}}||\frac{{e}_{1}}{||{r}^{(0)}|{|}_{2}}-{H}_{k+1,k}y|{|}_{2}\end{eqnarray} zu wählen ist, wobei e1 = (1, 0, …, 0)T ε ℝk. Man erhält so das GMRES-Verfahren:

Wähle x(0) ε ℝn.Setze r(0) = bAx(0).Setze h1,0 = ||r(0)||2Setze q(1) = r(0)/h10.Iteriere für k = 0, 1, …   Falls hk+1,k = 0   Dann stop, x(k) ist gesuchte Lösung.   Sonst berechne \begin{eqnarray}\begin{array}{l}{r}^{(k+1)}=A{q}^{(k+1)}\\ {\text{F}\rm{\ddot{u}}\text{r}}\,i=1:k+1\\ \quad \,\,\,{h}_{i,k+1}={({q}^{(i)})}^{T}w\\ \quad \,\,\,{r}^{(k+1)}={r}^{(k+1)}-{h}_{i,k+1}{q}^{(i)}\\ \text{Ende}\,{\text{F}\rm{\ddot{u}}\text{r}}\\ {h}_{k+2,k+1}=||{r}^{{}_{(k+1)}}|{|}_{2}\\ {x}^{(k+1)}={x}^{(0)}+{Q}_{k+1}{y}^{(k+1)}\\ \,\,\,\text{wobei}\min =||\frac{{e}_{1}}{||{r}^{(0)}|{|}_{2}}-{H}_{k+1,k}{y}^{(k+1)}|{|}_{2}\end{array}\end{eqnarray}

Das Abbruchkriterium hk+1,k = 0 folgt aus der Beobachtung\begin{eqnarray}{(b-A{x}^{(k)})}^{T}(b-A{x}^{(k)})=||b-A{x}^{(k)}|{|}_{2}^{2}={h}_{k+1,k}^{2}.\end{eqnarray} Das Ausgleichsproblem (1) kann effizient mittels der Methode der kleinsten Quadrate gelöst werden. In der Praxis muß es nicht in jedem Iterationsschritt gelöst werden; es ist ausreichend, dies einmal am Ende des Algorithmus zu tun, wenn hk+1,k = 0 (bzw. klein genug) ist.

Pro Iterationsschritt sind nur eine Matrix-Vektor-Multiplikation Ap(k) und einige Skalarprodukte durchzuführen; der Gesamtaufwand ist daher insbesondere für sparse Matrizen A sehr gering.

Bei der Berechnung der (k+1)-ten Iterierten wird Information aus allen k vorherigen Schritt benötigt. Der Rechen- und Speicheraufwand wächst also mit k an.

Theoretisch ist bei exakter Rechnung spätestens x(n) die gesuchte Lösung. Da jedoch aufgrund von Rundungsfehlern dies i. a. nicht eintreten wird, und da der Rechen- und Speicheraufwand mit k anwächst, verwendet man das GMRES-Verfahren in der Praxis nicht in der oben angegebenen Form. Man bestimmt vielmehr a priori ein Anzahl m von Schritten, für welche man das GMRES-Verfahren noch gut ausführen kann (hinsichtlich Rechen- und Speicheraufwand), und führt dann m Schritte des Verfahrens durch. Anschließend startet man das GMRES-Verfahren erneut, dieses Mal mit dem berechneten x(m) als neuen Startvektor (man „wirft” also die schon berechneten Vektoren q(1), …, q(m) „weg”). Dieses Vorgehen wiederholt man, bis hk+1,k klein genug ist.

Für das Konvergenzverhalten des Verfahrens, d. h. für eine Aussage, wie schnell die Iterierten x(k) gegen die gesuchte Lösung x konvergieren, ist die Konditionszahl von A von entscheidender Bedeutung. Hat A eine kleine Konditionszahl, so wird die Konvergenz i. a. recht schnell sein. Ist die Konditionszahl von A hingegen groß, so wird die Konvergenz nur sehr langsam sein. In diesem Fall sollte man versuchen, die Konvergenzeigenschaften durch Vorkonditionierung zu verbessern.

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