Fibonacci-Suche und Goldene-Schnitt-Suche

Hallo,

es geht mir um das numerische Auffinden von Minima.

kann jemand nochmal für Dumme erklären, wo der Vorteil der Fibonacci-Suche gegenüber der binären Suche ist? Warum nimmt man ausgerechnet Fibonacci-Zahlen?

Ich las, dass die Fibonacci-Suche "im Grenzwert" zur Goldenen-Schnitt-Suche wird. Was heißt "im Grenzwert"? Und welche Vorteile hat die Goldene-Schnitt-Suche wiederrum gegenüber der Fibonacci-Suche?

Danke
fibofibo

Herbststurm

Hi

Da mir das Forum hier schon sehr stark geholfen hat, mag ich etwas zurück geben

@Topic
Das ist eigentlich gar nicht so kompliziert. In der Numerik kommt der goldene Schnitt öfters vor. Was dieser ist kannst du z.B. im Wiki Eintrag dazu sehr schön nachlesen.

Eine Möglichkeit ein Minima einer Funktion zu finden ist die Goldener Schnitt Suche. Die Idee ist die, dass du das Minimumm über eine Intervall Schachtelung (das ist eine Folge von Intervallen, bei der bei jedem Folgenglied die Länge des Intervalls kleiner wird, bis man im Rahmen eines numerischen Fehlers, das Minimum eingequetscht hat) findest, wie z.B. auch bei der Nullstellensuche via dem Bisektionsverfahren. Da hast du auch gleich die Antwort zu einer deiner Fragen. Die binäre Suche ist ein Algorithmus zur Beschreibung von Intervallschachtelungen, sprich viel weitreichender als "nur" die Goldene Schitt Suche.

Man nimmt sich bei der Minima Suche via Intervallschachtelung ein Tripel $(a,b,c)$ her und und ändert dies von Schritt zu Schritt derart, dass der mittlere Punkt des neuen Intervalls diejenige Abszisse ist, so dass der zugehörige Funktionswert am besten sich dem Minimum annähert. Damit steht die Grundidee und das Problem ist nun, dass hier offen gelassen ist, wie diese Intervalle konkret konstruiert werden. Man kann nun relativ leicht mathematisch zeigen (wenn du das nicht nachrechnen kannst, kann ich es dir hier vorrechnen), dass das beste Intervall für diese Schachtelung durch den goldenen Schnitt gegeben ist (Siehe das erste Bild bei Wiki zum goldenen Schnitt).

Der goldene Schnitt kommt öfters vor. Was ich zum Beispiel auch sehr nett finde ist, dass die Konvergenzordung des Sekantenverfahrens zur Nullstellenbestimmung (das ist eine schwächere Form des Newton Verfahrens), eine superlineare Konvergenz zeigt. Dies meint, dass die Ordnung gerade auch dem goldenen Schnitt entspricht

Der Namen Fibonacci-Suche als Synonym für die Goldene Schnitt Suche ist gut gewählt. Die Fibonacci Folge ist eine rekursiv definierte Folge, bei der jeweils zwei aufeinander folgende Folgenglieder addiert werden. Trivialerweise damit hochgradig divergent. Die Folge welche aber aus dem Quotienten zweier aufeinander folgender Fibonacci Zahlen gebildet wird, die konvergiert aber und zwar gegen den goldenen Schnitt. Quotient ist das wichtige Wort. Obig meinte ich ja, dass das Verhältnis des Tripels im goldenen Schnitt steht. Numerisch ist also die Frage, wie beim Tripel $(a,b,c)$ ein neuer Punkt $x$ konstruiert wird. Der Ansatz ist, dass der mittlere Punkt gegeben ist über das Verhältnis

$\dfrac{b-a}{c-a} =: w, ~ \dfrac{c-b}{c-a} = 1-w$

Mache dir mal geometrisch klar was das heißt Dann ist der nächste Punkt $x$ natürlich auch als Verhältnis formulierbar

$\dfrac{x-b}{c-a} =:z$

Wenn du das nun durchrechnest, kommst du relativ leicht auf die Bestimmungsgleichung $w^2-3w+1=0$ und jetzt sieh dir davon mal die Lösungen an und vergleiche mit dem goldenen Schnitt

Falls du magst, habe ich den C Code zur Implementierung der Goldenen Schnitt Suche.

Gruß

Jester

Aber den Knackpunkt hast Du jetzt nicht verraten, nämlich warum goldener schnitt und nicht was anderes. Ich mach das mal.

Zunächst sollte man sich klar machen, dass, sebst wenn man eine konvexe Funktion f minimiert, für drei Stellen (a,b,c) die Werte zu kennen nicht hilft, rauszufinden ob das Minimum nun in (a,b) oder in (c,d) liegt. Man benötigt zusätzlich zu den beiden Randwerten zwei Werte im Inneren. Insgesamt also vier Stellen (a,b,c,d). Ist nun f(b) < f(c) so liegt das Minimum im Intervall (a,c) sonst in (b,d). Das Problem ist jetzt, dass man in jedem Schritt zwei innere Werte wählen muss, die das Intervall möglichst gleichmäßig unterteilen (sonst konvergiert man nicht schnell). Allerdings muss man die Funktioon f an beiden diesen Stellen auswerten, was ggf. Teuer ist. Durch die spezielle Wahl bei der Goldener-Schnitt-Suche ist es stets so, dass man drei der vier Werte schon aus dem vorherigen Schritt kennt, also nur einen einzigen Wert neu bechnen muss. Gleichzeitig schrumpft der Bereich schön gleichmäßig, sodass das Verfahren schnell konvergiert.

Zusammenfassung: das verfahren garantiert, dass die suche schnell konvergiert und dennoch die funktion in jedem suchschritt nur einmal ausgewertet werden muss.

Herbststurm

Jetzt hast du die Denkaufgabe dabei heraus genommen. Ich habe bewusst nur den Ansatz hingeschrieben. :p

Gruß

Jester

Herbststurm schrieb:

Jetzt hast du die Denkaufgabe dabei heraus genommen. Ich habe bewusst nur den Ansatz hingeschrieben. :p

Gruß

Tut mir leid. Aber offensichtlich haben wir ein unterschiedliches Verständnis davon was ein Ansatz ist. ich lese in deine, text im wesentlichen "der goldene schnitt ist ganz toll und kommt oft vor. Man kann beweisen dass das so am besten ist." Ich sehe nicht, wie jemand, der auf dem Niveau fragt, sich daraus den nötigen Zugang rausarbeiten soll. Noch dazu nebst falscher Spur mit Tripeln (a,b,c)...

Ich glaube das überfordert den OP ein bisschen. Wie mans nun genau nachrechnet hab ich ja auch nicht hingeschrieben, und das ist sicher eine gute Übung, da gebe ich Dir recht.