==Метод Ньютона решения системы нелинейных уравнений==
Для понимания материалов настоящего пункта желательно ознакомиться с разделами ((:polynomial/newton#metod_njutona_reshenija_uravnenija МЕТОД НЬЮТОНА РЕШЕНИЯ УРАВНЕНИЯ)) и ((:algebra2:dets:jacobian МАТРИЦА ЯКОБИ И ЯКОБИАН)). Предполагается знание основных понятий теории обыкновенных дифференциальных уравнений: динамическая система, фазовая траектория, устойчивость стационарного решения, метод ломаных Эйлера.
Рассмотрим систему двух вещественных алгебраических уравнений
$$
f(x,y)=0, \ g(x,y)=0 \, .
$$
По аналогии с ((:polynomial:newton#metod_njutona_reshenija_uravnenija методом Ньютона)) решения уравнения от одной неизвестной, попробуем найти вещественное решение этой системы, сгенерировав итерационную последовательность в $ \mathbb R^2 $, сходящуюся к этому решению. Допустим, что из каких-то соображений нам удалось установить, что вещественное решение системы существует, и что некоторая точка $ (x_0, y_0) $ достаточно близка к этому решению. Раскладываем полиномы по ((:polynomialm#formula_tejlora формуле Тейлора)) по степеням $ x-x_0, y-y_0 $ и оставляем в этих разложениях только первые слагаемые:
$$
f(x,y)\equiv f(x_0,y_0)+ \frac{\partial f}{\partial x}\Bigg|_{(x_0,y_0)}(x-x_0)+\frac{\partial f}{\partial y}\Bigg|_{(x_0,y_0)}(y-y_0) + \dots \, ,
$$
$$
g(x,y)\equiv g(x_0,y_0)+ \frac{\partial g}{\partial x}\Bigg|_{(x_0,y_0)}(x-x_0)+\frac{\partial g}{\partial y}\Bigg|_{(x_0,y_0)}(y-y_0) + \dots \, .
$$
Теперь вместо системы нелинейных уравнений рассматриваем систему
$$
\left\{
\begin{array}{ccc}
f(x_0,y_0)&+ \frac{\partial f}{\partial x}\Bigg|_{(x_0,y_0)}(x-x_0)+\frac{\partial f}{\partial y}\Bigg|_{(x_0,y_0)}(y-y_0) &= 0,\\
g(x_0,y_0)&+ \frac{\partial g}{\partial x}\Bigg|_{(x_0,y_0)}(x-x_0)+\frac{\partial g}{\partial y}\Bigg|_{(x_0,y_0)}(y-y_0) &= 0
\end{array}
\right.
$$
линейных уравнений. Она гарантировано имеет решение если матрица
$$
\mathbf J=
\left(
\begin{array}{cc}
\partial f /\partial x & \partial f /\partial y \\
\partial g /\partial x & \partial g /\partial y
\end{array}
\right)
$$
будет неособенной при $ x=x_0,y=y_0 $. При этом предположении решение системы единственно и может быть выражено в виде
$$
\left(
\begin{array}{c}
x_1 \\
y_1
\end{array}
\right)=
\left(
\begin{array}{c}
x_0 \\
y_0
\end{array}
\right) - \mathbf J^{-1} \left(
\begin{array}{c}
f(x_0,y_0) \\
g(x_0,y_0)
\end{array}
\right) \, .
$$
Получаем полную аналогию с одномерным методом Ньютона; роль производной теперь выполняет матрица Якоби. Можно ожидать, что точка $ (x_1,y_1) $ будет лежать ближе к неизвестному нам решению исходной системы, нежели стартовая точка $ (x_0, y_0 ) $. Если это предположение выполняется, то можно попытаться организовать вычисление итерационной последовательности
$$
\left\{ \left(
\begin{array}{c}
x_j \\
y_j
\end{array}
\right)=
\left(
\begin{array}{c}
x_{j-1} \\
y_{j-1}
\end{array}
\right) - \mathbf J^{-1} \Bigg|_{_{(x_{j-1},y_{j-1})}} \left(
\begin{array}{c}
f(x_{j-1},y_{j-1}) \\
g(x_{j-1},y_{j-1})
\end{array}
\right) \right\}_{j=1}^{\infty}
$$
и потестировать ее на сходимость к решению. Одно ограничение для этого умозаключения довольно очевидно: матрица Якоби должна быть неособенной (невырожденной) на всех итерациях (а, желательно, и не очень близкой к вырожденным матрицам).
Метод известен как **метод Ньютона** хотя сам Ньютон не имеет к нему отношения, он только уравнение от одной неизвестной ((:polynomial/newton решал)).
!!П!! **Пример.** Найти вещественное решение системы уравнений
$$\left\{\begin{array}{l}
f(x,y)=3\,x^2+3\,xy+3\,y^2-3\,x-12\,y+10=0 \ ,\\
g(x,y)=x^3+y^3-x^2+xy-5\,y^2-5\,x+7\,y-3=0 \ .
\end{array}\right.
$$
**Решение.** Эта система решается методами
☞
((dets/resultant#iskljuchenie_peremennyx_v_sisteme_polinomialnyx_uravnenij ТЕОРИИ ИСКЛЮЧЕНИЯ)). Ответ известен с абсолютной достоверностью и любой наперед заданной погрешностью: всего имеется ровно $ 4 $ вещественных решения, с точностью до $ \pm 10^{-6} $
они следующие
$$ (-1.435740, 3.463788) ,\ (-1.220415, 1.732698),\ (-0.118404, 2.939291), (-0.015821, 1.181895) \,. $$
Теперь тестируем метод Ньютона. Матрица Якоби
$$
\mathbf J=
\left(
\begin{array}{cc}
6\,x+3 y-3 & 3\,x+6\,y-12\\
3\,x^2-2\,x+y-5 & 3\,y^2+x-10\,y+7
\end{array}
\right)
$$
имеет
$$
\det \mathbf J=-9\,x^3-18\,x^2y+18\,xy^2+9\,y^3+48\,x^2-48\,xy-45\,y^2+30\,x+93\,y-81 \, .
$$
График кривой $ \det \mathbf J=0 $ и вещественных решений системы:
{{ :algebra2:dets:system_jac_12.png?600 |}}
Начальное приближение, очевидно, следует брать вне кривой $ \det \mathbf J=0 $.
Возьмем в качестве такого приближения точку $ (x_0,y_0)= (-2,3) $, имея целью построить последовательность метода Ньютона, сходящуюся к первому решению. Имеем[[Все последующие вычисления проводились с абсолютной точностью, т.е. в рациональных числах, а результаты представлялись округленными до $ \pm 10^{-3} $.]]
$$
\left(
\begin{array}{r}
-2 \\
3
\end{array}
\right) \rightarrow
\left(
\begin{array}{r}
-11/6 \\
35/6
\end{array}
\right) =
\left(
\begin{array}{r}
-1.8(3) \\
5.8(3)
\end{array}
\right)
\rightarrow
\left(
\begin{array}{r}
\frac{6361}{4032} \\
\frac{2125}{576}
\end{array}
\right)\approx
\left(
\begin{array}{r}
1.577 \\
3.689
\end{array}
\right)
\approx \succ \left(
\begin{array}{r}
0.032 \\
3.711
\end{array}
\right)
\approx \succ
\left(
\begin{array}{r}
-0.204 \\
3.221
\end{array}
\right)
\approx \succ
\left(
\begin{array}{r}
-0.144\\
2.988
\end{array}
\right)
\approx \succ
$$
$$
\approx \succ
\left(
\begin{array}{r}
-0.119\\
2.940
\end{array}
\right)
\approx \succ
\left(
\begin{array}{r}
-0.118\\
2.939
\end{array}
\right)
\approx \succ \dots
$$
то есть имеет место сходимость к третьему решению системы. Проявим упорство: возьмем $ (x_0,y_0) $ еще ближе к первому решению:
$$
\left(
\begin{array}{r}
-3/2 \\
7/2
\end{array}
\right) \rightarrow
\left(
\begin{array}{r}
-\frac{1105}{768}\\
\frac{887}{256}
\end{array}
\right) \approx
\left(
\begin{array}{r}
-1.438\\
3.464
\end{array}
\right) \rightarrow
\left(
\begin{array}{r}
-\frac{7052840042911}{4912307191296}\\
\frac{17015205675239}{4912307191296}
\end{array}
\right) \approx
\left(
\begin{array}{r}
-1.43574\\
3.46379
\end{array}
\right) \rightarrow \dots
$$
Здесь последовательность сходится к тому решению, которое мы искали.
Метод работает и для поиска невещественных решений:
$$
\left(
\begin{array}{r}
3/2+1/3 \mathbf i\\
4/5+3/2 \mathbf i
\end{array}
\right) \approx \succ
\left(
\begin{array}{r}
1.66 +0.33 \mathbf i\\
0.84+1.58 \mathbf i
\end{array}
\right) \approx \succ
\left(
\begin{array}{r}
1.645+0.337 \mathbf i\\
0.841+1.573 \mathbf i
\end{array}
\right) \approx \succ
\left(
\begin{array}{r}
1.6452+0.3377 \mathbf i\\
0.8412+1.5735 \mathbf i
\end{array}
\right) \approx \succ \dots
$$
♦
!!=>!! При выборе
$$ f(x,y):=\partial F(x,y) / \partial x, \ g(x,y):=\partial F(x,y) / \partial y $$
метод Ньютона может быть применен для поиска ((:polynomialm#ehkstremumy_polinoma стационарных точек)) функции $ F(x,y) $. В этом случае (и при условии существования всех частных производных функции $ F $ до второго порядка включительно) матрица Якоби превращается в ((:polynomialm#formula_tejlora матрицу Гессе)).
Возникают три вопроса.
1.
Можно ли гарантировать сходимость последовательности метода Ньютона к решению при выборе стартового приближения достаточно близко к нему?
2.
Сходится ли вообще произвольная последовательность метода Ньютона хоть к какому-то решению системы?
3.
Как локализовать решения системы уравнений или, хотя бы, установить точное число этих решений?
Ответ на вопрос
1
положителен. Если удается гарантировать, что на решении $ (x_{\ast},y_{\ast}) $ якобиан не обращается в нуль, то в $ \mathbb R^2 $ или $ \mathbb C^2 $ существует окрестность точки $ (x_{\ast},y_{\ast}) $ такая, что для любой стартовой точки $ (x_0,y_0) $ из этой окрестности последовательность метода Ньютона сходится к $ (x_{\ast},y_{\ast}) $. Размеры окрестности на практике не оценить: "//достаточно малая//".
!!П!! **Пример (продолжение предыдущего).** Изобразим на плоскости $ (x,y) $ векторное поле, а именно в каждой точке $(x,y) $ отложим вектор с координатами конца
$$
- \mathbf J^{-1} \Bigg|_{_{(x,y)}} \left(
\begin{array}{c}
f(x,y) \\
g(x,y)
\end{array}
\right) \ .
$$
Физическая природа этого поля несущественна, но, для наглядности, будем считать его гравитационным.
На рисунке это поле изображено в квадрате $ -4\le x\le 4, -4\le y\le 4 $.
{{ :algebra2:dets:jacob_field1.jpg?400 |}}
Решения системы $ f(x,y)=0,g(x,y)=0 $ задают стационарные точки поля (изображены красным): в них вектор поля становится нулевым. При помещении пробной материальной частицы в эти точки частица останется в покое. Поведение поля в малой окрестности решения проиллюстрируем увеличением масштаба --- ниже поле приведено в квадрате $ -2< x < -1,3
♦