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

UptoLike

ВУЗ: 

ТПУ | Томск

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

Рубрика: 

14
2.1.4. Метод золотого сечения
Деление интервала на неравные части позволяет найти еще более эффек-
тивный метод. Вычислим функцию на концах отрезка [a, b] и положим
12
, .a x b x
Вычислим также функцию в двух внутренних точках
34
, .xx
Сравним все четыре значения функции и выберем среди них наименьшее
(рис.°7). Пусть, например, наименьшим оказалось f(x
3
). Очевидно, минимум
находиться в одном из прилегающих к нему отрезков. Поэтому отрезок
4
, xb
можно отбросить и оставить отрезок
4
, .ax
Рис. 7. Иллюстрация к методу золотого сечения
Первый шаг сделан. На отрезке
4
, ax
снова надо выбрать две внутрен-
ние точки, вычислив в них и на концах значения функции и сделать следующий
шаг. Но на предыдущем шаге вычислений мы уже нашли функцию на концах
нового отрезка
4
, ax
и в одной его внутренней точке
3
x
. Потому достаточно
выбрать внутри
4
, ax
еще одну точку
5
,x
определить в ней значение функции
и провести необходимые сравнения. Это вчетверо уменьшает объем вычислений
на одном шаге процесса. Как выгодно размещать точки? Каждый раз оставшийся
отрезок делиться на три части и затем отбрасывается один из крайних отрезков.
Обозначим первоначальный интервал неопределенности через D (рис. 8).
Рис. 8. Деление интервала в методе золотого сечения
Так как в общем случае может быть отброшен любой из отрезков
или
42
,xx
то выберем точки
3
x
и
4
x
так, чтобы длины этих отрезков были одинако-
вы:
3 1 2 4
.x x x x
После отбрасывания получится новый интервал неопреде-
ленности длины
D
.

Страницы