Вычислительная математика

       

          
 
 
 

                                           Рисунок 1 - Последовательность точек α. 

     Из  рисунке 1 видно, что интервал неопределенности лежит между точками α₀ и α₂. Выберем новую точку α₃ так, чтобы получить золотое сечение интервала неопределенности (рис. 2).

       
 
 
 
 
 
 

Рисунок 2 - Сокращение интервала неопределенности. 

     Вычислительный  процесс сокращения интервала необходимо продолжить, пока не будет выполнено  условие одномерного поиска

        ,                                                               (9)

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

Для нашей функции  имеем: 

Начальные условия:

=-3,2        =5,5        F( )=424,47 

Итерация 1:

(i) =-3.2    (i) =5.5

F[ (i), (i)]=424.4701

Составляющие  вектора градиента: [-0,0087065794645  0,19069660583]

Вектор Н:      1.000 0.0001

                       0.000 1.0001

Составляющие  вектора направления: [0,0087065794645 -0,19069660583] Оптимальное значение α: 1.2472651878

Вектор σ при оптимальном α: [ 0,10859413471  -2.3784923789]

(i+1)=-3.091406

(i+1)=3.121508

F[ (i+1), (i+1)]=2.937506661 

Итерация 2:

(i) =-3.091406    (i) =3.120508

F[ (i), (i)]=2.9375066641

Составляющие  вектора градиента: [-2.1448391281 -0.9834990181]

Вектор Н:     0.028   -0.611

                      -0.611  0.028

Составляющие  вектора направления: [-0,0080837138148  -0,13902022035] Оптимальное значение α: 0.024030782817

Вектор σ при оптимальном α: [ 0.00019425806716  -0.0033407647224]

(i+1)=-3.0911212

(i+1)=3.118167

F[ (i+1), (i+1)]=2.937065238 

Итерация 3:

(i) =-3.0911212   (i) =3.118167

F[ (i), (i)]= 2.937065238

Составляющие  вектора градиента: [-2.1432230730  -1.2455110308]

Вектор Н:    0.000   -0.001

                      -0.001  0.000

Составляющие  вектора направления: [-0,006364664546  -0.00009168204582] Оптимальное значение α: 17.462189909

Вектор σ при оптимальном α: [ 0.28576288009   -0.0016009692953]

 (i+1)= -2.805449

(i+1)= 3.134177

F[ (i+1), (i+1)]= 0.000332520 

Итерация 4:

(i) = -2.805449   (i) =3.134177

F[ (i), (i)]= 2.937065238

Составляющие  вектора градиента: [-0.01772905304  0.23025870287 ]

Вектор Н:    0.013   -0.000

                      -0.000  0.013

Составляющие  вектора направления: [-0.00026278296199  -0.0028781129997] Оптимальное значение α: 0.97207338405

Вектор σ при оптимальном α: [ 0.00025544432313   -0.0027977370433]

(i+1)= -2.805193

(i+1)= 3.131379

F[ (i+1), (i+1)]= 0.000000354 

Итерация 5:

(i+1)= -2.805193

(i+1)= 3.131379

F[ (i+1), (i+1)]= 0.000000354

Составляющие  вектора градиента: [-0.0047976356877  0.0052348000258 ]

Вектор Н:    0.013   -0.000

                      -0.000  0.013

Составляющие  вектора направления:[-0.000066170409115 -0.00006.6728224783] Оптимальное значение α: 1.308962

Вектор σ при оптимальном α: [ 0.000086614551056   -0.000087344710569]

(i+1)= -2.805107

(i+1)= 3.131291

F[ (i+1), (i+1)]= 0.000000022 

При достижении пределов заданной точности поиск минимума завершается. Минимум найден. 

3.3.  Сокращение интервала неопределенности

методом квадратичной аппроксимации

      В основе метода лежит аппроксимация  функции Ф(a) квадратичным полиномом. Для ускорения поиска на этапе выделения интервала неопределенности необходимо ввести, как и ранее, переменный шаг a_i в (4):  ;                                                              (10)

a₀ = 1, если при этом происходит убывание функции, a_-1 = 0, t - коэффициент, численное значение которого в начале одномерного поиска равно нулю, а затем возрастает на 1 через каждые R шагов. Пусть произведены измерения функции в точках a₀, a₁, a₂  согласно алгоритму .  Интервал неопределенности лежит между точками a₀ и a₂ (рис. 1). Для сокращения интервала заменяем реальную функцию Ф(a) аппроксимирующей функцией Ф_апр(a), которая проходит через те же точки a₀, a₁, a₂, Ф_апр(a)=aa²+ba+c и имеет координату минимума a_опт= – b/(2a). Связывая неизвестные коэффициенты a, b, c со значениями  a₀, a₁, a₂  и Ф(a₀), Ф(a₁), Ф(a₂) получаем расчетную формулу:

      .                       (11)

     Причем  точка a₃=a_опт (рис. 2) попадает внутрь интервала неопределенности a₂ - a₀.

     Новый интервал неопределенности уменьшился и стал равным          a₂ - a₁. Вычислительный процесс сокращения интервала необходимо продолжить, пока не будет выполнено условие одномерного поиска (9).

     Среди алгоритмов, использующих информацию о градиенте, наиболее распространенными  являются квазиньютоновские. В этих (итерационных) алгоритмах целевая функция в окрестностях произвольной точки аппроксимируется квадратичной функцией, при этом на каждой итерации решается задача локальной минимизации

      ,

где H – симметричная и положительно определенная матрица вторых частных и смешанных производных (матрица Гессе, или гессиан), с – постоянный вектор, b – константа.

     Оптимальное решение приведенной задачи соответствует  нулевым значениям первых производных, то есть  

      ,  откуда  .

     Ньютоновские  алгоритмы (в отличие от квазиньютоновских) непосредственно вычисляют Н (как отмечалось, прямое вычисление матрицы Н требует больших вычислительных затрат) и осуществляют движение в рассчитанном на очередной итерации направлении уменьшения целевой функции до достижения минимума (с использованием методов одномерного поиска). В квазиньютоновских алгоритмах такое вычисление не производится, а используется некоторая аппроксимация Н.

     Среди подобных алгоритмов одним из наиболее популярных и используемых в пакете Optimization Toolbox является так называемый BFGS-алгоритм, получивший свое название по фамилиям предложивших его авторов (Broyden, Fletcher, Goldfarb, Shanoo), в котором аппроксимация Н производится итерационно, по формуле

, где  , .

     Заметим, что наиболее удобно иметь аппроксимацию  не матрицы Н, а обратной к ней матрицы Н^-1, приведенное рекуррентное соотношение подобную замену допускает, при этом сам алгоритм становится практически идентичным хорошо известному отечественным исследователям алгоритму Давидона-Флетчера-Пауэлла, за тем исключением, что в последнем векторы q заменены на векторы s и наоборот. 

     Именно  такие алгоритмы являются основой  численных методов, заложенных в  распространенные математические пакеты прикладных программ (MS Excel, Mathcad, Mathlab). 

Блок-схема алгоритма  минимизации функции многих переменных метода

Давидона-Флетчера-Пауэлла  приведена на рисунке 3. 
 

       
 
 
 
 
 
 
 
 
 

     

     

       
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Рисунок 3 - Блок-схема алгоритма минимизации функции

 

Список  литературы: 
 
 

Вычислительная  математика: методические указания к лабораторным работам / Рязан.гос.радиотехн.ун-т.; сост. А.Н.Кабанов.-Рязань, 2008.- 48 c.