- •Киров 2006
- •Рецензент: к.Т.Н., доцент каф. Эвм Матвеева л.И.
- •1 Оформление лабораторной работы
- •1.1 Цель работы
- •1.2 Формирование отчета
- •2 Общие принципы методов поиска безусловного экстремума
- •3 Методы нулевого порядка
- •3.1 Метод конфигураций (метод Хука - Дживса)
- •3.2 Метод деформируемого многогранника
- •3.3 Метод вращающихся координат (метод Розенброка)
- •3.4 Метод сопряженных направлений (метод Пауэлла)
- •4 Методы первого порядка
- •4.1 Метод градиентного спуска с постоянным шагом
- •4.2 Метод наискорейшего градиентного спуска (Метод Коши)
- •4.3 Метод Гаусса - Зейделя
- •4.4 Метод сопряженных градиентов (Флетчера – Ривса)
- •5 Методы второго порядка
- •5.1 Метод Ньютона
- •5.2 Метод Ньютона - Рафсона
- •5.3 Метод Марквардта
- •6 Пример отчета по лабораторной работе
- •7 Блок вариантов заданий
- •8 Библиографический список
5.2 Метод Ньютона - Рафсона
Стратегия метода Ньютона-Рафсона состоит в построении последовательности точек , таких, что Точки последовательности вычисляются по правилу
где - задается пользователем, а величина шага определяется из условия
.
Эта задача может решаться либо аналитически с использованием необходимого условия минимума с последующей проверкой достаточного условия , либо численно как задача
где интервал [a,b] задается пользователем.
Если функция достаточно сложна, то возможна ее замена полиномом второй или третьей степени и тогда шаг может быть определен из условия при выполнении условия .
При численном решении задачи определения величины шага степень близости найденного значения к оптимальному значению , удовлетворяющему условиям , , зависит от задания интервала [a,b] и точности метода одномерной минимизации.
Построение последовательности заканчивается в точке , для которой , где - заданное число, или при (М – предельное число итераций), или при двукратном одновременном выполнении двух неравенств , где -малое положительное число.
Утверждение: Пусть функция f(x) дважды непрерывно дифференцируема и сильно выпукла на , а ее матрица Гессе H(x) удовлетворяет условию Липшица
Тогда последовательность сходится независимо от выбора начальной точки к точке минимума с квадратичной скоростью , где m – оценка наименьшего собственного значения матрицы.
Алгоритм:
Шаг 1. Задать , М – предельное число итераций. Найти градиент и матрицу Гессе .
Шаг 2. Положить k = 0.
Шаг 3. Вычислить .
Шаг 4. Проверить выполнение критерия окончания :
а) если неравенство выполнено, то расчет окончен и ;
б) в противном случае перейти к шагу 5.
Шаг 5. Проверить выполнение неравенства :
а) если неравенство выполнено, то расчет окончен и ;
б) в противном случае перейти к шагу 6.
Шаг 6. Вычислить матрицу .
Шаг 7. Вычислить матрицу .
Шаг 8. Проверить выполнение условия :
а) если , то найти ;
б) если нет, то положить .
Шаг 9. Определить .
Шаг 10. Найти точку шаг из условия .
Шаг 11. Вычислить .
Шаг 12. Проверить выполнение неравенств
:
а) если оба условия выполнены при текущем значении k и k = k - 1, то расчет окончен, ;
б) в противном случае положить k = k+1 и перейти к шагу 3.
Пример: Методом Ньютона-Рафсона найти локальный минимум функции
Решение:
1. Зададим , M: , , M =10.
Найдем градиент функции в произвольной точке и матрицу Гессе .
2. Положим k = 0.
30. Вычислим : .
40. Проверим условие : .
50. Проверим условие : .
60. Вычислим : .
70. Вычислим : .
80. Проверим выполнение условия . Т.к. , то согласно критерию Сильвестра . Поэтому найдем .
90. Определим .
100. Определим из условия . Получаем:
Из условия находим . При этом , т.е. найденная величина шага обеспечивает минимум функции .
110. Вычислим :
120. Проверим условия: :
.
Полагаем k = 1, переходим к шагу 3.
31. Вычислим : .
41. Проверим условие : .
Расчет окончен. Найдена точка .
Проанализируем полученную точку:
Функция является строго выпуклой, т.к. ее матрица вторых производных в силу того, что . Найденная точка есть точка локального и одновременно глобального минимума функции.
Решение задачи представлено на рисунке 5.3.
Рисунок 5.3.