МЕТОДЫ ОПТИМИЗАЦИИ ЗФО НП 15.03.04; 27.03.04 Лектор: канд. физ.-мат. наук, доцент Смирнова Людмила Алексеевна
Практическое занятие №3 Тема: Одномерная оптимизация Численная реализация метода дихотомии
Постановка задачи Определение. Унимодальной называется функция, имеющая на заданном отрезке единственный экстремум. Требуется найти точку минимума x * унимодальной функции f(x) на интервале [ а, b ]. Свойство унимодальной функции Пусть f(x) - унимодальная на Тогда, если если Таким образом, на основании вычисленных значений функции можно указать отрезок, в котором находится точка минимума (локализовать эту точку).
В методе результаты каждого вычисления используются при выборе точки следующего вычисления функции. Алгоритм метода 1. Исходный интервал L 0 = [ а, b ] делят пополам. 2. Вблизи точки деления (по разные ее стороны) дважды определяют значение целевой функции в точках 3. Используя свойство унимодальности, определяют интервал, в котором находится экстремальное значение целевой функции и отбрасывают тот интервал, где экстремум заведомо не лежит, уменьшая тем самым интервал неопределенности L 0. Процесс расчета повторяют пор, пока не будет получен интервал L n, где L n < 2, содержащий точку оптимума.
Алгоритм метода Шаг 1. Задаются количество итераций l ; N=2l, точность приближения e; полагают номер итерации k = 1. Шаг 2. На k - й итерации вычисляются границы расчетного интервала и значения функции в этих точках Шаг 3. Выбираются границы нового расчетного интервала
Алгоритм метода Шаг 4. Проверяется условие окончания вычислений : либо по числу итераций либо по длине интервала неопределенности 2 e. Если это условие выполняется, то определяются: - итоговый отрезок локализации точки минимума, - точка минимума, - значение функции в точке минимума Конец счета. Если условие окончания НЕ выполняется, то полагают ; переходят к шагу 2.
Номер итерации k Середина интервала L k-1 Левая граница расчетного интервала Правая граница расчетного интервала Значение функции на левой границе Значение функции на правой границе Выбранный интервал неопределенности L k Длина интервала неопределенности L k 0 - 1 3 5 37 [1; 3] 2 1 2 1,95 2,05 1,644 2,446 [1; 2,05 ] 1,05 2 1,525 1,475 1,575 1,680 1,270 [1,475 ; 2,05 ] 0,575 3 1, 7625 1,7125 1,8125 1,004 1,082 [1,475 ; 1,8125 ] 0,3375 4 1,644 1,594 1,694 1,211 1,017 [1,594;1,8123] 0,2183 5 1,703 1,653 1,753 1,072 1,005 [1,653;1,8123] 0,159 Задание 4 (КР1). Найти минимум функции заданной на интервале [1; 3], методом дихотомии, с точностью e = 0.1 Формулы границ расчетного интервала на k -й итерации: Аналитическое решение задачи
СПАСИБО ЗА ВНИМАНИЕ
