Метод половинного деления

Метод половинного деления, называемый также методом дихотомии, является процедурой последовательного поиска. Пусть определен отрезок [a₀, b₀], которому принадлежит точка локального минимума x*. Далее для сужения промежутка, содержащего точку экстремума, используем две точки x₁ и x₂, расположенные симметрично на расстоянии δ > 0 от середины отрезка:

Константа δ должна быть меньше допустимой конечной длины отрезка,

Δ_k= b_k- a_k> 0.

Рассчитываем значение функции в этих точках y₁=f(x₁) и y₂=f(x₂) и в зависимости от их соотношения новые границы отрезка, содержащего точку экстремума, [a₁, b₁] будут следующие:

• y₁< y₂, a₁=a₀ и b₁=x₂;

• y₁> y₂, a₁=x₁ и b₁=b₀;

• y₁= y₂, a₁=x1 и b₁=x2.

Название метода половинного деления мотивировано тем, что если величина ε достаточно мала, то длина отрезка (b – a) уменьшается почти вдвое.

Метод квадратичной аппроксимации (метод Пауэлла).

Основан на аппроксимации функции полиномом второго порядка в некоторой окрестности и расчета на его основе координаты точки оптимума.

Пусть известны значения функции в трех точках x₀,x₁,x₂, составляющие соответственно у₀, у₁, у₂. Тогда функцию f(x) можно аппроксимировать полиномом

Оптимальное значение можно оценить по формуле

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

Методы оптимизации многомерных функций.

Далее будем рассматривать алгоритмы оптимизации функции нескольких переменных.

Основные алгоритмы будем рассматривать на примере функции двух переменных вида

Для наглядного изображения таких функций часто используют линии уровня, рис. 13.1.

Дата добавления: 2015-10-29