Методы оптимизации. Азарнова Т.В - 24 стр.

                                                       26

                  a   y       z    x*          b   x                a       x* y           z     b   x



                            Рис.9                                            Рис. 10
                            Метод деления промежутка пополам
      Метод деления промежутка пополам относится к последовательным
стратегиям и позволяет исключить из дальнейшего рассмотрения на каждой
итерации половину текущего промежутка неопределенности. Работа
алгоритма    заканчивается,     когда         длина     текущего          промежутка
неопределенности оказывается не более некоторой величины ε >0 , которую
называют требуемой точностью. Метод принадлежит к методам нулевого
порядка. На каждой итерации сравниваются значения функции в трех
пробных точках, равномерно распределенных на текущем промежутке, т.е.
делящих его на четыре равные части.
                                     Алгоритм
  Шаг 1. Задать начальный промежуток неопределенности L0 =[a 0 , b0 ] и
ε >0 - требуемую точность. Положить k =0 .
                          a +bk
  Шаг 2. Вычислить: x kc = k
                             2
                                   , L2 k =bk −a k , f x kc .             ( )
                                L2k                 L2k
  Шаг 3. Вычислить: y k =a k +        , z k =bk −        , f ( yk ) , f (zk ) .
                                  4                  4
  Шаг 4. Сравнить значения f ( y k ) и f ( x kc ) :
         а) если                         ( )
                          f ( y k ) < f x kc , исключить промежуток           (x   c
                                                                                   k , bk   ],   положив
bk +1 =x kc , a k +1 =a k . Средней точкой нового промежутка становится точка
y k : x kc +1 = y k . Перейти к шагу 6.
                                    ( )
          б) если f ( y k ) ≥ f x kc , перейти к шагу 5.
     Шаг 5. Сравнить f ( z k ) и f ( x kc ) :
а)     если                        ( )
                      f ( z k ) < f x kc ,   исключить       промежуток      [a        c
                                                                                  k , xk    )    положив
a k +1 =x kc , bk +1 =bk . Средней точкой нового промежутка становится точка
z k : x kc +1 =z k . Перейти к шагу 6.
б) если                           ( )
               f ( z k ) ≥ f x kc , исключить промежутки [a k , y k ), (z k , bk ], положив
a k +1 = y k , bk +1 =z k . Средняя точка нового промежутка не изменится
x kc +1 =x kc .
     Шаг 6. Вычислить                   L2( k +1) =bk +1 −a k +1 . Если   L2( k +1) ≤ε , алгоритм
завершает свою работу, и делается вывод, что x * ∈L2( k +1) , а в качестве
приближенного решения можно, например, взять середину данного