Метод Ньютона (метод касательных). Решение систем нелинейных алгебраических уравнений
2.2 Метод Ньютона
Идея метода заключается в линеаризации уравнений системы , что позволяет свести исходную задачу решения СНУ к многократному решению системы линейных уравнений.
Пусть известно приближение xi(k) решения системы нелинейных уравнений xi*. Введем в рассмотрение поправку xi как разницу между решением и его приближением:
,
Подставим полученное выражение для xi* в исходную систему.
Неизвестными в этой системе нелинейных уравнений являются поправки xi. Для определения xi нужно решить эту систему. Но решить эту задачу так же сложно, как и исходную. Однако эту систему можно линеаризовать, и, решив ее, получить приближенные значения поправок xi для данного приближения, т.е. xi(k). Эти поправки не позволяют сразу получить точное решение , но дают возможность приблизиться к решению, - получить новое приближение решения
,
Для линеаризации системы следует разложить функцию fi в ряды Тейлора в окрестности xi(k), ограничиваясь первыми дифференциалами.
Полученная система имеет вид:
,
Все коэффициенты этого уравнения можно вычислить, используя последнее приближение решения xi(k). Для решения системы линейных уравнений при n=2,3 можно использовать формулы Крамера, при большей размерности системы n - метод исключения Гаусса.
Значения поправок используются для оценки достигнутой точности решения. Если максимальная по абсолютной величине поправка меньше заданной точности , расчет завершается. Таким образом, условие окончания расчета:
Можно использовать и среднее значение модулей поправок:
В матричной форме систему можно записать как:
где: , - матрица Якоби (производных),
- вектор поправок
- вектор-функция
W(X(k)) - матрица Якоби, вычисленная для очередного приближения.
F(X(k)) - вектор-функция, вычисленная для очередного приближения.
Выразим вектор поправок ?X(k) из :
где W-1 - матрица, обратная матрице Якоби.
Окончательно формула последовательных приближений метода Ньютона решения СНУ в матричной форме имеет вид:
Достаточные условия сходимости для общего случая имеют очень сложный вид, и на практике проверяются редко. Нужно отметить, что метод сходится очень быстро (за 3 - 5 итераций), если det|W| 0 и начальное приближение X(0) выбрано близким к решению (отличаются не более чем на 10%).
Алгоритм решения СНУ методом Ньютона состоит в следующем:
1) Задается размерность системы n, требуемая точность ?, начальное приближенное решение .
2) Вычисляются элементы матрицы Якоби
3) Вычисляется обратная матрица .
4) Вычисляется вектор функция , , .
5) Вычисляются вектор поправок
6) Уточняется решение
7) Оценивается достигнутая точность
8) Проверяется условие завершения итерационного процесса ???
Если оно не соблюдается, алгоритм выполняется снова с пункта 2.
Для уменьшения количества арифметических действий Рафсон предложил не вычислять обратную матрицу W-1, а вычислять поправки как решение СЛУ: , данный метод получил название метод Ньютона-Рафсона.
Достоинством методов Ньютона является быстрая сходимость, недостатками - сложность расчетов (вычисление производных, многократное решение системы линейных уравнений), сильная зависимость от начального приближения.