Инструменты сайта


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

Для понимания материалов настоящего пункта желательно ознакомиться с разделами МЕТОД НЬЮТОНА РЕШЕНИЯ УРАВНЕНИЯ и МАТРИЦА ЯКОБИ И ЯКОБИАН. Предполагается знание основных понятий теории обыкновенных дифференциальных уравнений: динамическая система, фазовая траектория, устойчивость стационарного решения, метод ломаных Эйлера.

Рассмотрим систему двух вещественных алгебраических уравнений $$ f(x,y)=0, \ g(x,y)=0 \, . $$ По аналогии с методом Ньютона решения уравнения от одной неизвестной, попробуем найти вещественное решение этой системы, сгенерировав итерационную последовательность в $ \mathbb R^2 $, сходящуюся к этому решению. Допустим, что из каких-то соображений нам удалось установить, что вещественное решение системы существует, и что некоторая точка $ (x_0, y_0) $ достаточно близка к этому решению. Раскладываем полиномы по формуле Тейлора по степеням $ 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} $$ и потестировать ее на сходимость к решению. Одно ограничение для этого умозаключения довольно очевидно: матрица Якоби должна быть неособенной (невырожденной) на всех итерациях (а, желательно, и не очень близкой к вырожденным матрицам).

Метод известен как метод Ньютона хотя сам Ньютон не имеет к нему отношения, он только уравнение от одной неизвестной решал.
П

Пример. Найти вещественное решение системы уравнений

$$\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. $$

Решение. Эта система решается методами ТЕОРИИ ИСКЛЮЧЕНИЯ. Ответ известен с абсолютной достоверностью и любой наперед заданной погрешностью: всего имеется ровно $ 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 $ и вещественных решений системы:

Начальное приближение, очевидно, следует брать вне кривой $ \det \mathbf J=0 $. Возьмем в качестве такого приближения точку $ (x_0,y_0)= (-2,3) $, имея целью построить последовательность метода Ньютона, сходящуюся к первому решению. Имеем1) $$ \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 $$ метод Ньютона может быть применен для поиска стационарных точек функции $ F(x,y) $. В этом случае (и при условии существования всех частных производных функции $ F $ до второго порядка включительно) матрица Якоби превращается в матрицу Гессе.

Возникают три вопроса.

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) $ отложим вектор с координатами конца

$$ \left( \begin{array}{c} x \\ y \end{array} \right) - \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 $. Решения системы $ f(x,y)=0,g(x,y)=0 $ задают стационарные точки поля (изображены красным): в них вектор поля становится нулевым. При помещении пробной материальной частицы в эти точки частица останется в покое. В какую бы другую точку не поместить пробную частицу — поле будет перемещать ее по траектории, в каждой точке которой касательная коллинеарна вектору скоростей, т.е. вектору с координатами концов $$ (0,0) \ \mbox{и} \ - \mathbf J^{-1} \Bigg|_{_{(x,y)}} \left( \begin{array}{c} f(x,y) \\ g(x,y) \end{array} \right) \ . $$ Направляющий вектор касательной к траектории, заданной в параметрическом виде $ (x(t),y(t)) $ при каждом значении $ t $ задается системой уравнений $$ \left(\begin{array}{c} d\, x / d\, t \\ d\, y / d\, t \end{array} \right)= - \mathbf J^{-1} \Bigg|_{_{(x,y)}} \left( \begin{array}{c} f(x,y) \\ g(x,y) \end{array} \right) \, , $$ которая представляет собой динамическую систему дифференциальных уравнений. Задача теперь заключается в исследовании поведения решений (траекторий) этой системы — зотя бы в окрестности стационарных точек, т.е. интересующих нас решений системы алгебраических уравнений.

Поведение поля в малой окрестности решения проиллюстрируем увеличением масштаба — ниже поле приведено в квадрате $ -2< x < -1,3<y<4 $: Видим, что поле «загоняет» любую траекторию в стационарную точку. Чем это наблюдение подтверждается аналитически? — Для ответа на этот вопрос приходится обращаться к качественной теории дифференциальных уравнений [1].

Если вычислить матрицу Якоби векторного поля $$ - \mathbf J^{-1} \Bigg|_{_{(x,y)}} \left( \begin{array}{c} f(x,y) \\ g(x,y) \end{array} \right) \ , $$ то в каждом вещественном решении $ (x_{\ast},y_{\ast}) $ системы $ f=0,g=0 $ она принимает вид $$ \left(\begin{array}{rr} -1 & 0 \\ 0 & -1 \end{array} \right) \, . $$ Точка $ (x_{\ast},y_{\ast}) $ оказыватся не просто положениями равновесия, а асимптотически устойчивым. Любая траектория2) динамической системы, начинающаяся в точке $ (x_0,y_0) $, лежащей в некоторой окрестности $ (x_{\ast},y_{\ast}) $, будет стремиться к $ (x_{\ast},y_{\ast}) $ при $ t \to +\infty $. Метод Ньютона представляет собой вариант построения приближения решения системы дифференциальных уравнений методом ломаных Эйлера. В этом случае величина шага $ h $ берется равной $ 1 $. Эта величина может оказаться слишком большой, и вместо сходимости к ближайшему к стартовой точке $ (x_0,y_0) $ решению можем получить сходимость к какому-то иному А то и вовсе хаотичное блуждание в плоскости. Только при удачном выборе $ (x_0,y_0) $ близко к решению $ (x_{\ast},y_{\ast}) $ можно гарантировать монотонное (в смысле уменьшения отклонения) стремление последовательности метода Ньютона к $ (x_{\ast},y_{\ast}) $.

Условие отсутствия решения у системы $$ f(x,y)=0, g(x,y)=0, \det \mathbf J =0 $$ в случае полиномиальных функций $ f $ и $ g $ может быть установлено алгебраическими методами, т.е. выражено в виде алгебраического неравенства относительно коэффициентов $ f $ и $ g $.

Ответ на вопрос 2 аналогичен ответу для одномерного случая. Если последовательность сходится к точке $ (x_{\ast},y_{\ast}) $, в которой $ \det \mathbf J \ne 0 $, то $ f(x_{\ast},y_{\ast})=0, g(x_{\ast},y_{\ast})=0 $. Вместе с тем, можно подобрать $ (x_0,y_0) $, что предела у последовательности метода Ньютона существовать не будет. (См. комментарий к частному случаю метода — поиску мнимого корня вещественного полинома.)

Универсального (подходящего для произвольных функций $ f $ и $ g $) ответа на вопрос 3 не существует. Но для полиномиальных функций существуют чисто алгебраические процедуры определения точного числа вещественных решений системы и даже их локализации (например, определения количества решений в произвольном прямоугольнике $ a<x<b,c<y< d $). Процедуры конструктивные (конечное число элементарных алгебраических операций над коэффициентами полиномов), но громоздкие.

Осталось прояснить еще два вопроса.

4. В чем смысл условия $ \det J \ne 0 $? Почему при его нарушении сходимость метода не гарантируется?

5. Какова природа сходимости метода Ньютона? В одномерном случае — при решении уравнения $ f(x)=0 $ — дается понятное геометрическое обоснование метода («метод касательных»). Что является аналогом в двумерном случае?

Прежде всего, заметим, что каждое из линейных уравнений системы, например, $$ 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 $$ не определяет касательную ни к одной из кривых $ f(x,y)=0 $ или $ f(x,y)=f(x_0,y_0) $.

Источники

[1]. Степанов В.В., Немыцкий В.В. Качественная теория дифференциальных уравнений. 1947. - 448с pdf

1)
Все последующие вычисления проводились с абсолютной точностью, т.е. в рациональных числах, а результаты представлялись округленными до $ \pm 10^{-3} $.
2)
Она называется еще фазовой траекторией.
algebra2/dets/jacobian/newton_mult.txt · Последние изменения: 2024/09/08 13:53 — au