Метод дихотомии (половинного деления)

В некоторых источниках [15 ] метод половинного деления отличают от метода дихотомии в выборе интервала. Мы будем придерживаться общепринятого подхода[5, 13, 14]. Название метода объясняется тем, что на каждом следующем шаге описанного алгоритма отрезок, содержащий точку минимума, становится примерно вдвое короче. Искомая длина интервала исследования, в котором лежит искомый оптимум, уменьшается с каждым шагом N почти в два раза.

Алгоритм метода состоит из следующих этапов:

1) делят исходный интервал исследования пополам;

2) вблизи точки деления (по разные ее стороны) подсчитывается дважды значение целевой функции f(x₁), f(x_n), где (x_n - x₁) - наименьший интервал изменения управляющей переменной, при котором становится возможным обнаружить отличие между f(x₁) и f(x_n);

3) используя свойство унимодальных функций, определяют интервал, в котором находится экстремальное значение целевой функции, затем процесс расчета повторяется по аналогичной схеме до тех пор, пока не будет найден оптимум.

Алгоритм метода.

Пусть требуется найти минимум унимодальной функции f(х) на отрезке [ а, b ]и указать точку x_*, в к-рой он достигается.

                                       (34.6)

1. Отрезок [а, b] делят пополам

                                            (35.6)

2. Вблизи его середины (   вычисляют значения функции f(x) в двух точках:

и ,                           (36.6)

 где число ε>0, достаточно мало.

3. Вычисляют значения f(x₁) и f(x₂).

4. Сравнивают значения f(x₁) и f(x₂). Для дальнейших расчетов выбирают тот интервал, который заведомо содержит точку х_*.

Так, если  , это будет отрезок [ а, х₂ ], в противном случае - отрезок [ х₁, b].

5. Повторяют п.п.2-4.

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

               (37.6)

За приближения к f_* принимают значения  при достаточно больших n.

В отличие от метода прямого перебора, в котором эффективность поиска прямо пропорциональна числу расчетов, в методе дихотомии эффективность возрастает с ростом N экспоненциально. Так, если для определения оптимального значения искомой переменной методом прямого перебора требуется около 1000 вычислений, то методом дихотомии - 20. Однако, на классе унимодальных, функций метод половинного деления не является наилучшим. Существуют более эффективные методы, позволяющие при том же количестве вычислений значений функции достигнуть лучшей точности, например, метод Фибоначчи.

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

 

Как ни эффективен метод дихотомии, существует еще более совершенный. В методе Фибоначчи точка деления интервала исследования определяется с каждым новым расчетом (в методе дихотомии необходимо на каждом шаге выполнять два расчета). В интервал исследования попадает предыдущий расчет, и для продолжения поиска достаточно лишь произвести расчет симметрично имеющемуся.

 Пусть задано число расчетов (шагов) N. необходимо их так произвести, чтобы интервал, в котором лежит оптимум, был минимальным. Для этих целей наиболее подходят числа Фибоначчи (1; 2; 3; 5; 8; 13; 21) .

Алгоритм поиска, использующий числа Фибоначчи (поиск минимума):

1. По заданной точности Δ, с которой необходимо найти положение экстремума функции R(x) в интервале [a,b], рассчитывается вспомогательное число N:

         .                                 (38.6)

2. Для получения значения N находится такое число Фибоначчи F_s, чтобы выполнялось неравенство:

     .                              (39.6)

Рисунок 1.6. Метод чисел Фиюоначчи.

 

3. Определяется минимальный шаг поиска по формуле:

                                 .                                     (40.6)

4. Рассчитывается значение функции R(x) в начале интервала, т.е. R(a).

5. Следующая точка, в которой вычисляется значение R(x), находится по формуле:                      

                                               (41.6)

6. Если этот шаг оказался удачным, т.е.R(x⁽¹⁾)< R(a), то следующая точка определяется как

.                                          (42.6)

При R(x⁽¹⁾)> R(a), (шаг неудачный),

                                      (43.6)

7. Последующие шаги выполняются с уменьшающейся величиной шага, которая для i-го шага будет равна

                                  (44.6)

Указанный процесс продолжается до тех пор, пока не будут исчерпаны все числа Фибоначчи в убывающей последовательности:F_s-1-2=F_s-i - F_s-i-1.

Если сравнивать результаты расчета, полученные с помощью методов дихотомии и Фибоначчи, то легко заметить, что для поиска оптимума в методе дихотомии потребовалось выполнить число итераций N-13 с двойным счетом, а при использовании метода Фибоначчи - только с N=21 с одинарным на каждой итерации.

Метод золотого сечения

 

Метод Фибоначчи требует дополнительных расчетов, так как заранее неизвестно число предполагаемых вычислений. Однако существует еще один метод, который совершенно не зависит от числа готовящихся вычислений и почти столь же эффективен, как метод Фибоначчи. Правило - каждый раз ставить точку расчета симметрично на расстоянии, равном от концов интервала исследования.

Деление интервала на неравные части позволяет найти еще более эффективный метод. Вычислим функцию на концах отрезка [ a, b ] и положим a = x ₁, b = x ₂. Вычислим также функцию в двух внутренних точках x ₃, x ₄. Сравним все четыре значения функции и выберем среди них наименьшее. Пусть, например, наименьшим оказалось f (x₃). Очевидно, минимум находиться в одном из прилегающих к нему отрезков. Поэтому отрезок [ x ₄, b ] можно отбросить и оставить отрезок [a, x ₄].

Рисунок 2.6. Метод золотого сечения.

 

На отрезке [a, x ₄] снова надо выбрать две внутренние точки, вычислив в них и на концах значения функции и сделать следующий шаг. Но на предыдущем шаге вычислений мы уже нашли функцию на концах нового отрезка [a, x ₄] и в одной его внутренней точке x ₄. Потому достаточно выбрать внутри [a, x ₄] еще одну точку x₅ определить в ней значение функции и провести необходимые сравнения. Это вчетверо уменьшает объем вычислений на одном шаге процесса.

Каждый раз оставшийся отрезок делиться на три части и затем отбрасывается один из крайних отрезков.

Обозначим первоначальный интервал неопределенности через D.

 

Рисунок 3.6. Определение «золотого сечения».

 

Так как в общем случае может быть отброшен любой из отрезков Х₁,Х₃ или Х₄,Х₂ то выберем точки Х₃ и Х₄ так, чтобы длины этих отрезков были одинаковы:

x₃-x₁=x₄-x₂.                                               (45.6)

После отбрасывания получится новый интервал неопределенности длины D′. Обозначим отношение     буквой φ:

.                                   (46.6)

Далее продолжим процесс аналогично. Для этого интервал D′ разделим подобно интервалу D, то есть положим

 ,                                         (47.6)

где  - следующий интервал неопределенности. Но  по длине равен отрезку, отброшенному на предыдущем этапе, то есть

.                                    (48.6)

Поэтому получим:

.                             (49.6)

Это приводит к уравнению

                                            (50.6)

или, что то же

                                .

Положительный корень этого уравнения дает

 .                          (51.6)

Т.е., примерно в 1,62 раза меньшая часть меньше большей части. Или меньшая часть составляет примерно 38%, а большая часть – 62% длины исследуемого интервала.

В качества сравнения преимуществ и недостатков метода Фибоначчи над остальными методами прямого поиска приведем табл.6.1. Как видно из таблицы совсем не эффективен метод оптимального пассивного поиска. Метод Фибоначчи по эффективности превосходит метод деления пополам и почти одинаков с методом золотого сечения.

 

Таблица 1.6. Сравнительная характеристика методов по длине отрезка локализации и оценке погрешности

Метод поиска	Длина отрезка локализации	Величина гарантированной оценки погрешности
Оптимальный пассивный поиск
Метод деления отрезка пополам (N – четное, величиной δ пренебрегаем)
Метод Фибоначчи

Эффективность методов, также характеризуется числом итераций, при которой необходимо достичь определенной точности ε. Сравнить эффективность метода Фибоначчи с другими методами по этому критерию можно по таблице 6.2,

Таблица 6.2. Сравнительная характеристика методов по количеству итераций для достижения определенного ε.

Метод прямого поиска	Число N при заданном ε
	ε=10^-1	ε=10^-2	ε=10^-3	ε=10^-4	ε=10^-5
Оптимальный пассивный поиск	9	99	999	9999	99999
Метод деления отрезка пополам	6	12	18	26	32
Метод Фибоначчи	5	10	15	19	24
Метод золотого сечения	5	10	15	20	24

 

Как видим из приведенных характеристик, метод Фибоначчи является по большинству описанных критериев предпочтительным методом при решении задач, связанных с нахождением экстремумов функции на заданном интервале.