MINRES-Verfahren

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von MINRES)
Zur Navigation springen Zur Suche springen
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 englisch minimum residual „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.[1]

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

Eigenschaften des MINRES-Verfahrens

[Bearbeiten | Quelltext bearbeiten]

Das MINRES-Verfahren berechnet iterativ eine Näherungslösung eines linearen Gleichungssystems der Form

.

Dabei ist eine symmetrische Matrix und die rechte Seite.

Hierzu wird die Norm des Residuums im -dimensionalen Krylowraum

minimiert. Dabei ist ein Startwert und .

Genauer definieren wir die Näherungslösungen durch

.

Dabei ist die euklidische Norm im .

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

Konstruktionsidee von MINRES

[Bearbeiten | Quelltext bearbeiten]

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 (zu Beginn meist ein Nullvektor), die rechte Seite und das Residuum .

Man kopiert das Residuum in einen Vektor und nimmt diesen aus obigem Grund als Korrekturrichtung für die Näherungslösung. Dazu berechnet man sein Bild . Dieses Bild will man optimal an das Residuum heranaddieren, sodass dessen Länge kleinstmöglich wird (daher der Verfahren-Name). Dazu rechnet man , mit . Dazu muss sein (Gram-Schmidt). Die zugehörige Näherungslösung für dieses Residuum kennt man: .

Für das neue Residuum erstellt man wieder eine Kopie und berechnet wieder das Bild . Um durch Wiederholung dieses Prinzips das Residuum immer weiter zu verkleinern, möchte man im nächsten Schritt ein Residuum erzeugen, dass auf und senkrecht steht. Da einen Richtungsanteil von enthalten könnte, muss auf orthogonalisiert und analog angepasst werden, damit danach weiterhin gilt. Für wird . So setzt man das über viele Iterationen fort.

Auf diese Weise müsste in der -ten Iteration die Richtung auf Vorgängern orthogonalisiert werden. Lanczos konnte jedoch zeigen, dass bereits auf all diesen Richtungen senkrecht steht, falls nur auf seinen beiden Vorgängern orthogonalisiert (= senkrecht gestellt) wird. Dies liegt an der Symmetrie von (weshalb das Verfahren auch nur im symmetrischen Fall funktioniert).

Algorithmus des MINRES-Verfahrens

[Bearbeiten | Quelltext bearbeiten]

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 ), sondern deren Bilder (unten bezeichnet mit ) ü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 beliebig und berechnet

Dann iterieren wir für die folgenden Schritte:

  • Berechne die durch
falls kleiner als eine vorgegebene Toleranz ist, bricht man an dieser Stelle den Algorithmus mit der Näherungslösung ab, ansonsten berechnet man eine neue Abstiegsrichtung mittels
  • für (der Schritt wird erst ab dem zweiten Iterationsschritt durchgeführt) berechne:

Konvergenzrate des MINRES-Verfahrens

[Bearbeiten | Quelltext bearbeiten]

Im Fall von positiv definiten Matrizen lässt sich die Konvergenzrate des MINRES-Verfahrens ähnlich wie beim CG-Verfahren abschätzen.[2] Im Gegensatz zum CG-Verfahren gilt die Abschätzung allerdings nicht für die Fehler der Iterierten, sondern für das Residuum. Es gilt:

.

Dabei ist die Konditionszahl der Matrix .

Beispiel-Implementierung in GNU Octave / Matlab

[Bearbeiten | Quelltext bearbeiten]
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

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. Christopher C. Paige, Michael A. Saunders: Solution of sparse indefinite systems of linear equations. In: SIAM Journal on Numerical Analysis. Band 12, Nr. 4, 1975.
  2. Sven Gross, Arnold Reusken: Numerical Methods for Two-phase Incompressible Flows. Springer, ISBN 978-3-642-19685-0, Kap. 5.2.