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

Заметим, что точка  (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)–итальянский математик.