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

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

Основные соотношения метода вытекают из следующих предпосылок. Пусть на k-ой итерации метода золотого сечения интервал неопределенности равен [a_k, b_k]. Точки x_k, y_k выбираются на основе следующих условий.

x_k=a_k+(1-)(b_k-a_k)

y_k=a_k+(b_k-a_k), где  (0, 1)– коэффициент сжатия.

Длина нового интервала неопределенности определяется следующим способом: b_k+1 - a_k+1 =  (b_k - a_k)

Кроме того, должны выполняться равенства

b_k - x_k = y_k - a_k; x_k = a_k + (1 - )(b_k - a_k); y_k = a_k +(b_k - a_k).

Для новой итерации x_k+1 и y_k+1 выбираются так, что x_k+1 совпадает с y_k, или y_k+1 совпадает с x_k. Это условие обеспечивает возможность того, что на (k +1)-й итерации потребуется только одно новое вычисление функции.

При сравнении значений функции в двух точках возможны два варианта. 1. Если f(x_k) > f(y_k), то в этом случае a_k+1 = x_k и b_k+1 = b_k. При x_k+1 = y_k имеем y_k+1 = a_k+1 + (b_k+1 - a_k+1) = x_k + (b_k+1 - a_k+1). Подставляя в это выражение для x_k и y_k уравнения из предыдущего первого условия, получим, что ² +  - 1 = 0.

2. Если f(x_k)  f(y_k), то в этом случае a_k+1 = a_k и b_k+1 = y_k. При y_k+1 = x_k имеем x_k+1 = a_k+1 + (1 - )(b_k+1 - a_k+1) = a_k + (1 - )(y_k - a_k). Подставляем в это выражение для x_k и y_k уравнения из предыдущего первого условия также получим ² +  - 1 = 0.

Корнями уравнения ² +  - 1=0 являются  = 0.618 и  = -1.618. Так как  должно быть из интервала (0, 1), то принимаем  = 0.618. На первой итерации метода необходимы два вычисления функции в точках x₁ и y₁, но на каждой последующей требуется только одно вычисление, так как либо x_k+1 = y_k, либо y_k+1 = x_k.

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

Начальный этап. Задается конечная длина интервала неопределенности l > 0, начальный интервал [a₁, b₁]. Вычислить x₁ = a₁ + (1 - )(b₁ - a₁) и y₁ = a₁ + (b₁ - a₁), приняв  = 0.618. Найти f(x₁), и f(y₁). Задать k = 1 и перейти к основному этапу.

Основной этап. Шаг 1. Если b_k - a_k < 1, то остановиться; оптимальная точка принадлежит интервалу [a_k, b_k]. При f(x_k) > f(y_k), перейти к шагу 2, если f(x_k)  f(y_k), то к шагу 3.

Шаг 2. Положить a_k+1 = x_k; b_k+1 = b_k; x_k+1 = y_k; f(x_k+1) = f(y_k). Вычислить y_k+1 = a_k+1 + (b_k+1 - a_k+1).

Вычислить f(y_k+1) и перейти к шагу 4.

Шаг 3. Положить а_k+1 = a_k, b_k+1 = y_k, y_k+1 = x_k, f(y_k+1) = f(x_k). Вычислить x_k+1 = a_k+1 + (1-)(b_k+1 - a_k+1). Вычислить f(x_k+1) и перейти к шагу 4.

Шаг 4. Заменить k = k + 1 и перейти к шагу 1.

Пример расчета экстремума функции методом золотого сечения.

Постановка задачи. Минимизировать f(x) = x² + 2x на интервале x[-3; 5] сократив его до величины l  0,2.

Рассчитываем минимум функции f(x) = x² + 2x с использованием табличного процессора ECXEL по рассмотренному выше алгоритму. Результаты расчетов представлены в таблице 2.4.

Таблица 2.4

Расчет экстремума функции f(x)= x² + 2x методом золотого сечения.

№	аk	bk	xk	yk	f(xk)	f(yk)	|b-a|	Критерий
1	-3.000	5.000	0.056	1.944	0.115	7.667	8.000	не достигнут
2	-3.000	1.944	-1.111	0.056	-0.988	0.116	4.944	не достигнут
3	-3.000	0.056	-1.832	-1.111	-0.307	-0.988	3.056	не достигнут
4	-1.832	0.056	-1.111	-0.665	-0.988	-0.888	1.889	не достигнут
5	-1.832	-0.665	-1.387	-1.111	-0.851	-0.988	1.167	не достигнут
6	-1.387	-0.665	-1.111	-0.941	-0.988	-0.996	0.721	не достигнут
7	-1.111	-0.665	-0.941	-0.835	-0.996	-0.973	0.446	не достигнут
8	-1.111	-0.835	-1.006	-0.941	-1.000	-0.996	0.276	не достигнут
9	-1.111	-0.941	-1.046	-1.006	-0.998	-1.000	0.170	достигнут

После восьми итераций интервал неопределенности составил [-1,111; -0,941]. При этом |b₉ - a₉|=0,170, что меньше заданной величины 0,2. В качестве точки минимума может быть взята середина интервала -1,026. Искомый минимум равен ‑1,0.