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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  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.

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