RulTO-1 (Правила выполнения РГР для заочников)

Лунева С.Ю. Методические указания к РГР и КР по ТО (ТО и ЧМ))стр.1Этап №1Методы безусловной минимизации функции многих переменных22Дано: f ( X) = x + x ⋅ y + 2 y + 20 x + 10 y + 2 → extrа) Аналитически отыскать экстремум функции двух переменных(с использованием аппарата необходимых и достаточных условий экстремума)необходимые условияэкстремумаАлгоритм решения задачи с использованием необходимых и достаточных условийT ∂f (X ) ∂f (X)  .1.

Записать градиент функции f ( X) : ∇f ( X) = ,..,∂x∂x1n 2. Записать необходимые условия безусловного экстремума – составить системуалгебраических уравнений вида: ∂f (X)= 0, i = 1..n∂xi*достаточные условия экстремума инеобходимые условия 2-го порядка3. Найти стационарные точки функции X , решив полученную систему.4. Составить матрицу Гессе H( X) .*5. Вычислить матрицу Гессе в точках X .6. Проверить знакоопределенность матрицы H ( X * ) для каждой точки:•H(X* ) > 0 - X * - локальный минимум функции•H(X* ) < 0 - X * - локальный максимум функции•H(X* ) ≥ 0 - требуются дополнительная проверка на локальный минимум•H(X* ) ≤ 0 - требуются дополнительная проверка на локальный максимумH(X* ) <> 0 - в точке X * нет экстремума.*Исследование знакоопределенности матрицы H( X ) :•H(X* ) > 0 - критерий Сильвестра или на основании определения (все λ j > 0 )•H(X* ) < 0 - критерий Сильвестра или на основании определения (все λ j < 0 )•H(X* ) ≥ 0 - на основании определения (все λ j ≥ 0 ), H(X* ) ≤ 0 - на основанииопределения (все λ j ≤ 0 )•H(X* ) <> 0 - на основании определения ( λ j разных знаков).Пример выполнения этапа №1, 2010 г.Лунева С.Ю.

Методические указания к РГР и КР по ТО (ТО и ЧМ))стр.2Критерий Сильвестра (критерий знакоопределенности матрицы)Матрица является положительно определенной , если все ее диагональные минорыположительны; матрица является отрицательно определенной, если ее диагональныеминоры чередуют знак, начиная с «-».Решение:Запишем градиент функции: 2 x + y + 20 ∇f (X ) =  x + 4 y + 10 Запишем необходимые условия экстремума и вычислим координаты стационарных точек:2 x + y + 20 = 0x + 4 y + 10 = 02 x + y + 20 = 0⇒ (1)− 7y = 0(1) − 2⋅( 2 ) ⇒2 x + y + 20 = 0y = 0Получена стационарная точка функции X* = ( −10,⇒x = −10y = 00)TСоставим матрицу Гессе:∂ 2f∂x 2= 2;∂ 2f= 1;∂ y∂ x∂ 2f= 1;∂x ∂y∂ 2f∂y 2= 4;⇒2 1H(X) = 14Вычислим матрицу Гессе в полученной стационарной точке:2 1H(X*) = 1 4Определим характер полученной стационарной точки, используя критерий Сильвестра:∆1 = 2 > 0∆ 2 = 2 ⋅ 4 − 1⋅1 = 7 > 0Так как все диагональные миноры матрицы положительны, матрица Гессе являетсяположительно-определенной H( X*) > 0 , и, следовательно, точкаявляется точкой локального минимума функции.X* = (−10, 0)TОтвет: функции f ( X) имеет локальный безусловный минимум в точке с координатамиX* = (−10, 0) .Пример выполнения этапа №1, 2010 г.Лунева С.Ю.

Методические указания к РГР и КР по ТО (ТО и ЧМ))стр.3б) Сделать три итерации методом градиентного спуска из начальной точкиX 0 = (0, 0)T в направлении экстремумаВнимание !Для пунктов б)-е): если при аналитическом решении задачи найден локальный максимум функций, то длячисленного решения задачи необходимо умножить исходную функцию на (-1) и перейти к задаче поискаминимума, при этом нужно пересчитать градиент и матрицу Гессе для новой функции. В результирующихтаблицах значение функции нужно умножить на (-1).Алгоритм метода градиентного спускаX k +1 = X k − t k ∇f (X k ) , здесь:••d k = −∇f (X k ) - направление антиградиента функции;t k > 0 - шаг выбирается из условия убывания функции в точкахпоследовательности: f (Xk +1) < f (X k )Итерация 0 0X 0 =   0f (X 0 ) = 02 + 0 ⋅ 0 + 2 ⋅ 02 + 20 ⋅ 0 + 10 ⋅ 0 + 2 = 2 2 ⋅ 0 + 0 + 20   20  =  ∇f (X 0 ) = 0+4⋅0+10  10 ∇f (X 0 ) = 20 2 + 10 2 = 22.3607Итерация 11100Вычислим точку X по формуле: X = X − t 0∇f ( X ) .

Зададим шаг t 0 = 0.1 0 20   − 2 X1 =   − 0.1 ⋅   =   010   − 1 f (X1 ) = (−2) 2 + (−2) ⋅ (−1) + 2 ⋅ (−1)2 + 20 ⋅ (−2) + 10 ⋅ (−1) + 2 = −40f (X1 ) < f (X 0 ) , следовательно, шаг выбран удачно 2 ⋅ (−2) + (−1) + 20  15  =  ∇f (X1 ) = (−2)+4⋅(−1)+10 4∇f (X1 ) = 152 + 42 = 15.52417Пример выполнения этапа №1, 2010 г.Лунева С.Ю.

Методические указания к РГР и КР по ТО (ТО и ЧМ))стр.4Итерация 22211Вычислим точку X по формуле: X = X − t1∇f (X ) . Зададим шаг t1 = 0.1 − 215   − 3.5 X 2 =   − 0.1 ⋅   = −14−1.4   f (X 2 ) = (−3.5) 2 + (−3.5) ⋅ (−1.4) + 2 ⋅ (−1.4) 2 + 20 ⋅ (−3.5) + 10 ⋅ (−1.4) + 2 = −60.93f (X 2 ) < f (X1 ) , следовательно, шаг выбран удачно 2 ⋅ (−3.5) + (−1.4) + 20  11.6  = ∇f (X 2 ) = (3.5)4(1.4)100.9−+⋅−+ ∇f (X 2 ) = 11.62 + 0.92 = 11.63486Итерация 33322Вычислим точку X по формуле: X = X − t 2∇f ( X ) . Зададим шаг t 2 = 0.1 − 3.5 11.6   − 4.66  − 0.1 ⋅  = X3 = −−1.40.91.49 f (X 3 ) = (−4.66)2 + (−4.66) ⋅ (−1.49) + 2 ⋅ (−1.49) 2 + 20 ⋅ (−4.66) + 10 ⋅ (−1.49) + 2 = −73.0008f (X 3 ) < f (X 2 ) , следовательно, шаг выбран удачно 2 ⋅ (−4.66) + (−1.49) + 20   9.19  = ∇f (X 3 ) =  (−4.66) + 4 ⋅ (−1.49) + 10   − 0.62 ∇f (X 3 ) = 9.19 2 + (−0.62) 2 = 9.21089Приведенные вычисления представим в виде таблицы№0123x0-2-3.5-4.66y0-1-1.4-1.49t0.10.10.1∇x201511.69.19∇y1040.9-0.62||∇f(X)||22.360715.5241711.634869.21089Пример выполнения этапа №1, 2010 г.f2-40-60.93-73.0008Лунева С.Ю.

Методические указания к РГР и КР по ТО (ТО и ЧМ))стр.5в) Сделать одну итерацию методом наискорейшего спуска из начальной точкиX 0 = (0, 0)T в направлении экстремумаАлгоритм метода наискорейшего градиентного спускаX k +1 = X k − t k ∇f (X k ) , здесь:••d k = −∇f (X k ) - направление антиградиента функции;t k > 0 - вычисляется из условия наибольшего убывания функции в точкахпоследовательности: t k = arg min[f (Xk +1)]Итерация 0. Итерация 0 совпадает с 0-й итерацией метода градиентного спуска.Итерация 11100Вычислим точку X по формуле: X = X − t 0∇f ( X ) . 0 20   − 20 ⋅ t 0 X1 =   − t 0 ⋅   =  010   − 10 ⋅ t 0 Вычислим шаг t 0 :f (X1 ) = (−20 ⋅ t 0 ) 2 + (−20 ⋅ t 0 ) ⋅ (−10 ⋅ t 0 ) + 2 ⋅ (−10 ⋅ t 0 )2 + 20 ⋅ (−20 ⋅ t 0 ) + 10 ⋅ (−10 ⋅ t 0 ) + 2 =2222= 400 ⋅ t 0 + 200 ⋅ t 0 + 200 ⋅ t 0 − 400 ⋅ t 0 − 100 ⋅ t 0 + 2 = 800 ⋅ t 0 − 500 ⋅ t 0 + 2df (X1 )500= 1600 ⋅ t 0 − 500 = 0 ⇒ t 0 == 0.3125dt 01600 − 20 ⋅ 0.3125   − 6.25  = X1 =  − 10 ⋅ 0.3125   − 3.125 f (X1 ) = 800 ⋅ 0.31252 − 500 ⋅ 0.13125 + 2 = −76.125 2 ⋅ (−6.25) + (−3.125) + 20   4.375  = ∇f (X1 ) = (−6.25)+4⋅(−3.125)+10−8.75 ∇f (X1 ) = 4.3752 + (−8.75) 2 = 9.7828Приведенные вычисления представим в виде таблицы№xyt∇x∇y||∇f(X)||f010-6.250-3.1250.3125204.37510-8.7522.36079.782810-76.125Пример выполнения этапа №1, 2010 г.Лунева С.Ю.

Методические указания к РГР и КР по ТО (ТО и ЧМ))стр.6г) Сделать две итерации методом сопряженных градиентов из начальной точкиX 0 = (0, 0)T в направлении экстремумаАлгоритм метода сопряженных градиентовX k +1 = X k + t k d k , здесь:•d 0 = −∇f (X 0 )d k = −∇f (X k ) + βk −1d k −1β k −1 =•∇f ( X k )2∇f (X k −1 )2t k > 0 - вычисляется из условия наибольшего убывания функции в точкахпоследовательности: t k = arg min[f (Xk +1)]Итерация 0. Итерация 0 совпадает с 0-й итерацией метода градиентного спуска.Итерация 1.

Итерация 1 совпадает с 1-й итерацией метода наискорейшего спуска.Итерация 22Вычислим точку X по формулам:X 2 = X1 + t1d1d1 = −∇f (X1 ) + β0 d 0 ,β0 =∇f (X1 )2∇f ( X 0 )2d 0 = −∇f (X 0 )9.78282β0 == 0.1914122.36072 4.375  − 20   − 8.20313 + 0.19141⋅  = d1 = − −8.75−106.83594  − 6.25  − 8.20313  − 6.25 − 8.20313 ⋅ t1  + t1 ⋅  = X 2 =  − 3.125  6.83594   − 3.125 + 6.83594 ⋅ t1 Вычислим шаг t1:2f (X 2 ) = ( −6.25 − 8.20313 ⋅ t1 ) + ( −6.25 − 8.20313 ⋅ t1 ) ⋅ ( −3.125 + 6.83594 ⋅ t1 ) ++ 2 ⋅ (−3.125 + 6.83594 ⋅ t1 ) 2 ++ 20 ⋅ (−6.25 − 8.20313 ⋅ t1 ) + 10 ⋅ (−3.125 + 6.83594 ⋅ t1 ) + 2 == 104.67523 ⋅ t12 − 95.70313 ⋅ t1 − 76.125Пример выполнения этапа №1, 2010 г.Лунева С.Ю. Методические указания к РГР и КР по ТО (ТО и ЧМ))стр.7df (X 2 )95.70313= 209.35059 ⋅ t1 − 95.70313 = 0 ⇒ t1 == 0.45714dt1209.35059 − 6.25 − 8.20313 ⋅ 0.45714   − 9.99997   − 10  =  ≈ X 2 == 3.1256.835940.457140.000010−+⋅−  f (X 2 ) = 104.67523 ⋅ 0.45714 2 − 95.70313 ⋅ 0.45714 − 76.125 = −98.00001 ≈ −98 2 ⋅ (−9.99997) + (−0.00001) + 20   0.00006   0  =  ≈  ∇f (X 2 ) =  (−9.99997) + 4 ⋅ (−0.00001) + 10   0.00026   0 ∇f (X 2 ) = 0.00006 2 + 0.00026 2 = 0.00027 ≈ 022Т.к.

∇f ( X ) = 0 , то X -стационарная точка функции ! Вычисления закончены !Приведенные вычисления представим в виде таблицы№012xyt∇x∇y||∇f(X)||f00-201022.360710βdxdy--20-10xyt∇x∇y||∇f(X)||f-6.25-3.1250.31254.375-8.759.7828-76.125βdxdy0.19141-8.203136.83594xyt∇x∇y||∇f(X)||f-500.45714000-98Пример выполнения этапа №1, 2010 г.Лунева С.Ю. Методические указания к РГР и КР по ТО (ТО и ЧМ))стр.80д) Сделать одну итерацию методом Ньютона из начальной точки X = (0, 0)направлении экстремумаTвАлгоритм метода НьютонаX k +1 = X k − H −1 (X k )∇f (X k ) , здесь:•d k = − H −1 (X k )∇f (X k ) - направление спуска.Итерация 0.

Итерация 0 совпадает с 0-й итерацией метода градиентного спуска.Итерация 1110−100Вычислим точку X по формуле: X = X − H ( X )∇f ( X )0Вычислим матрицу обратную к матрице Гессе, вычисленной в точке X :2 1 4 7 −1 71  4 − 1 ⇒ H −1 (X 0 ) = ⋅  ⇒ H −1 (X 0 ) = H(X 0 ) = 14−12−17277Тогда 0   4 7 − 1 7   20   0   80 7 − 10 7   0  10   − 10  ⋅   =   −  =   −   = X1 =   − 0−1727100−207+207000            f (X1 ) = (−10)2 + 2 ⋅ (−10) ⋅ 0 + 2 ⋅ 02 + 20 ⋅ (−10) + 10 ⋅ 0 + 2 = −98 2 ⋅ (−10) + 0 + 20   0  =  ∇f (X1 ) =  − 10 + 2 ⋅ 0 + 10   0 ∇f (X1 ) = 0 2 + 02 = 011Т.к. ∇f ( X ) = 0 , то X -стационарная точка функции ! Вычисления закончены !Приведенные вычисления представим в виде таблицы№xy∇x∇yf||∇f(X)||010-100020010010-9822.36070Пример выполнения этапа №1, 2010 г..