Direkt zum Inhalt

Lexikon der Mathematik: Fibonacci-Algorithmus

ein Verfahren zur Approximation eines bestimmten Punktes \(\bar{x}\) in einem endlichen Intervall [a1, b1]. Dabei kann \(\bar{x}\) z. B. Nullstelle einer stetigen Funktion oder Extremalpunkt einer unimodalen Funktion f : [a1, b1] → ℝ sein.

Es wird eine Anzahl von Iterationspunkten erzeugt, unter denen schließlich einer das gesuchte \(\bar{x}\) mit einer vorgegebenen Genauigkeit annähert. Die benötigte Anzahl von Iterationen liegt mit der Kenntnis der Approximationsgüte vor.

Man beginnt mit dem Intervall [a1, b1] und berechnet in der k-ten Iteration aus den aktuellen Intervallrändern ak und bk neue Intervallpunkte

\begin{eqnarray}\begin{equation}x_{k}\ :=\ a_{k}+\frac{f_{n-k-1}}{f_{n-k+1}}\cdot (b_{k}-a_{k})\end{equation}\end{eqnarray}

und

\begin{eqnarray}\begin{equation}y_{k}\ :=\ a_{k}+\frac{f_{n-k}}{f_{n-k+1}}\cdot (b_{k}-a_{k}).\end{equation}\end{eqnarray}

Hier bezeichnet fj die j-te Fibonacci-Zahl (Fibonacci-Folge).

Nach Auswertung der Zielfunktion f in xk und yk werden ak+1 und bk+1 nach gewissen Kriterien aktualisiert, und zwar entweder zu ak+1 := xk und bk+1 := bk, oder zu ak+1 := ak und bk+1 : = yk.

Wesentliche Eigenschaft des Verfahrens ist, daß die Länge des neuen Intervalls um den Faktor

\begin{eqnarray}\begin{equation}\frac{f_{n-k}}{f_{n-k+1}}\end{equation}\end{eqnarray}

verkürzt wird. Deshalb läßt sich die notwendige Anzahl von Iterationen vor Beginn des Algorithmus bestimmen.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos