Grundlagen - Fibonacci Suche

Suchen
Direkt zum Seiteninhalt

Hauptmenü

Grundlagen

1. Unimodalität / Konvexität
Die Funktion y=f(x) von der in einem Intervall x є [a,b] das Minimum gefunden werden soll, muss unimodal sein.

Das heißt, dass  y=f(x) in diesem Intervall streng monoton (fallend bzw. steigend) sein muss und nur ein lokales Minimum auftreten darf.
Ähnliches gilt für mehrdimensionale Funktionen y=f(x1,...,xn).
Auch hier darf in dem untersuchten Gebiet nur ein einziges Minimum auftreten. In diesem Fall spricht man von Konvexität. Dabei ist es so, dass eine Verbindungs-Gerade zwischen 2 beliebigen innerhalb des untersuchten Gebietes liegenden Punkten vollständig innerhalb des Gebietes bleiben muss.



2. Genauigkeit
Bei der Fibonacci-Suche wird zu Beginn festgelegt mit wie viel Schritten das Minimum einer
Funktion y=f(x) in einem Intervall x є [a,b] gefunden werden soll.
Ist m die Anzahl der Suchschritte, so ergibt sich am Ende der Berechnung eine Unsicherheit von



Damit muss m so gewählt werden, dass der mögliche Fehler entsprechend klein wird.
Beispiel:

a    =  5
b   = 15
εm = 0,01
Daus folgt


Da F16 = 987 und F17 = 1597 ist, wird m=15.
Mit m=15 Schritten wird das Minimum der Funktion mit einem Fehler von maximal ±0,0063 bestimmt.

Hinweis:

An den Intervallgrenzen a und b werden bei der Fibonacci Suche die Funktionswerte nicht berechnet!

 
Zurück zum Seiteninhalt | Zurück zum Hauptmenü