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

 

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное  учреждение высшего профессионального  образования 

«Тольяттинский  государственный университет»

Факультет математики и информатики

Кафедра прикладной математики и информатики

Будылкина Ксения Сергеевна

Тема

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

Научный руководитель:

      Тырыгина  Г.А. 

Работу  выполнил:

Студентка гр.ПМИб-301

Будылкина К.С. 

Электронная версия сдана в электронную библиотеку

Тольятти 2011 
 

Факультет математики и информатики

Кафедра прикладная математика и информатика

Утверждаю_____________________________201__г.    Зав.кафедрой

ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ

Студенту___________________________________курса  гр. №________________________ 
1 Тема работы  .      _________________________________________________________________________________________________________________________________________________________ 
2. Задание на специальную разработку____________________________________________ 
__________________________________________________________________________________________________________________________________________________________________ 
3. Содержание подлежащих разработке вопросов

______________________________________________________________________________________________________________________________________________________________________________ 
4. Перечень обязательного иллюстративного материала   ___________________________________________________________________  
__________________________________________________________________________________________________________________________________________________________________ 
5. Рекомендуемая литература и материалы_________________________________________ 
__________________________________________________________________________________________________________________________________________________________ 

Срок  сдачи законченной работы «___»___________________20__г.

Дата  выдачи    «___»___________________20__г.

                  Руководитель_____________________________

Задание принял к исполнению «___»___________________20__г.

                        Студент___________________________

Аннотация.

     Данная  работа состоит из 8 разделов, некоторые из которых содержат несколько подразделов, дополняющих основную тему. Работа начинается с рассмотрения определения системы и определения применения метода Ньютона к ней. Некоторые разделы содержат теоремы и приведенные к ним доказательства. Приложение содержит блок- схему для решения системы методом Ньютона и примеры к данной теме.

     Актуальность: система уравнений требует больших  вычислений что бы найти конкретное решение, для этого необходимо тщательно рассмотреть метод Ньютона.

     Цель  работы: изучить один из методов решения систем нелинейных уравнений.

     Задачи: установить существование условий, скорости сходимости метода и различных модификаций для упрощения вычислений. 
 
 
 
 
 
 
 
 

Содержание. 
 
 
 
 
 
 
 

Введение.

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

     В основе метода Ньютона лежит идея линеаризации всех нелинейных уравнений системы. Линеаризация - один из методов приближённого представления замкнутых нелинейных систем, при котором исследование нелинейной системы заменяется анализом линейной системы, в некотором смысле эквивалентной исходной.

     Новым фактором, осложняющим применение метода Ньютона к решению n- мерных систем, является необходимость решения n- мерных линейных задач на каждой итерации, вычислительные затраты на которые растут с ростом n очень быстро. Для решении этой проблемы так рассмотрим разные модификации метода Ньютона.

     Под решением некой нелинейной системы  уравнений F(x) понимается нахождение такого решения, когда каждое уравнение в данной нелинейной системе будет равно нулю.

       Таким образом, имеем n уравнений и n неизвестных и нужно найти такие xÎÂⁿ, что будет справедливо F(x)=0, где

     Пусть требуется решить систему уравнений 

                                             (1) 

где x₁, x₂, ...x_n заданные нелинейные вещественнозначные функции n вещественных переменных.

      Обозначив 
 
 

данную систему  (1) можно записать одним уравнением F(x)=0, относительно векторной функции F векторного аргумента x. Таким образом,  исходную задачу можно рассматривать как задачу о нулях нелинейного отображения

F: Â_n® Â_n. В этой постановке она является прямым обобщением задачи построения методов нахождения нулей одномерных нелинейных отображений.  
 
 
 
 
 

Алгоритм  вычисления методом Ньютона.

     Пусть  (А_k)- некоторая последовательность невырожденных (n x n) –матриц. Тогда последовательность задач x= x- А_kF(x), k=0, 1, 2,… имеет те же решения, что и исходное уравнение F(x)=0.  Для приближенного нахождения этих решений можно записать итерационный процесс

x^(k+1)= x^(k)- А_kF(x^(k)), k=0, 1, 2,… (2), имеющий вид простых итераций

x^(k+1)= Ф(x^(k)), k=0, 1, 2,…

При F(х):=F_k(х):= х- А_kF(х)  ,   где x= Ф(x),

Ф(x):= = ,

в случае А_k= А это метод простых итераций с линейной сходимостью последовательности  (x^(k)). Если А_k  различны при разных k, то

x^(k+1)=x^(k)- А_kF(x^(k)), k=0, 1, 2,…определяет большое семейство

итерационных методов с матричными параметрами А_k .

     Пусть А_k:= , где

 
 

                                                       - матрица Якоби для вектор- функции F(х).

Матрица  J, составленная из частных производных  функций F= (f₁, …f_n ),

f_i = (x₁,...,x_n), при отображении F: Âⁿ ® Âⁿ, в точке x, называется матрицей Якоби данной системы функций. 

Подставив матрицу А_k  в (2), получаем формулу метода Ньютона:

x^(k+1)= x^(k)-

F(x^(k))  (3)

Эту формулу  можно представить в неявном  виде:

F`(x^(k)) (x^(k+1)- x^(k))= -F(x^(k))  (4)

Сравнивая (4) с формальным разложением F(х) в ряд Тейлора 

видим, что последовательность  (х^(k)) в методе Ньютона получается в результате подмены при каждом k=1, 2,.. нелинейного уравнения F(х)=0, или, что то же уравнения

линейным  уравнением F(x^(k)) + F`(x^(k))(x-x^(k))= 0, т.е. пошаговой линеаризацией. 
 
 
 
 
 
 
 
 
 

Условия сходимости метода Ньютона.

      Пусть имеет место отображение  F:Âⁿ ®Âⁿ

 

Пусть W_а={х:||x-x*||<a}. Пусть при некоторых а, а₁, а₂ Î(0, µ) выполняются условия:

 ||[F`(x)]^-1|| £a₁ "xÎW_а      (*)

||F`(u<sub>1</sub>)- F (u<sub>2</sub>)- F`(u₂)( u₁- u₂)||£a₂ ||u₂- u₁||²     (**)  " u₁, u₂ ÎW_а

     Положим С= а₁ а₂ , b=min{a_i,c^-1}. При выполнении условий (*)(**),

     х⁰ ÎW_а , W_b={х_i:||x-x*||<b} итерационный процесс Ньютона сходится, причём известна оценка ||x^k-x*||£c^-1(c||x⁰-x¹||)^{2^k}.

если последовательность приближается к x^* , то Dх^k®0. На практике не пользуются этим условием сходимости, а производят исчисления до тех пор, пока все разности не станут достаточно малыми, т.е. не будет выполняться условие max|Dх^k _i|<e,1£ i£n и e заданная точность.

С ростом числа уравнений системы 

скорость сходимости метода ухудшается. 

Скорость сходимости метода Ньютона.

Теорема 1.

      Пусть непрерывная векторная функция F: MÍÂ_n ®Â_n  и последовательность векторов x^(k) ÎM таковы, что при всех kÎ N₀ выполняются условия:

1) || x^(k+1)- x^(k)||£lp_k;

2) ||F(x^(k))||£ p_k,  где числа р_k определяются рекуррентным равенством

p_k+1 = G₀ p^µ _k ; k= 0, 1, 2, … , l> 0, G₀ > 0, p₀ > 0, µ> 0 – некоторые числовые параметры.

Тогда, если v:= G₀ p^µ-1 ₀<1 и замкнутый шар  

содержится  в М, то все члены последовательности  (х^(k)) принадлежат S, последовательность (х^(k)) имеет предел x^*ÎS, такой, что F(x^*)= 0; при этом быстрота сходимости (х^(k)) к x^* характеризуется неравенством ("kÎN).

||x*-x^(k)||£

Доказательство.

     Пользуясь  p_k+1 = G₀ p^µ _k , выразим элементы последовательности (р_i) через ее начальный член p₀ и определенную в теореме величину v:

p_i= G₀ p^µ _i-1= G₀ (G₀ p^µ _i-1)^µ= G₀^1+µ p _i-2^{µ^2} = G₀^{1+µ+ µ^2} p _i-3^{µ^3}=…=

  G₀^{1+µ+ µ^2+..+µ^i-1} p ₀^{µ^i}= * p₀^{µ^i-1}* p₀^{1- µ^i}* p₀ ^{µ^i}= p₀*