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

Метод Фибоначчи

Читайте также:
  1. F. Метод, основанный на использовании свойства монотонности показательной функции .
  2. FAST (Методика быстрого анализа решения)
  3. I этап Подготовка к развитию грудобрюшного типа дыхания по традиционной методике
  4. I. 2.1. Графический метод решения задачи ЛП
  5. I. 3.2. Двойственный симплекс-метод.
  6. I. ГИМНАСТИКА, ЕЕ ЗАДАЧИ И МЕТОДИЧЕСКИЕ ОСОБЕННОСТИ
  7. I. Метод рассмотрения остатков от деления.
  8. I. Методические основы
  9. I. Методические основы оценки эффективности инвестиционных проектов
  10. I. Организационно-методический раздел
  11. I. Предмет и метод теоретической экономики
  12. I. Что изучает экономика. Предмет и метод экономики.

 

Последовательность чисел Фибоначчи определяется соотношением:

 

(8)

 

 

и имеет вид:

 

 

 

Подобно методу золотого сечения процедура поиска с использованием чисел Фибоначчи требует два вычисления функции на первом шаге, а на каждом последующем - только по одному. Однако, в отличие от метода золотого сечения, в этой процедуре общее число S вычисления функции должно быть выбрано заранее. Кроме того, сокращение интервала неопределенности не остается постоянным, а меняется от шага к шагу: на k-ом шаге длина интервала неопределенности сжимается с коэффициентом

 

 

Первые два вычисления проводятся в точках:

 

 

 

расположенных симметрично относительно середины отрезка [a,b]. Если f(x1)<f(x2), то новым отрезком локализации минимума является [a, x2], в случае f(x1)≥f(x2)-[x1, b]. Каждая следующая точка выбирается симметрично относительно середины полученного отрезка к лежащей внутри этого отрезка точке уже проведенного вычисления (x1 или x2). При этом любая внутренняя точка делит отрезок локализации в отношении, двух последовательных чисел Фибоначчи.

 

 

Взаимное расположение точек первых трех вычислений в случае f(x1)<f(x2) показано на рис. 7.

 

Первый шаг

 

 

Второй шаг

 

Рис. 7.

 

После (S-1)-го шага точка проведенного вычисления оказывается в середине отрезка локализации. Точка последнего, S-го, шага выбирается на расстоянии δ от середины этого отрезка, где δ - заранее фиксированное малое положительное число (константа различимости).

 

После S вычислений функции длина отрезка локализации составляет (с точностью до δ):

(9)

 

 

Сравнение (9) и (7) показывает, что при одном и том же S метод Фибоначчи дает меньший интервал неопределенности, чем метод золотого сечения, т.е. является более эффективным. Однако для достаточно больших S значение стремится к (0,618)S-1, так что эти методы становятся почти идентичными.

 

В том случае; когда при использовании метода Фибоначчи задан.конечный интервал неопределенности ε, число S можно определить из условия:

(10)

 

 

Алгоритм минимизации функции f(x) с использование, чисел Фибоначчи.

 

1. По заданной точности рассчитывается вспомогательное число

 

 

2. Для полученного значения N находится такое число Фибоначчи FS, для которого выполняется неравенство:

 

3.

 

4. По формуле (9) определяется длина конечного интервала неопределенности l.

 

5. Вычисляются значения x1=a+l∙FS-2, x2=b-l∙FS-2.

 

6. В зависимости от соотношения f(x1) и f(x2) выбирается новый интервал локализации минимума.

 

7. Внутри полученного интервала находится новая точка (x1 или x2), симметричная к уже имеющейся точке и отстоящая от конца интервала на величину l∙FS-1-k, где k - номер шага. В этой точке рассчитывается значение f(x). Затем вычисления повторяются, начиная с пункта 5, до тех пор, пока k не станет равно S-1. Тогда переходят к пункту 7.

 

8. Полагают x2=x1+δ, находят f(x2). Если f(x2)>f(x1)то минимум реализуется на интервале (a, x1), в противном случае - на интервале (x1, b).

 

Блок-схема описанного алгоритма приведена на рис.8.

 

 

Рис. 8. Блок – схема алгоритма поиска минимума функции f(x) использованием чисел Фибоначчи

 

 


 


1 | 2 |

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



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