WikiSort.ru - Программирование

ПОИСК ПО САЙТУ | о проекте

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

См. также

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

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

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии