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

В основе этого метода лежит понятие "золотого сечения", введенного Леонардо да Винчи и используемого, в частности, при построении архитектурных сооружений античности и эпохи Возрождения.

Золотым сечением отрезка называется его разбиение на две неравные части, так, что отношение длины всего отрезка к длине его большей части равно отношению длины большей части к длине меньшей части (рис.1.3, слева)

= .

Рис 1.3

Золотое сечение осуществляется двумя точками x₁ и x₂, расположенными симметрично относительно середины отрезка (рис.1.3, справа). Нетрудно проверить, что

= = , (1.10)

= = . (1.11)

Точка x₁ осуществляет золотое сечение не только отрезка [a, b], но и отрезка [a, x₂], а точка x₂ осуществляет золотое сечение не только отрезка [a, b], но и отрезка [x₁, b]. Действительно,

= = ,

= = .

Из (1.10) и (1.11) получаем:

x₁ = a + , x₂ = a + . (1.12)

Формулы (1.12) являются основными расчетными формулами метода золотого сечения.

Из (1.12) следует, что x₁ + x₂ = a + b. Если обозначить r = , то формулы (1.12) можно переписать так:

x₁ = b – r(b – a), x₂ = a + r(b – a) (1.13)

Процедура деления отрезка [a, b] такая же, как и для методов дихотомии и Фибоначчи. Вычисляются значения функции в выбранных точках: f(x₁) и f(x₂). Определяется новый отрезок локализации [a₁, b₁] следующим образом:

если f(x₁)  f(x₂), то a₁ = a, b₁ = x₂;

если f(x₁) > f(x₂), то a₁ = x₁, b₁ = b.

Далее процедура деления отрезка [a₁, b₁] повторяется с использованием формул (1.12) или (1.13).

Так же, как и в методе Фибоначчи, одна из пробных точек x₁, x₂ станет пробной точкой на новом отрезке локализации. Поэтому на каждой итерации достаточно определить только одно значение f(x), так как другое уже найдено на предыдущей итерации.

В конце вычислений можно взять в качестве приближенного значения x^* середину последнего из полученных отрезков.

После выполнения n итераций погрешность удовлетворяет следующему неравенству:

_n = < .

Условием окончания вычислений является выполнение неравенства _n <.

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

Шаг 1. Ввести исходные данные: a, b, . Положить r = , _n = .

Шаг 2. Определить x₁ и x₂ по формулам (1.13).

Шаг 3. Вычислить f(x₁) и f(x₂).

Шаг 4. Проверить критерий окончания вычислений. Если _n <, перейти к шагу 5, иначе – к шагу 6.

Шаг 5. Перейти к новому отрезку локализации и новым пробным точкам. Если f(x₁)  f(x₂), то положить b = x₂, x₂ = x₁, f(x₂) = f(x₁), x₁ = b – r(b – a) и вычислить f(x₁). Иначе положить a = x₁, x₁ = x₂, f(x₁) = f(x₂), x₂ = a + r(b – a) и вычислить f(x₂).

Положить _n = r_n и перейти к шагу 4.

Шаг 6. Положить x^*  . Вычислить f ^* f(x^*).

Пример 1.5.

Методом золотого сечения решим задачу, рассмотренную ранее: f(x) = x⁴ + e ^–x  min, x  [0, 1],  = 0.1.

Результаты вычислений приведены в табл. 1.6.

Таблица 1.6

Номер итерации	a	b	n	x1	x2	f(x1)	f(x2)	Сравнение f(x1) и f(x2)
1 2 3 4 5	0 0.382 0.382 0.382 0.472	1 1.000 0.764 0.618 0.618	0.5 0.309 0.191 0.118 0.073	0.382 0.618 0.528 0.472	0.618 0.764 0.618 0.528	0.704 0.685 0.668 0.673	0.685 0.807 0.685 0.668	f(x1) > f(x2) f(x1) < f(x2) f(x1) < f(x2) f(x1) > f(x2)

Вычисления прекращаются после 5-ой итерации, так как требуемая точность достигнута (0.073 < 0.1).

Таким образом, x^*   0.55 и f(x^*)  0.67.