2.2 Метод Ньютона

Идея метода заключается в линеаризации уравнений системы , что позволяет свести исходную задачу решения СНУ к многократному решению системы линейных уравнений.

Пусть известно приближение x_i^(k) решения системы нелинейных уравнений x_i^*. Введем в рассмотрение поправку x_i как разницу между решением и его приближением:

,

Подставим полученное выражение для x_i^* в исходную систему.

Неизвестными в этой системе нелинейных уравнений являются поправки x_i. Для определения x_i нужно решить эту систему. Но решить эту задачу так же сложно, как и исходную. Однако эту систему можно линеаризовать, и, решив ее, получить приближенные значения поправок x_i для данного приближения, т.е. x_i^(k). Эти поправки не позволяют сразу получить точное решение , но дают возможность приблизиться к решению, - получить новое приближение решения

,

Для линеаризации системы следует разложить функцию f_i в ряды Тейлора в окрестности x_i^(k), ограничиваясь первыми дифференциалами.

Полученная система имеет вид:

,

Все коэффициенты этого уравнения можно вычислить, используя последнее приближение решения x_i^(k). Для решения системы линейных уравнений при n=2,3 можно использовать формулы Крамера, при большей размерности системы n - метод исключения Гаусса.

Значения поправок используются для оценки достигнутой точности решения. Если максимальная по абсолютной величине поправка меньше заданной точности , расчет завершается. Таким образом, условие окончания расчета:

Можно использовать и среднее значение модулей поправок:

В матричной форме систему можно записать как:

где: , - матрица Якоби (производных),

- вектор поправок

- вектор-функция

W(X^(k)) - матрица Якоби, вычисленная для очередного приближения.

F(X^(k)) - вектор-функция, вычисленная для очередного приближения.

Выразим вектор поправок ?X^(k) из :

где W^-1 - матрица, обратная матрице Якоби.

Окончательно формула последовательных приближений метода Ньютона решения СНУ в матричной форме имеет вид:

Достаточные условия сходимости для общего случая имеют очень сложный вид, и на практике проверяются редко. Нужно отметить, что метод сходится очень быстро (за 3 - 5 итераций), если det|W| 0 и начальное приближение X⁽⁰⁾ выбрано близким к решению (отличаются не более чем на 10%).

Алгоритм решения СНУ методом Ньютона состоит в следующем:

1) Задается размерность системы n, требуемая точность ?, начальное приближенное решение .

2) Вычисляются элементы матрицы Якоби

3) Вычисляется обратная матрица .

4) Вычисляется вектор функция , , .

5) Вычисляются вектор поправок

6) Уточняется решение

7) Оценивается достигнутая точность

8) Проверяется условие завершения итерационного процесса ???

Если оно не соблюдается, алгоритм выполняется снова с пункта 2.

Для уменьшения количества арифметических действий Рафсон предложил не вычислять обратную матрицу W^-1, а вычислять поправки как решение СЛУ: , данный метод получил название метод Ньютона-Рафсона.

Достоинством методов Ньютона является быстрая сходимость, недостатками - сложность расчетов (вычисление производных, многократное решение системы линейных уравнений), сильная зависимость от начального приближения.