Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Топ:
Комплексной системы оценки состояния охраны труда на производственном объекте (КСОТ-П): Цели и задачи Комплексной системы оценки состояния охраны труда и определению факторов рисков по охране труда...
Выпускная квалификационная работа: Основная часть ВКР, как правило, состоит из двух-трех глав, каждая из которых, в свою очередь...
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного хозяйства...
Интересное:
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Аура как энергетическое поле: многослойную ауру человека можно представить себе подобным...
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Дисциплины:
2020-12-06 | 397 |
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)–итальянский математик.
|
|
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!