Пример выполнения этапа №1 РГР (Примеры выполнения РГР (все в одном архиве))

Образец выполнения этапа №1 РГРРасчетно-графическая работапо курсу «Теория оптимизации и численные методы».Выполнил студент группы 04-206 Иванов И.И.Вариант №1Задание:f (X) = x 2 + x ⋅ y + 2y 2 + 20x + 10y + 2 → extr .Этап №1. Тема: Методы безусловной минимизации ФМПЗадание:а) Аналитически отыскать безусловный экстремум функции (используя аппарат необходимых и достаточныхусловий).0TИз начальной точки с координатами X = (0, 0) сделать в направлении экстремума:б) 3 итерации методом градиентного спуска (точность счета - 5 знаков после запятой).в) 1 итерацию методом наискорейшего спуска (точность счета - 5 знаков после запятой).г) 2 итерации методом Гаусса-Зейделя (точность счета - 5 знаков после запятой).д) 2 итерации методом сопряженных градиентов (точность счета - 5 знаков после запятой).е) 1 итерацию методом Ньютона (точность счета - 5 знаков после запятой).1.

МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХПЕРЕМЕННЫХЗадание 1а).Дано: f (X) = x 2 + x ⋅ y + 2y 2 + 20x + 10y + 2 → extrАналитически отыскать экстремум функции двух переменныхнеобходимых и достаточных условий безусловного экстремума).(сиспользованиемРешение: 2x + y + 20 Запишем градиент функции: ∇f (X) =  x + 4y + 10 Запишем необходимые условия экстремума и вычислим координаты стационарных точек:2x + y + 20 = 0 x + 4y + 10 = 0⇒(1)(1) − 2⋅(2)2x + y + 20 = 0−7y = 0⇒2x + y + 20 = 0y = 0⇒ x = −10y = 0Получена стационарная точка функции X* = (−10, 0)T .1Образец выполнения этапа №1 РГРСоставим матрицу Гессе:∂2f∂2f= 2;= 1;∂x∂y∂x 2∂2f= 1;∂ y∂ x∂2f∂y 2= 4;⇒2 1H(X) = 1 4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) .безусловный минимум в точке с координатами2Образец выполнения этапа №1 РГРЗадание 1б).Дано: f (X) = x 2 + x ⋅ y + 2y 2 + 20x + 10y + 2 → extr .Сделать три итерации методом градиентного спуска из начальной точки X 0 = (0, 0)T внаправлении экстремума.Внимание !Для пунктов б)-е): если при аналитическом решении задачи найден локальный максимум функций, то длячисленного решения задачи необходимо умножить исходную функцию на (-1) и перейти к задаче поиска минимума,при этом нужно пересчитать градиент и матрицу Гессе для новой функции.

В результирующих таблицах значениефункции нужно умножить на (-1).Решение: 2x + y + 20 Найдём градиент функции: ∇f (X) =  x + 4y + 10 Итерация 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Итерация 1Вычислим точку X1 по формуле: X1 = X 0 − t 0∇f (X 0 ) . Зададим шаг t 0 = 0.1 0 20   − 2 X 1 =   − 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.524173Образец выполнения этапа №1 РГРИтерация 2Вычислим точку X 2 по формуле: X 2 = X1 − t1∇f (X1 ) .

Зададим шаг t1 = 0.1 −2  15   −3.5 X 2 =   − 0.1 ⋅   =  −1  4   −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) + 10   0.9 ∇f (X 2 ) = 11.62 + 0.92 = 11.63486Итерация 3Вычислим точку X 3 по формуле: X3 = X 2 − t 2 ∇f (X 2 ) . Зададим шаг t 2 = 0.1 −3.5 11.6   −4.66 X3 =  − 0.1 ⋅ = −1.4  0.9   −1.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 (X3 ) = 9.192 + (−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.21089f2-40-60.93-73.00084Образец выполнения этапа №1 РГРЗадание 1в).Дано: f (X) = x 2 + x ⋅ y + 2y 2 + 20x + 10y + 2 → extr .Сделать одну итерацию методом наискорейшего градиентного спуска из начальной точкиX 0 = (0, 0)T в направлении экстремума.Решение:Итерация 0.

Итерация 0 совпадает с 0-й итерацией метода градиентного спуска.Итерация 1Вычислим точку X1 по формуле: X1 = X 0 − t 0∇f (X 0 ) .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 == 400 ⋅ t 02 + 200 ⋅ t 02 + 200 ⋅ t 02 − 400 ⋅ t 0 − 100 ⋅ t 0 + 2 = 800 ⋅ t 02 − 500 ⋅ t 0 + 2df (X1 )500= 1600 ⋅ t 0 − 500 = 0 ⇒ t 0 == 0.3125dt 01600d 2 f (X1 )dt 02= 1600 > 0 ⇒ при t 0 = 0.3125 функция f (X1 ) принимает минимальное значение −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.1255Образец выполнения этапа №1 РГРЗадание 1г).Дано: f (X) = x 2 + x ⋅ y + 2y 2 + 20x + 10y + 2 → extr .Сделать две итерациинаправлении экстремума.методом Гаусса-Зейделя из начальной точки X 0 = (0, 0)T вРешение:Итерация 0.

Итерация 0 совпадает с 0-й итерацией метода градиентного спуска.Итерация 1Вычислим точку X1 по формуле: X1 = X0 − t 0 ∇f (X 0 ) пр.на x1.0 20   −20 ⋅ t 0 X1 =   − t 0 ⋅   = 00   0 Вычислим шаг t 0 :f (X1 ) = (−20 ⋅ t 0 )2 + (−20 ⋅ t 0 ) ⋅ (0) + 2 ⋅ (0)2 + 20 ⋅ (−20 ⋅ t 0 ) + 10 ⋅ (0) + 2 == 400 ⋅ t 02 − 400 ⋅ t 0 + 2df (X1 )400= 800 ⋅ t 0 − 400 = 0 ⇒ t 0 == 0.5dt 0800d 2 f (X1 )dt 02= 800 > 0 ⇒ при t 0 = 0.5 функция f (X1 ) принимает минимальное значение −20 ⋅ 0.5   −10 X1 = = 0 0 f (X1 ) = 400 ⋅ 0.52 − 400 ⋅ 0.5 + 2 = −98 2 ⋅ (−10) + 0 + 20   0 ∇f (X1 ) = =  (−10) + 4 ⋅ (0) + 10   0 ∇f (X1 ) = 02 + 02 = 0Т.к. ∇f (X1 ) = 0 , то X1 - стационарная точка функции! Вычисления закончены!Приведенные вычисления представим в виде таблицы№xyt∇x∇y||∇f(X)||f010-10000.520010022.360702-986Образец выполнения этапа №1 РГРЗадание 1д).Дано: f (X) = x 2 + x ⋅ y + 2y 2 + 20x + 10y + 2 → extr .Сделать две итерации методом сопряженных градиентов из начальной точки X 0 = (0, 0)T внаправлении экстремума.Решение:Итерация 0.

Итерация 0 совпадает с 0-й итерацией метода градиентного спуска.Итерация 1. Итерация 1 совпадает с 1-й итерацией метода наискорейшего спуска.Итерация 2Вычислим точку X 2 по формулам:X 2 = X1 + t1d1d1 = −∇f (X1 ) + β0 d 0 ,β0 =β0 =∇f (X1 )2∇f (X 0 )2d 0 = −∇f (X 0 )9.78282= 0.1914122.3607 2 4.375  −20   −8.20313 d1 = −  + 0.19141 ⋅ = −8.75  −10   6.83594  −6.25  −8.20313   −6.25 − 8.20313 ⋅ t1 X2 = + t1 ⋅ = −3.125  6.83594   −3.125 + 6.83594 ⋅ t1 Вычислим шаг t1:f (X 2 ) = (−6.25 − 8.20313 ⋅ t1 )2 + (−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.125df (X 2 )95.70313= 209.35059 ⋅ t1 − 95.70313 = 0 ⇒ t1 == 0.45714dt1209.35059d 2 f (X 2 )dt12= 209.35059 > 0 ⇒ при t1 = 0.45714 функция f (X 2 ) принимает минимальное значение −6.25 − 8.20313 ⋅ 0.45714   −9.99997   −10 X2 = =≈ −3.125 + 6.83594 ⋅ 0.45714   −0.00001   0 f (X 2 ) = 104.67523 ⋅ 0.45714 2 − 95.70313 ⋅ 0.45714 − 76.125 = −98.00001 ≈ −987Образец выполнения этапа №1 РГР 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.000062 + 0.000262 = 0.00027 ≈ 0Т.к.

∇f (X 2 ) = 0 , то X 2 - стационарная точка функции! Вычисления закончены!Приведенные вычисления представим в виде таблицы№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-988Образец выполнения этапа №1 РГРЗадание 1е).Дано: f (X) = x 2 + x ⋅ y + 2y 2 + 20x + 10y + 2 → extr .Сделать одну итерацию методом Ньютона из начальной точки X 0 = (0, 0)T в направленииэкстремума.Решение:Итерация 0.

Итерация 0 совпадает с 0-й итерацией метода градиентного спуска. Воспользуемсяполученными ранее результатами.Итерация 1Вычислим точку X1 по формуле: X1 = X 0 − H −1 (X 0 )∇f (X 0 )Вычислим матрицу обратную к матрице Гессе, вычисленной в точке X 0 :2 1 4 7 −1 7 1  4 −1 −10−10H(X 0 ) =  ⇒ H (X ) = ⋅  ⇒ H (X ) = 7  −1 2 1 4 −1 7 2 7 Тогда 0   4 7 −1 7   20   0   80 7 − 10 7   0  10   −10 X1 =   − ⋅  =   −  =  −  =  0   −1 7 2 7   10   0   −20 7 + 20 7   0   0   0 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 ) = 02 + 02 = 0Т.к.

∇f (X1 ) = 0 , то X1 - стационарная точка функции! Вычисления закончены!Приведенные вычисления представим в виде таблицы№xy∇x∇yf||∇f(X)||010-100020010010-9822.360709.