Методы оптимизации. Харчистов Б.Ф. - 39 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

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

Рубрика: 

39
Метод дихотомии (половинного деления)
В данном случае общее количество вычислений
f
(
x
) чет-
ное, т.е. ,,2,1,2
"== l lN
на
j
-м шаге (
j
-й итерации) произво-
дится пара вычислений
)(
1
j
x
и
)(
2
j
x
, отстоящих на расстояни и
2/
ε
по обе стороны от середины текущего отрезка локализации
],[
)1()1(
−−
jj
ba
. Если
)(
1
j
f ≤
)(
2
j
f
, то отбрасывается часть отрезка,
расположенная справа от
)(
2
j
x
; если
()
jj
ff
2
)(
1
>
, то отбрасывается
часть отрезка, расположенная слева от
)(
1
j
x
.
Используются два условия окончания вычислений:
а) выполнение заданного количества вычислений
N
;
б) достижение заданно й величины
δ
уменьшения отрезка лока-
лизации.
Итак, алгоритм поиска минимума унимодальной функции
методом дихотомии заключается в следующем.
1. Задаются
N
(либо
δ
) и
ε
, полагается
j
=1.
2. На
j
-й итерации вычисляются
,
2
)(
2
1
,
2
)(
2
1
)1()1()(
2
)1()1()(
1
εε
++=−+=
−−−−
jjjjjj
bax bax
).(),(
)(
2
)(
2
)(
1
)(
1
jjjj
xff xff ==
Если
)(
1
j
f ≤
)(
2
j
f
, то ,
)1()(
−
=
jj
aa
)(
2
)(
jj
xb =
.
Если
)(
1
j
f >
)(
2
j
f
, то
)(
1
)(
jj
xa =
,
)1()(
−
=
jj
bb
.
3. Проверяется условие окончания вычислений:
а)
j
=
N
/2 либо б) .
0
2
δ
≤
L
L
j
Если оно выполняется, то определяются итоговый отрезок
локализации, оценки точки минимума
x
∗
и величины минимума
)(
**
xff =
, и вычисления завершаются.
Если условие не выполняется, то полагается 1
+= jj
и

Страницы