Войти на сайт

или
Регистрация

Навигация


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

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

Рассмотрим систему уравнений

 

в предположении, что  – непрерывно-дифференцируемые функции.

Полагая

,

прейдём к векторной записи

 (3.1)

Опишем общий шаг метода. Пусть уже получено приближение  проведём линеаризацию вектор-функции  в окрестности точки  - разложим функцию  в ряд Тейлора, оставив только два первых члена в силу малости отклонения приближения  от корня:


.

Здесь – матрица Якоби для вектор-функции .

Очередное приближение  определяется как решение линейной системы , т.е.

Если матрица Якоби  не вырожденна, то решение системы линейной системы можно записать в явном виде, что приводит к стандартной формуле метода Ньютона

 (3.2)

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

Через уже известное приближение  к корню  можно записать, что , где . Тогда после линеаризации получим систему уравнений, линейную относительно . Таким образом, на каждом шаге мы будем находить приращения , и новое приближение к решению по формулам:

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


Рассмотрим вопрос о сходимости метода Ньютона. Точное условие сходимости метода Ньютона для решения систем нелинейных уравнений имеет довольно сложный вид. можно отметить очевидный результат: в достаточно малой окрестности корня итерации сходятся, если матрица Якоби невырожденная, причём сходимость квадратичная.

Приведём ряд теорем, выполнение условий которых должно обеспечивать сходимость метода Ньютона.

Пусть в пространстве  выбрана некоторая векторная норма  и согласованная с ней матричная норма .

Теорема (о сходимости). Пусть

1)                вектор-функция  определена и непрерывно-дифференцируема в области

 

где  – решение уравнения (3.1),

2) для всех  существует обратная матрица , причём

3)для всех

4)

Тогда метод Ньютона (3.2)

1)

2)

3)

Доказательство. Докажем первое утверждение теоремы с помощью индукции. По условию . Допустим, что . Поскольку , то . Рассмотрим условие 3) теоремы для  

.

Согласно формуле (3.2)

,

Кроме того . Тогда предыдущее неравенство принимает вид

Следовательно,

Таким образом, имеет место неравенство

 (3.3)

По предположению индукции . Поскольку в силу условия 4)

, то

Это значит, что для , и шаг индукции реализован. Превое утверждение теоремы доказано.

Продолжим доказательство. Положим перепишем оценку (3.3) после умножения на в виде . Покажем, что

 (3.4)

Будем рассуждать по индукции. При  неравенство (3.4.) очевидно. Допустим, что оно справедливо для некоторого . Тогда

Переход  завершен, т.е. неравенство (3.4) справедливо для всех . Перепишем его в исходных обозначениях

Получили утверждение 3). При этом

, т.е. .

Это значит, что имеет место сходимость:  

Замечание 1. Неравенство (3.3) при условии  означает, что последовательность  сходится к решению  с квадратичной скоростью.

Замечание 2. Поскольку , то из утверждения 3) следует оценка погрешности метода Ньютона

Теорема. Если fi(x) непрерывны, вместе с первыми производными в выпуклой области G, содержащей решение системы $X^{\ast}$и при $x= X^{\ast}$матрица Fx не вырождена, то существует такая окрестность что при любом метод Ньютона сходится к $x^{\ast}$.$\Box$

$x^0\in R$

Доказательство. Рассмотрим

\begin{eqnarray*}f_i(z)-f_i(y)&=&\int^1_0\frac{d}{dt}f_i(y_1+t(z_1-y_1),\quady... ...um^n_{j=1}\frac{\partial}{\partial x_j}f_i(y+t(z-y))(z_j-y_j)dt.\end{eqnarray*}

Введем и матрицу и матрицу. Очевидно, что F(x,x)= F(x), то есть имеем

$F_{ij}(y,z)=\int^1_0\frac{\partial}{\partial x_j}f_i(y+t(z-y))dt$,$F(y,z)=\{F_{ij}\}$
 

 (12)


Есть тождества

\begin{eqnarray*}f(X^{\ast})&=&0,\enskip X^{\ast}=\varphi(X^{\ast})\equiv X^{\... ...st})f(X^{\ast})\\ x^{k+1}&=&\varphi(x^k)=x^k-F^{-1}_x(x^k)f(x^k),\end{eqnarray*}

Тогда.

\begin{displaymath}x^{k+1}-X^{\ast}=\big[E-F^{-1}_x(x^k)F(X^{\ast},x^k)\big](x^k-X^{\ast}).\end{displaymath}

Вблизи окрестности $X^{\ast}$для любого найдется такое x0, что если,. то

Тогда

\begin{eqnarray*}\Vert x^k-X^{\ast}\Vert& \leq &K^k\Vert x^0-X^{\ast}\Vert\\ li... ...}\Vert x^k-X^{\ast}\Vert&=&0,\quad lim_{k\to\infty}x^k=X^{\ast}.\end{eqnarray*}

На начальное приближение x0 наложено труднопроверяемое условие.

$\{\Vert x-x^0\Vert\leq\rho\}$Теорема Канторовича. Если функции fi(x) непрерывны вместе со своими 1 -ми и 2 -ми производными в некоторой выпуклой области G, содержащей точку x0 вместе с ее окрестностью и выполнены следующие условия:

в точке x0 существует матрица F-1 такая

\begin{displaymath}\Vert F^{-1}_x(x^0)\Vert _{\infty}\leq M_0\end{displaymath}

 

то последовательность xk+1=xk-f-1x(xk)F(xk) сходится к $X^{\ast}$.$X^{\ast}$является единственным решением системы f(x)=0 в области и имеет место оценка

\begin{displaymath}\Vert X^{\ast}-x^k\Vert _1\leq(\frac{1}{2})^{k-1}h^{2^k}_0r_0.\end{displaymath}$\Box$

Докажем 3 неравенства

а) $\Vert f(x+\Delta x)-f(x)\Vert _{\infty}\leq F_x(\xi)\Vert\Vert\Delta x\Vert$

б)$\Vert F_x(x+\Delta x)-F_x(x)\Vert\leq nN\Vert\Delta x\Vert$

в) $\Vert f(x+\Delta x)-f(x)-F_x(x)\Delta x\Vert\leq\frac{1}{2}nN\Vert\Delta x\Vert^2_{\infty}$

\begin{eqnarray*}\Vert f(x+\Deltax)-f(x)\Vert&=&max_i\vert\sum^n_{j=1} \frac{\... ...ial x_j}\vert\\ &\leq&\Vert\Deltax\Vert\cdot\Vert F_x(\xi)\Vert.\end{eqnarray*}


б)\begin{eqnarray*}\Vert F_x(x+\Deltax)-F_x(x)\Vert&=&max_i\sum^n_{j=1}\vert\sum... ...partial x_q\partial x_k}\vert\leq nN\Vert\Deltax\Vert _{\infty}.\end{eqnarray*}

\begin{eqnarray*}\Vert f(x+\Delta x)-f(x)-F_x(x)\Delta x\Vert&=&max_i\vert f_i... ...al x_k}\vert\\ &\leq&\frac{n}{2}\cdot\Vert\Delta x\Vert^2\cdot N.\end{eqnarray*}

в)

\begin{displaymath}\Vert x^1-x^0\Vert=\Vert F^{-1}_x(x^0)f(x^0)\Vert\leq\Vert F^{-1}_x\Vert\Vert f(x^0)\Vert\leqM_0\delta=r_0<\frac{\rho}{2}.\end{displaymath} 

\begin{eqnarray*}\Vert E-F^{-1}_x(x^0)F_x(x^1)\Vert&=&\Vert F^{-1}_x(x^0)(F_x(x... ...0\Vert\\ &\leq&nr_0M_0N\\ &=& \frac{h_0}{2}\\ &\leq&\frac{1}{2},\end{eqnarray*} 

т.е. матрица F-1x(x0)Fx(x1) невырождена, и


\begin{displaymath}\Vert\big[F^{-1}_x(x^0)F_x(x^1)\big]^{-1}\Vert\leq\frac{1}{1-h_0/2}\leq 2.\end{displaymath}

\begin{displaymath}\Vert E\Vert-\Vert A\Vert\leq\Vert E-A\Vert,\quad1-\alpha\l... ...rt A^{-1}\Vert\leq\frac{1}{\Vert A\Vert}\leq\frac{1}{1-\alpha}\end{displaymath}

\begin{displaymath}F^{-1}_x(x^1)=\big[F^{-1}_x(x^0)F_x(x^1)\big]^{-1}F^{-1}_x(x^0)\end{displaymath} и

\begin{displaymath}\Vert F^{-1}_x(x^1)\Vert\leq 2\cdot M_0.\end{displaymath}

Fx(x0)(x1-x0)+f(x0)=0

\begin{displaymath}\Vert f(x^1)\Vert\leq\Vert f(x^1)f(x^0)-F_x(x_0)(x^1-x^0)\Vert\leq\frac{1}{2}nN\cdot r^2_0\end{displaymath}

\begin{displaymath}\Vert F^{-1}(x^1)f(x^1)\Vert\leq\frac{1}{2} nN\cdotr^2_0\cdot 2M_0=(M_0nr_0N)r_0=\frac{h_0r_0}{2}\leq\frac{r_0}{2}.\end{displaymath}

Покажем, что при всех k имеют место неравенства:

 (А)

\begin{displaymath}\Vert F^{-1}_x(x^k)\Vert\leq 2M_0;\quad \Vert f(x^k)\Vert\leq\frac{nNr^2_0}{2^{2k-1}}h^{2^k-2}_0\leq\frac{nNr^2_0}{2^{2k-1}}.\end{displaymath}

\begin{displaymath}\Vert F^{-1}_x(x^k)f(x^k)\Vert\leq\frac{r_0}{2^k} \mbox{, при }k=1\mbox{ ужепоказали.}\end{displaymath}

Пусть имеет место m=k-1

\begin{eqnarray*}\Vert x^{m+1}-x^m\Vert&=&\Vert F^{-1}_x(x^m)f(x^m)\Vert\leq\fr... ...1}}+\ldots+\frac{r_0}{2}+r_0<2r_0\leq\rho_0; x^{m+1}\in R_0(x_0)\end{eqnarray*}

Повторим неравенства

\begin{eqnarray*}\Vert E-F^{-1}_x(x^m)F_x(x^{m+1})\Vert&\leq& 2^mM_0nN\frac{r_0... ...{2^m-2}_0=\frac{h^{2^m-1}_0r_0}{2^{m+1}}\leq\frac{r_0}{2^{m+1}}.\end{eqnarray*}

Неравенство (А) показывает, что в круге R последовательность xk является фундаментальной, т.е. имеется предел.

Оценим сходимость

\begin{eqnarray*}\Vert x^{k+p}-x^k\Vert&\leq&\Vert x^{k+p}-x^{k+p-1}\Vert+\ldot... ...\ldots+\frac{1}{2^{p-1}}\big]\leq\frac{r_0}{2^{k-1}}h^{2^k-1}_0,\end{eqnarray*}т.е.,

устремляя правая часть не меняется,, т.е. при очень хорошая сходимость.


Информация о работе «Итерационные методы решения систем нелинейных уравнений»
Раздел: Математика
Количество знаков с пробелами: 37732
Количество таблиц: 2
Количество изображений: 12

Похожие работы

Скачать
15003
0
14

... метод Бройдена, написана программа реализующая его. СПИСОК ЛИТЕРАТУРЫ 1.    С.Л. Подвальный, Л.В. Холопкина. Вычислительная математика- учебное пособие ВГТУ, 2004 - 147 с. 2.    Методы решения систем нелинейных уравнений. Метод Ньютона. Его реализации и модификации. - Электрон. дан. – Режим доступа: www.exponenta.ru/educat/referat/XVkonkurs/15/index.asp. ПРИЛОЖЕНИЕ Текст программы ...

Скачать
10711
0
8

... –0.6 = 0 9. 10. ( x -1)3 + 0.5ex = 0 11. 12. x5 –3x2 + 1 = 0 13. x3 –4x2 –10x –10 = 0 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. x 4- 2.9x3 +0.1x2 + 5.8x - 4.2=0 25. x4+2.83x3- 4.5x2-64x-20=0 26. МЕТОДЫ РЕШЕНИЯ СИСТЕМЫ НЕЛИНЕЙНЫХ УРАВНЕНИЙ 1.         Постановка задачи Пусть требуется решить систему n ...

Скачать
14674
0
13

... 1040, мы все еще получаем сходимость, при количестве итераций порядка 130.   4 Анализ результатов, выводы Целью нашего исследование было сравнение методов простой итерации и Ньютона для решения систем из двух нелинейных уравнений по числу итераций, времени сходимости в зависимости от выбора начального приближения к решению и допустимой ошибки. Зависимость этих параметров от выбора начального ...

Скачать
33577
0
0

... с помощью рекурентных соотношений? 104) Приведите конечно-разностные выражения для первой производной. 105) Подынтегральная функция y = f(x) задана таблицейВзяв h = 0,3, вычислить интеграл  на отрезке [0,3; 0,9] методом Симпсона. Зав. кафедрой --------------------------------------------------   Экзаменационный билет по предмету ЧИСЛЕННЫЕ МЕТОДЫ Билет № 22 106) Как ...

0 комментариев


Наверх