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.
Algorithmus
|

Animation: Minimumsuche nach dem Verfahren des Goldenen Schnitts
|
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 dem Konzept der Prozeduren höherer Ordnung lässt sich die Minimumsuche natürlich schnell zur Suche lokaler Extrema verallgemeinern:
Hinweis: Die zu untersuchende mathematische Funktion wird als Lambda-Term in einem Interaktionsfenster eingegeben, z.B.:
(lambda (x) (* 3 (sin (* 2 x))))
Zurück zur Binären Suche.