Недостатком наиболее эффективного метода Фибоначчи является то, что должно быть задано количество вычислений N. Метод золотого сечения почти столь же эффективен, как и метод Фибоначчи, но при этом не зависит от N. Алгоритм поиска по методу золотого сечения определяется тем же правилом симметрии, что и алгоритм по методу Фибоначчи: на первой итерации выбираются две точки, расположенные симметрично относительно середины исходного отрезка; на каждой последующей итерации выбирается одна точка, расположенная симметрично оставшейся точки. Разница заключается в выборе точек. Метод золотого сечения основан на делении отрезка локализации лзолотым сечением, т.е. таком делении, когда отношение большей части отрезка
ко всему отрезку равно отношению меньшей части к большей Х Х Х
A C B
AC = CB AB ~ AC '
При таком делении используются две дроби Фибоначчи
ф( = 3 - ^ = 0,382, Ф2 = ^ -1 = 0,618, 1 2 2 2
удовлетворяющие условиям
Ф( + Ф2 = 1, Ф( = (Ф2)2. В случае метода золотого сечения используются два условия окончания вычислений:
а) выполнение заданного количества вычислений N,
б) достижение заданной величины 5 уменьшения отрезка локализации.
Итак, алгоритм поиска минимума унимодальной функции методом золотого сечения заключается в следующем.
Задается N (либо 5), полагается j=1.
На j-й итерации вычисляются
x(j) = a(j-1) + Ф( (b( j -1) - a(j-1)),
1 j) = a(j-1) + Ф( (b( j-1) - a(j-()) :(j) = a(j-1) + Ф2(Ь(j-1) - a(j-1)), f(( j) = f (x(j)), f2( j) = f (x2j)).
Если f(( j) < f2( j), то a(j) = a(j-1), b( j) = x^j), x^j+() = x((
Если f((j) > f2(j), то a(j) = x((j), b(j) = b(j-1), x((j+() = xtj). 3. Проверяется условие окончания вычислений:
Li+(
а) j = N -1 либо б) ^ <5.
L0
Если оно выполняется, то определяются итоговый отрезок локализации, оценки точки минимума x* и величины минимума г*
j и вычисления завершаются.
Если условие не выполняется, то полагается j=j+1 и осуществляется переход к п.2.
Пример. Определить методом золотого сечения минимум
(j)
функции f (х) = х4 - 6х2 +10, заданной на отрезке Л=[1,3], при N=4.
Решение.
В данном случае будут выполнены N - 1 = 3 итерации. Результаты вычислений заносим в табл. 4.5.
Таблица 4.5
Номер итера-ции х{ j) х (j) 2 f1( j) < > f2( j) a( j} b( j)
0 1 2 3 *
1,764
*
1,472 1,764 *
2,236
1,764
*
1,944 1,012 1,694 1,012 < > < 4,999 1,012 1,607 1 1
1,472 1,472 3
2,236 2,236 1,944
Поскольку j = N - 1 = 3 , то вычисления завершаются.
Точка минимума локализована на отрезке Л4 = [1,472; 1,944], х* = х{3) = 1,764, f * = f (х<3)) = 1,012.
Ответ: Л4 = [1,472; 1,944], х = 1,764, f = 1,012.
|
- 4.2. активные методы поиска минимума
методов поиска принято указывать в используемых обозначениях номер итерации с помощью надстрочного индекса в круглых скобках. В соответствии с этим отрезок локализации после ] итераций будет обозначаться А( ]) = [a(J), b( J)]. Если при этом произведено i вычислений значений f(x), то А(j) =А,, a(j) = at, b(j U b,. На практических занятиях рассматриваются такие активные методы поиска, как метод
- Задачи
методом дихотомии минимум функции 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], при
- КОНТРОЛЬНЫЕ РАБОТЫ
методы минимизации унимодальных и многоэкстремальных функций. В контрольную работу включены три задачи. Задача 1. Заданы унимодальная функция fx), исходный отрезок локализации минимума А, количество вычислений N, малое положительное число ? (при четном N). Определить методом пассивного поиска итоговый отрезок локализации минимума AN, оценки точки минимума x и величины минимума f . Задача 2а.
- ВСТУПЛЕНИЕ
методов разбудит недовольных и критиков, которых даже в Венеции, несмотря на определенную инертность, в те годы было достаточно в самом классе правящих аристократов. Факинеи считал, что стремление Беккариа к реформам основывалось на природном равенстве людей. А оно разрушало все старинные традиции итальянских государств и основы их аристократического общественного устройства. Он подстегнул страх,
- 15.5. УПРАВЛЕНИЕ ИЗДЕРЖКАМИ ПРЕДПРИЯТИЯ С ЦЕЛЬЮ ИХ МИНИМИЗАЦИИ
метода: метод максимальной и минимальной точки; графический (статистический метод); метод наименьших квадратов. Использование этих методов позволяет рассчитать ставку переменных затрат на единицу продукции и на ее основе - величину постоянных затрат в составе смешанных. Метод верхнейЧнижней точки заключается в том, что из совокупности данных выбираются два периода с наибольшим и наименьшим
- 5.3. Противостояние рейдерству (захватнической политике)
методы, а несколько позже использовались процедуры банкротства, то наиболее актуальный способ передела собственности - корпоративный захват. И эффективное противодействие подобному сложному, многоаспектному явлению современной российской хозяйственной и правовой действительности предполагает разработку и последовательную реализацию целого комплекса мер, стратегических и тактических способов
- 22,1. Международный финансовый бизнес: понятие, эволюция и участники
методов и банковских технологий. Наряду с позитивными изменениями мировой финансовой среды сле дует отметить и ряд негативных моментов: более частыми стали между народные финансовые кризисы, углубляется кризис международный
- 23.5. Россия и международные финансовые организации: тенденции сотрудничества
методам бухгалтерского учета, методоло гии оценки рисков и создания резервов при работе с новыми финансо выми инструментами. Членство в БМР позволило Банку России использовать его возмож ности для осуществления депозитных, валютных, кредитных, агентских и других операций, сделок с золотом и ценными бумагами, а также обме ниваться информацией с центральными банками зарубежных стран по акту альным
- 32.1. Эволюция международного туризма во второй половине XX века
методов в продвижении туристских услуг на миро вой рынок является ежегодное проведение крупнейших международных выставок и ярмарок, к основным из которых относятся международная выставка ITB в Берлине (Германия), World Travel Market в Лондоне (Вели кобритания), FITUR в Мадриде (Испания), Московская международная туристская ярмарка в России и
- Сущность денег и их эволюция
методы распределения; несоответствие качества продукта требованиям, необходимым для удовлетворения потребностей, делает его ненужным для хозяйства, как это было со многими видами продукции в советской экономике; если ресурс существует в достатке, как например, земля, но свободно не продается, - он также не считается товаром и, соответственно, неэффективно используется в хозяйственной
|
Экономика