Главная
Новости
Статьи
Строительство
Ремонт
Дизайн и интерьер
Строительная теплофизика
Прочность сплавов
Основания и фундаменты
Осадочные породы
Прочность дорог
Минералогия глин
Краны башенные
Справочник токаря
Цементный бетон




26.06.2022


26.06.2022


25.06.2022


24.06.2022


21.06.2022


17.06.2022


17.06.2022





Яндекс.Метрика

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

24.01.2022


Метод золотого сечения — метод поиска экстремума действительной функции одной переменной на заданном отрезке. В основе метода лежит принцип деления отрезка в пропорциях золотого сечения. Является одним из простейших вычислительных методов решения задач оптимизации. Впервые представлен Джеком Кифером в 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.
  • Имя:*
    E-Mail:
    Комментарий: