Метод золотого перетину

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

Опис методу[ред. | ред. код]

Нехай задано функцію . Тоді для того, щоб знайти невизначене значення цієї функції на заданому відрізку, що відповідає критерію пошуку (нехай це буде мінімум), розглянутий відрізок ділиться в пропорції золотого перетину в обох напрямках, тобто вибираються дві точки та такі, що:

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

Таким чином:

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

Алгоритм[ред. | ред. код]

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

Формалізація[ред. | ред. код]

  1. Крок 1. Задаються початкові межі відрізка  і точність .
  2. Крок 2. Розраховують початкові точки поділу: і значення в них цільової функції: .
    • Якщо  (для пошуку максимуму змінити нерівність на ), то
    • Інакше .
  3. Крок 3.
    • Якщо , то  і зупинитися.
    • Інакше повернутися до кроку 2.

Метод чисел Фібоначчі[ред. | ред. код]

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

  1. Крок 1. Задаються початкові межі відрізка  і кількість ітерацій , розраховують початкові точки поділу:  цільової функції: .
  2. Крок 2. .
    • Якщо , то .
    • Інакше .
  3. Крок 3.
    • Якщо , то і зупинитися.
    • Інакше повернутися до кроку 2.

Література[ред. | ред. код]

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

Див. також[ред. | ред. код]