Метод половинного деления как метод оптимизации

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

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

Дана функция . Необходимо найти , доставляющий минимум (или максимум) функции на интервале с заданной точностью , т.е. найти

.

Запишем словесный алгоритм метода.

1. На каждом шаге процесса поиска делим отрезок пополам, - координата середины отрезка .

2. Вычисляем значение функции в окрестности вычисленной точки , т.е.
.

3. Сравниваем и и отбрасываем одну из половинок отрезка (рис. 1).

§ При поиске минимума:

§ Если , то отбрасываем отрезок , тогда . (рис. 1.а)

§ Иначе отбрасываем отрезок , тогда . (рис. 1.б)

§ При поиске максимума:

§ Если , то отбрасываем отрезок , тогда .

§ Иначе отбрасываем отрезок , тогда .

4. Деление отрезка продолжается, пока его длина не станет меньше заданной точности , т.е. .

Схема алгоритма метода представлена на рис 2.

На рис 2:

- константа,

При выводе – координата точки, в которой функция имеет минимум (или максимум), – значение функции в этой точке.