Main menu

**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, ...*Note*

*In some publications, the number sequence is started but not with F _{0} = 0 but with F_{1} = 1. Both are correct.*

The individual values can not only recursive, but can also be calculated directly with the formula

More

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).