RulTO-1 (1013555)
Текст из файла
Лунева С.Ю. Методические указания к РГР и КР по ТО (ТО и ЧМ))стр.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∂x1n 2. Записать необходимые условия безусловного экстремума – составить системуалгебраических уравнений вида: ∂f (X)= 0, i = 1..n∂xi*достаточные условия экстремума инеобходимые условия 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 = 0x + 4 y + 10 = 02 x + y + 20 = 0⇒ (1)− 7y = 0(1) − 2⋅( 2 ) ⇒2 x + y + 20 = 0y = 0Получена стационарная точка функции X* = ( −10,⇒x = −10y = 00)TСоставим матрицу Гессе:∂ 2f∂x 2= 2;∂ 2f= 1;∂ y∂ x∂ 2f= 1;∂x ∂y∂ 2f∂y 2= 4;⇒2 1H(X) = 14Вычислим матрицу Гессе в полученной стационарной точке:2 1H(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 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Итерация 11100Вычислим точку X по формуле: X = X − t 0∇f ( X ) .
Зададим шаг t 0 = 0.1 0 20 − 2 X1 = − 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.52417Пример выполнения этапа №1, 2010 г.Лунева С.Ю.
Методические указания к РГР и КР по ТО (ТО и ЧМ))стр.4Итерация 22211Вычислим точку X по формуле: X = X − t1∇f (X ) . Зададим шаг t1 = 0.1 − 215 − 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 ⋅ = 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 =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 71 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 г..
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.