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

Это один из наиболее эффективных методов нулевого порядка, использующихся для решения задачи (1.1.1).

Опуская этап отделения (локализации) положения локального минимума функции f (x), перейдем к этапу уточнения положения этого минимума. Начнем с исходного интервала неопределенности D₀ = (a, b), содержащего х ^* – искомую точку локального минимума унимодальной на интервале D₀ функции f (x). Как и в методе половинного деления, последовательное уточнение положения точки х ^* представляет собой итерационный процесс. На каждом шаге этого процесса строится новый интервал неопределенности; его длина меньше длины текущего интервала, в который он входит. В результате построения получаем последовательность вложенных интервалов неопределенности D _i, i = 0, 2, 3, …, k, …:

D₀ = (a, b) É D₁ = (a ⁽¹⁾, b ⁽¹⁾) É … É D _k = (a ^(k), b ^(k)) É …

При этом если исходный интервал D₀ содержит искомую точку х ^*, то ее будут содержать и все остальные интервалы последовательности.

Пусть L_i – длина i -го интервала неопределенности, i = 0, 2, 3, …, k, … Так же как и при использовании метода половинного деления, для анализа текущего интервала неопределенности D _i на i -м шаге процесса будем выбирать внутри этого интервала две пробные точки, расположенные симметрично относительно его середины. Однако в отличие от метода половинного деления потребуем, чтобы для строящейся последовательности вложенных интервалов выполнялись следующие условия:

– длина каждого интервала должна равняться сумме длин двух последующих интервалов этой последовательности:

L_i = L_{i + 1} + L_{i + 2}, i = 0, 1, 2, …; (1.3.1)

– отношение длины любого интервала последовательности к длине предыдущего интервала должно оставаться постоянным и равным некоторому числу l (0 < l < 1):

L_{i + 1} / L_i = L_{i + 2} / L_{i + 1} = l, i = 0, 1, 2, … (1.3.2)

Последнее условие часто называют правилом "золотого сечения".

Из совместного решения уравнений (1.3.1) и (1.3.2) находим

l = (-1+Ö(5))/2»0,618

Итак, согласно методу золотого сечения на i -м шаге пробные точки располагаются на расстоянии » 0,382 L_i от концов текущего интервала
неопределенности D _i. При i = 0 потребуется введение сразу двух пробных точек для интервала D₀; при всех i > 1 достаточно будет ввести лишь одну новую точку в интервал D _i, так как одна из пробных точек, использовавшихся для интервала D_{i – 1}, останется таковой и для D _i. Таким образом,
за k -шагов процесса потребуется лишь k + 1 вычислений функции. Длина интервала неопределенности D _k на k -м шаге метода будет определяться по формуле

L_k = l ^k L ₀, k = 0, 1, 2, …

В итоге для уменьшения интервала неопределенности не менее чем в 100 раз потребуется сделать 10 шагов и, следовательно, 11 вычислений значений функции f (x), что лучше, чем при использовании метода половинного деления, где для этого потребовалось произвести 14 вычислений.

Пусть функция f (x) является унимодальной на интервале (a, b)
и задано достаточно малое число d > 0 – требуемая точность определения
точки искомого минимума х ^* Î (a, b) данной функции. Тогда метод золотого сечения можно записать в виде следующего алгоритма:

1. Задать функцию f (x) и числа a, b, t» 0.618, d > 0;

2. Если b – a £ 2d Þ перейти к выполнению п. 11.

3. Вычислить с = t (b – a).

4. Вычислить x₁ =b – с; x₂ = a + с.

5. Вычислить значения f (x ₁) и f (x ₂).

6. Если f (x ₁) > f (x ₂) положить a: = x ₁.

Иначе перейти к выполнению п. 8.

7. Если (b – a) £ 2d перейти к выполнению п. 11.

Иначе положить x ₁ = x ₂; f (x ₁):= f (x ₂).

Вычислить с =t (b – a), x ₂ = a + с, f (x ₂). Перейти к выполнению п. 6.

8. Если f (x ₁) < f (x ₂) положить b:= x ₂.

Иначе перейти к выполнению п. 10.

9. Если (b – a) £ 2d перейти к выполнению п. 11.

Иначе положить x ₂ = x ₁; f (x ₂)= f (x ₁).

Вычислить с =t (b – a), x ₁ = b – с, f (x ₁). Перейти к выполнению п. 6.

10. Положить a:= x ₁; b:= x ₂.

Иначе перейти к выполнению п. 2.

11. Положить х ^* =(a + b)/2. Процесс завершен.

Работу метода золотого сечения удобно отображать в таблице, аналогичной предложенной для метода половинного деления (см. табл. 1.2.1).

В заключение дадим общую характеристику метода золотого сечения для решения задачи (1.1.1), которая во многом сходна с характеристикой метода половинного деления:

– всегда сходится к решению задачи (1.1.1);

– скорость сходимости линейная. На каждом шаге длина интервала неопределенности уменьшается в l» 0.618 раз. После k -го шага процесса она составит L_k = l ^kL ₀. Нетрудно подсчитать количество итераций, необходимых для уменьшения исходного интервала неопределенности в заданное количество раз. Например, чтобы уменьшить ее не менее чем в 100 раз, потребуется 10 итераций;

– на каждом шаге (кроме нулевого) требуется вычисление значений функции f (x) в одной из точек: х ₁ или х ₂. Эти точки расположены симметрично относительно центра текущего интервала неопределенности на расстоянии» 0.236(b – a) друг от друга, где (a, b) – текущий интервал неопределенности. На нулевом шаге значение функции f (x) необходимо вычислить в обеих точках.

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