Нелинейное программирование. Нурминский Е.А. - 13 стр.

UptoLike

ВУЗ: 

ДВФУ | Владивосток

Составители: 

Рубрика: 

2.2 Скорость сходимости градиентного метода
В вычислительной практике большое значение имеет не только сам факт
сходимости метода к решению задачи, но и то, насколько быстро он дост-
игает приемлимую точность решения. Точность решения при этом можно
измерять отклонением вычисляемого значения целевой функции от мини-
мума:
или отклонением самой точки от истиного положения оптимума:
Если при то говорят, что имеет место сходимость по функц-
ионалу, а если , то говорят, что имеет место сходимость по решению.
Величины , могут убывать как геометрические прогресии:
для некоторых констант . В этом случае говорят о линейной ско-
рости сходимости и эффективность определяется значениеми множителей
, . Для дважды дифференцируемых функций в окрестности миниму-
ма обычно оценивается как , в силу квадратичного характера
поведения в этой окрестности.
Если близко к , то сходимость быстрая, если близко к ( как это
к несчастью чаще всего и бывает ), то реальная сходимость может быть
довольно медленной.
Некоторые высокоэффективные численные методы обладают и более
высокой скоростью сходимости, например
или
В этом случае сходимость называют квадратичной. Как легко видеть, при
этом количество точных знаков на каждой итерации удваивается.
Квадратичную сходимость имеют методы Ньютоновского типа, с кото-
рыми мы ознакомимся позднее, а пока исследуем скорость сходимости пр-
остейших вариантов градиентных методов.
Теорема 14 Пусть — дважды дифференцируемая функция с поло-
жительно определенной матрицей вторых производных , удовлетв-
оряющей неравенствам .
3
Тогда градиентный метод с
постоянным шагом
имеет следующую оценку скорости сходимости:
где .
3
Матричное неравенство
означает, что неотрицательно определена, —
единичная матрица.
13
2.2        Скорость сходимости градиентного метода
В вычислительной практике большое значение имеет не только сам факт
сходимости метода к решению задачи, но и то, насколько быстро он дост-
игает приемлимую точность решения. Точность решения при этом можно


                                                                                                  :
измерять отклонением вычисляемого значения целевой функции от мини-
мума:
                                      
                                                                             
                               

                                                                                             5  : 
или отклонением самой точки от истиного положения оптимума:
                                                                               = 
Если 
              &
             при      %
                                 

                                        & =& %
                        то говорят, что имеет место сходимость по функц-
                                    =
ионалу, а если                 
                    , то говорят, что имеет место сходимость по решению.

                                               #
   Величины  ,  могут убывать как геометрические прогресии:
                                                                                      = #
                                                                                                 = 7*!8-90//
для некоторых констант
                                                                 
                               . В этом случае говорят о линейной ско-      =
  =
                                                                                        
рости сходимости и эффективность определяется значениеми множителей
   
  , . Для дважды дифференцируемых функций в окрестности миниму-
                                                                                       = 
ма
                   
      обычно оценивается как          , в силу квадратичного характера
поведения в этой окрестности.
                                                 %
   Если близко к , то сходимость быстрая, если близко к ( как это                                                                    *
к несчастью чаще всего и бывает ), то реальная сходимость может быть
довольно медленной.
   Некоторые высокоэффективные численные методы обладают и более

                                                                  #                              
                                                                                                        #     
высокой скоростью сходимости, например
                                                                           
                                                                                       или 
В этом случае сходимость называют квадратичной. Как легко видеть, при
этом количество точных знаков на каждой итерации удваивается.
   Квадратичную сходимость имеют методы Ньютоновского типа, с кото-
рыми мы ознакомимся позднее, а пока исследуем скорость сходимости пр-
остейших вариантов градиентных методов.
                                                     
Теорема 14 Пусть        — дважды дифференцируемая функция с поло-
                                                                                                                          > > 
жительно определенной матрицей вторых производных
оряющей неравенствам           . 3 Тогда градиентный    #  >>  #
                                                        , удовлетв-
                                                            метод с
постоянным шагом
                                                            >  5  %'0*!0//
имеет следующую оценку скорости сходимости:
                                               =  5                          : S #
где    #            *
                        
                           +              *  2 . 
   3 Матричное неравенство                                            означает, что                неотрицательно определена,      —
единичная матрица.


                                                                                              13

Страницы