Отчёт к первой лабе

Ф ЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮМ ОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ(государственный технический университет)Кафедра 304(вычислительные машины, системы и сети)Лабораторная работа по курсу«Автоматизация проектирования»Отчёт по работе№1 .Методы решения задач безусловной оптимизации(наименование работы)Вариант задания№2 .Лабораторную работу выполнил:студент гр. 13-501, Резвяков Денис Михайлович(должность)(Ф. И.

О.)(подпись)Лабораторную работу принял:доцент каф. 304, Силаева Татьяна Александровна(должность)(Ф. И. О.)«.(подпись)»2010 г.(дата приёма)Цель работы: Изучить и практически овладеть основнымиметодами решения задач безусловной оптимизации.ЗаданиеБезусловно оптимизировать функцию: extr f ( X ) ,X3248.Порядок выполнения работы1. Найти решение задачи безусловной оптимизации функцииf(X) с помощью следующих методов: а) классического;б) Ньютона; в) градиентного спуска при заданном h = 0,2;г) наискорейшего спуска.В трёх итерационных методах выполнить вручную толькопо одной итерации, используя одинаковое значение X(0),компоненты которого должны отличаться от найденногопо классическому методу экстремума на +1.2.

Провести сравнительный анализ полученных на первойитерации результатов решения заданной задачи безусловнойоптимизации функции с помощью трёх итерационных методов,сформулировать выводы.3. Выполнить на ЭВМ расчёт безусловного экстремума функцииf(X) с точностью ε = 10-4 согласно методам: Ньютона и трёмградиентным, включая метод сопряжённых градиентов.4. Выполнить сравнительный анализ результатов решения однойи той же задачи безусловной оптимизации функции с помощьюпяти используемых в работе методов и сформулировать выводы.–2–2. Сравнительный анализ полученных результатов и выводКлассический метод решения задачи наиболее точный иесли есть возможность его использовать, то следует воспользоваться им. Остальные методы приближённого нахождениярешения предназначены для поиска результата в сложныхзадачах.Метод Ньютона на первой же итерации показал болееблизкий к истинному значению минимума результат.

Однакосам по себе метод достаточно сложный и требует вычислениявторых производных исходной функции по всем её переменным, что не только увеличивает сложность алгоритма, но изначительно увеличивает время обработки каждой итерации.Метод градиентного спуска на первой итерации показалсамый дальний от истинного значения минимума результат.Также метод не предусматривает расчёта величины шага h,который влияет на скорость и возможность получения результата. В то же время данный метод вообще не требует нахождениякаких-либо вторых производных, что значительно упрощает егоалгоритм и ускоряет обработку каждой итерации.Метод наискорейшего спуска на первой итерации показалболее близкий результат, чем в предыдущем методе, но в то жевремя значительно более дальний, чем метод Ньютона. Данныйметод лишён недостатка предыдущего метода, связанногос выбором шага итерации h, но из-за этого он требует дополнительных непростых расчётов и нахождения второй производной.Хотя, в общем, обработка каждой итерации всё равно остаётсяпроще, чем в методе Ньютона.–5–3.

Результаты выполнения расчётов на ЭВМа) Метод Ньютона:Входные данные:f(x)=x1^3+x2^2+x3^2-3x1-2x2-4x3+8h=0.2;eps=1.0E-4X(0)=(2;2;3)Результаты вычислений:X(0) =k = 0X(1) =k = 1X(2) =k = 2X(3) =k = 3X(4) =k = 4X(5) =( 2.0000, 2.0000, 3.0000), f(X(0)) = 7.0000T(0) = (-0.7500,-1.0000,-1.0000)( 1.2500, 1.0000, 2.0000), f(X(1)) = 1.2031T(1) = (-0.2250, 0.0000, 0.0000)( 1.0250, 1.0000, 2.0000), f(X(2)) = 1.0019T(2) = (-0.0247, 0.0000, 0.0000)( 1.0003, 1.0000, 2.0000), f(X(3)) = 1.0000T(3) = (-0.0003, 0.0000, 0.0000)( 1.0000, 1.0000, 2.0000), f(X(4)) = 1.0000T(4) = ( 0.0000, 0.0000, 0.0000)( 1.0000, 1.0000, 2.0000), f(X(5)) = 1.0000Для нахождения точки минимума с заданной точностью εметодом Ньютона потребовалось 5 итераций.б) Метод градиентного спуска:Входные данные:x1(3)+x2(2)+x3(2)-3x1-2x2-4x3+82.0000000000E-011.0000000000E-0432.0000000000E+002.0000000000E+003.0000000000E+00Результаты вычислений:k = 0,Gr_f(X)k = 1,Gr_f(X)k = 2,Gr_f(X)k = 3,Gr_f(X)k = 4,Gr_f(X)k = 5,Gr_f(X)k = 6,Gr_f(X)k = 7,Gr_f(X)k = 8,Gr_f(X)k = 9,Gr_f(X)k = 10,Gr_f(X)k = 11,Gr_f(X)X = ( 2.0000, 2.0000, 3.0000), f(X) = 7.0000= ( 9.0000, 2.0000, 2.0000), Norma_gr_f(X) = 9.43398X = ( 0.2000, 1.6000, 2.6000), f(X) = 3.1280= (-2.8800, 1.2000, 1.2000), Norma_gr_f(X) = 3.34281X = ( 0.7760, 1.3600, 2.3600), f(X) = 1.3985= (-1.1935, 0.7200, 0.7200), Norma_gr_f(X) = 1.56881X = ( 1.0147, 1.2160, 2.2160), f(X) = 1.0940= ( 0.0888, 0.4320, 0.4320), Norma_gr_f(X) = 0.61736X = ( 0.9969, 1.1296, 2.1296), f(X) = 1.0336= (-0.0184, 0.2592, 0.2592), Norma_gr_f(X) = 0.36702X = ( 1.0006, 1.0778, 2.0778), f(X) = 1.0121= ( 0.0036, 0.1555, 0.1555), Norma_gr_f(X) = 0.21997X = ( 0.9999, 1.0467, 2.0467), f(X) = 1.0044= (-0.0007, 0.0933, 0.0933), Norma_gr_f(X) = 0.13197X = ( 1.0000, 1.0280, 2.0280), f(X) = 1.0016= ( 0.0001, 0.0560, 0.0560), Norma_gr_f(X) = 0.07918X = ( 1.0000, 1.0168, 2.0168), f(X) = 1.0006= (-0.0000, 0.0336, 0.0336), Norma_gr_f(X) = 0.04751X = ( 1.0000, 1.0101, 2.0101), f(X) = 1.0002= ( 0.0000, 0.0202, 0.0202), Norma_gr_f(X) = 0.02850X = ( 1.0000, 1.0060, 2.0060), f(X) = 1.0001= (-0.0000, 0.0121, 0.0121), Norma_gr_f(X) = 0.01710X = ( 1.0000, 1.0036, 2.0036), f(X) = 1.0000= ( 0.0000, 0.0073, 0.0073), Norma_gr_f(X) = 0.01026–6–k = 12,Gr_f(X)k = 13,Gr_f(X)k = 14,Gr_f(X)k = 15,Gr_f(X)k = 16,Gr_f(X)k = 17,Gr_f(X)k = 18,Gr_f(X)k = 19,Gr_f(X)k = 20,Gr_f(X)k = 21,Gr_f(X)X = ( 1.0000, 1.0022,= (-0.0000, 0.0044, 0.0044),X = ( 1.0000, 1.0013,= ( 0.0000, 0.0026, 0.0026),X = ( 1.0000, 1.0008,= (-0.0000, 0.0016, 0.0016),X = ( 1.0000, 1.0005,= ( 0.0000, 0.0009, 0.0009),X = ( 1.0000, 1.0003,= (-0.0000, 0.0006, 0.0006),X = ( 1.0000, 1.0002,= ( 0.0000, 0.0003, 0.0003),X = ( 1.0000, 1.0001,= (-0.0000, 0.0002, 0.0002),X = ( 1.0000, 1.0001,= ( 0.0000, 0.0001, 0.0001),X = ( 1.0000, 1.0000,= (-0.0000, 0.0001, 0.0001),X = ( 1.0000, 1.0000,= ( 0.0000, 0.0000, 0.0000),2.0022), f(X) = 1.0000Norma_gr_f(X) = 0.006162.0013), f(X) = 1.0000Norma_gr_f(X) = 0.003692.0008), f(X) = 1.0000Norma_gr_f(X) = 0.002222.0005), f(X) = 1.0000Norma_gr_f(X) = 0.001332.0003), f(X) = 1.0000Norma_gr_f(X) = 0.000802.0002), f(X) = 1.0000Norma_gr_f(X) = 0.000482.0001), f(X) = 1.0000Norma_gr_f(X) = 0.000292.0001), f(X) = 1.0000Norma_gr_f(X) = 0.000172.0000), f(X) = 1.0000Norma_gr_f(X) = 0.000102.0000), f(X) = 1.0000Norma_gr_f(X) = 0.00006Для нахождения точки минимума с заданной точностью εметодом градиентного спуска потребовалось 21 итерация.в) Методом наискорейшего спуска:Входные данные:x1(3)+x2(2)+x3(2)-3x1-2x2-4x3+82.0000000000E-011.0000000000E-0432.0000000000E+002.0000000000E+003.0000000000E+00Результаты вычислений:k = 0X= ( 2.0000, 2.0000, 3.0000),Norma_Gr_f(X) = 9.43398, f(X)k = 1X= ( 0.8817, 1.7515, 2.7515),Norma_Gr_f(X) = 2.22800, f(X)k = 2X= ( 1.1633, 1.1178, 2.1178),Norma_Gr_f(X) = 1.11104, f(X)k = 3X= ( 0.9882, 1.0789, 2.0789),Norma_Gr_f(X) = 0.23382, f(X)k = 4X= ( 1.0179, 1.0121, 2.0121),Norma_Gr_f(X) = 0.11382, f(X)k = 5X= ( 0.9988, 1.0078, 2.0078),Norma_Gr_f(X) = 0.02319, f(X)k = 6X= ( 1.0018, 1.0012, 2.0012),Norma_Gr_f(X) = 0.01125, f(X)k = 7X= ( 0.9999, 1.0008, 2.0008),Norma_Gr_f(X) = 0.00228, f(X)Gr_f(X) = ( 9.0000, 2.0000, 2.0000)= 7.0000, h = 0.12426Gr_f(X) = (-0.6680, 1.5030, 1.5030)= 2.1698, h = 0.42164Gr_f(X) = ( 1.0599, 0.2355, 0.2355)= 1.1121, h = 0.16517Gr_f(X) = (-0.0701, 0.1577, 0.1577)= 1.0129, h = 0.42351Gr_f(X) = ( 0.1086, 0.0241, 0.0241)= 1.0013, h = 0.17586Gr_f(X) = (-0.0070, 0.0156, 0.0156)= 1.0001, h = 0.42378Gr_f(X) = ( 0.0107, 0.0024, 0.0024)= 1.0000, h = 0.17715Gr_f(X) = (-0.0007, 0.0015, 0.0015)= 1.0000, h = 0.42381–7–k = 8X= ( 1.0002, 1.0001, 2.0001),Norma_Gr_f(X) = 0.00111, f(X)k = 9X= ( 1.0000, 1.0001, 2.0001),Norma_Gr_f(X) = 0.00022, f(X)k = 10X= ( 1.0000, 1.0000, 2.0000),Norma_Gr_f(X) = 0.00011, f(X)k = 11X= ( 1.0000, 1.0000, 2.0000),Norma_Gr_f(X) = 0.00002, f(X)Gr_f(X) = ( 0.0011, 0.0002, 0.0002)= 1.0000, h = 0.17728Gr_f(X) = (-0.0001, 0.0002, 0.0002)= 1.0000, h = 0.42381Gr_f(X) = ( 0.0001, 0.0000, 0.0000)= 1.0000, h = 0.17729Gr_f(X) = (-0.0000, 0.0000, 0.0000)= 1.0000, h = 0.42381Для нахождения точки минимума с заданной точностью εметодом наискорейшего спуска потребовалось 11 итераций.г) Методом сопряжённых градиентов:Входные данные:x1(3)+x2(2)+x3(2)-3x1-2x2-4x3+82.0000000000E-011.0000000000E-0432.0000000000E+002.0000000000E+003.0000000000E+00Результаты вычислений:k = 0X= ( 2.0000, 2.0000, 3.0000),Norma_Gr_f(X) = 9.43398, f(X)k = 1X= ( 0.8817, 1.7515, 2.7515),Norma_Gr_f(X) = 2.22800, f(X)k = 2X= ( 0.9596, 0.9939, 1.9939),Norma_Gr_f(X) = 0.23833, f(X)k = 3X= ( 0.9999, 0.9928, 1.9928),Norma_Gr_f(X) = 0.02027, f(X)k = 4X= ( 1.0011, 0.9997, 1.9997),Norma_Gr_f(X) = 0.00648, f(X)k = 5X= ( 1.0000, 1.0001, 2.0001),Norma_Gr_f(X) = 0.00021, f(X)k = 6X= ( 1.0000, 1.0000, 2.0000),Norma_Gr_f(X) = 0.00012, f(X)k = 7X= ( 1.0000, 1.0000, 2.0000),Norma_Gr_f(X) = 0.00000, f(X)Gr_f(X) = ( 9.0000, 2.0000, 2.0000)= 7.0000, h = 0.12426Gr_f(X) = (-0.6680, 1.5030, 1.5030)= 2.1698, h = 0.46924Gr_f(X) = (-0.2377,-0.0122,-0.0122)= 1.0049, h = 0.16824Gr_f(X) = (-0.0007,-0.0143,-0.0143)= 1.0001, h = 0.48202Gr_f(X) = ( 0.0064,-0.0006,-0.0006)= 1.0000, h = 0.17109Gr_f(X) = ( 0.0001, 0.0001, 0.0001)= 1.0000, h = 0.35581Gr_f(X) = (-0.0001, 0.0000, 0.0000)= 1.0000, h = 0.23378Gr_f(X) = (-0.0000,-0.0000,-0.0000)= 1.0000, h = 0.20084Для нахождения точки минимума с заданной точностью εметодом сопряжённых градиентов потребовалось 7 итераций.–8–4.

Сравнительный анализ методов и выводыВ данной лабораторной работе невозможно зафиксировать,сколько времени тратит машина на одну итерацию в каждомконкретном методе, поэтому воспользуемся теоретическимирассуждениями из ранее сделанных выводов (см. п. 2, стр 5).Метод Ньютона дал результат нужной точности за 5 итераций — это самое малое из всех методов число шагов.

Но попредыдущим выводам теоретически алгоритм данного методаявляется самым сложным и самым длительным из всех.Метод градиентного спуска достиг требуемой по условиюточности за 21 итерацию — самое большое из всех методовчисло шагов. В то же время метод самый простой из всехи теоретически каждая итерация отрабатывается достаточнобыстро.Метод наискорейшего спуска получил результат за 11 итераций. Однако данный метод требует перерасчёта размерашага h на каждой итерации, что в свою очередь усложняеталгоритм и замедляет обработку одной итерации, но в то жевремя исключает расходимость и обеспечивает достаточнуюсходимость, в отличие от предыдущего метода.Метод сопряжённых градиентов закончил вычислениеминимума за 7 итераций.