В методе перебора, рассмотренном выше, точки , в которых определяются значения ¦(), выбираются заранее. Если же для выбора очередной точки вычисления ¦() использовать информацию, содержащуюся в уже найденных значениях f(х), то поиск точки минимума можно сделать более эффективным, то есть сократить число определяемых для этого значений ¦().
Фактически все одномерные методы поиска основаны на предположении, что исследуемая функция обладает свойством унимодальности, по крайней мере, в допустимой области. Это позволяет определить, в каком из задуманных двумя точками подинтервалов точка оптимума отсутствует.
Методы поиска, которые позволяют определить оптимум функции одной переменной путем последовательного исключения подинтервалов и, следовательно, путем уменьшения интервала поиска, носят название методов исключения интервалов.
Теорема. Пусть функция f унимодальна на замкнутом интервале а £ x £ b, а ее минимум достигается в точке *. Рассмотрим точки и , расположенные в интервале таким образом, что а<<<b. Сравнивая значения функции в точках и можно сделать следующие выводы.
1. Если ¦ () >¦ (), то точка минимума не лежит в интервале ¦(), то есть *Î(, b) (рис. 5.1, а).
a) б)
Рис. 5.1. Графические иллюстрации к теореме.
2. Если ¦() < ¦(), то точка минимума не лежит в интервале (,b), то есть *Î(a,) (рис.5.1, б).
Примечание. Если ¦() = ¦(), то можно исключить оба крайних интервала (a,) и (,b); при этом точка минимума должна располагаться в интервале (,).
Согласно теореме, которую иногда называют правилом исключения интервалов, можно реализовать процедуру поиска, позволяющую найти точку оптимума путем последовательного исключения частей исходного ограниченного интервала. Поиск завершается, когда оставшийся подинтервал уменьшается до достаточно малых размеров. Несомненным достоинством поисковых методов такого рода является то, что они основаны лишь на вычислении значении функции. При этом не требуется, чтобы исследуемые функции были дифференцируемы; более того, допустимы случаи, когда функцию нельзя далее записать в аналитическом виде.
В процессе применения рассматриваемых методов поиска можно выделить два этапа:
1. этап установления границ интервала, на котором реализуется процедура поиска границ достаточно широкого интервала, содержащего точку оптимума;
2. этап уменьшения интервала, на котором реализуется конечная последовательность преобразования исходного интервала с тем, чтобы уменьшить его длину до заранее установленной величины.
5.1.2.1. Этап установления границ интервала.
На этом этапе сначала выбирается исходная точка, а затем на основе правила исключения строится относительно широкий интервал, содержащий точку оптимума. Обычно поиск граничных точек такого интервала проводится с помощью эвристических методов поиска. В этом случаи (k+1)-я пробная точка определяется по рекуррентной формуле (метод Swann W. H.).
, k=0,1,2,...,
где – произвольно выбранная начальная точка; D - подбираемая некоторым способом величина шага.
Знак D определяется путем сравнения значений ¦(), ¦(+½D½) и ¦(-½D½). Если
¦(-½D½) ³ ¦() ³ ¦(+½D½),
то, согласно предположению об унимодальности, точка минимума должна располагаться правее точки и величина D выбирается положительной. Если изменить знаки неравенств на противоположные, то D следует выбирать отрицательной.
Если же
¦(-½D½) ³ ¦() £ ¦(+½D½),
то точка минимума лежит между -½D½и +½D½ и поиск граничных точек завершен.
Случай, когда
¦(-½D½) £ ¦() ³ ¦(+½D½),
противоречит предложению об унимодальности.
Пример 5.2. Рассмотрим задачу минимизации функции
при заданной начальной точке =30 и величине шага ½D½=5.
Знак D определяется на основе сравнения значений
¦()=¦(30)= 4900
¦(+½D½)=¦(35)= 4225
¦(-½D½)=¦(25)= 5625
Так как,
¦(-½D½) ³ ¦ () ³ ¦(+½D½),
то величина D должна быть положительной, а координата точки минимума * должна быть больше 30. Имеем =+ D = 35. Далее = +2D= 45, ¦(45)= 3025<¦(),
откуда * >35.
= +D=65, ¦(65)=1225< ¦(),
откуда * >45
= +D=105, ¦(105)= 25< ¦(),
откуда * >65
= +D=185, ¦(185)= 7225> ¦().
Следовательно, * <185. Таким образом, шесть шагов вычислений * позволили выявить интервал 65£ * £185, в котором расположена точка *. Эффективность поиска граничных точек зависит от величин шага D. Если D велико получаем грубые оценки координат граничных точек. Если D мало, то может потребоваться большой объем вычислений.
5.1.2.2. Этап уменьшения интервала. Метод деления интервала пополам (дихотомии).
После того как установлены границы интервала, содержащего точку оптимума, можно применить более сложную процедуру уменьшения интервала с целью получения уточненных оценок координат оптимума. Поскольку местонахождение точки оптимума неизвестно, целесообразно предположить, что размещение пробных точек должно обеспечивать уменьшения интервала в одном и том же отношении. Кроме того, в целях повышения эффективности алгоритма необходимо потребовать, чтобы указанное отношение было максимальным. Подобную стратегию иногда называют минимаксной стратегией поиска. Рассмотрим метод деления интервала пополам.
Метод деления интервала пополам является простейшим последовательным методом минимизации (методы минимизации, в которых точки определяются в процессе минимума с помощью найденных ранее значений функции ¦() называются последовательными методами). Он позволяет для любой функции ¦() Î Q[a;b] построить последовательность вложенных отрезков [a;b] É [;] É...É [;] É[;], каждый из которых содержит хотя бы одну из точек минимума * функции. Пусть e>0 – требуемая точность определения точки *. Выбрав dÎ[0;2e] (d может характеризовать погрешность измерений величины , и ограничена снизу возможностями измерительного прибора), построим последовательности {},{},{}и{}, n=0,1,.., используя рекуррентные формулы.
=, =;
; ; (5.1)
=, =, если ¦()< ¦(),
= , =, если ¦()>¦().
а) б)
Рис.5.2. Уменьшение интервала поиска точки минимума методом деления интервала пополам.
Переход от отрезка [;] к отрезку [;] методом деления отрезка пополам иллюстрируется на рисунке 5.2,а , если ¦()< ¦(), и на рисунке5.2,б, если ¦()>¦(). Полагая , находим * с абсолютной погрешностью, не превосходящей величины.
(5.2)
Используя условие, из последнего выражения можно найти необходимое число шагов n для обеспечения требуемой точности e
Однако на практике часто поступают иначе: определив границы отрезка [;], вычисляют
по формуле (5.2) и сравнивают с заданной точностью e.
Пример 5.2. Найти минимальное значение ¦* и точку минимума * функции
на отрезке [1,5;2,0].
Точку * найти с погрешностью e=0,05.
Положим d=0,02< 2e=0,1. Построим последовательность вложенных отрезков [;] по формулам (5.1), записывая результаты вычислений в таблицу 5.2
Таблица 5.2
Значения вложенных отрезков и функций ¦(x).
n
¦()
¦()
Примечание
1.5
2.0
0.25
1.74
1.76
-92.135
-92.096
¦()<¦(), =
1.5
1.76
0.13
1.62
1.64
-91.486
-91.696
¦()>¦(), =
1.62
1.76
0.07
1.68
1.70
-91.995
-92.084
¦()>¦(), =
1.68
1.76
0.04
,точность достигнута
Следовательно, и . Для увеличения скорости сходимости метода величину dÎ(0;2e) целесообразно выбирать как можно меньшей, однако этот выбор ограничен снизу используемым количеством верных десятичных знаков при задании аргумента х. В любом случае d должно быть больше машинного нуля применяемой ЭВМ.
Упражнения.
Методом деления отрезка пополам найти точку минимума * функции ¦() на отрезке [a;b] с точностью e и минимум ¦*.
, в которых определяются значения ¦(
), выбираются заранее. Если же для выбора очередной точки вычисления ¦(
и 
, расположенные в интервале таким образом, что а<
, k=0,1,2,...,
– произвольно выбранная начальная точка; D - подбираемая некоторым способом величина шага.
= 
D=65, ¦(65)=1225< ¦(
= 
D=105, ¦(105)= 25< ¦(
= 
D=185, ¦(185)= 7225> ¦(
;
] É...É [
;
] É[
;
], каждый из которых содержит хотя бы одну из точек минимума 
. Пусть e>0 – требуемая точность определения точки 
}и{
}, n=0,1,.., используя рекуррентные формулы.
=
, 
=
;
; 
; (5.1)
, если ¦(
)< ¦(
, находим 
(5.2)
, из последнего выражения можно найти необходимое число шагов n для обеспечения требуемой точности e
на отрезке [1,5;2,0].
)<¦(
), 
)>¦(
), 
=
)>¦(
), 
=
и 
. Для увеличения скорости сходимости метода величину dÎ(0;2e) целесообразно выбирать как можно меньшей, однако этот выбор ограничен снизу используемым количеством верных десятичных знаков при задании аргумента х. В любом случае d должно быть больше машинного нуля применяемой ЭВМ.
, [-5;-4], e=0,02.
, [1,5;2], e=0,05.
, [-1;0], e=0,1.
, [0,5;1], e=0,05.
, [0;0,5], e=0,02.