АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Методы одномерного поиска экстремума. Метод поиска с использованием чисел Фибоначчи

Читайте также:
  1. A) Метод опроса
  2. I. Метод стандартизации
  3. I. Методы выбора инновационной политики
  4. I. ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЙ РАЗДЕЛ
  5. I. Основные характеристики и проблемы философской методологии.
  6. I.ЗАГАЛЬНІ МЕТОДИЧНІ ВКАЗІВКИ
  7. II. ВИРУСОЛОГИЧЕСКИЙ МЕТОД
  8. II. Вывод и анализ кинетических уравнений 0-, 1-, 2-ого порядков. Методы определения порядка реакции
  9. II. Методологічні засади, підходи, принципи, критерії формування позитивної мотивації на здоровий спосіб життя у дітей та молоді
  10. II. Методы прогнозирования и поиска идей
  11. II. Формальная логика как первая система методов философии.
  12. II. Цитогенетический метод

Метод Фибоначчи является одним из наиболее эффективных методов одномерной оптимизации выпуклых или квазивыпуклых функций. Подобно методу золотого сечения, он требует двух вычислений функции на первой итерации, а на каждой последующей только по одному. Однако этот метод отличается от метода золотого сечения тем, что коэффициент сокращения интервала неопределенности меняется от итерации к итерации. Метод основан на последовательности чисел Фибоначчи , которая определяется следующим образом [2, 18]:

(6.3.7)

Таким образом, последовательность Фибоначчи имеет вид 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Предположим, что на -й итерации интервал неопределенности равен . Рассмотрим две точки и определяемые следующим образом:

(6.3.8)

(6.3.9)

где n – заданное общее число вычислений функции.

Согласно теореме 6.1, новый интервал неопределенности будет равен , если и , если . В первом случае, учитывая (6.3.8) и полагая в (6.3.7), получим

(6.3.10)

Во втором случае, учитывая (6.3.9), получаем

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

Подставив выражение для из (6.3.8) и заменив на , получим

(6.3.11)

Подставляя это значение в (6.3.11), получим

. (6.3.12)

Если , то выполнив аналогичные преобразования, получим . Таким образом, в обоих случаях на -й итерации требуется только одно вычисление функции.

В отличие от методов дихотомического поиска и золотого сечения в методе Фибоначчи требуется, чтобы общее число вычислений (или коэффициент сокращения исходного интервала) было задано заранее. Это объясняется тем, что точки, в которых производятся вычисления, определяются по формулам (6.3.8), (6.3.9) и, следовательно, зависят от . Из формулы (6.3.10) следует, что длина интервала неопределенности на -й итерации сжимается с коэффициентом . Следовательно, после итерации, где – заданное общее число вычислений функции , длина интервала неопределенности сократится от до .


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)