Метод деления отрезка пополам

Метод деления отрезка пополам – это многоэтапное применение метода прямого поиска с небольшими коэффициентами сужения интервалов неопределенности.

В методе прямого поиска при K _C = 100 потребуется N = 200 вычислений целевой функции. Попробуем уменьшить интервал неопределенности не сразу в 100 раз, а в два этапа (на каждом этапе в 10 раз).

Пример 1 (в 2 этапа): а) KC1 = 10, N1 = 20. б) KC2 = 10, N2 = 20. KC = KC1×KC2 = 100, N = N1 + N2 = 40. Вывод: в данном случае количество вычислений уменьшилось в 5 раз по сравнению с методом прямого поиска, следовательно, скорость расчетов увеличилась в 5 раз.

Пример 2 (в 3 этапа):

а) K _C1 = 5, N₁ = 10. б) K _C2 = 5, N₂ = 10. в) K _C3 = 4, N₃ = 8.

K _C = K _C1 ×K _C2 ×K _C3 = 100, N = N ₁ + N ₂ + N ₃ = 28.

В данном случае количество вычислений уменьшилось более чем в 7 раз по сравнению с методом прямого поиска.

Вывод: чем меньше коэффициент, тем меньше требуется вычислений целевой функции. Минимальное значение K _C = 2.

Алгоритм метода: 1) Исходный отрезок делится на 4 равных части, т.е. вычисляются точки x1, x2, x3. 2) Вычисляется значение функции в этих точках f1,f2,f3. 3) а) Если f1< f2 и f1< f3, то B = x2; б) Если f2< f1 и f2< f3, то A = x1, B = x3; в) Если f3< f1 и f3< f2, то A = x2.

4) Если выполняется условие ½ B – A ½ < e, то расчеты прекращаются и точкой минимума считается точка x* = x ₂.

Берется новый полученный интервал и вновь делится, но на каждом следующем интервале берутся только две точки, т. к. середина отрезка уже известна.

;

Сравним методы прямого поиска и деления отрезка пополам:

1) Метод прямого поиска:

K _C = 1000 Þ N = 2000. K _C = 1000000 Þ N = 2000000.

2) Метод деления отрезка пополам:

K _C = 1000 Þ N = 20. K _C = 1000000 Þ N = 40.

Достоинство метода: он значительно эффективней (быстрее) предыдущего метода.

Недостатки метода: нет гарантии, что этот метод найдет глобальный минимум неунимодальной функции. Для унимодальной функции этот метод всегда находит глобальный минимум или максимум.

Метод деления отрезка пополам – это многократное применение метода прямого поиска с коэффициентом сужения 2 (K _C = 2).

Дата добавления: 2014-01-13