Методы Оптимизации Систем Автоматизированного Проектирования

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

Постановка задачи.

Тебуется наути безусловный минимум функции f(x) одной переменной, т.е. такую точку , что .

Стратегия поиска.

Метод относится к последовательным стратегиям и позволяет исключить из дальнейшего рассмотрения на каждой итерации ровно половину текущего интервала неопределенности. Задается начальный интервал неопределенности и требуемая точность.

Алгоритм основан на анализе значений функции в трех точках, равномерно распределенных на текущем интервале (делящих его на четыре равные части). Поиск заканчивается, когда длина текущего интервала неопределенности оказывается меньше установленной величины.

Алгоритм.

Задать начальный интервал неопределенности и требуемую точность .

Вычислить среднюю точку , длину интервала и значение функции в средней точке .

Вычислить точки:,,а также значения функции в этих точках: ,

Сравнить значения и :
а) если < , исключить интервал , положить . Средней точкой нового интервала становится точка : . Перейти к шагу 7.

если , перейти к шагу 6.

Сравнить значения и :
а) если < , исключить интервал , положить . Средней точкой нового интервала становится точка Перейти к шагу 7.

Стр.: ..., 2, 3