Численные методы оптимизации. Рейзлин В.И. - 13 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

Составители: 

Рубрика: 

13
Заметим, что унимодальная функция не обязана быть гладкой или даже
непрерывной.
Из предположения унимодальности следует, что для любых точек
12
,xx
интервала [a, b], таких, что
*
12
x x x
справедливо
21
( ) ( )f x f x
. Аналогично,
если
*
12
,x x x
то
21
( ) ( )f x f x
. Обратно, если
12
xx
и
12
( ) ( )f x f x
, то
*
1
,x x b
а если
12
( ) ( )f x f x
, то
*
2
a x x
. Далее будем считать исследуемую
функцию унимодальной.
2.1.3. Метод деления интервала пополам
Разделим интервал [a, b] на две равные части (рис. 6), а затем каждую из
частей еще на две равные части.
Рис. 6. Иллюстрация к методу половинного деления
Это первый этап поиска минимума. На нем после пяти вычислений функ-
ции (два – на краях и три – внутри интервала [a, b]) интервал неопределенности
сужается вдвое, то есть на этом этапе
. Новый интервал неопределенно-
сти
45
, xx
снова разделим пополам, а затем каждую половину снова пополам.
Теперь значения функции по краям и в его середине уже известны. Поэтому для
завершения поиска на этом этапе требуется вычислить только два значения
функции, после чего интервал неопределенности снова уменьшится вдвое. Это
преимущество рассмотренного метода сохранится и в дальнейшем.
После N вычислений функции коэффициент дробления интервала состав-
ляет
3
2
(0,5) , 5,7,9,...
N
N
(2.2)
Здесь N=5,7,9,…, так как интервал неопределенности, начиная со второго
этапа, уменьшается только после двух вычислений функции.
Из (2.1),(2.2) видно, что метод деления пополам эффективнее, чем общий
поиск.
D
a=x
1
x
4
x
3
x
5
b=x
2

Страницы