semopt3 (1013527), страница 2
Текст из файла (страница 2)
Найдена точка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. Зададим 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
