Extremwertsuche nach dem Verfahren des Goldenen Schnitts
Die binäre Suche muss nicht zwingend zur Intervallhalbierung führen.
Wir betrachten die Extremwertsuche nach dem Verfahren des Goldenen Schnitts zunächst für die Suche eines lokalen Minimums:
Animation: Minimumsuche nach dem Verfahren des Goldenen Schnitts
Algorithmus (Minimumsuche):
Lege ein Suchintervall durch zwei äußere Intervallgrenzen fest.
Zerlege dieses Suchintervall durch einen zweimaligen Goldenen Schnitt in 3 Teilintervalle.
Berechne die Funktionswerte an beiden Schnittstellen.
Das neue Suchintervall wird aus der Schnittstelle mit dem größeren der beiden Funktionswerte und einer der äußeren Intervallgrenzen derart gebildet, dass die Schnittstelle mit dem kleineren Funktionswert eingeschlossen wird.
Führe im neuen Suchintervall den Goldener Schnitt durch, der wieder zu 3 Teilintervallen führt.
Wiederhole das Verfahren solange, bis das Suchintervall einer hinreichend kleinen ε-Umgebung genügt.
Der Funktionswert eines Arguments aus dieser ε-Umgebung entspricht dem gesuchten Minimum.
Implementation
Mit einem kleinen Trick lässt sich ein und dieselbe Suchfunktion sowohl für lokale Minima als auch für lokale Maxima einsetzen. Der Vergleich der Funktionswerte wird mit einem Korrekturfaktor geführt, der lediglich die Werte oder annehmen kann, z.B.:
if (k*fkt(li) > k*fkt(re)) ...
Dieser Faktor kann als Parameter übergeben werden und hat die gleiche Wirkung wie die Umkehr des Relationszeichens bei einem herkömmlichen Vergleich.
