23. Метод Фибоначчи

Хотя метод золотого сечения и обладает высокой эффективностью, ясно, что он не является оптимальным при заданном числе вычислений целевой функции. Если конструктору заранее известно, что он сможет использовать лишь два значения целевой функции, то он, конечно, предпочтет метод дихотомии, который позволяет уменьшить интервал неопределенности сразу вдвое, а не в 1/0,618 раза, как метод золотого сечения. Если есть возможность в процессе поиска оптимума изменять расположение точек, в которых вычисляются значения целевой функции, то можно соединить преимущества симметричного расположения точек, о которых говорилось выше, с преимуществами метода дихотомии и построить оптимальный алгоритм поиска. Пусть Z_п — длина интервала неопределенности после N-гo шага. Условие симметрии имеет вид

Z_J-2 = Z_J-1 + Z_J, 1<J<N,

а условие вычисления последнего значения целевой функции на полученном методом дихотомии интервале б записывается в виде

Z_N-1=2Z_N-e.

Из этих двух соотношений, возвращаясь назад, можно найти требуемую величину любого промежуточного интервала неопре­деленности и тем самым найти точки, в которых вычисляется целевая функция. Например,

Z_N-3=Z_N-2 + Z_N-1 = (Z_N-1 + Z_N) + Z_N-1 =5 Z_N —2e

и Z_N-4=8Z_N—3e.

Общее выражение для произвольного интервала неопределен­ности имеет вид

Z_N-K = F_K+1Z_N -F_K-1e

где коэффициенты Fj называются числами Фибоначчи и опреде­ляются следующим образом:

F₀= l, F₁ =l, F_K=F_K-1+F_K-2 при К = 2, 3 . . . .

В табл. 5.1 приведены некоторые числа Фибоначчи. В общем слу­чае величину последнего интервала неопределенности можно выразить в виде

В пределе при е0 нижняя граница определяется величиной наименьшего интервала неопределенности, которую можно получить при заданном числе вычислений целевой функции.

Таблица 5.1

K	FK
0	1
1	1
2	2
3	3
4	5
5	8
6	13
7	21
8	34
9	55
10	89
11	144
12	233
13	377
14	610
15	987
16	1597
17	2584
18	4181
19	6765
20	10946

Применяя метод Фибоначчи, прежде всего решают, сколько значений целевой функции N может быть использовано. Затем, зная величину интервала неопределенности, выбирают распределение этих значений N в нем. Так как Z₁=Z₀=l, то сначала вычисляют целевую функцию в точках, расположенных на расстояниях Z₂ от противоположных концов исходного интервала. В этом случае

где е — наименьшее приращение х, при котором значения целевой функции отличимы друг от друга. На следующем шаге выбирают величину смещений Z₃ относительно Z₂.В дальнейшем сохраняют подходящее значение интервала и повторяют процесс до тех пор, пока не будет вычеслено N-ое значение целевой функции.