Geum.ru

 

Аудит / Институциональная экономика / Информационные технологии в экономике / История экономики / Логистика / Макроэкономика / Международная экономика / Микроэкономика / Мировая экономика / Операционный анализ / Оптимизация / Страхование / Управленческий учет / Экономика / Экономика и управление народным хозяйством (по отраслям) / Экономическая теория / Экономический анализ Главная Экономика Оптимизация
Харчистов Б.Ф.. Методы оптимизации, 2004

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

Метод Фибоначчи является наилучшим (в смысле максимального уменьшения длины отрезка локализации) среди активных методов поиска.
Согласно методу Фибоначчи, на первом шаге (первой итерации) проводятся два вычисления значений fx) в точках x1(1) и xл (причем x1(1)< x^1)), расположенных симметрично относительно середины отрезка Л0 = [a, b]. По результатам вычислений одна из частей отрезка ([a, x1(1)] либо [ x^1), b]) отбрасывается, при этом одна из точек (соответственно x^1) либо x1(1)) уже проведенных вычислений остается внутри отрезка Л2 = Л(1). На каждом последующем шаге (последующей итерации) точка очередного вычисления выбирается симметрично оставшейся точки. Таким образом, на первой итерации проводятся два вычисления значений fx), на каждой последующей - одно вычисление. Поэтому при заданном количестве вычислений N будет выполнено N -1 шагов (итераций).
При вычислении x1j) и x^j), j = 1, N -1, используются числа Фибоначчи, определяемые следующим образом:
Fo = F = 1, Fk = Fk-1 + Fk-2, k = 2,3,....
Условием окончания вычислений является выполнение заданного количества вычислений N.
Итак, алгоритм поиска минимума унимодальной функции методом Фибоначчи заключается в следующем.
1 . Задается N, определяются числа Фибоначчи Fk, k = 0, N + 1, выбирается е из условия
b-a
е < .
F
N+1
Полагается j=1.
2. На j-й итерации вычисляются
F N - J +1
х{] = a(J-1) + (b(J-1) - a(j-1)) - -( 1
?
FN - J +1 FN - J +1
F N - J +1
х2 J) = a(J-1) + (b(J-1) - a(j-1)) + ^ ?,
2
N - J +1 N - J +1
flJ) = f ( х{ J)), f2( J) = f ( х2J)).
Если fJ) < f2(J), то a(J) = a(J-1), b(J) = х2J), х2J+1) = х{J).
Если f1(J) > f2(J), то a(J) = х{J), b(J) = b(J-1), х{J+1) = х2]).
3. Проверяется условие окончания вычислений
j = N -1.
Если оно выполняется, то определяются итоговый отрезок локализации, оценки точки минимума х* и величины минимума
f = f (х ) и вычисления завершаются.
Если условие не выполняется, то полагается j=]+1 и осуществляется переход к п.2.
Примечание. На j-й, j>1, итерации вычисляется только та
точка х(J), i = 1,2, которая не была определена на предыдущей итерации.
*
Отметим, что оценкой точки минимума х является та из точек х(N-1), i = 1,2, которая осталась внутри итогового отрезка
локализации AN .
Пример. Определить методом Фибоначчи минимум функции f (х) = х4 -6х2 +10, заданной на отрезке А=[1,3], при N=4. Решение.
В данном случае будут выполнены N -1 = 3 итерации.
Определяем числа Фибоначчи Fk, k = 1,5 :
F0 = F1 = 1, F2 = 2, F3 = 3, F4 = 5, F5 = 8.
b - a 3 -1
е < = = 0,25.
F5 8 '
Выбираем е=0,1. Первая итерация
x1(1) = a(0) + ^(b(0) - a(0)) - е = 1 + ^2(3 -1) -
FN FN F4
- (-О4 . 0,1 = 1 + = (+ 0,78 = 1,78,
F4 5
x2() = a(0) + (b(0) - a(0)) + ^^е = 1 + ^(3 -1) +
FN FN F4
+1=1)1. 0,( = (+ 1201 = (+ (,22 = 2,22.
5
F4 Вторая итерация x(2) = a(1) + ^(b о) - a(1)) - е = 1 + F (2,22 -1) ж
FN-1 FN-1 F3
(-1)3 1 1 '1,22 + 0,1
0,1 = 1 + Ч2 L. = 1 + 0,44 = 1,44.
3
F3
Третья итерация x23) = a(2) + ^ (b(2) - a(2)) + е = 1,44 + F(2,22 -
FN-2 FN-2 F2
(-1)2 1 0 78 + 01 1,44) + Х 0,1 = 1,44 + Ч^ - = 1,44 + 0,44 = 1,88.
F2 2
Результаты вычислений заносим в табл. 4.4. Таблица 4.4 Номер итерации x{ j) x (j) л2 f1( 1) < > f2( 1) а(j) b( j) 0 1 *
1,78 *
2,22 1,028 < 4,719 1 1 3
2,22 2 1,44* 1,78 1,858 > 1,028 1,44 2,22 3 1,78 1,88* 1,028 < 1,286 1,44 1,88 Примечание. Знаком * помечаем точки x( j \ /=1,2, вычис
ляемые на j-й итерации.
Поскольку j=N-1=3, то вычисления завершаются. Точка минимума локализована на отрезке А 4 = [1,44; 1,88],
x* = xf3) = 1,78, f * = f (x(3)) = 1,028 .
Ответ: А4 = [1,44; 1,88], x = 1,78, f = 1,028.
<< Предыдушая Следующая >>
= К содержанию =
Похожие документы: "Метод Фибоначчи"
  1. 4.2. активные методы поиска минимума
    методов поиска принято указывать в используемых обозначениях номер итерации с помощью надстрочного индекса в круглых скобках. В соответствии с этим отрезок локализации после ] итераций будет обозначаться А( ]) = [a(J), b( J)]. Если при этом произведено i вычислений значений f(x), то А(j) =А,, a(j) = at, b(j U b,. На практических занятиях рассматриваются такие активные методы поиска, как метод
  2. Метод золотого сечения
    метода Фибоначчи является то, что должно быть задано количество вычислений N. Метод золотого сечения почти столь же эффективен, как и метод Фибоначчи, но при этом не зависит от N. Алгоритм поиска по методу золотого сечения определяется тем же правилом симметрии, что и алгоритм по методу Фибоначчи: на первой итерации выбираются две точки, расположенные симметрично относительно середины исходного
  3. Задачи
    методом дихотомии минимум функции f (х) = х2 - 3х + 2, заданной на отрезке Л = [0, 4], при N=8, ? = 0,1. Определить методом Фибоначчи минимум функции f (х) = х2 - 3х + 2, заданной на отрезке Л = [0, 4], при N=4, ? = 0,2. Определить методом золотого сечения минимум функции f (х) = х2 - 3х + 2, заданной на отрезке Л = [0, 4], при
  4. КОНТРОЛЬНЫЕ РАБОТЫ
    методы минимизации унимодальных и многоэкстремальных функций. В контрольную работу включены три задачи. Задача 1. Заданы унимодальная функция fx), исходный отрезок локализации минимума А, количество вычислений N, малое положительное число ? (при четном N). Определить методом пассивного поиска итоговый отрезок локализации минимума AN, оценки точки минимума x и величины минимума f . Задача 2а.
  5. СБОР ДАННЫХ И ОПРЕДЕЛЕНИЕ ПРАВИЛ
    метода результаты были еще хуже. Вероятно, это означает, что ни одно из использованных скользящих средних не ухватывает существенные черты временного ряда для акций, которые мы выбрали для рассмотрения (или же дело просто в том, что трейдеры акций Юнилевер не пользуются этим временным лагом). Мы не стремились исследовать всевозможные варианты с целью найти подходящий лаг и не пытались применять
  6. ВСТУПЛЕНИЕ
    методов разбудит недовольных и критиков, которых даже в Венеции, несмотря на определенную инертность, в те годы было достаточно в самом классе правящих аристократов. Факинеи считал, что стремление Беккариа к реформам основывалось на природном равенстве людей. А оно разрушало все старинные традиции итальянских государств и основы их аристократического общественного устройства. Он подстегнул страх,
  7. ХУ1. 0 ПЫТКЕ
    метод больше подходит для решения этой проблемы, чем судейское усмотрение. Основываясь на данных о силе мускулов и чувствительности нервной системы невиновного, можно рассчитать тот болевой предел, за которым этот невиновный вынужден будет признать себя виновным в совершении преступления. Допрос обвиняемого производится с целью выявления действительного положения дел, но если выявить это трудно
  8. XXXIV О ДОЛЖНИКАХ
    методы сурового дознания, хотят заставить угрозой каторги раскрыть тайну несостоятельного должника, предполагаемого невиновным! Я считаю, что законодатель должен руководствоваться следующим основным принципом: оценка отрицательных последствий ущерба обществу в политической сфере находится в прямой зависимости от величины этого ущерба и в обратной от трудности его определения. Следовало бы
  9. XXXVIII НАВОДЯЩИЕ ВОПРОСЫ, ПОКАЗАНИЯ
    метод обосновывают двумя соображениями: или опа219 сением мушипп подсудимому ответ, который бы сразу отвел от него все обвинения, или, может быть, полагают противоестественным для подсудимого предъявлять непосредственно самому себе обвинения. Как бы то ни было, но в обоих случаях налицо явное противоречие законов, допускающих пытку наряду с этим методом ведения допроса. Действительно, какой же
  10. ВОСПИТАНИЕ
    метод приказаний не приемлем для воспитания. Этим достигается лишь притворное и кратковременное