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

Метод золотого сечения — метод поиска экстремума действительной функции одной переменной на заданном отрезке. В основе метода лежит принцип деления отрезка в пропорциях золотого сечения. Является одним из простейших вычислительных методов решения задач оптимизации. Впервые представлен Джеком Кифером в 1953 году.

Описание метода

Пусть задана функция f ( x ) : [ a , b ] → R , f ( x ) ∈ C ( [ a , b ] ) {displaystyle f(x):;[a,;b] o mathbb {R} ,;f(x)in mathrm {C} ([a,;b])} . Тогда для того, чтобы найти неопределённое значение этой функции на заданном отрезке, отвечающее критерию поиска (пусть это будет минимум), рассматриваемый отрезок делится в пропорции золотого сечения в обоих направлениях, то есть выбираются две точки x 1 {displaystyle x_{1}} и x 2 {displaystyle x_{2}} такие, что:

b − a b − x 1 = b − a x 2 − a = Φ = 1 + 5 2 = 1.618 … {displaystyle {frac {b-a}{b-x_{1}}}={frac {b-a}{x_{2}-a}}=Phi ={frac {1+{sqrt {5}}}{2}}=1.618ldots } , где Φ {displaystyle Phi } — пропорция золотого сечения.

Таким образом:

x 1 = b − ( b − a ) Φ x 2 = a + ( b − a ) Φ {displaystyle {egin{array}{ccc}x_{1}&=&b-{frac {(b-a)}{Phi }}x_{2}&=&a+{frac {(b-a)}{Phi }}end{array}}}

То есть точка x 1 {displaystyle x_{1}} делит отрезок [ a , x 2 ] {displaystyle [a,;x_{2}]} в отношении золотого сечения. Аналогично x 2 {displaystyle x_{2}} делит отрезок [ x 1 , b ] {displaystyle [x_{1},;b]} в той же пропорции. Это свойство и используется для построения итеративного процесса.

Алгоритм

На первой итерации заданный отрезок делится двумя симметричными относительно его центра точками и рассчитываются значения в этих точках.

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

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

Процедура продолжается до тех пор, пока не будет достигнута заданная точность.

Формализация

Шаг 1. Задаются начальные границы отрезка a , b {displaystyle a,;b} и точность ε {displaystyle varepsilon } .

Шаг 2. Рассчитывают начальные точки деления: x 1 = b − ( b − a ) Φ , x 2 = a + ( b − a ) Φ {displaystyle x_{1}=b-{frac {(b-a)}{Phi }},quad x_{2}=a+{frac {(b-a)}{Phi }}} и значения в них целевой функции: y 1 = f ( x 1 ) , y 2 = f ( x 2 ) {displaystyle y_{1}=f(x_{1}),;y_{2}=f(x_{2})} .

Если y 1 ≥ y 2 {displaystyle y_{1}geq y_{2}} (для поиска max изменить неравенство на y 1 ≤ y 2 {displaystyle y_{1}leq y_{2}} ), то a = x 1 {displaystyle a=x_{1}}
Иначе b = x 2 {displaystyle b=x_{2}} .

Шаг 3.

Если | b − a | < ε {displaystyle |b-a|<varepsilon } , то x = a + b 2 {displaystyle x={frac {a+b}{2}}} и останов.
Иначе возврат к шагу 2.

Алгоритм взят из книги Мэтьюза и Финка «Численные методы. Использование MATLAB».

Реализация данного алгоритма на языке F#, в которой значения целевой функции используются повторно:

let phi = 0.5 * (1.0 + sqrt 5.0) let minimize f eps a b = let rec min_rec f eps a b fx1 fx2 = if b - a < eps then 0.5 * (a + b) else let t = (b - a) / phi let x1, x2 = b - t, a + t let fx1 = match fx1 with Some v -> v | None -> f x1 let fx2 = match fx2 with Some v -> v | None -> f x2 if fx1 >= fx2 then min_rec f eps x1 b (Some fx2) None else min_rec f eps a x2 None (Some fx1) min_rec f eps (min a b) (max a b) None None // Примеры вызова: minimize cos 1e-6 0.0 6.28 |> printfn "%.10g" // = 3.141592794; функция f вызвана 34 раза. minimize (fun x -> (x - 1.0)**2.0) 1e-6 0.0 10.0 |> printfn "%.10g" // = 1.000000145; функция f вызвана 35 раз.

Метод чисел Фибоначчи

В силу того, что в асимптотике Φ = lim n → ∞ F n + 1 F n {displaystyle Phi =lim _{n o infty }{frac {F_{n+1}}{F_{n}}}} , метод золотого сечения может быть трансформирован в так называемый метод чисел Фибоначчи. Однако при этом в силу свойств чисел Фибоначчи количество итераций строго ограничено. Это удобно, если сразу задано количество возможных обращений к функции.

Алгоритм

Шаг 1. Задаются начальные границы отрезка a , b {displaystyle a,;b} и число итераций n {displaystyle n} , рассчитывают начальные точки деления: x 1 = a + ( b − a ) F n − 2 F n , x 2 = a + ( b − a ) F n − 1 F n {displaystyle x_{1}=a+(b-a){frac {F_{n-2}}{F_{n}}},quad x_{2}=a+(b-a){frac {F_{n-1}}{F_{n}}}} и значения в них целевой функции: y 1 = f ( x 1 ) , y 2 = f ( x 2 ) {displaystyle y_{1}=f(x_{1}),;y_{2}=f(x_{2})} .

Шаг 2. n = n − 1 {displaystyle n=n-1} .

Если y 1 > y 2 {displaystyle y_{1}>y_{2}} , то a = x 1 , x 1 = x 2 , x 2 = b − ( x 1 − a ) , y 1 = y 2 , y 2 = f ( x 2 ) {displaystyle a=x_{1},;x_{1}=x_{2},;x_{2}=b-(x_{1}-a),;y_{1}=y_{2},;y_{2}=f(x_{2})} .
Иначе b = x 2 , x 2 = x 1 , x 1 = a + ( b − x 2 ) , y 2 = y 1 , y 1 = f ( x 1 ) {displaystyle b=x_{2},;x_{2}=x_{1},;x_{1}=a+(b-x_{2}),;y_{2}=y_{1},;y_{1}=f(x_{1})} .

Шаг 3.

Если n = 1 {displaystyle n=1} , то x = x 1 + x 2 2 {displaystyle x={frac {x_{1}+x_{2}}{2}}} и остановка.
Иначе возврат к шагу 2.