Methode der konjugierten Gradienten
Zur Lösung des linearen Gleichungssystems mit n Unbekannten
mit der symmetrischen und positiven Koeffizientenmatrix A wird nun genau der entgegengesetzte Weg zu dem oben beschrieben Verfahren gewählt: Es wird das zu dem Gleichungssystem analoge Minimalproblem
betrachtet, wobei der Vektor x gesucht wird, für den F minimal wird. Die Strategie ist, dass man mit einem Startvektor x0 beginnt und eine Folge von iterierten Vektoren x1, x2, x3, ... mit dem Ziel erzeugt, dass diese sich immer mehr dem Lösungsvektor nähern, der F zum Minimum macht. Dies hat sich zu einem umfangreichen Spezialgebiet der numerischen Mathematik entwickelt, auf das hier nicht eingegangen werden soll. Die Stichworte dazu, für die man auch im Internet zahlreiche Seiten findet, lauten u. a.: "Krylow-Unterraum-Verfahren", "Methode des steilsten Abstiegs" und "Verfahren der konjugierten Richtungen". Hier soll ausschließlich die "Methode der konjugierten Gradienten" betrachtet werden, die eine gewisse Sonderstellung unter den Verfahren dieser Klasse einnimmt.
Bei der "Methode der konjugierten Gradienten" nähert man sich dem Minimum von F, indem man auf der Fläche F(x), beginnend an einem beliebigen Startpunkt jeweils in die Richtung "wandert", dass man sich dem Minimum auf optimale Weise nähert, wobei das Wort "optimal" für jeden Schritt so zu verstehen ist, dass man aus den zu diesem Zeitpunkt verfügbaren Informationen eine Richtung wählt, die theoretisch garantiert, dass nach n Schritten der Minimalpunkt (und damit die Lösung des Gleichungssystems) erreicht wird.
Auf die Herleitung des nachfolgend angegebenen Algorithmus wird hier verzichtet, eine sehr schöne kompakte Darstellung findet man z. B. im PDF-Skript von Hagemann und Schenk (Universität Basel).
Gleichungssystem:
Anfangswerte:
Iterationsschritt i = 0:
Vorbereitung des Iterationsschrittes i = 1:
Iterationsschritt i = 1:
Vorbereitung des Iterationsschrittes i = 2:
Residuenvektor = Nullvektor, Prozess beendet.
|
|
In Kurzfassung kann die Methode der konjugierten Gradienten wie folgt formuliert werden, rechts daneben findet man jeweils die Rechnung für das Gleichungssystem, das oben für das Stabwerk formuliert wurde:
- Gestartet wird mit einem beliebigen Vektor x0 (dies kann auch ein Nullvektor sein), mit dem ein erster "Residuenvektor" r0 berechnet wird, der auch als erster "Korrekturvektor" p0 verwendet wird:
- Jeder Iterationsschritt i folgt folgender Strategie: Der Vektor xi+1 wird durch Korrektur des Vektors xi in die Richtung pi berechnet, wobei die "Schrittlänge des pi-Schrittes" durch einen Faktor λi bestimmt wird:
- Als Vorbereitung des folgenden Iterationsschrittes werden ein neuer Residuenvektor ri+1 und ein neuer Korrekturvektor pi+1 berechnet:
- Es folgt der nächste Integrationsschritt nach den oben angegebenen Formeln. Der Prozess konvergiert, wenn Rundungsfehler keine Rolle spielen, nach n Iterationsschritten (i = 0, 1, 2, ... , n-1). Die Methode der konjugierten Gradienten kann also sowohl als Iterationsverfahren als auch als direktes Verfahren gesehen werden, das wie die Eliminationsverfahren das Ergebnis nach einer endlichen Anzahl von Operationen liefert.
Man beachte die typische Besonderheit der iterativen Verfahren: Die Koeffizientenmatrix A wird ausschließlich für die Operation "Matrix · Vektor" verwendet (die Bildung des Produkts Api muss natürlich in jedem Iterationsschritt einschließlich der Vorbereitung des folgenden Schrittes nur einmal ausgeführt werden). Die Matrix A selbst wird nicht verändert (das für die Eliminationsverfahren typische Problem des "Fill-in" gibt es bei Iterationsverfahren nicht). Deshalb können die Vorteile dünn besetzter Matrizen voll genutzt werden.
Andererseits sind die iterativen Verfahren nicht so stabil wie die direkten Verfahren. Man vergleiche hierzu die beiden Seiten "Testrechnungen mit iterativen Verfahren (1)" und "Testrechnungen mit iterativen Verfahren (2)". Eine Verbesserung kann durch "Präkonditionierung" erreicht werden, das oben vorgestellte Verfahren kann z. B. sehr einfach modifiziert werden zum "Präkonditionierten Konjugierte-Gradienten-Verfahren".
|