Метод золотого сечения

На основе минимаксной стратегии более эффективны схемы сокращения интервала неопределенности. Это достигается делением интервала на неравные части.

На рис. 2.6 графически приведены два первых шага сокращения интервала поиска в методе золотого сечения.

Рис. 2.6. Геометрическая иллюстрация метода золотого сечения: а — сокращение интервала неопределенности на начальном шаге; б — сокращение интервача неопределенности на втором шаге.

Рассмотрим сокращение интервала неопределенности.

1. Пусть задан интервал единичной длины.

Точки х, и х₂ выбраны в соответствии с рекомендациями 1 минимаксной стратегии.

Пусть/(х₂)>/(х,), х, =0,4 и х₂=0,6, исключаем интервал [х₂, 1], так как ищем минимум.

2. Рассмотрим интервал [0,х,].

Выберем вторую точку xi в соответствии с рекомендацией 2 минимаксной стратегии и запишем отношение исключаемого интервала ко всей длине интервала, т. е.

Так как в числителе длина исключаемого интервала, то с одной стороны (из числителя) она равна г • (1 — г), а из рисунка г — (1 — г). Исходя из этого равенства запишем уравнение для нахождения г:

Положительный корень этого уравнения т = «о, 61 803.

Схема поиска, при котором пробные точки делятся в гаком отношении, называются методом золотого сечения.

Замечания

1. Схема сокращения интервала неопределенности приведена на рис. 2.7.

Рис. 2.7. Геометрическая иллюстрация сокращения интервала в методе золотого сечения

Длина интервалов от шага к шагу уменьшается в одном и том же отношении г:

2. После п шагов величина интервала.

3. Любой интервал [a, b] может быть сведен к единичному интервалу. Если х е [а, 6], то перейдем к новой переменной.

Перепишем пробные точки с учетом введенной величины г:

4. В методе золотого сечения отношение интервалов постоянно и равно ~ 0,61 803. Однако существует метод Фибоначчи, в котором это отношение меняется как числа последовательности Фибоначчи:

F.

Отношение интервалов в методе равно ——, т. е. {½, 1/3, 2/5, 3/8,.

F"+l.

5/13…}.