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

      Применение той же последовательно  аппроксимации обратных матриц к  простейшему рекурсивному методу Ньютона (6), или, что то же, к двухступенчатому процессу (7), определяет его аппроксимационный аналог 

Доказательство  кубической сходимости метода требует  более жестких ограничений на свойства F(x) и близость х⁽⁰⁾ к х*, А₀ к ^-1, чем в предыдущем методе. К улучшению сходимости здесь может привести повышение порядка аппроксимации обратных матриц, например, за счет добавления ещё одного слагаемого в формуле для подсчёта А_k+1:

Теорема 5.

     Пусть функция F(x) определена и дифференцируема в МÍÂ_n , причем

$L>0: L||x- || "x, ÎM

Тогда если вектор х⁽⁰⁾ и матрица А₀ таковы, что при некотором l> 0 выполняются неравенства

£Ll²  (9)

v:= 4Ll² £1-          (10)

Т.е. берем  такое l>0 должен удовлетворять кубическому неравенству

4Lp₀l³-2L||A₀||p₀l²-l+||A₀||£0

и                                                                      то начатый с данных х⁽⁰⁾, А₀ ААМН

(8) сходится в S к решению х* уравнения F(x)= 0 и имеет место оценка погрешности ||x*-x^(k)||£ . (11)

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

      Введем в рассмотрение последовательности положительных величин p_k, b_k, b_k , определяемых при k=0,1,2,... равенствами

      (12)

                                             (13) 

Очевидно  невозрастание этих последовательностей. Легко также заметить, что b_k=Ll² p _k  "kÎN₀ . (14)

Действительно, предположив равенство (14) верным при некотором k имеем

b_k+1=(2Ll² p _k )² = Ll² *4Ll² p ²_k  = Ll² p _k+1, т.е. то, что получили бы формальной заменой в (14) k на k+1.

     Обозначим B:=E-F`(x<sup>(k)</sup>)A<sub>k</sub> (-невязка для A<sub>k</sub> относительно [F`(x^(k))]^-1 ). *Невязка – разность между значением функции, вычисленным по результатам измерений, и истинным ее значением, возникающая вследствие неизбежных погрешностей измерений.

Докажем, что при любом kÎN₀ скалярные последовательности  (р_k ), (b_k ), (b_k) мажорируют последовательности норм векторов  F (x^(k)) и матриц  Y_k , B_k соответственно и вместе с тем l ограничивает сверху  ||A_k ||. С этой целью сделаем индукционное предположение, что одновременно выполняются неравенства ||F(x^(k))||£p_k, ||Y_k-1||£b_k-1, ||B_k||£b_k и ||A_k||£l. (15)

     Тогда ясно, что = = £ +

+L|| x^(k+1)-x^(k)|| ||A_k||£b_k+Ll|| ||£Ll²p_k+ Ll²p_k=b_k

(см. (8), (13), (14), (12)).

= = = £ ²£ =b_k+1

(см. (8), (13) и предыдущее неравенство). 
 
 

(см. Теорему  3, (8), (15), (14) и нач. равенство).

Из (8) следует, что 

£ £ £ ..£ £ _, но b_k=1/2v^{2^k} получаем 

В заключении имеем  £ £lp_k, p_k, p_k+1=G₀p_k² , где G₀=4Ll², p₀=

(т.е.  µ=2, v=G₀p₀=4Ll²p₀).

Разностный метод Ньютона.

     На  базе метода Ньютона (3) можно построить близкий к нему по поведению итерационный процесс, не требующий вычисления производных. Сделаем это, заменив частные производные в матрице Якоби J(x) разностными отношениями, т.е. подставив в формулу (2)  x^(k+1)= x^(k)- F(x^(k)), k=0, 1, 2…      вместо А_k матрицу ^-1,

 где J(x,h):=

при удачном  задании последовательности малых  векторов h^(k)=( h₁^(k),.. h_n^(k))^T

(постоянной или сходящейся к  0 полученный таким путем разностный (дискретный) метод Ньютона

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

Заключение.

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

 

Список используемой литературы.

1. Вержбицкий, В.М. Численные методы (линейная алгебра и нелинейные уравнения): Учеб. пособие для вузов/ В.М. Вержбицкий. – 2-е изд., испр. – М.: ООО «Издательский дом «ОНИКС 21 век», 2005. – 432 с.: ил. – ISBN 5-329-01110-8 

2.  Калиткин Н.Н. Численные методы/Н.Н. Калиткин. – М.: Наука, 1978. – 512 с.: ил. 

3. Бахвалов, Н.С.  Численные методы :Учеб. пособие/  Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков. – 2-е изд., перераб. – М.: Бином. Лаборатория знаний, 2003. – 632 с.: ил. – ISBN 5-94774-060-5

 

Приложение.

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

Пример 1.

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

исходя из начального приближения x₀ = y₀ = z₀ =0,5.

Полагая:

х⁽⁰⁾ =             ,      f (х) = 

имеем:

f (х) = 

Отсюда

f ( х⁽⁰⁾ ) = = 
 

Составим матрицу Якоби 

W(x) =  
 

Имеем

W ( х⁽⁰⁾ ) =                              , причем D = det W ( х⁽⁰⁾ ) =  = -40 
 

Следовательно, матрица W ( х⁽⁰⁾ ) - неособенная. Составим обратную ей матрицу

W ^-1 ( х⁽⁰⁾ ) = -1/40                                 =  

По формуле Ньютона получаем первое приближение

х⁽¹⁾ = x⁽⁰⁾ - W ^-1(x⁽⁰⁾ ) f (x⁽⁰⁾ ) =          -               =

= + = 
    

Аналогично находятся  дальнейшие приближения. Результаты вычислений приведены в Таблице

Последовательные  приближения корней

i x y z 0 0,5 0,5 0,5 1 0,875 0,5 0,375 2 0,78981 0,49662 0,36993 3 0,78521 0,49662 0,36992

 

Останавливаясь  на приближении x⁽³⁾ , будем иметь:

x = 0,7852; y = 0,4966; z =0,3699. 
 
 

Пример 2.

Применим  метод  для решения системы уравнений

Матрица частных  производных в аналитическом  виде

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

                                         =

Возьмем начальное  приближение х=0,15, у=0,17

Первая  итерация: матрица Якоби:

Вектор значений функции:

Рассчитанный  вектор поправок:

Новое приближение: х=0,15-0,0138=0,0136196

                          у=0,17+0,071604=0,241604

Вторая  итерация:

Рассчитанный  вектор поправок:

Новое приближение: х= 0,168157

                                     у= 0,268688

Третья  иерация:

Рассчитанный  вектор поправок:

Новое приближение: х= 0,181878

                                     у= 0,282509

На 25-й итерации эвклидова норма вектора невязок составляет  2.77∙10^-7, эвклидова норма вектора поправок составляет  1.96∙10^-7 и решение сходится к  x = 0.2, y = 0.3 с абсолютной погрешностью менее 1∙10^-6 .