Процедура решения задачи
1. Используя алгоритм Ньютона, найти точку х k, в которой выполняется по крайней мере один критерий окончания расчета. 2. Так как , то осуществить проверку выполнения достаточных условий минимума > 0. Если условие выполнено, то точка х k может рассматриваться как найденное приближение точки минимума х*. Проверку выполнения достаточных условий минимума можно заменить проверкой функции f ( x ) на выпуклость.
Пример 2.1. Найти локальный минимум функции . □ I. Определение точки х k, в которой выполняется по крайней мере один критерий окончания расчетов. 1. Зададим х0, М: х0 = (0,5; 1)Т, ; М=10. Найдем градиент функции в произвольной точке и матрицу Гессе . 2. Положим k = 0. 30. Вычислим : = (3; 2,5)Т. 40. Проверим выполнение условия : = 3,9 > 0,1. Переходим к шагу 5. 50. Проверим выполнение условия : k = 0 <10. Переходим к шагу 6. 60. Вычислим : . 70. Вычислим : . 80. Проверим выполнение условия >0. Так как , , то согласно критерию Сильвестра > 0. 90. Определим . 100. Вычислим . 110. Проверим выполнение условий , : = 1,12 > 0,15; = 2>0,15. Полагаем k = 1, переходим к шагу 3. 31. Вычислим : = (0,0)T. 41. Проверим выполнение условия : = 0 <0,1. Расчет окончен. Заметим, что в точке х1 выполняется необходимое условие первого порядка, поэтому она является стационарной точкой. II. Анализ точки х1. Функция является строго выпуклой, так как ее матрица вторых производных в силу того, что , . Найденная точка х1 =(0,0)T есть точка локального и одновременно глобального минимума f (х). Рис. 9 На рис. 9 траектория спуска изображена сплошной линией. ■
Метод Ньютона-Рафсона Стратегия поиска Стратегия метода Ньютона-Рафсона [Newton-Raphson] состоит в построении последовательности точек {х k}, k = 0,1,..., таких, что k = 0,1,.... Точки последовательности вычисляются по правилу (7) где х0 задается пользователем; величина шага определяется из условия . (8) Задача (7.5) может решаться либо аналитически с использованием необходимого условия минимума с последующей проверкой достаточного условия , либо численно как задача (9) где интервал [a , b]задается пользователем. Если функция достаточно сложна, то возможна ее замена полиномом второй или третьей степени и тогда шаг может быть определен из условия при выполнении условия . При численном решении задачи определения величины шага степень близости найденного значения к оптимальному значению , удовлетворяющему условиям , , зависит от задания интервала [a , b]и точности методов одномерной минимизации. Построение последовательности {х k} заканчивается в точке х k, для которой , где - заданное число, или при (М - предельное число итераций), или при двукратном одновременном выполнении двух неравенств , , где - малое положительное число. Вопрос о том, может ли точка х k рассматриваться как найденное приближение искомой точки минимума, решается путем проведения дополнительного исследования, которое описано ниже. Сходимость Утверждение. Пусть функция f ( x ) дважды непрерывно дифференцируема и сильно выпукла на Rn , а ее матрица Гессе Н(х) удовлетворяет условию Липшица . Тогда последовательность {х k } сходится независимо от выбора начальной тонки х0 к точке минимума х* с квадратичной скоростью , где т - оценка наименьшего собственного значения матрицы. Замечание. Сходимость к точке минимума метода Ньютона-Рафсона гарантируется независимо от выбора начального приближения лишь для сильно выпуклых функций. Поэтому при практическом использовании метода Ньютона-Рафсона следует: а) анализировать матрицу Гессе на выполнение условия >0, k= 0,1,..., и заменять формулу на формулу метода градиентного спуска в случае его невыполнения; б) производить анализ точки х k с целью выяснения, является ли она найденным приближением искомой точки х*.
Популярное: Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас... Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы... Личность ребенка как объект и субъект в образовательной технологии: В настоящее время в России идет становление новой системы образования, ориентированного на вхождение... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (253)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |