Метод Ньютона - Рафсона

Стратегия метода Ньютона-Рафсона состоит в построении последовательности точек , таких, что Точки последовательности вычисляются по правилу

где - задается пользователем, а величина шага определяется из условия

.

Эта задача может решаться либо аналитически с использованием необходимого условия минимума с последующей проверкой достаточного условия , либо численно как задача

где интервал [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.

3⁰. Вычислим : .

4⁰. Проверим условие : .

5⁰. Проверим условие : .

6⁰. Вычислим : .

7⁰. Вычислим : .

8⁰. Проверим выполнение условия . Т.к. , то согласно критерию Сильвестра . Поэтому найдем .

9⁰. Определим .

10⁰. Определим из условия . Получаем:

Из условия находим . При этом , т.е. найденная величина шага обеспечивает минимум функции .

11⁰. Вычислим :

12⁰. Проверим условия: :

.

Полагаем k = 1, переходим к шагу 3.

3¹. Вычислим : .

4¹. Проверим условие : .

Расчет окончен. Найдена точка .

Проанализируем полученную точку:

Функция является строго выпуклой, т.к. ее матрица вторых производных в силу того, что . Найденная точка есть точка локального и одновременно глобального минимума функции.

Решение задачи представлено на рисунке 5.3.

Рисунок 5.3.

Дата добавления: 2015-07-20