Basics - Fibonacci Search

Search
Go to content

Main menu

Basics

1. Unimodality / convexity
The function y = f(x) must be unimodal in the interval  x є [a,b] - in which the minimum is to be determined. This means that y=f(x) in this interval must be strictly monotone (decreasing or increasing) and only a local minimum is allowed.
Something similar is demanded for multi-dimensional functions y=f(x1,...,xn). Again, only one single minimum is allowed in the area under study. In this case we speak of convexity. This means that a connection line between two any points within the study area must remain completely within this area.


2.  Accuracy
At the start of the Fibonacci search it has to be set with how many steps the Minimum / Maximum of a
function y = f (x) in an interval x є [a, b] shall be found.
Is m the number of search steps, at the end of the calculations, it remains an uncertainty



Thus m must be chosen so that the residual error is correspondingly small.

Sample:

a    =  5
b   = 15
εm = 0.01
It follows


Since F16 = 987 and F17 = 1597, m = 15 is selected.
With m = 15 steps, the minimum of the function with an error of within ± 0.0063 is determined.

Note:

At the interval boundaries a and b, the function values are not calculated in the Fibonacci search!

 
Back to content | Back to main menu