MoinMoin!

Irgendwie verstehe ich den letzten Schritt des Fibonacci-Algorithmus nicht ganz. Das merkwürdige ist, dass ich denke, dass ich ihn damals in der Vorlesung komplett verstanden habe.

Wie gesagt, geht es um den letzten Schritt. Da haben wir nun ein Intervall, dass in zwei Teile geteilt wird: [latex]l_{N-1}=\frac{F_0}{F_2}L_{N-2}=\frac{1}{2}L_{N-2}[/latex], d.h. das sieht so aus:
|----|----| 0 1/2 1
Wie beantwortet man nun die Frage, in welchem Intervall (entweder [0, 1/2] oder [1/2, 1]) sich das Optimum befindet? In dem Beispiel auf Seite F7 sind die eingezeichneten Kästchen irgendwie verwirrend (an welcher Stelle muss die neue Messung durchgeführt werden?) und im "Text" ist auch nichts erklärt. In den Schritten zuvor gab es ja immer zwei Punkte und nicht nur einen.

Ich vermute mal, die Mitte des Intervalls soll als angenommenes
Optimum zurückgegeben werden (weil man in der Anwendung
z.B. eine Zahl braucht und nicht ein Intervall, in dem sie drinliegt).
Von diesem Wert weiß man dann, dass er höchstens [latex]\alpha L_1/2[/latex]
vom tatsächlichen Optimum abweicht.

Ja, so dachte ich mir das ja eigentlich auch. So richtig haut das aber nicht hin. Im Skript steht ja, dass die Genauigkeit, also die größe des Intervals, in dem das Optimum liegt, [latex]\alpha=\frac{1}{F_N}[/latex] beträgt.

Jetzt sei N=3 und der Einfachheit L_1=1. Dann ist [latex]l_1=\frac{F_1}{F_3}=\frac{1}{3}[/latex], [latex]L_2=L_1-l_1=\frac{2}{3}[/latex] und [latex]l_2=\frac{F_0}{F_2}L_2=\frac{1}{2}\cdot\frac{2}{3}=\frac{1}{3}[/latex].

L_1 |----|----|----| 0 1/3 2/3 1 L_2 |----|----| 0 1/3 2/3
Jetzt folgern wir, das Optimum sei bei 1/3. Dann ist dass Intervall, in dem das Optimum liegen kann aber 2/3 lang und nicht wie im Skript steht [latex]\alpha=\frac{1}{F_3}=\frac{1}{3}[/latex]. Irgendwo fehlt bei mir also noch ein Schritt, der in der Tabelle auf Seite F7 auch eingezeichnet ist. Daraus erschließt sich mir aber leider nicht, wie das funktionieren soll.

Ja, du hast recht, die Beschreibung des letzten Schritts ist nicht
im Skript. Da mir auch ein paar andere Sachen nicht ganz klar
waren, hab ich mal in dem angegebenen Buch nachgesehen
("Optimization: Theory and Practice" von Gordon S. Beveridge).
Aus dem scheint er alles über die klassischen Optimierungsverfahren
zu haben (alle Formeln finden sich dort erklärt und ohne Fehler [22]).

Dort steht zum letzen Schritt der Fibonacci-Suche:

This final experiment should not be positioned at precisely the same
point as before (obviously) as no new information will be gained. To
obtain the accuracy [latex]\alpha=1/F_N[/latex] (*) one must apply the
dichotomous concept and place the last experiment very close to the
remaining valid experiment, "close" being defined as in … This permits
the last experiment to be used to select the location of the optimum to
within [latex]\frac{1}{2}L_{N-1}[/latex]. If the last experiment is not
run in a dichotomous fashion, (*) is invalid.

Danke!