![]() КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Метод Фибоначчи
Идея метода. Отличается от метода золотого сечения величиной коэффициента λ в формулах (8) или (9), определяющих длины отрезков поиска Изменив коэффициент λ, причем выбирая Лемма 3. Пусть 1) 2) Поскольку числа Фибоначчи: 1, 1, 2, 3, 5, 8, 13, 21, 34, … то получим значения
Свойство 2 леммы 3 можно уточнить:
![]() ![]() ![]() ![]() ![]() ![]() Лемма 4. Пусть λ выбирается из условий:
Тогда для любых k = 1,2,…,n справедливы неравенства 0 < Таким образом, при всяком λ, выбранном из условий леммы 4, согласно неравенствам (10) вложения [ak, bk] могут быть гарантированы только при k ≤ n. Теорема 1. Если 1) 2) для любых λ, удовлетворяющих условиям леммы 4, выполняются неравенства 0 < Свойство 1) получается из формулы (9) при
Свойство 2)
Если n – нечетное, то при 0 <
Если n – четное, то при
Тогда из свойства 1) на основании формулы (8) для длин вложенных отрезков поиска
![]() ![]() ![]() ![]() ![]() ![]() ![]() Итак, при заданном числе n нужно остановиться на (n–2)-м шаге. Поэтому в методе Фибоначчи последовательность {
тогда после n–2 шагов последовательность [ak, bk] стягивалась к точке Схема метода. Соответствует схеме метода золотого сечения при шагах k = 0,1,2,…,n–3. Число n задано такое, чтобы выполнялось Формулы вычисления промежуточных точек yk и zk на отрезке поиска [ak, bk]: yk = ak + zk = ak + Определим новый отрезок поиска [ak+1, bk+1]. Для этого сравним значения f(yk) и f(zk): · если f(yk) ≤ f(zk) · если f(yk) > f(zk) Выбор решения. В качестве приближения для xmin выбирается точка
оставшаяся после n–2 шагов, для которой уже вычислено значение целевой функции. Анализ метода. 1) Длины 2) Коэффициенты сжатия на каждом шаге
3) Из свойства 2 теоремы 1 Таким образом, при поиске точки минимума методом Фибоначчи через заданное число шагов получим отрезок наименьшей длины по сравнению с любым другим алгоритмом с последовательностью { 4) Вычислим коэффициент сжатия после n–2 шагов:
Длина 5) В этом случае: погрешность определения точки xmin: | Тогда из формулы (13)
6) Степень близости полученного приближенного значения целевой функции и минимума этой функции на [a, b] определяется неравенством: |f(xmin) – f( 7) Общее количество m вычислений значений функции, требующее для достижения заданной точности ε > 0, равно m = n – 2. Коэффициент сжатия γ (величина отношения длин конечного и начального отрезков поиска) при данном алгоритме поиска после m вычислений значений функции равен γ = 1/Fm+2. Например, коэффициент сжатия γ после m = 10 вычислений значений функции равен: · для метода Фибоначчи γ = 1/F12 = 1/144 ≈ 0,00694; (12 итераций) · для метода золотого сечения γ = λm–1 ≈ (0,618)9 ≈ 0,013156. (9 итераций) т. е. почти в 1,895 раза длина конечного отрезка поиска для метода Фибоначчи меньше, чем для метода золотого сечения.
Дата добавления: 2015-07-02; Просмотров: 635; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |