2. 2 Метод Ньютона
Метод Ньютона - это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727). Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Улучшением метода является метод хорд и касательных. Метод Ньютона в основном используется для решения задач оптимизации, в которых требуется определить нуль первой производной либо градиента в случае многомерного пространства.
Стратегия метода Ньютона состоит в
построении последовательности точек,
таких, что значение функции в предыдущей
точки больше, чем в последующей. Точки
последовательности выбираются по
правилу:
.
Начальная точка задается пользователем,
а направление спуска определяется по
формуле
,
где Н(х) – матрица Гессе,
-
градиент исходной функции.
3 Алгоритм работы программы
Шаг 1. Пользователь выбирает метод нахождения минимума функции, и вид данной функции из предложенных.
а) При выборе метода Хука – Дживса:
1. Задаем функцию зависимости от двух аргументов.
Пользователь задает начальные значения:
начальную точку, шаги по координатным
направлениям:
,
ошибку
,
коэффициент уменьшения шага
.
2. Осуществляем следующий поиск по выбранному координатному направлению:
а) если :
,
то шаг считается удачным. В этом случае
следует положить
и переходим к шагу 3;
б) если в п. а шаг неудачный, то делается
шаг в противоположное направление. Если
,
то положим
и перейдем к шагу 3.
3. Проверим условие: если
,
то перейдем к шагу 4, иначе, к шагу 5.
4. Провести поиск по образцу. Положить
,
и перейти к шагу 2.
а) если все шаги по координатным направлениям меньше числа , то поиск закончен
б) для тех i, для которых больше , уменьшить величину шага на a перейти к шагу 2.
б) При выборе метода Ньютона
1. Задаем значения нулевой точки, ошибку .
2. Находим матрицу Гессе Н(х) и градиент.
3. Положим к = 0, и вычислим градиент
в точке
.
4. Проверить выполнение критерия
окончания
а) Если неравенство выполнено, то расчет
окончен и
б) Если нет, то перейти к пункту 5.
5. Вычислить матрицу
.
6. Вычислить матрицу
.
7. Проверить выполнения условия > 0
а) если да, то перейти к шагу 9
б) если нет, то перейти к шагу 10, положив
8. Определить
9. Найти точку
,
t=1, если
>0,
иначе выбрать t из
дополнительных условий.
10. Если условие выполняется
,
поиск окончен, в противном случае
положить к = к + 1, и перейти к пункту
3.
Шаг 2. Выводим полученные значения точек, и значения функции в этих точках.
Шаг 3. Нарисовать линии уровней заданной функции и итерационную процедуру поиска минимума.
4. Аналитическое решение уравнений
Решим заданные уравнения аналитическим способом.
1.
Найдем первые частные производные:
Прировняем полученные производные к нулю и найдем корни уравнения:
Искомое решение уравнения
.
2.
Найдем первые частные производные:
Прировняем полученные производные к нулю и найдем корни уравнения:
Искомое решение уравнения
.
3.
Найдем первые частные производные:
Прировняем полученные производные к нулю и найдем корни уравнения:
Искомое решение уравнения
5. Реализация метода в программной среде С++