Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Топ:
Устройство и оснащение процедурного кабинета: Решающая роль в обеспечении правильного лечения пациентов отводится процедурной медсестре...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов...
Интересное:
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Дисциплины:
2020-12-06 | 403 |
5.00
из
|
Заказать работу |
|
|
Заметим, что точка (n- тая итерация) отстоит от концов отрезка на величину, не превышающую . Поэтому верна оценка:
. (8)
Каждая итерация сокращает длину отрезка локализации в раз. Значит, и справедлива следующая априорная оценка погрешности:
. (9)
Таким образом, метод золотого сечения сходится со скоростью геометрической прогрессии, знаменатель которой .
2.4. Метод Фибоначчи *
Данный метод обеспечивает максимальное гарантированное сокращение отрезка локализации при заданном числе N вычислений функции и основан на использовании чисел Фибоначчи таких, что: для всех
при начальных значениях
Метод Фибоначчи состоит из шагов. Очередной -й шаг выполняется аналогично -й итерации метода деления отрезка пополам, но точки и находятся по формулам
, (10)
где – длина отрезка локализации (рис.2.7).
Рис. 2.7. Графическая интерпретация метода Фибоначчи
Аналогично методу деления отрезка пополам определяется новый отрезок локализации:
если , то ;
если , то .
В первом случае за очередное приближение к точке минимума принимают , во втором случае – .
Оценка погрешности метода Фибоначчи
Так же, как и в методе золотого сечения точка будет однозначно совпадать с одной из точек (в зависимости от выбора подотрезка на очередном шаге локализации):
, . (11)
Поэтому на очередном шаге достаточно вычислить значение функции лишь в одной недостающей точке. В результате выполнения шагов отрезок локализации уменьшается в раз, а точка оказывается центральной для последнего отрезка локализации . Поэтому для справедлива следующая оценка погрешности:
|
. (12)
Метод парабол
Существует множество методов локализации экстремума гладкой функции. Некоторые из них, например метод бисекции и метод Ньютона требуют вычисления производных. Такие методы достаточно эффективны, но не очень удобны для программной реализации, так как именно проблема вычисления производных является трудоемкой в ЭВМ-реализации. Предлагаемый метод не требует вычисления производных и, как мы убедимся ниже, является достаточно эффективным в случае удачной предварительной его настройки.
Предположим, что уже известны три предыдущих приближения к точке – локального минимума функции , т.е. получена локализующая тройка В качестве такой тройки можно воспользоваться, например, вычислениями, полученными на трех последних шагах () методом пассивного поиска. При этом соответствие между и нужно установить так, чтобы выполнялось условие критерия 2: . Вложенная в новая локализующая тройка строится при помощи интерполяционного полинома Ньютона . График полинома является параболой (рис.2.5.1), проходящей через три точки плоскости с координатами . Точка минимума полинома лежит в . Вычислив и , сравним значение со значением и по критерию 2 найдем новую локализирующую тройку.
Полином удобно представить в форме Ньютона с разделенными разностями:
(13)
y
y=
y=
x
Рис.2.8. К методу парабол
В формуле (13) коэффициенты при неизвестных полинома представлены формулами:
|
;
;
.
Сделав соответствующие приведения в терминах разделенных разностей, точку можно определить, воспользовавшись одной из формул:
, (14)
или
, (15)
или
. (16)
Выбор точки следует сделать по тому представлению, которое будет вычисляться с меньшей потерей точности (значащих цифр в разностях). Однако, такой выбор на ЭВМ осуществить достаточно трудоемко. Поэтому, для определения конкретной точки в ЭВМ-реализации можно принять условие: выбрать ту точку, значение которой по величине является средним из трех возможных. То есть:
, если , или ;
, если , или ; (17)
, если , или .
Кроме того, и это существенно, на выбор точки влияет также то, насколько близко точка оказывается к точкам и на числовой оси.
Если
а) ,
или
б) ,
то большое значение N в этих отношениях () означает одностороннюю сходимость к стационарной точке, но не к точке локального минимума. Поэтому, при выполнении условия а) следует положить , а при выполнении условия б) принять точку .
Начало
1
Ввод
Конец
проверка нет выбор
условий новой нет
критерия 2 тройки
да
вычисление
по (14)-(16) и
выбор по (17)
нет
|
14
да
2
да
2
да да
да
1
Схема 2.5. К методу парабол
* Леонардо Пизанский (1180-1240)–итальянский математик.
|
|
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!