Методы исключения интервалов

Существует ряд одномерных методов поиска, ориентированных на нахождение точки оптимума внутри заданного интервала.

Среди этих методов можно выделить методы исключения интервалов.

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

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

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

Правило исключения интервалов

Пусть функция f унимодальна на интервале a<= x<= b, а ее минимум достигается в точке x*.

Рассмотрим точки x₁ и x₂, расположенные в интервале таким образом, что a<x₁<x₂<b.

Сравнивая значения функции в точках x₁ и x₂, можно сделать следующие выводы:

1. Если f(x₁)>f(x₂), то точка минимума f(x) не лежит в интервале (a,x₁), т.е. x*О (x₁,b)



2. Если f(x₁)<f(x₂), то точка минимума не лежит в интервале (x₂,b), т.е. x*О (a,x₂)



3. Если f(x₁)=f(x₂), то можно исключить оба крайних интервала (a,x₁) и (x₂,b), при этом x*О (x₁,x₂)

Согласно правила исключения интервалов, можно реализовать процедуру поиска, позволяющую найти точку оптимума путем последовательного исключения частей исходного ограниченного интервала.

Поиск завершается, когда оставшийся интервал уменьшается до достаточно малых размеров.

Достоинства этих методов:

- устраняется необходимость полного перебора всех допустимых точек;

- методы основаны лишь на вычислении значений функции.

(при этом не требуется, чтобы исследуемые функции были дифференцируемы).

В процессе применения рассматриваемых методов поиска можно выделить два этапа:

1. Этап установления границ интервала, на котором реализуется процедура поиска границ достаточно широкого интервала, содержащего точку оптимума.
2. Этап уменьшения интервала, на котором реализуется конечная последовательность преобразований исходного интервала с тем, чтобы уменьшить его длину до заранее установленной величины.