Konjugiertes Gradientenverfahren für quadratische Funktionen
Im Fall einer quadratischen Funktion der Gestalt
.
Für das konjugierte Gradientenverfahren wählen wir zunächst einen Startpunkt und berechnen den Gradienten an dieser Stelle.
Wir nehmen an, dass nicht schon ein kritischer Punkt von ist, also gilt.
Dann gibt es eine Richtung mit der Eigenschaft .
Wir untersuchen nun das Verhalten von auf dem Halbstrahl, der bei beginnt und in Richtung von verläuft.
Dazu betrachten wir die Funktion einer Variablen , .
Ist ein Einheitsvektor (Länge 1), so gibt die Schrittweite an, um die wir uns von entfernen.
Man nennt nun eine Abstiegsrichtung für im Punkte , falls gilt.
Ist eine Abstiegsrichtung, so gilt für alle hinreichend kleinen .
Eine sinnvolle Wahl für die Schrittweite ergibt sich, wenn man minimiert.
Wir setzen nun und bestimmen das Minimum der Funktion .
Es ist offensichtlich, dass eine Abstiegsrichtung liefert, denn .
Beispiel: Zur Minimierung der Funktion
Der Gradient an dieser Stelle ist und wir müssen von aus in die Richtung minimieren.
D.h. wir berechnen das Minimum der Funktion ,
welches wir in der Nullstelle der Ableitung finden.
Wir erhalten einen neuen Iterationspunkt und berechnen den Gradienten an dieser Stelle .
Als nächstes müssen wir ein zu konjugiertes Tupel bestimmen und dann die Funktion ausgehend von entlang dieser Richtung minimieren, d.h. das Minimum der Funktion bestimmen.
Man kann zeigen, dass der neue Iterationspunkt dann schon das gesuchte strenge Minimum der quadratischen Funktion ist.
Ein zu konjugiertes Tupel erhalten wir, indem wir
mit
setzen.
Zusammenfassend erhalten wir den folgenden Algorithmus:
|
Wegen und
erhält man die (eindeutig bestimmte) exakte Schrittweite
.
In dieser Gleichung ist der Nenner grösser Null (da positiv definit ist)
und der Zähler kleiner Null (da Abstiegsrichtung ist).
Man erhält also wie gewünscht einen Wert grösser Null für .
Beispiel (Fortsetzung):
Unser neuer Iterationspunkt ist nun
.
Der Gradient an dieser Stelle ist .
Für berechnen wir und müssen nun von aus
in die zu konjugierte Richtung minmieren,
d.h. das Minimum der Funktion bestimmen.
Dazu berechnen wir die Nullstelle der ersten Ableitung .
Der Punkt ist dann das gesuchte strenge Minimum von .
Der Gradient an dieser Stelle ist .
Für berechnen wir und müssen nun von aus
in die zu konjugierte Richtung minmieren,
d.h. das Minimum der Funktion bestimmen.
Dazu berechnen wir die Nullstelle der ersten Ableitung .
Der Punkt ist dann das gesuchte strenge Minimum von .