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

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

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

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

Теорема 5.1. Пусть функция ¦ унимодальнана замкнутом интервале a £ x £ b, а ее минимум достигается в точке x . Рассмотрим точки x и x , расположенные в интервале таким образом, что a < x < x < b. Сравнивая значения функции в точках x и x можно сделать следующие выводы.

1. Если ¦(x ) > ¦(x ), то точка минимума ¦(x) не лежит в интервале (a, x ), т.е. x Î (x , b) (рис. 5.1,а)

Рис. 5.1. Графические иллюстрации к теореме 5.1

2. Если ¦(x ) < ¦(x ), то точка минимума не лежит в интервале (x , b), т.е. x Î (a, x ), (см. рис. 5.1,б).

Примечание. Если ¦(x ) = ¦(x ), то можно исключить оба крайних интервала (a, x ) и (x , b); при этом точка минимума должна располагаться в интервале (x , x ).

Согласно теореме 5.1, которую иногда называют правилом исключения интервалов, можно реализовать процедуру поиска, позволяющую найти точку оптимума путем последовательного исключения частей исходного ограниченного интервала. Поиск завершается, когда оставшийся подынтервал уменьшается до достаточно малых размеров. Несомненным достоинством поисковых методов такого рода является то, что они основаны лишь на вычислении значений функции. При этом не требуется, чтобы исследуемые функции были дифференцируемы; более того, допустимы случаи, когда функцию нельзя даже записать в аналитическом виде.

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

1. этап установления границ интервала, на котором реализуется процедура поиска границ достаточно широкого интервала, содержащего точку оптимума;

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