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

Как известно, золотым сечением отрезка называется деление отрезка на две неравные части так, чтобы отношение длины всего отрезка к длине большей части равнялось отношению длины большей части к длине меньшей части отрезка. Легко показать, что золотое сечение отрезка производится двумя точками y и z, симметричными относительно середины отрезка, т.е. золотое сечение должно обладать следующими свойствами: 1) Если количество пробных точек принимается равным двум, то их следует размещать на одинаковых расстояниях от середины интервала.

2) Пробные точки должны размещаться в интервале по симметричной схеме таким образом, чтобы отношение длины исключаемого подынтервала к величине интервала поиска оставалось постоянным.

3) На каждой итерации процедуры поиска должно вычисляться только одно значение функции в получаемой точке.

Руководствуясь этими требованиями (1-3), рассмотрим симметричное расположение двух пробных точек на исходном интервале единичной длины, которое показано на рисунке 7.2. (Выбор единичного интервала обусловлен соображениями удобства). Пробные точки отстоят от граничных точек интервала на расстоянии . При таком симметричном расположении точек длина остающегося после исключения интервала всегда равна независимо от того, какое из значений функции в пробных точках оказывается лучшим. Предположим, что исключается правый подынтервал. На рисунке 7.3 показано, что оставшийся подынтервал длины содержит одну пробную точку, расположенную на расстоянии от левой граничной точки. Для того чтобы симметрия поискового образца сохранялась, расстояние должно составлять -ю часть длины интервала (которая равна ). При таком выборе следующая пробная точка размещается на расстоянии, равной -й части длины интервала, от правой граничной точки интервала (рис. 7.4).

Величину выбираем из условия - отношение длины исключаемого подынтервала к величине интервала поиска оставалось постоянным.

(7.2)

Отсюда следует, что при выборе в соответствии с условием симметрия поискового образца, показанного на рисунке 7.2, сохраняется при переходе к уменьшенному интервалу, который изображен на рисунке 7.4. Решая это квадратное уравнение, получаем

(7.3)

откуда положительное решение . Схема поиска, при которой пробные точки делят интервал в этом отношении, известна под названием поиска с помощью метода золотого сечения. Заметим, что после первых двух вычислений значений функции каждое последующее вычисление позволяет исключить подынтервал, величина которого составляет -ю долю от длины интервала поиска. Следовательно, если исходный интервал имеет единичную длину, то величина интервала, полученного в результате N вычислений значений функции, равна . Можно показать, что поиск с помощью метода золотого сечения является асимптотически наиболее эффективным способом реализации минимаксной стратегии поиска.

В общем случае отрезка [a,b]

Нетрудно также проверить, что точка y производит золотое сечение отрезка , а точка z производит золотое сечение отрезка . На этом свойстве, позволяющем на каждой итерации вычислить значение функции лишь в одной пробной точке, и основан алгоритм золотого сечения.

Алгоритм метода золотого сечения.

Рассмотрим задачу

Исходные данные – отрезок, содержащий точку максимума, - параметр окончания счета.

1. , , . ; ; ; .

2. Если , то перейти к шагу 4.

3. , ; ; . ; , перейти к шагу 5.

4. , ; ; ; ; .

5. Если , то , конец.

6. , перейти к шагу 2.

Пример 7.3. Найти точку максимума функции на отрезке ; .

, .

.

.

; .

Итерация 1

Так как , то , ; ; ;

; ; .

Итерация 2

Так как , то , ; ; ; ; ; .

Итерация 3.

Так как , то , ; ; ; ; ; .

Итерация 4

Так как , то , ; ; ; ; ; , следовательно, .

Как было отмечено выше, на каждой итерации метода золотого сечения производится лишь одно вычисление значения функции. При этом длина полученного в результате одной итерации отрезка составляет , где - длина исходного интервала.

Если сравнить методы дихотомического поиска и золотого сечения, используя в качестве критерия эффективности относительное уменьшение исходного интервала F, то

т.е. метод золотого сечения оказывается более эффективным [4].