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

Метод Ньютона (метод дотичних) для наближеного розв’язку рівняння полягає в побудові ітераційної послідовності

, (2.22)

що збігається до кореня рівняння, на відрізку локалізації кореня.

Теорема 7 Якщо f(a) f(b)<0, причому f¢(x) і f²(x) не дорівнюють нулю і зберігають певні знаки при a £ x £ b, то, виходячи з початкового наближення x₀Î[a,b], що задовольняє нерівність

, (2.23)

можна обчислити методом Ньютона єдиний корінь x рівняння з будь-яким ступенем точності.

Доведення. Нехай, наприклад, f(а)<0, f(b)>0, f¢(x)>0, f²(x)>0 при a £ x £b (інші випадки розглядаються аналогічно). Відповідно до нерівності (2.23) маємо f(x₀)>0. (наприклад, можна взяти x₀=b). Методом математичної індукції доведемо, що всі наближення x_n>x (n=0,1,2…) і, отже, f(x_n)>0. Справді, насамперед, x₀>x. Нехай тепер x_n>x. Покладемо x = x_n + (x - x_n).

Застосовуючи формулу Тейлора, одержимо

0 = f(x)= f(x_n) + f¢(x_n)(x - x_n)+ , (2.24)

де x<c_n<x_n. Оскільки f²(x)>0, маємо

і отже, , що і потрібно було довести.

З огляду на знаки f(x_n) та f¢(x_n), маємо x_n+1<x_n (n=0,1,…), тобто послідовні наближення x₀,x₁,…,x_n,… утворять обмежену монотонно спадну послідовність. Отже, існує .

Переходячи до границі в рівності (2.22), будемо мати

,

тобто f() = 0. Звідси = x, що і потрібно було довести.

Тому, застосовуючи метод Ньютона, варто керуватися таким правилом: за вихідну точку x₀ вибирається той кінець інтервалу (а,b), якому відповідає ордината того самого знака, що і знак f²(x).

Зауваження. З формули (2.22) бачимо, що чим більше числове значенняf¢(x) в околі кореня, тим меншою є поправка, яку треба додати до попереднього наближення, щоб отримати наступне. З цієї причини метод Ньютона особливо зручний тоді, коли в околі кореня графік функції має велику крутизну. Якщо ж f¢(x) біля кореня – мала, то застосовувати даний метод не рекомендується.

Для оцінки похибки n -го наближення x_n можна скористатися формулою

, (2.25)

де m₁ найменше значення ½ f¢(x) ½ на відрізку [ a,b ].

Виведемо ще одну формулу для оцінки точності наближення x_n.

Застосовуючи формулу Тейлора, маємо:

, (2.26)

де x_n-1Î (x_n-1, x_n). Оскільки з визначення наближення x_n маємо

, то з (2.26) знаходимо: де М₂ – найбільше значення ½ f² (x) ½ на відрізку [ a,b ]. Отже, на підставі формули (26) остаточно одержуємо

(2.27)

Якщо процес збігається, то x_n-x_n-1 ®0 при n®¥. Тому при n³N маємо тобто «у сталені» початкові десяткові знаки наближень x_n-1 і x_n, починаючи з деякого наближення, є правильними.

Зауважимо, що в загальному випадку збіг з точністю до e двох послідовних наближень x_n-1 і x_n зовсім не гарантує, що з тією самою точністю збігаються значення x_n і точний корінь x.

Проаналізуємо абсолютні похибки двох послідовних наближень x_n і x_n+1. З формули (2.24) одержуємо

,

де c_nÎ (x_n, x). Звідси, з огляду на формулу (2.22), будемо мати

і, отже,

. (2.28)

Формула (2.28) забезпечує швидку збіжність процесу Ньютона, якщо початкове наближення x₀ таке, що . Зокрема, якщо і , тобто наближення x_n мало m правильних десяткових знаків після коми, то наступне наближення x_n+1 буде мати не менше 2m правильних знаків; іншими словами, якщо , то за допомогою методу Ньютона число правильних знаків після коми шуканого кореня x подвоюється на кожному кроці.

Приклад. Знайти корінь рівняння з точністю

1 Це рівняння має один корінь на (f(0)f(1))<0)

Знайдемо похідні

.

2 Вибираємо початкове наближення кореня так, щоб Обираємо , тому що .

3 Будуємо ітераційну послідовність

4 Обчислення припиняємо, тому що , і за наближене значення кореня з точністю беремо

Приклад реалізації чисельного алгоритму розв’язування нелінійних рівнянь на псевдокоді

//Метод Ньютона. Вважаємо, що умова збіжності методу перевірена

f(x):

//повертає значення функції для даного х

End

f1(x):

//повертає значення першої похідної функції для данного х

End

f2(x):

//повертає значення другої похідної функції для даного х

End

//a,b – границі відрізка, eps – точність розв’язку

Solve_Nonlinear(a,b,eps):

1 if f1(a)<f1(b) then

2 min:=abs(f1(a))

Else

4 min:=abs(f1(b))

Fi

6 if f2(a)>f2(b) then

7 max:=abs(f2(a))

Else

9 max:=abs(f2(b))

Fi

11 fault:=sqrt(2*min*eps)

12 if f(b)*f2(b)>0 then

13 x:=b

Else

15 x:=a

Fi

Repeat

18 n++

19 if n>1 then

20 x:=xn

Fi

22 xn:=x-f(x)/f1(x)

23 until abs(xn-x)<=fault

24 return x

End

2.8 Обумовленість задачі визначення кореня

Нехай – корінь, що підлягає визначенню. Будемо вважати, що вхідними даними для задачі обчислення кореня є значення функції . Оскільки обчислюється наближено, то позначимо функцію, отриману в дійсності через . Припустимо, що в малому околі кореня виконується нерівність: . Для близьких до значень х справедлива рівність , отже, . Це означає, що число обумовленості задачі знаходження кореня дорівнює . З останньої формули можна зробити висновок, що чим менше значення похідної функції в точці кореня, тим задача гірше обумовлена. Зокрема, задача знаходження кратного кореня має число обумовленості – нескінченність.

Інтервал невизначеності кореня. Якщо функція неперервна, то знайдеться такий малий окіл кореня , що має радіус ε, у якому виконується нерівність . Це означає, що для знак обчисленого значення взагалі не зобов’язаний збігатися зі знаком , і, отже, стає неможливим визначити, яке саме значення х з інтервалу обертає функцію f в нуль. Цей інтервал називається інтервалом невизначеності кореня. Очевидно, що радіус інтервалу невизначеності для простого кореня дорівнює . Аналогічно можна показати, що для кратного кореня . Це означає, що для простого кореня радіус інтервалу невизначеності прямо пропорційний похибці обчислення функції , а для кратного кореня .

Приклад. Теоретична оцінка радіуса інтервалу невизначеності кореня.

Нехай . Корінь рівняння простий і дорівнює . Тоді і . Якщо , то . Це означає, що знайти корінь із точністю меншою, ніж радіус інтервалу невизначеності, не вдасться.