|
|||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Метод Фибоначчи
Последовательность чисел Фибоначчи определяется соотношением:
(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) использованием чисел Фибоначчи
Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.) |