УМК (1013374), страница 28
Текст из файла (страница 28)
Сравним f x 1 и f x 0 . Вывод: f x 1 < f x 0 . Перейдем к шагу 9.90 . Вычислим x 1x1 − x 001010Вывод: положим k = 1 и перейдем к шагу 3.( ) ( )∇f (x ) : ∇f ( x1 )31 . Вычислим ∇f x 1 : ∇f x 1 = ( − 0,625; 0,51) .41 . Вычислим1T= 0,81 > 0,1 . Перейдем к шагу 5.51 . Проверим условие k ≥ M : k = 1 < 10 = M .
Перейдем к шагу 6.61 . Зададим t1 = 0,25 .71 . Вычислим x 2 : x 2 = ( − 0,25; 0,375) − 0,25 ( − 0,625; 0,5)TT( )= ( − 0,094; 0,25) ;Tf x 2 = 0,056 .( )( )( ) ( )− x и f (x ) − f (x ) := 0,2 > 0,15 ;f (x ) − f (x )81 . Сравним f x 2 с f x 1 . Вывод: f x 2 < f x 1 . Перейдем к шагу 9.91 .
Вычислим x 2x 2 − x112121= 0,115 < 0,15 .Вывод: положим k = 2 и перейдем к шагу 3.( ) ( )∇f (x ) : ∇f (x )32 . Вычислим ∇f x 2 : ∇f x 2 = ( − 0,126; 0,406) .4 2 . Вычислим22T= 0,425 > 0,1 . Перейдем к шагу 5.5 2 . Проверим условие k ≥ M : k = 2 < 10 = M , перейдем к шагу 6.6 2 .
Зададим t 2 = 0,25 .7 2 . Вычислим x 3 : x 3 = ( − 0,094; 0,25) − 0,25 ( − 0,126; 0,406)TT( )= ( − 0,063; 0,15) ;f x 3 = 0,021 .( )( )( ) ( )− x и f (x ) − f (x ) := 0,105 < 0,15 ;f (x ) − f (x ) = 0,035 < 0,15 .82 . Сравним f x 3 и f x 2 . Вывод: f x 3 < f x 2 . Перейдем к шагу 9.92 . Вычислим x 3x3 − x223232Вывод: положим k = 3 и перейдем к шагу 3.( ) ( )∇f (x ) : ∇f (x )33 . Вычислим ∇f x 3 : ∇f x 3 = ( − 0,102; 0,237) .43 . Вычислим33T= 0,257 > 0,1 . Перейдем к шагу 5.53 .
Проверим условие k ≥ M : k = 3 < 10 = M , перейдем к шагу 6.63 . Зададим t3 = 0,25 .166T73 . Вычислим x 4 : x 4 = ( − 0,063; 0,15) − 0,25 ( − 0,102; 0,237)T( )T= ( − 0,038; 0,091) ;Tf x 4 = 0,0076 .( )( ) ( ) ( )9 . Вычислим x − x , f (x ) − f (x ) :x − x = 0,064 < 0,15 ;f (x ) − f (x ) = 0,015 < 0,15 .) − f (x ) < ε выполнены при k = 2,3 . РасчетУсловияx−x <ε ,f (xокончен.
Найдена точка x = ( − 0,038; 0,091) ; f ( x ) = 0,0076 .83 . Сравним f x 4 и f x 3 : f x 4 < f x 3 .344k +13433k4k +123k2T44II. Проведем анализ точки x 4 . Функция f ( x ) = 2 x12 + x1x 2 + x 2 2 является дваждыдифференцируемой, поэтому проведем проверку достаточных условий минимума в точке⎛ 4 1⎞x 4 . Для этого проанализируем матрицу Гессе H = ⎜⎟ .
Матрица является постоянной⎝ 1 2⎠и положительно определенной (т.е. H > 0 ), так как оба ее угловых минора Δ 1 = 4 иΔ 2 = 7 положительны. Следовательно, точка x 4 = ( − 0,038; 0,091)Tесть найденное при-( )ближение точки локального минимума x ∗ = (0,0) , а значение f x 4 = 0,0076 есть найT( )денное приближение значения f x ∗ = 0 . Б. МЕТОД НАИСКОРЕЙШЕГО ГРАДИЕНТНОГО СПУСКААлгоритмШаг 1. Задать x 0 , ε1 > 0 , ε 2 > 0 , предельное число итераций M. Найти градиентT⎛ ∂ f (x )∂ f (x ) ⎞⎟ .функции в произвольной точке ∇f ( x ) = ⎜⎜,...,⎟xx∂∂1n ⎠⎝Шаг 2. Положить k = 0 .( )Шаг 3. Вычислить ∇f x k .( )Шаг 4. Проверить выполнение критерия окончания ∇f x kа) если критерий выполнен, то x ∗ = x k ;б) если критерий не выполнен, то перейти к шагу 5.Шаг 5.
Проверить выполнение неравенства k ≥ M :а) если неравенство выполнено, то x ∗ = x k ;б) если нет, то перейти к шагу 6.Шаг 6. Вычислить величину шага t k∗ из условия(.( )) → mintϕ(t k ) = f x k − t k ∇f x kk167< ε1 :( )Шаг 7. Вычислить x k +1 = x k − t k∗ ∇f x k .Шаг 8. Проверить выполнение условий(x k +1 − x k < ε 2 ,) ( )f x k +1 − f x k< ε2 :а) если оба условия выполнены при текущем значении k и k = k − 1 , то расчетокончен, x ∗ = x k +1 ;б) если хотя бы одно из условий не выполнено, то положить k = k + 1 и перейти кшагу 3.Геометрическая интерпретация метода для n = 2 приведена на рис.
2.C1 > C 2x2f ( x ) = C1x0− ∇f ( x 0 )x1f (x ) = C 2x1Рис. 2Пример 2. Найти локальный минимум функцииf ( x ) = 2 x12 + x1x 2 + x 2 2 . I. Определим точку x k , в которой выполнен по крайней мере один из критериевокончания расчетов.1. Зададим x 0 , ε1 , ε 2 , M : x 0 = (0,5;1) ; ε1 = 0,1; ε 2 = 0,15; M = 10 . Найдем граTдиент функции в произвольной точке ∇f ( x ) = (4 x1 + x 2 ; x1 + 2 x 2 )T .2. Положим k = 0 .( ) ( )∇f (x ) : ∇f (x )30 . Вычислим ∇f x 0 : ∇f x 0 = (3; 2,5) .4 0 .
Вычислим00T= 3,9 > 0,1 . Перейдем к шагу 5.5 0 . Проверим условие k ≥ M : k = 0 < 10 = M , перейдем к шагу 6.6 0 . Следующую точку найдем по формулеx 1 = x 0 − t 0 ∇f ( x 0 ) = (0,5; 1)T − t 0 (3; 2,5)T = (0,5 − 3t 0 ; 1 − 2,5 ⋅ t 0 )T .168Подставим полученные выражения x11 = 0,5 − 3t 0 , x 21 = 1 − 2,5 ⋅ t 0 для координатв f ( x ) : ϕ(t 0 ) = 2 ⋅ (0,5 − 3t 0 ) 2 + (0,5 − 3t 0 ) ⋅ (1 − 2,5 ⋅ t 0 ) + (1 − 2,5 ⋅ t 0 ) 2 . Найдем минимумфункции ϕ(t 0 ) по t 0 с помощью необходимых условий безусловного экстремума:dϕ(t 0 )dt 0= 4 ⋅ (0,5 − 3t 0 ) ⋅ (−3) + (−3) ⋅ (1 − 2,5t 0 ) + (−2,5) ⋅ (0,5 − 3t 0 ) + 2 ⋅ (1 − 2,5 ⋅ t 0 ) ⋅ (−2,5) =d 2 ϕ(t 0 )∗= 63,25 > 0 , найденное знаdt 02чение шага обеспечивает минимум функции ϕ(t 0 ) по t 0 .Заметим, что можно получить формулу для вычисления наилучшей величины шага∗t k на любой итерации из условия= −15,25 + 63,25 ⋅ t 0 = 0 . Отсюда t 0 ≅ 0,24 . Так как(.( )) → mintϕ(t k ) = f x k − t k ∇f x kИмеем( ) (∇f x k = 4 x1k + x 2k ; x1k + x 2k)Tk( ) [(2k1k2t k∗=)) + (x − t (4x + x ))(x+ ( x − t ( x + x )) .ϕ(t k ) = 2 x1k − t k (4 x1k + x 2k )Из условия((4 4 x1 + x 2)k 2(4 x1k(+ 2 4 x1Определим t 0∗ : t 0∗ = 0,24 .k12k1( )k2)− t k (x1k + x 2k ) ++ 2x 2 kkk+ 2x 2)) + 2 (x2T)k 2.k+ 2x 2T= ( − 0,22; 0,4) .17 0 .
Найдем x 1 = x 0 − t 0∗ ∇f x 0 : x 1 = (0,5;1) − 0,24(3; 2,5)T( ) ( ):80 . Вычислим x 1 − x 0 : x 1 − x 0 = 0,937 > 0,15 . Вычислим f x 1 − f x 0( ) ( )f x1 − f x 0= 1,83 > 0,15 . Вывод: положим k = 1 и перейдем к шагу 3.( ) ( )∇f (x ) = 0,752 > 0,1 .31 . Вычислим ∇f x 1 : ∇f x 1 = ( − 0,48; 0,58) .41 . ВычислимT151 .
Проверим условие k ≥ M : k = 1 < 10 = M .61 . Определим t1∗ : t1∗ = 0,546 (см. п. 6 0 ).( )71 . Найдем x 2 = x 1 − t1∗ ∇f x 1 :x 2 = ( − 0,22; 0,4) − 0,546 ( − 0,48; 0,58)Tx 2 − x1= (0,04; 0,08) .TT( ) ( )= 0,41 > 0,15 ;f (x ) − f (x )81 . Вычислим x 2 − x 1 ,f x 2 − f x1 :2169)]2k12k2k2) + (x+ x )(x+ x2kkk1kkdϕ= 0 получаемdt kk(; x k − t k ∇f x k = x1k − t k 4 x1k + x 2k ; x 2k − t k x1k + x 2k1= 0,156 > 0,15 .T,Положим k = 2 и перейдем к шагу 3.( ) ( )∇f (x ) : ∇f (x )32 . Вычислим ∇f x 2 : ∇f x 2 = (0,24; 0,2) .4 2 . Вычислим22T= 0,312 > 0,1 .5 2 . Проверим условие k ≥ M : k = 2 < 10 = M .6 2 .
Определим t 2∗ : t 2∗ = 0,24 (см. п. 6 0 ).( )7 2 . Найдем x 3 = x 2 − t 2∗ ∇f x 2 :x 3 = (0,04; 0,08)− 0,24 (0,24; 0,2)T= ( − 0,0176; 0,032) .T( ) ( ):= 0,0749 < 0,15 ;f (x ) − f (x )82 . Вычислим x 3 − x 2 ,x3 − x2Tf x3 − f x232= 0,0116 < 0,15 .Положим k = 3 и перейдем к шагу 3.( ) ( )∇f (x ) : ∇f (x ), f ( x ) = 0,00127 .33 . Вычислим ∇f x 3 : ∇f x 3 = ( − 0,012; − 0,0816) .43 . Вычислим3x 3 = ( − 0,0176; 0,032)T3T= 0,082 < 0,1 .
Расчет окончен. Найдена точка3II. Проведем анализ точки x 3 . В примере 1 было показано, что точка x 3 являетсянайденным приближением точки минимума x ∗ . ■В. МЕТОД ГАУССА–ЗЕЙДЕЛЯАлгоритмШаг 1. Задать x 00 , ε1 > 0 , ε 2 > 0 ; предельное число M циклов счета, кратное n ,где n – размерность вектора x . Найти градиент ∇f (x ) .Шаг 2. Задать номер цикла j = 0 .Шаг 3.
Проверить условие j ≥ M :а) если j ≥ M , то расчет окончен и x ∗ = x jk ;б) если j < M , то перейти к шагу 4.Шаг 4. Задать k = 0 .Шаг 5. Проверить условие k ≤ n − 1 :а) если k ≤ n − 1 , то перейти к шагу 6;б) если k = n , то положить j = j + 1 и перейти к шагу 3.( )Шаг 6. Вычислить ∇f x jk .( )Шаг 7. Проверить выполнение условия ∇f x jk< ε1 :а) если условие выполнено, то расчет окончен и x ∗ = x jk ;б) если нет, то перейти к шагу 8.170Шаг 8. Вычислить t k∗ из условия⎛⎞⎛ ∂ f (x ) ⎞⎟⎟e⋅ϕ(t k ) = f ⎜ x jk − t k ⎜⎜k +1 ⎟ → min .⎟⎜tk⎝ ∂ x k +1 ⎠ x = x jk⎝⎠⎛ ∂ f (x ) ⎞⎟Шаг 9.
Вычислить x jk +1 = x jk − t k∗ ⎜⎜⋅ e k +1 .⎟x∂⎝ k +1 ⎠ x = x jkШаг 10. Проверить выполнение условийx jk +1 − x jk < ε 2 ,() ( )f x jk +1 − f x jk< ε2 :а) если оба условия выполнены в двух последовательных циклах с номерами j иj − 1 , то расчет окончен, найдена точка x ∗ = x jk +1 ;б) если не выполняется хотя бы одно условие, положить k = k + 1 и перейти кшагу 5.Геометрическая интерпретация метода для n = 2 приведена на рис.
3.x2f ( x ) = C1C1 > C 2x 01x 00x 02f ( x) = C 2x1Рис. 3Пример 3. Найти локальный минимум функцииf ( x ) = 2 x12 + x1x 2 + x 2 2 . I. Определим точку x jk , в которой выполнен хотя бы один из критериев окончания расчетов.1. Зададим x 00 , ε1 , ε 2 , M : x 00 = (0,5;1) , ε1 = 0,1; ε 2 = 0,15; M = 10 . Найдем граTдиент функции в произвольной точке ∇f ( x ) = (4 x1 + x 2 ; x1 + 2 x 2 )T .2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
