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

Метод поиска, реализующий процедуру выбора точек испытаний по формулам (3.8)—(3.9) (см. предыдущий пост) коэффициентами tk*, которые вычисляются из выражений (3.37), называется методом Фибоначчи. Это название возникло в связи с тем, что стратегия поиска оптимального решения х* по данному методу, как нетрудно видеть, связана с использованием чисел Фибоначчи (3.29).

На первом этапе, который соответствует первому шагу поиска (k = 0), эквидистантно от концов априорного интервала неопределенности [a, b] проводится пара испытаний в точках, определяемых N-м и (N — 1)-м числами Фибоначчи:

x11 = а + (b — a) UN-1/uN+1; (3.38)
x21 = а + (b — a) UN/uN+1;

Согласно условию унимодальности функций Q (х) перед вторым этапом происходит сокращение интервала неопределенности по информации о ее значениях в точках x11 и x21: если Q (x11) < Q (x21), то a1 = а и b1 = x21, в противном случае а1 = x11 и b1 = b.

Второй этап поиска включает в себя (N — 3) итерационных шага k = 1, 2, …, N — 3, на каждом из которых в интервале неопределенности [аk, bk] рассматривается пара испытаний, расположение которой задается следующими формулами:

x1k+1 = ak + (bk— ak)uN-k-1/uN-k+1, (3.39)

x2k+1 = ak + (bk— ak)uN-k/uN-k+1. (3.40)

При проведении испытаний по формулам (3.39)— (3.40) на каждом шаге второго этапа (k = 1, 2, …, N — 3) необходимо заново вычислять только одну координату для точки нового испытания (x1k+1 иди x2k+1).

Пусть на k-м шаге имеем Q (x1k) < Q (x2k). Из условия унимодальности функции Q (х) на (k + 1)-м шаге будет исследоваться уже интервал [ak+1, bk+1], где ak+1 = ak, bk+1 = х2k, внутри которого находится точка x1k. На (k + 1)-м шаге из выражения (3.40) можем записать

x2k+1 = ak+1 + (bk+1 — ak+1)uN-k/uN+1-k = ak + (x2k — ak)uN-k/uN-k+1.

Подставим в полученное выражение значение x2k из (3.40):

x1k+1 = ak + (bk — ak) uN-k-1/uN-k+1.

Откуда, учитывая (3.39), получаем, что

x1k+1 = x1k.

Что и требовалось показать. Аналогично доказывается, что при Q (x1k) ≥ Q(x2k) имеем x1k+1 = x2k.

После проведения (N — 1)-го испытания необходимо решить, по какую сторону от точки x1N-3 (x1N-3), находящейся внутри интервала, неопределенности [аN-2, bN-2], лежит точка истинного минимума х*.



Рис. 3.2. Первые четыре шага поиска минимума унимодальной функции по методу Фибоначчи

Для этого последнее N-e испытание проводится вблизи от точки предыдущего испытания в точке (x1N-3 — δ), что позволяет Определить апостериорный интервал неопределенности [aN, bN]. Этим заканчивается третий этап поиска по методу Фибоначчи.

Для нечетного числа испытаний N длина апостериорного интервала неопределенности, получаемого с помощью метода Фибоначчи, равна:

lN (F2) = (b — a)/uN. (3.41)

Подставляя оптимальнее решение t0 из (3.36) в (3.34), для апостериорного интервала неопределенности при нечетном числе испытаний N можем записать:

bN — aN = (b-a)(uN+1uN+2 — uNuN-1)/(uN+1)

На рис. 3.3 показана зависимость отношения длин апостериорных интервалов неопределенности методов поиска F1 и F1 от допустимого числа испытаний N:

lN (F1)/lN (F2) = uN/2N/2.

Из приведенной зависимости видно, что метод Фибоначчи F2 на классе унимодальных функций является более эффективным, чем метод деления пополам F1. Так, например, при N = 14 апостериорный интервал неопределенности, полученный по методу F2, приблизительно в 5 раз меньше апостериорного интервала неопределенности, гарантированного методом F1.

Недостаток метода Фибоначчи заключается в том, что в нем априори необходимо задавать число испытаний N, так как на первом этапе поиска требуется вычислять N-oe и (N — 1)-ое числа Фибоначчи для определения параметра t0. В связи о этим рассмотрим экстремальную задачу (3.15)—(3.17), но введем при этом дополнительное требование о том, что на каждой итерации коэффициенты tk сохраняют постоянное значение t*:

tk = t* = const, k = 0, 1, 2, …, N — 1.



Рис. 3.3. Зависимость отношения критериев эффективности метода деления пополам и метода Фибоначчи от числа испытаний N



Рис. 3.4. Блок схема поиска минимума по алгоритмам, реализующим метод Фибоначчи и метод золотого сечения

Тогда экстремальная задача (3.3) выбора наилучшего метода F* при выполнении условий (3.10), (3.12) и (3.45) сводится к следующей задаче оптимизации:

min (1 — t*)N. (3.46)

при условии, что

0 ≤ t* < 1/2; (3.47)

t2* — 3t* + 1 = 0. (3.48)

Из равенства (3.48) получаем, что t*= (3 ±√5)/2.

Но в силу ограничения (3.47) оптимальным решением экстремальной задачи (3.46)—(3.48) является параметр:

t* = (3 — √5)/2 = 0,381966010.


Оставить комментарий





Статистика

Рейтинг@Mail.ru