Пример выполнения этапа №1 РГР (1013568)
Текст из файла
Образец выполнения этапа №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 = 0y = 0⇒ x = −10y = 0Получена стационарная точка функции X* = (−10, 0)T .1Образец выполнения этапа №1 РГРСоставим матрицу Гессе:∂2f∂2f= 2;= 1;∂x∂y∂x 2∂2f= 1;∂ y∂ x∂2f∂y 2= 4;⇒2 1H(X) = 1 42 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 0X 0 = 0f (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 ⋅ = 010 − 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 ⋅ = 010 −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 ⋅ = 00 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.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.