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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм взят из источника: Джон Г.Мэтьюз, Куртис Д.Финк. "Численные методы. Использование MATLAB". — М, СПб: "Вильямс", 2001. — 716 с.

Простейшая реализация данного алгоритма на языке F# (содержит лишние вычисления минимизируемой функции):

let phi = 0.5 * (1.0 + sqrt 5.0)
let rec minimize f eps a b = 
    if abs(b - a) < eps then 
        0.5 * (a + b)
    else 
        let t = (b - a) / phi
        let x1, x2 = b - t, a + t
        if f x1 >= f x2 then
            minimize f eps x1 b
        else
            minimize f eps a x2
// Примеры вызова:
minimize cos 1e-6 0.0 6.28
// = 3.141592794; число итераций: 33; функция f вызвана 64 раза.
minimize (fun x -> (x - 1.0)**2.0) 1e-6 0.0 10.0 
// = 1.000000145; число итераций: 35; функция f вызвана 68 раз.

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

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

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

  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.

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