Решение систем нелинейных уравнений методом Ньютона

Дана система нелинейных уравнений

(10.5)

или

Необходимо решить эту систему, т.е. найти вектор , удовлетворяющий систему (10.5) с точностью .

Метод Ньютона наиболее распространенный метод решения систем нелинейных уравнений. Он обеспечивает более быструю сходимость по сравнению с методом итераций.

В основе метода Ньютона лежит идея линеаризации всех нелинейных уравнений системы (10.5). Сообщим всей системе (10.5) малые приращения h_j и разложим каждое уравнение системы (10.5) в ряд Тейлора:

(10.6)

где

h_j- приращение по каждой x_j;

R_i - остаточные нелинейные члены второго и более высоких порядков каждого ряда Тейлора.

Если приращения h_j таковы, что переменные x_j принимают значения близкие к корню, то будем считать, что левые части уравнений системы (10.6) обращаются в нули. Тогда отбросив R_i сведем задачу решения системы нелинейных уравнений (10.5) к решению системы линейных уравнений, в которой неизвестными являются приращения h_j,

(10.7)

Система (10.7) – система линейных уравнений с неизвестными h_j, . Запишем (10.7) в матричной форме

где

(3.3)

(10.7)

Матрица А, составленая из частных производных ; называется матрицей Якоби или Якобианом.

Метод Ньютона состоит из двух этапов:

На первом этапе реализации метода Ньютона необходимо построить систему (11.3).

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

(10.8)

или

Итерационный процесс прекращается, как только выполнится условие

(10.9)

по всем приращениям одновременно.

Определение матрицы Якоби

В методе Ньютона на каждом шаге итерационного процесса поиска необходимо формировать матрицу Якоби, при этом каждый элемент матрицы можно определить:

1. аналитически, как частную производную ,
2. методом численного дифференцирования, как отношение приращения функции к приращению аргумента, т.е.

В результате частная производная по первой координате х₁ определится как

а частная производная по координате х_j определится как

где .

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

На рисунке 10.4 представлена укрупнённая схема алгоритма (блок-схема) метода Ньютона. На рисунках 10.5 и 10.6 представлены схемы алгоритмов метода Ньютона с различными способами определения матрицы Якоби.

Рис. 10.4. Блок-схема алгоритма метода Ньютона

Рис. 10.5. Схема алгоритма метода Ньютона (аналитическое определение матрицы Якоби)

Рис. 10.6. Схема алгоритма метода Ньютона (определение матрицы Якоби с помощью численного дифференцирования)