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

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Метод чисел Фибоначчи»)
Перейти к навигации Перейти к поиску

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

Описание метода[править | править код]

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

Иллюстрация выбора промежуточных точек метода золотого сечения.
, где — пропорция золотого сечения.

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

То есть точка делит отрезок в отношении золотого сечения. Аналогично делит отрезок в той же пропорции. Это свойство и используется для построения итеративного процесса.

Алгоритм[править | править код]

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

Формализация[править | править код]

  1. Шаг 1. Задаются начальные границы отрезка и точность .
  2. Шаг 2. Рассчитывают начальные точки деления: и значения в них целевой функции: .
    • Если (для поиска max изменить неравенство на ), то
    • Иначе .
  3. Шаг 3.
    • Если , то и останов.
    • Иначе возврат к шагу 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 раз.

Метод чисел Фибоначчи[править | править код]

В силу того, что в асимптотике , метод золотого сечения может быть трансформирован в так называемый метод чисел Фибоначчи. Однако при этом в силу свойств чисел Фибоначчи количество итераций строго ограничено. Это удобно, если сразу задано количество возможных обращений к функции.

Алгоритм[править | править код]

  1. Шаг 1. Задаются начальные границы отрезка и число итераций , рассчитывают начальные точки деления: и значения в них целевой функции: .
  2. Шаг 2. .
    • Если , то .
    • Иначе .
  3. Шаг 3.
    • Если , то и остановка.
    • Иначе возврат к шагу 2.

Литература[править | править код]

  1. Акулич И. Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.
  2. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
  3. Коршунов Ю. М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.
  4. Максимов Ю. А., Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
  5. Максимов Ю. А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980.
  6. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575—576.
  7. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1973. — С. 832 с илл..
  8. Джон Г. Мэтьюз, Куртис Д. Финк. Численные методы. Использование MATLAB. — 3-е издание. — М., СПб.: Вильямс, 2001. — С. 716.

См. также[править | править код]