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⁽⁰⁾, 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 Q_k = (q⁽¹⁾q⁽²⁾ … 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⁽¹⁾ = r⁽⁰⁾/||r⁽⁰⁾||₂ 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 e₁ = (1, 0, …, 0)^T ε ℝ^k. Man erhält so das GMRES-Verfahren:

Wähle x⁽⁰⁾ ε ℝⁿ.Setze r⁽⁰⁾ = b − Ax⁽⁰⁾.Setze h_1,0 = ||r⁽⁰⁾||₂Setze q⁽¹⁾ = r⁽⁰⁾/h₁₀.Iteriere für k = 0, 1, …   Falls h_k+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 h_k+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 h_k+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⁽ⁿ⁾ 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⁽¹⁾, …, q^(m) „weg”). Dieses Vorgehen wiederholt man, bis h_k+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.