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

Основная идея данного метода – сокращение числа n_ш вычислений функции на каждом шаге (кроме первого)до 1 (минимально возможного значения) с дальнейшим использованием при поиске минимума второй пробной точки каждого шага, которая попадает внутрь нового доверительного интервала. Несмотря на то, что доверительный интервал сокращается при этом существенно менее, чем в два раза (в отличие от дихотомии), данный метод за счёт уменьшения n_ш работает в общем значительно быстрее.

Золотым сечением отрезка [ a,b ]называется такое его деление промежуточной точкой с, при котором выполняется соотношение (рис 10.12 а), где ξ – коэффициент золотого сечения.

а б

Рис 10.12. Прямое и обратное золотые сечения отрезка

Выразим через xи отрезок ab отрезки ас и cb: аc = x ab; cb= x ac = x² ab.

Из условия аc + cb = ab после подстановки данных выражений и сокращения на аb получим следующее квадратное уравнение относительно x:

x² + x - 1 = 0.

Решая его, находим корни:

Отбрасывая отрицательный корень, получим искомую величину отношения:

Разбивать отрезок [ a,b ]можно не только в прямом, но и в обратном направлении – от b к a. Аналогичная точка d лежит симметрично с относительно средней точки интервала (a+b)/2(рис.10.12 б).

Величину отношения ad/ab получим, вычитая x из 1:

Точки d, с, задающие обратное и прямое разбиение отрезка в золотом сечении, обладают следующими свойствами.

1. Если отбросить часть отрезка [ а,d ], то с – золотое сечение оставшейся части [ d, b ].

2. Если отбросить часть отрезка [ с, b ], то d – золотое сечение оставшейся части [ a, с ].

Данные свойства можно доказать непосредственной подстановкой значений

Допустим, необходимо с точностью e найти минимум унимодальной функции F (x) на [ a,b ].

Предварительные действия (Шаг 0).

Доверительный отрезок принимаем равным заданному: а ₀ = а, b ₀ = b.

Шаги i (i>0) выполняются в цикле при выполнении условия (b_i - a _i > e).

Шаг 1. 1. Расчет положения двух пробных точек:

х ₂ =а ₀ + x(b ₀ - а ₀ )» а ₀ + 0,618 (b ₀ - а ₀ );

х ₁ = (b₀ + а ₀ ) - x ₂ » а ₀ + 0,382(b ₀ - а ₀ ).

2. Расчет значений функций F (x ₁) и F (x ₂).

3. Анализ значений функции в точках х₁, х₂ и изменение доверительного отрезка по аналогии с дихотомией:

а) при F (x ₁) ³ F (x ₂) принимаем: a ₁ = х ₁, х ₁ = х ₂, b ₁ = b ₀,

б) при F (x ₁) < F (x ₂) принимаем: a ₁ = а ₀, х ₂ = х ₁, b ₁ = х ₂.

4. Проверка окончания цикла: если (b ₁ - a ₁) > e -продолжение цикла, иначе - выход.

Шаги i (i>1). Из предыдущей итерации (i -1) известно одно значение функции F (x) во внутренней точке х доверительного отрезка [ a_{i- 1}; x _{i- 1}]. Поэтому для сокращения достаточно ввести только одну новую пробную точку.

1. Расчет положения новой пробной точки: х¢ = (b_{i- 1} + а_{i- 1}) - х, расчет значения функции F (x¢).

2. Упорядочение пробных точек х, х¢ и значений функции в них:

если (х < х¢), то { х ₁ = х; F (x ₁)= F (x); х ₂ = х¢; F (x ₂)= F (x¢) };

иначе { х ₁ = х¢; F (x ₁)= F (x¢); х ₂ = х; F (x ₂)= F (x) }.

Пункты 3 и 4 совпадают с шагом 1.

Скорость сходимости и точность метода. Так как на каждом шаге длина доверительного отрезка сокращается в t = 1/x» 1,618 раз, то длина[ a ₁ ,b ₁] связана с длиной [ a, b ] следующим образом: b ₁- a ₁ = x (b ₀- a ₀ ) =x (b - a).

По аналогии для произвольного шага k длина доверительного отрезка: b_k - a_k = x ^k (b - a).

Процесс заканчивается, когда выполняется неравенство b_k - a_k = x ^k (b - a) £ e.

Отсюда следует, что номер шага k, на котором достигается требуемая точность e, равен k (e)= ]log_t (b - a)/e [ = ]log_t M [.

На первом шаге выполняется два вычисления целевой функции, на всех последующих n_ш= 1. Поэтому полное число необходимых вычислений F (х)

п (e) =1 + n_ш k (e) = 1+] log _t ((b - a)/e)[.

Зависимость e (п) находим из равенства (b -a)/e = t ^{( n-1 )}: e (п) = (b - a)x ^(n-1).

Асимптотические скорости роста зависимостей e(n) и n (e) для метода золотого сечения:

e (n) = O[(b-a)x ⁿ];

п(e) = O [log _t ((b - a)/e)] =O [log _t M ].

Данный метод является ещё более быстрым по сравнению с дихотомией, так как в формуле для п (e)основание логарифма t» 1,618 < 2. Как и дихотомия, он является регулярным. Также он принадлежит к группе так называемых симметричных методов.

Последовательный метод определения экстремума называют симметричным, если на каждом i –том шаге поиска экстремума на доверительном отрезке [ a_i,b_i ] уже известна одна пробная точка x ₁ и значение целевой функции F (x ₁) в ней. Вторая (новая) пробная точка x ₂определяется как симметричная x ₁ относительно средней точки (a_i+b_i)/2 доверительного интервала: x ₂= a_i+ b_i - x ₁.

Метод дихотомии не является симметричным.

Замечание 1. Известная пробная точка x ₁ в симметричном методе может быть как меньше, так и больше значения (a_i+b_i)/2.

Замечание 2. Свойство симметрии метода позволяет значительно упростить расчёт новых пробных точек. Формула x ₂= a_i+ b_i - x ₁ позволяет рассчитать вторую пробную точку x₂ независимо от того, как первая точка x ₁расположена относительно средней точки доверительного отрезка (до или после).

Замечание 3. В практических расчетах при большом числе итераций из-за накопления погрешностей вычисления положение пробной точки x ₁ на отрезках [ a_i,b_i ] может значительно отклоняться от золотого сечения. При этом, соответственно, полное число необходимых вычислений целевой функции п (e) будет увеличиваться. Для предотвращения этого явления, положение точки x с известным значением функции можно периодически уточнять по формулам х=a+ x(b-a)либо х=a+ (1-x)(b-a) в зависимости от того, к какому из данных значений она ближе.

Пример 1. Найти минимум функции F (х) = х ² – 2 х на доверительном отрезке [0,2;2]по методу золотого сечения при заданной точности e =0,5.

Решение.

Шаг 0. а ₀ = а, b ₀ = b.

Шаг 1. Расчет положения двух пробных точек: х ₂ =а ₀ + x(b ₀ – а₀)»1,3124; х ₁ = (b ₀ +а ₀)- х ₂)» 0,8876. Значения функции в них: F (x₁) = -0,9874; F (x ₂) = -0,7768. Так как F (x₁)< F (x ₂), то отбрасываем часть доверительного отрезка [ x ₂ ;b ₀].Получаем новый доверительный отрезок [ а ₁ ;b ₁] = [0,2;1,3124].

b ₁ -а ₁ = 1,1124 > e = 0,5;продолжаем поиск.

Шаг 2. Границы доверительного отрезка а ₁ = 0,2; b ₁ = 1,3124. На нем известно значение функции в точке х» 0,8876, F (x) = -0,9874.

Новая пробная точка: х¢ = (b ₁ +а ₁) - 0,8876» 0,6248. Значение функции в новой точке х¢: F (x¢) = -0,8592.

Поскольку х¢<х, то принимаем х ₁ = х¢; F (x ₁) = F (x¢); х ₂ = х; F (x ₂) = F (x).

Так как F (x ₁) > F (x ₂), то отбрасываем часть доверительного отрезка [ a ₁ ;x ₁].Получаем новый отрезок [ а ₂; b₂] = [0,6246;1,3124].

b ₂ -а ₂ = 0,6878 > e = 0,5;продолжаем поиск.

Шаг 3. а ₂ = 0,6246; b ₂= 1,3124. Известно значение функции в точке х» 0,8876, F (x) = -0,9874.

Новая пробная точка: х¢ = (b ₂ +а ₂) - 0,8876» 1,0494.. Значение функции в новой точке х¢: F (x¢)= --0,9976.

Поскольку х¢>х, то принимаем х ₁ = х; F (x ₁) = F (x); х ₂ =х¢; F (x ₂) = F (x¢).

Так как F (x ₁)> F (x ₂),то отбрасываем часть доверительного отрезка [ a ₁; x ₁] и получаем отрезок [ а ₃; b ₃] = [0,8876; 1,3124].

b ₃ -а ₃=0,4248 < e =0,5;следовательно, поиск завершен.

Ответ. Выполнено3 шага, использовано 4 пробных точки. Найден итоговый доверительный интервал: [ а ₃, b ₃] = [0,8876; 1,3124]длины 0,4248.

Как видно из Примера 1 п.10.3, число необходимых вычислений функции сократилось по сравнению с методом дихотомии с 6 до 4.

Вопросы для проверки знаний.

1. Что называют а) золотым сечением отрезка, б) прямым и обратным золотым сечением отрезка?

2. Как практически рассчитать точки, задающие прямое и обратное золотое сечение отрезка?

3. Какое свойство золотого сечения используется при сокращении доверительного отрезка?

4. Какие методы называют симметричными и как симметричность используется для упрощения расчета пробных точек?

5. Как выполняются первый и последующие шаги в методе золотого сечения?

6. За счет чего метод золотого сечения является более быстрым по сравнению с дихотомией?