Quelltext der Seite MINRES-Verfahren

[[Datei:Minres illustration de.svg|mini|Ein Vergleich der Norm des Fehlers sowie des Residuums beim [[CG-Verfahren]] (blau) und dem MINRES-Verfahren (grün). Die verwendete Matrix stammt aus einem 2d-[[Randwertproblem]].]]

Das '''MINRES-Verfahren''' (von {{enS}} '''''min'''imum '''res'''idual'' „minimales Residuum“) ist ein [[Krylow-Unterraum-Verfahren]] zur iterativen Lösung von symmetrischen linearen Gleichungssystemen. Es wurde 1975 von den Mathematikern [[Christopher Conway Paige]] und [[Michael Alan Saunders]] vorgeschlagen.<ref>{{Literatur | Autor=Christopher C. Paige, Michael A. Saunders | Titel=Solution of sparse indefinite systems of linear equations | Sammelwerk=[[SIAM Journal on Numerical Analysis]] | Band=12 | Nummer=4 | Datum=1975}}</ref>

Im Unterschied zum [[CG-Verfahren]] wird beim MINRES-Verfahren nicht vorausgesetzt, dass die Matrix [[Definitheit|positiv definit]] ist, nur die Symmetrie der Matrix wird zwingend vorausgesetzt.

== Eigenschaften des MINRES-Verfahrens ==
Das MINRES-Verfahren berechnet iterativ eine Näherungslösung eines linearen Gleichungssystems der Form
: <math>Ax = b</math>.

Dabei ist <math>A\in\mathbb{R}^{n\times n}</math> eine [[symmetrische Matrix]] und <math>b\in\mathbb{R}^n</math> die rechte Seite.

Hierzu wird die Norm des Residuums <math>r(x) := b - Ax</math> im <math>k</math>-dimensionalen [[Krylowraum]]
: <math>V_k = x_0+\operatorname{span}\{r_0, Ar_0\ldots,A^{k-1}r_0\}.</math>
minimiert. Dabei ist <math>x_0\in\mathbb{R}^n</math> ein Startwert und <math>r_0 := r(x_0)</math>.

Genauer definieren wir die Näherungslösungen <math>x_k</math> durch
: <math>x_k := \mathrm{argmin}_{x\in V_k} \|r(x)\|</math>.
Dabei ist <math>\|\cdot\|</math> die [[euklidische Norm]] im <math>\mathbb{R}^n</math>.

Wegen der Symmetrie von <math>A</math> ist es dabei im Gegensatz zum [[GMRES-Verfahren]] möglich, diesen Minimierungsprozess rekursiv durchzuführen. Im <math>k</math>-ten Schritt ist jeweils nur der Rückgriff auf die Iterierten aus den letzten beiden Schritten nötig (kurze Rekursion).

== Konstruktionsidee von MINRES ==

Krylov-Unterraum-Verfahren beschränken sich darauf, nur Vektoren aus Matrix-Vektor-Produkten mit der Systemmatrix zu benutzen. Das hat Vorteile, weil die Matrix dazu nicht explizit, sondern nur als Funktion für das Matrix-Vektor-Produkt verfügbar sein muss. Zu Beginn sind die einzigen bekannten Vektoren die aktuelle Näherungslösung <math>x_0</math> (zu Beginn meist ein Nullvektor), die rechte Seite <math>b</math> und das Residuum <math>r_0 = b - A \cdot x_0</math>. 

Man kopiert das Residuum in einen Vektor <math>p_0</math> und nimmt diesen aus obigem Grund als Korrekturrichtung für die Näherungslösung. Dazu berechnet man sein Bild <math>s_0 = A \cdot p_0</math>. Dieses Bild will man optimal an das Residuum heranaddieren, sodass dessen Länge kleinstmöglich wird (daher der Verfahren-Name). Dazu rechnet man <math>r_1 = r_0 - \xi \cdot s_0</math>, mit <math>r_1 \perp s_0</math>. Dazu muss <math>\xi = \langle s_0,r_0 \rangle/\langle s_0,s_0 \rangle</math> sein (Gram-Schmidt). Die zugehörige Näherungslösung <math>x_1</math> für dieses Residuum kennt man: <math>x_1 = x_0 + \xi \cdot p_0</math>. 

Für das neue Residuum erstellt man wieder eine Kopie <math>p_1</math> und berechnet wieder das Bild <math>s_1 = A \cdot p_1</math>. Um durch Wiederholung dieses Prinzips das Residuum immer weiter zu verkleinern, möchte man im nächsten Schritt ein Residuum <math>r_2</math> erzeugen, dass auf <math>s_0</math> und <math>s_1</math> senkrecht steht. Da <math>s_1</math> einen Richtungsanteil von <math>s_0</math> enthalten könnte, muss <math>s_1</math> auf <math>s_0</math> orthogonalisiert und <math>p_1</math> analog angepasst werden, damit danach weiterhin <math>s_1 = A \cdot p_1</math> gilt. Für <math>s_1 := s_1 - \tau \cdot s_0</math> wird <math>p_1 := p_1 - \tau \cdot p_0</math>. So setzt man das über viele Iterationen fort.

Auf diese Weise müsste in der <math>i</math>-ten Iteration die Richtung <math>s_i</math> auf <math>i-1</math> Vorgängern <math>s_1,\dotsc,s_{i-1}</math> orthogonalisiert werden. Lanczos konnte jedoch zeigen, dass <math>s_i</math> bereits auf all diesen Richtungen senkrecht steht, falls <math>s_i</math> nur auf seinen beiden Vorgängern <math>s_{i-1},s_{i-2}</math> orthogonalisiert (= senkrecht gestellt) wird. Dies liegt an der Symmetrie von <math>A</math> (weshalb das Verfahren auch nur im symmetrischen Fall funktioniert).

== Algorithmus des MINRES-Verfahrens ==
Anmerkung: Das MINRES-Verfahren ist vergleichsweise komplizierter als das algebraisch äquivalente Conjugate Residual Verfahren. Im Folgenden wurde daher ersatzweise das Conjugate Residual (CR) Verfahren niedergeschrieben. Es unterscheidet sich insoweit von MINRES, dass in CR nicht wie bei MINRES die Spalten einer Basis des Krylov-Raums (unten bezeichnet mit <math>p_k</math>), sondern deren Bilder (unten bezeichnet mit <math>s_k</math>) über die Lanczos-Rekursion orthogonalisiert werden. Es existieren effizientere und präkonditionierte Varianten mit weniger AXPYs. Vgl. dazu mit dem englischsprachigen Artikel.

Zunächst wählt man <math>x_0\in\mathbb{R}^n</math> beliebig und berechnet
: <math>r_0 = b - A x_0</math>
: <math>p_0 = r_0</math>
: <math>s_0 = A p_0</math>

Dann iterieren wir für <math>k=1,2,\dots</math> die folgenden Schritte:

* Berechne die <math>x_k,r_k</math> durch
: <math>\alpha_{k-1} = \frac{ \langle r_{k-1}, s_{k-1} \rangle}{ \langle s_{k-1}, s_{k-1} \rangle } </math>
: <math> x_k = x_{k-1} + \alpha_{k-1} p_{k-1} </math>
: <math> r_k = r_{k-1} - \alpha_{k-1} s_{k-1} </math>
: falls <math>\|r_k\|</math> kleiner als eine vorgegebene Toleranz ist, bricht man an dieser Stelle den Algorithmus mit der Näherungslösung <math>x_k</math> ab, ansonsten berechnet man eine neue Abstiegsrichtung <math>p_k</math> mittels
: <math>p_k \leftarrow s_{k-1}</math>
: <math>s_k \leftarrow As_{k-1}</math>
* für <math>l=1,2</math> (der Schritt <math>l=2</math> wird erst ab dem zweiten Iterationsschritt durchgeführt) berechne:
:: <math>\beta_{k,l} = \frac{\langle s_k, s_{k-l} \rangle}{ \langle s_{k-l}, s_{k-l} \rangle}</math>
:: <math>p_k \leftarrow p_k - \beta_{k,l} p_{k-l}</math>
:: <math>s_k \leftarrow s_k - \beta_{k,l} s_{k-l}</math>

== Konvergenzrate des MINRES-Verfahrens ==
Im Fall von positiv definiten Matrizen lässt sich die Konvergenzrate des MINRES-Verfahrens ähnlich wie beim CG-Verfahren abschätzen.<ref>{{Literatur | Autor=Sven Gross, Arnold Reusken | Titel=Numerical Methods for Two-phase Incompressible Flows | Verlag=Springer | ISBN=978-3-642-19685-0 | Kapitel=Kap. 5.2}}</ref> Im Gegensatz zum CG-Verfahren gilt die Abschätzung allerdings nicht für die Fehler der Iterierten, sondern für das Residuum. Es gilt:
: <math>\|r_k\| \le
2\left(\frac{\sqrt{\kappa(A)}-1}{\sqrt{\kappa(A)}+1}\right)^k\|r_{0}\|</math>.

Dabei ist <math>\kappa(A)</math> die [[Kondition (Mathematik)|Konditionszahl]]
der Matrix <math>A</math>.

== Beispiel-Implementierung in GNU Octave / Matlab ==
<syntaxhighlight lang="matlab">
function [x,r] = minres(A,b,x0,maxit,tol)
  x = x0;
  r = b - A*x0;
  p0 = r;
  s0 = A*p0;
  p1 = p0;
  s1 = s0;
  for iter=[1:maxit]
    p2 = p1;p1 = p0;
    s2 = s1;s1 = s0;
    alpha = r'*s1/(s1'*s1);
    x += alpha*p1;
    r -= alpha*s1;
    if (r'*r < tol^2)
      break
    end
    p0 = s1;
    s0 = A*s1;
    beta1 = s0'*s1/(s1'*s1);
    p0 -= beta1*p1;
    s0 -= beta1*s1;
    if iter > 1
      beta2 = s0'*s2/(s2'*s2);
      p0 -= beta2*p2;
      s0 -= beta2*s2;
    end
  end
end
</syntaxhighlight>

== Einzelnachweise ==
<references />

{{SORTIERUNG:Minresverfahren}}
[[Kategorie:Numerische lineare Algebra]]