УМК (1013374), страница 29
Текст из файла (страница 29)
Зададим j = 0 .30 . Проверим выполнение условия j ≥ M : j = 0 < 10 = M .4 0 . Зададим k = 0 .1715 0 . Проверим выполнение условия k ≤ n − 1 : k = 0 < 1 = n − 1 .( )( )∇f (x )6 0 . Вычислим ∇f x 00 : ∇f x 00 = (3; 2,5) .7 0 . Проверим условие00T< ε1 :( )∇f x 00= 3,9 > 0,1 .80 . Определим величину шага t 0∗ из условия⎞⎛⎛ ∂ f (x ) ⎞⎟ → min .⎟eϕ(t 0 ) = f ⎜ x j 0 − t 0 ⎜⎜⋅1⎟⎟⎜t0x∂0j1 ⎠x =x⎝⎠⎝⎛ ∂ f (x ) ⎞⎟Воспользуемся формулой при k = 0, j = 0 : x 01 = x 00 − t 0 ⎜⎜⋅ e1 .⎟⎝ ∂ x1 ⎠ x = x 00⎛ ∂ f (x ) ⎞⎟Поскольку ⎜⎜= 4 x1 + x 2⎟∂x001 ⎠x =x⎝x = x 00x 01 = (0,5; 1)T − t 0 ⋅ 3 ⋅ (1; 0)T = (0,5 − 3t 0 ; 1)T= 2 + 1 = 3 , e1 = (1; 0)T , тоили x101 = 0,5 − 3t 0 , x 201 = 1 .
Подставляяполученные выражения в f ( x ) , имеем ϕ(t 0 ) = 2(0,5 − 3t 0 ) 2 + (0,5 − 3t 0 ) ⋅ 1 + 1 .dϕ(t 0 )Из необходимого условия экстремума= 4 ⋅ (0,5 − 3t 0 ) ⋅ (−3) − 3 = 0 илиdt 0d 2 ϕ(t 0 )1. Так как= 36 > 0 , то найденное значение шага4dt 0 2обеспечивает минимум функции ϕ(t 0 ) по t 0 .Можно показать, что в силу структуры заданной функции f ( x ) величина шага в36t 0 − 9 = 0находим t 0∗ =⎛ ∂ f (x ) ⎞1⎟⎟направлении − ⎜⎜⋅ e1 не зависит от x k , является постоянной и равной .4⎝ ∂ x1 ⎠ x = x jk⎛ ∂ f (x ) ⎞⎟90 . Определим x 01 = x 00 − t 0∗ ⎜⎜⋅ e1 :⎟∂x1 ⎠ x = x 00⎝x 01 = ( − 0,25;1) .T( ) ( )f (x ) − f (x ) = 0,875 − 2100 . Проверим условия x 01 − x 00 < ε 2 ,x 01 − x 00 = 0,25 > 0,15 ,01f x 01 − f x 0000< ε2 := 1,125 > 0,15 .Положим k = 1 и перейдем к шагу 5.51 .
Проверим условие k ≤ n − 1 : k = 1 = n − 1 .( )( )∇f (x )61 . Вычислим ∇f x 01 : ∇f x 01 = (0;1,75) .71 . Проверим условие01T< ε1 :81 . Определим величину шага t1∗ из условия⎛ϕ(t1 ) = f ⎜ x j1 − t1⎜⎝( )∇f x 01= 1,75 > 0,1 .⎞⎛ ∂ f (x ) ⎞⎟⎜⎟e⋅2 ⎟ → min .⎜ ∂x ⎟t12 ⎠ x = x j1⎝⎠172⎛ ∂ f (x ) ⎞⎟Воспользуемся формулой при k = 1, j = 0 : x 02 = x 01 − t1 ⎜⎜⋅ e2 .⎟⎝ ∂ x 2 ⎠ x = x 01⎛ ∂ f (x ) ⎞⎟Поскольку ⎜⎜= x1 + 2 x 2 x = x 01 = − 0,25 + 2 = 1,75 , e 2 = (0; 1)T , то⎟∂x2 ⎠ x = x 01⎝x 02 = (− 0,25; 1)T − t1 ⋅ 1,75 ⋅ (0; 1)T = (− 0,25; 1 − 1,75 ⋅ t1 )T или x102 = − 0,25; x202 = 1 − 1,75 ⋅ t1 .Подставляя полученные выражения в f ( x ) , имеемϕ(t1 ) = 2(− 0,25)2 + (− 0,25) ⋅ (1 − 1,75 ⋅ t1 ) + (1 − 1,75 ⋅ t1 )2 .Из необходимого условия экстремумаdϕ(t1 )= 0,25 ⋅ 1,75 + 2 ⋅ (1 − 1,75 ⋅ t1 ) ⋅ (−1,75) = 0 или 2 ⋅ 1,75 2 t1 − 1,75 2 = 0dt1d 2 ϕ(t1 )1. Так как= 2 ⋅ 1,75 2 > 0 , то найденное значение шага обеспечива22dt1ет минимум функции ϕ(t1 ) по t1 .находим t1∗ =Можно показать, что в силу структуры функции f ( x ) величина шага в направле⎛ ∂ f (x ) ⎞⎟⎟нии − ⎜⎜⋅ e2⎝ ∂ x 2 ⎠ x = x jkостается постоянной и равной1.2⎛ ∂ f (x ) ⎞T⎟91 .
Вычислим x 02 = x 01 − t1∗ ⎜⎜⋅ e 2 : x 02 = ( − 0,25; 0,125) .⎟⎝ ∂ x 2 ⎠ x = x 01( ) ( )101 . Проверим условия x 02 − x 01 < ε 2 ,x 02 − x 01 = 0,875 > 0,15 ,f x 02 − f x 01( ) ( )f x 02 − f x 01< ε2 := 0,12 − 0,875 = 0,755 > 0,15 .Положим k = 2 и перейдем к шагу 5.5 2 . Проверим условие k ≤ n − 1 : k = 2 = n . Положим j = 1, x 10 = x 02 и перейдемк шагу 3.31 . Проверим условие j ≥ M : j = 1 < 10 = M .41 .
Зададим k = 0 .53 . Проверим условие k ≤ n − 1 : k = 0 < 1 = n − 1 .( )( )∇f (x )( )63 . Вычислим ∇f x 10 : ∇f x 10 = ∇f x 02 = ( − 0,875; 0,00) .73 . Проверим условие10< ε1 :T( )∇f x 10= 0,875 > 0,1 .83 . Полагаем t 0∗ = 0,25 (см. п. 80 ).⎛ ∂ f (x ) ⎞T⎟93 . Вычислим x 11 = x 10 − t 0∗ ⎜⎜⋅ e1 : x 11 = ( − 0,03; 0,125) .⎟⎝ ∂ x1 ⎠ x = x10103 . Проверим условия x 11 − x 10 < ε 2 ,173( ) ( )f x 11 − f x 10< ε2 :( ) ( )x 11 − x 10 = 0,22 > 0,15 ,f x 11 − f x 10= 0,013 − 0,1375 = 0,124 < 0,15 .Положим k = 1 и перейдем к шагу 5.5 4 .
Проверим условие k ≤ n − 1 : k = 1 = n − 1 .( )( )∇f (x )6 4 . Вычислим ∇f x 11 : ∇f x 11 = (0,005; 0,22) .7 4 . Проверим условие11T( )∇f x 11< ε1 := 0,22 > 0,1 .84 . Зададим t1∗ = 0,5 (см. п. 81 ).⎛ ∂ f (x ) ⎞T⎟94 . Вычислим x 12 = x 11 − t1∗ ⎜⎜⋅ e 2 : x 12 = ( − 0,03; 0,015) .⎟⎝ ∂ x 2 ⎠ x = x11( ) ( )104 . Проверим условия x 12 − x 11 < ε 2 ,f x 12 − f x 11( ) ( )x 12 − x 11 = 0,11 < 0,15 ,f x 12 − f x 11< ε2 := 0,0015 − 0,013 = 0,0115 < 0,15 .Положим k = 2 и перейдем к шагу 5.55 . Проверим условие k ≤ n − 1 : k = 2 = n . Положим j = 2, x 20 = x 12 и перейдем к шагу 3.32 .
Проверим условие j ≥ M : j = 2 < 10 = M .4 2 . Зададим k = 0 .5 6 . Проверим условие k ≤ n − 1 : k = 0 < 1 = n − 1 .( )( )∇f (x ) < ε :65 . Вычислим ∇f x 20 : ∇f x 20 = ( − 0,105; 0) .75 . Проверим условие201T( )∇f x 20= 0,105 > ε1 .85 . Зададим t 0∗ = 0,25 (см. п. 80 ).⎛ ∂ f (x ) ⎞T⎟95 . Вычислим x 21 = x 20 − t 0∗ ⎜⎜⋅ e1 : x 21 = ( − 0,004; 0,015) .⎟⎝ ∂ x1 ⎠ x = x 20105 . Проверим условия x 21 − x 20 < ε 2 ,x 21 − x 20 = 0,026 < 0,15 ,( ) ( ) = 0,000197 − 0,0015 = 0,0013 < 0,15 .) − f (x ) < ε выполнены в двух последо, f (xjk +1вательных циклах с номерами j = 2 иT( )< ε2 :f x 21 − f x 20Условия x jk +1 − x jk < ε 2x 21 = ( − 0,004; 0,015) ;( ) ( )f x 21 − f x 20jk2j − 1 = 1 .
Расчет окончен, найдена точкаf x 21 = 0,000197 .Полученыточкипоследовательностиx 00 → x 01 → x 02 = x 10 → x 11 → x 12 = x 20 → x 21 .II. Проведем анализ точки x 21 . Точка x 21 является найденным приближением точки минимума f ( x ) (см. пример 1). 174Занятие 4. ЧИСЛЕННЫЕ МЕТОДЫ ПОИСКА БЕЗУСЛОВНОГОЭКСТРЕМУМА. МЕТОДЫ ПЕРВОГО И ВТОРОГО ПОРЯДКА(продолжение занятия 3)Г.
МЕТОД ФЛЕТЧЕРА–РИВСАПостановка задачиПусть дана функция f ( x) , ограниченная снизу на множестве R n и имеющаянепрерывные частные производные во всех его точках.Требуется найти локальный минимум функции f ( x) на множестве допустимыхрешений X = R n , т.е. найти такую точку x ∗ ∈ R n , чтоf ( x ∗ ) = minn f ( x) .x∈ RАлгоритмШаг 1. Задать x 0 , ε1 > 0 , ε 2 > 0 , M – предельное число итераций.
Найти градиент ∇f (x ) .Шаг 2. Положить k = 0 .( )Шаг 3. Вычислить ∇f x k .( )Шаг 4. Проверить выполнение критерия окончания ∇f x k< ε1 :а) если критерий выполняется, то расчет окончен и x ∗ = x k ;б) если нет, то перейти к шагу 5.Шаг 5. Проверить условие k ≥ M :а) если неравенство выполняется, то расчет окончен и x ∗ = x k ;б) если нет, то при k = 0 перейти к шагу 6, а при k ≥ 1 перейти к шагу 7.( )Шаг 6. Определить d 0 = − ∇f x 0 .Шаг 7. Определитьβ k −1 =( )∇f x(∇f x2kk −1)2,( ( )[ ( ) (( )⎡⎧ ∇f x k , ∇ f x k − ∇ f x k − 1⎢⎪2⎪k −1⎢β∇fx=⎨⎢ k −1⎪⎢⎪⎩ 0, k ∈ J⎢⎣( )Шаг 8. Определить d k = − ∇f x k + β k −1 d k −1 .()Шаг 9. Найти t k∗ из условия ϕ(t k ) = f x k + t k d k → min .tkШаг 10.
Вычислить x k +1 = x k + t k∗ d k .Шаг 11. Проверить выполнение условийx k +1 − x k < ε 2 ,175() ( )f x k +1 − f x k< ε2 :) ] ),⎤k ∉J⎥⎥.⎥⎥⎥⎦а) в случае выполнения обоих условий в двух последовательных итерациях с номерами k и k − 1 расчет окончен, найдена точка x * = x k +1 ;б) если не выполняется хотя бы одно из условий, положить k = k + 1 и перейтик шагу 3.Геометрическая интерпретация метода для n = 2 изображена на рис.
4.x2x0− ∇f ( x 1 )x1C1 > C 2f ( x) = C1d 0 = −∇f ( x 0 )f ( x) = C 2d1β0d 0x∗0x1Рис. 4Пример 4. Найти локальный минимум функции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 )30 . Вычислим ∇f x 0 : ∇f x 0 = (3; 2,5) .4 0 .
Проверим условиеT0< ε1 :( )∇f x 0= 3,9 > 0,1 .5 0 . Проверим условие k ≥ M : k = 0 < 10 = M .( )6 0 . Определим d 0 = − ∇f x 0 : d 0 = − (3; 2,5) .T()90 . Определим t 0∗ из условия f x 0 + t 0 d 0 → min : t 0∗ = 0,24 (см. пример 2, такt0как первая итерация выполняется по методу наискорейшего спуска).100 . Вычислим x 1 = x 0 + t 0∗ d 0 : x 1 = ( − 0,22; 0,4) .T110 .
Проверим условия x 1 − x 0 < ε 2 ,176( ) ( )f x1 − f x 0< ε2 :( ) ( )x 1 − x 0 = 0,937 > 0,15 ;f x1 − f x 0= 0,17 − 2 = 1,83 > 0,15 .Положим k = 1 и перейдем к шагу 3.( )( )∇f (x )31 . Вычислим ∇f x 1 : ∇f x 1 = ( − 0,48; 0,58) .41 . Проверим условие1T( )∇f x 1< ε1 := 0,752 > 0,1 .51 . Проверим условие k ≥ M : k = 1 < 10 = M .71 . Определим β 081 .
Определим d 1( ): β = 0,0373 .=∇f (x )= − ∇f (x ) + β d :∇f x 1021d 1 = − ( − 0,48; 0,58)T0200− 0,0373 (3; 2,5)T(= ( 0,368; − 0,673) .T)91 . Определим t1∗ из условия f x 1 + t1 d 1 → min . Воспользуемся формулойt1x 2 = x 1 + t1 d 1 = (− 0,22; 0,4)T + t1 (0,368 ; − 0,673)T = (− 0,22 + 0,368 t1 ; 0,4 − 0,673 t1 )T .Подставляя полученное выражение в f ( x ) , имеемϕ(t1 ) = 2 ⋅ (− 0,22 + 0,368 t1 ) 2 + (− 0,22 + 0,368 t1 ) ⋅ (0,4 − 0,673 t1 ) + (0,4 − 0,673 t1 ) 2 .Применяя необходимое условие безусловного экстремумаd ϕ(t1 )= 4 ⋅ (− 0,22 + 0,368 t1 ) ⋅ 0,368 + 0,368 ⋅ (0,4 − 0,673 t1 ) +d t1+ (− 0,22 + 0,368 t1 ) ⋅ (−0,673) + 2 ⋅ (0,4 − 0,673 t1 ) ⋅ (− 0,673) = 0 ,находим t1∗ ≅ 0,595 .
Посколькуd 2 ϕ(t1 )d t1 2печивает минимум функции ϕ(t1 ) по t1 .= 0,952226 > 0 , найденное значение шага обес-101 . Вычислим x 2 = x 1 + t1∗ d 1 : x 2 = (0,0010; 0,000) .T( ) ( ) <ε :f (x ) − f (x ) = 0,17 > 0,15 .111 . Проверим условия x 2 − x 1 < ε 2 ,x 2 − x 1 = 0,456 > 0,15 ;f x 2 − f x1221Положим k = 2 и перейдем к шагу 3.( )4 . Проверим условие ∇f ( x ) < ε :Найдена точка x = (0,001; 0) ; f ( x ) = 2 ⋅ 10( )32 . Вычислим ∇f x 2 : ∇f x 2 = ( 0,003; 0,006) .222T12177T( ) = 0,0067 < 0,1 .
Расчет окончен.∇f x 2−6.II. Проведем анализ точки x 2 . Функция f ( x ) = 2 x12 + x1x 2 + x 2 2 есть квадратичная функция двух переменных, имеющая положительно определенную матрицу⎡4 1 ⎤вторых производных H = ⎢⎥ . Это позволяет сделать вывод, что функция f ( x )⎣1 2⎦имеет единственный минимум, приближение которого x 2 = (0,001; 0)итерации. ■Tнайдено за двеМЕТОДЫ ВТОРОГО ПОРЯДКАА. МЕТОД НЬЮТОНААлгоритмШаг 1. Задать x 0 , ε1 > 0, ε 2 > 0 , M – предельное число итераций. Найти градиент ∇f (x ) и матрицу Гессе H (x ) .Шаг 2.
Положить k = 0 .( )Шаг 3. Вычислить ∇f x k .( )Шаг 4. Проверить выполнение критерия окончания ∇f x k≤ ε1 :а) если неравенство выполнено, то расчет окончен и x ∗ = x k ;б) в противном случае перейти к шагу 5.Шаг 5. Проверить выполнение неравенства k ≥ M :а) если неравенство выполнено, расчет окончен и x ∗ = x k ;б) если нет, перейти к шагу 6.( )Шаг 7. Найти обратную матрицу H ( x ) .Шаг 8. Проверить выполнение условия H ( x ) > 0 :а) если H ( x ) > 0 , то перейти к шагу 9;Шаг 6. Вычислить элементы матрицы H x k .−1k−1−1kk( )б) если нет, то перейти к шагу 10, положив d k = −∇f x k .( ) ( )Шаг 9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
