Рассмотрим следующую задачу условной оптимизации: найти минимум одномерной унимодальной функции (), определенной в замкнутой области допустимых значений =[,],

Числа Фибоначчи и их некоторые свойства.
Числа Фибоначчи задаются следующим рекуррентным уравнением:
 (1)

Числа Фибоначчи ,..., приведены в нижеследующей табл. 1.
Таблица 1    
0123456789...
11235813213455...

Общее выражение для -го числа Фибоначчи можно получить из решения уравнения (1):

При больших значениях членом (-)N+1 можно пренебречь. При этом
 (2)

Отсюда следует, что . Т.е. отношение двух соседних чисел Фибоначчи примерно постоянно и равно .
Алгоритм Фибоначчи.
Алгоритм Фибоначчи относится к классу поисковых методов оптимизации и включает в себя два этапа.
Первый этап состоит из (-1)-й итерации для =1,2,…-1. Рассмотрим схему -й итерации, когда ТИНr=[,]:
  1. Вычисляем величины


  2. Вычисляем значения функции ().
  3. Если , то выполняем присваивания , , . Иначе - выполняем присваивания , ,
Алгоритм Фибоначчи обладает тем свойством, что после выполнения (-1)-й итерации имеет место следующая ситуация: . Т.е. в результате (-1)-й итерации сужение текущего интервала неопределенности не происходит:

Второй этап призван решить по какую сторону от точки лежит точка минимума функции ().
Второй этап выполняется по следующей схеме:
  1. Находим точку =+, где |ТИНN-1| - свободный параметр алгоритма.
  2. Вычисляем значение функции .
  3. Если , то выполняем присваивания . Иначе - выполняем присваивания
В качестве приближенного значения точки минимума с равными основаниями может быть принята любая точка ТИНN.
Некоторые свойства алгоритм Фибоначчи.
Утверждение 1. Для любого [1,-2] алгоритм Фибоначчи обладает следующим свойством: одна из точек , совпадает с одной из точек , (см. рис. 1).
Рис. 1.  К утверждению 1.
Доказательство. Пусть на -й итерации -ситуация б на рис. 1. В соответствии с алгоритмом Фибоначчи причем, очевидно, ТИНr+1. Рассмотрим точку

Подставим сюда значение координаты точки



Аналогично проводится доказательство для случая - ситуация а на рис. 1
Указанное свойство алгоритма Фибоначчи позволяет на каждой итерации (кроме первой) производить испытания только в одной точке.
Утверждение 2. Точки , расположены симметрично относительно концов текущего интервала неопределенности , т.е. расстояние точки до точки равно расстоянию точки до точки или, что то же самое, .
Доказательство. В соответствии с алгоритмом Фибоначчи имеем:



Но из формулы (1) следует, что . Подставляя это в предыдущую формулу, получим

Утверждение 3. В результате любой итерации алгоритма Фибоначчи длина текущего интервала неопределенности уменьшается в раз.
Доказательство. Поскольку (см. утверждения 2), достаточно рассмотреть только один из интервалов ,. Рассмотрим первый из указанных интервалов:
=+(-)-=(-)
Утверждение 4. При достаточно больших в результате одной итерации алгоритма Фибоначчи длина текущего интервала неопределенности уменьшается примерно в раз.
Доказательство. Справедливость утверждения следует из утверждения 3 и из того факта, что при достаточно больших имеем (см. (2)):

Из утверждения 4 следует, что при достаточно больших N алгоритм Фибоначчи практически идентичен алгоритму золотого сечения (см. следующий параграф).
Утверждение 5. В результате итераций алгоритма Фибоначчи длина текущего интервала неопределенности становится равной

 (3)

Доказательство. Из утверждения 3 следует, что:
Поэтому количество итераций , необходимых для нахождения минимума функции с точностью , находится из условия