Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen]
Mathematik-Online-Lexikon:

Goldene Suche

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Übersicht

Ein lokales Minimum einer stetigen Funktion $ f$ kann mit Hilfe eines Unterteilungsalgorithmus bestimmt werden. Man geht dazu von $ 3$ Punkten $ a<b<c$ aus mit

$\displaystyle f(a) \ge f(b) \le f(c) \,. $

Diese Ungleichungen implizieren, dass mindestens ein lokales Minimum von $ f$ in dem Intervall $ (a,c)$ liegt. Zur Verkleinerung des Intervalls wird $ f$ nun an einem weiteren Punkt $ x$ in dem größeren der Teilintervalle $ (a,b)$ oder $ (b,c)$ ausgewertet. Dann wird einer der Endpunkte durch $ x$ ersetzt, so dass für das neue geordnete Punktetripel $ \{a^\prime,b^\prime,c^\prime\}$ wiederum die für Existenz eines lokalen inneren Minimums hinreichende Ungleichung erfüllt ist. Die Prozedur wird wiederholt, bis eine vorgegebene Genauigkeit erreicht ist.

\includegraphics[width=0.5\linewidth]{Bild_Unterteilung_gold_Schnitt.eps}

Die Abbildung zeigt einige aufeinander folgende Schritte. Dabei wurden die Intervalle in dem optimalen Verhältnis

$\displaystyle r\, : \, (1-r) , \quad r = \frac{\sqrt{5}-1}{2} = 0.61803 \,, $

unterteilt. Der Parameter $ r$ ist die positive Lösung der Gleichung $ r^2 = 1-r$ . Gilt $ \left(c^\prime -a^\prime \right)=r (c-a)$ , so wird durch dieses als goldener Schnitt bekannte Teilverhältnis eine konstante Reduktion der Intervalllänge pro Schritt unabhängig von dem Vergleich $ (x,f(x))$ versus $ (b,f(b))$ erreicht. Für beliebige Startpunkte $ a$ , $ b$ und $ c$ ist die Intervallänge nach n Schritten $ \leq r^{n-1} \left( c-a \right)$ .

Erläuterung:

[Verweise]
  automatisch erstellt am 19.  8. 2013