One- and multidimensional Fibonacci search
- very easy -
Introduction / Preliminary remarks
About the Fibonacci numbers, there are many papers in the literature, therefore, discusses the features in
this article only briefly. In the literature and on the Internet. many treatises can be found. Many descriptions
of search using Fibonacci numbers assume that starting from an interval [a, b] within which the minimum
or maximum of a function to be determined, will be determined according to certain rules with m given
search steps more and more smaller intervals in where the minimum or maximum is sought. This process
is of course correct, but the derived algorithm is rather complex and for a multi-dimensional search highly
impractical. As a by-product of my diploma thesis (about 35 years ago) that dealt with time-optimal control,
I had designed an algorithm, which extremely simplified the Fibonacci search and easily applicable to
multidimensional problems made.
Short description of the Fibonacci numbers
For Fibonacci numbers is the following formation rule:
and in general for the m-th term of a sequence
This results in the infinite sequence of numbers: 0, 1 , 1, 2, 3, 5, 8, 13, 21, ...
In some publications, the number sequence is started but not with F0 = 0 but with F1 = 1. Both are correct.
The individual values can not only recursive, but can also be calculated directly with the formula
The foundations for an effective search algorithm are shown on the following pages first. Thereafter, the algorithm for the one-dimensional search is developed and based on this extended to n-dimensional search.
After that follows a brief derivation of the Fibonacci formula Eq. (2).