2.3.2. Оценка погрешности метода золотого сечения

Заметим, что точка (n-тая итерация) отстоит от концов отрезка на величину, не превышающую . Поэтому верна оценка:

. (8)

Каждая итерация сокращает длину отрезка локализации в раз . Значит, и справедлива следующая априорная оценка погрешности:

. (9)

Таким образом, метод золотого сечения сходится со скоростью геометрической прогрессии, знаменатель которой .

2.4. Метод Фибоначчи

Данный метод обеспечивает максимальное гарантированное сокращение отрезка локализации при заданном числе N вычислений функции и основан на использовании чисел Фибоначчи таких, что: для всех

при начальных значениях

Метод Фибоначчи состоит из шагов. Очередной -й шаг выполняется аналогично -й итерации метода деления отрезка пополам, но точки и находятся по формулам

, (10)

где – длина отрезка локализации (рис.2.7).

Рис. 2.7. Графическая интерпретация метода Фибоначчи

Аналогично методу деления отрезка пополам определяется новый отрезок локализации:

если , то ;

если , то .

В первом случае за очередное приближение к точке минимума принимают , во втором случае – .

2.4.2. Оценка погрешности метода Фибоначчи

Так же, как и в методе золотого сечения точка будет однозначно совпадать с одной из точек (в зависимости от выбора подотрезка на очередном шаге локализации):

, . (11)

Поэтому на очередном шаге достаточно вычислить значение функции лишь в одной недостающей точке. В результате выполнения шагов отрезок локализации уменьшается в раз, а точка оказывается центральной для последнего отрезка локализации . Поэтому для справедлива следующая оценка погрешности:

. (12)

2.5. Метод парабол

Существует множество методов локализации экстремума гладкой функции. Некоторые из них, например метод бисекции и метод Ньютона требуют вычисления производных. Такие методы достаточно эффективны, но не очень удобны для программной реализации, так как именно проблема вычисления производных является трудоемкой в ЭВМ-реализации. Предлагаемый метод не требует вычисления производных и, как мы убедимся ниже, является достаточно эффективным в случае удачной предварительной его настройки.

Предположим, что уже известны три предыдущих приближения к точке – локального минимума функции , т.е. получена локализующая тройка В качестве такой тройки можно воспользоваться, например, вычислениями, полученными на трех последних шагах ( ) методом пассивного поиска. При этом соответствие между и нужно установить так, чтобы выполнялось условие критерия 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)–итальянский математик.