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

является одновременно и сильными и слабыми сторонами метода: с одной
стороны он черезвычайно надежен, с другой стороны его скорость сходи-
                    :
мости невелика и он не использует возможного ”хорошего” поведения в
окрестности .

2.3.2        Поиск Фибоначчи
Если вычисление производный функции       затруднено, то возникает ин-                      
тересная задача построения эффективного метода решения (25), используя
лишь значения функции. Если в качестве показателя эффективности мето-
да считать длину интервала неопределенности после вычисления заданого
числа значений целевой функции, оптимальным является метод использ-
ующий так называемые числа Фибоначчи, впервые рассмотренные в XIII
веке итальянским математиком Фибоначчи.
   Эти числа образуют последовательность      , построенную по следу-                               2

                                                                      
ющим правилам:
                                                  +*,                                              <%'0*!/0/
Пусть        — количество вычислений функции           , которые мы можем себе                         
позволить. Отмасштабировав соответствующим образом начальный интер-
вал, можно считать, что он имеет исходную длину, равную 
 . Мы пока-
                                    

жем, что после
                                                 * 
                         вычислений длина интервала неопределенности может
быть сделана равной             .
      В качестве первого шага вычислим           в точках      
    
   
 . В                                         %@                            

    
ть либо до
  
      

                 %'
                
                               
зависимости от результатов интервал неопределенности можно уменьши-
                   
 ( см. рис. 1) или до 

                                                     
 ( см. рис. 2). Поскольку
                  
 , то второй случай сдвигом координат приводится к пер-
                                                                                                                
                                             
вому. Следовательно, в любом случае длина интервала неопределенности
уменьшается до 
 .

     Более того, внутри этого интервала находиться уже вычисленная точка
                                                                                                          

 ( в первом случае ) или 
         

                                                       
теьно вычислив в 
 или 
 , восстанавливаем ситуацию начального          *
                                                   
 ( во втором ). Дополни-
                                                                                                                              -
интервала, лишь с заменой

                *
                                   на
лучим интервал неопределенности, равный
                                             . Проделав
                                                            *
                                                                таких шагов, по-
                                                          с вычисленной внутри
                                   , то можно вычислить в точках 
                                                                                                           -
                                                                                                                                                     *       
                                                                                                    /
                                      *
точкой           . Так как                                                    для
                                                                                                                                                

                                                             &                                                        -            - 
достаточно малого и сузить интервал неопределенности до . Количество
вычислений функции при этом составляет                                    .
      Асимптотическая ( при           ) скорость сходимости поиска Фибонач-
         
 от того, как быстро растут числа Фибоначчи. Представив 
 в
         
чи зависит
виде
                       
              и использовав реккурентное соотношение для чисел Фибоначчи

                                                                 

                                                                     & *<%
получим для характеристическое уравнение



с корнями
                                               *                  
                                                                     L !-9  7*                   , L -'
                                                                               16