Розв’язання нелінійних рівнянь

↑

▷ Содержание

⇐ ПредыдущаяСтр 6 из 29Следующая ⇒

 у комплексній площині

Нехай задана функція f(х) дійсної змінної. Потрібно знайти нулі функції f(х) або, що те ж саме, корені рівняння

f(x)=0                                              (2.7)

Уже на прикладі алгебраїчного многочлена відомо, що нулі f(х) можуть бути як дійсними, так і комплексними. Тому більш точною є постановка задачі у визначенні коренів рівняння (2.7), розміщених у заданій області комплексної площини. Можна розглядати задачу визначення дійсних коренів, розміщених на заданому відрізку. Іноді, нехтуючи точністю формулювань, будемо говорити, що потрібно розв’язати рівняння (2.7).

У загальному випадку задача визначення коренів рівняння (2.7), як правило, розв’язується в два етапи. На першому етапі вивчається розміщення корені і проводиться їх відділення, тобто виділяються області в комплексній площині, що містять тільки один корінь. Крім того, вивчається питання про кратність коренів.  Знаходяться деякі початкові наближення для коренів рівняння (2.7). На другому етапі, використовуючи задане початкове наближення, будується ітераційний процес, що дозволяє уточнити значення невідомого кореня.

Не існує якихось загальних регулярних прийомів розв’язання задачі про розміщення коренів довільної функції f(х). Найбільш повно вивчене питання про розміщення коренів алгебраїчних многочленів

         f(x)=a₀+a₁x+a₂x²+…+a_mx^m.              (2.8)

Наприклад відомо, що якщо для многочлена (2.8) з дійсними коефіцієнтами виконані нерівності f(c)>0, f’(c)>0,…,f^(m)(c)>0, то додатні корені f(х) не перевершують числа с. Дійсно, з формули Тейлора

одержуємо, що f(x)>0 при x>c.

Чисельні методи розв’язання нелінійних рівнянь є, як правило, ітераційними методами, що припускають завдання досить близьких до шуканого розв’язку початкових даних. Перш ніж переходити до викладу конкретних ітераційних методів, відзначимо два прості прийоми відділення дійсних коренів рівняння (2.7). Припустимо, що f(х) визначена і неперервна на [а,b].

Перший прийом полягає в тому, що обчислюється таблиця значень функції f(х) у заданих точках х_k Î [а, b], k =0, 1,..., п. Якщо виявиться, що при якомусь к числа f(х_k), f(x_k+1) мають різні знаки, то це буде означати, що на інтервалі (х_k,x_k+1) рівняння (2.7) має принаймні один дійсний корінь (точніше, має непарне число коренів на (х_k, x_k+1)). Потім можна розбити інтервал (x_k,x_k+1) на більш дрібні інтервали і за допомогою аналогічної процедури уточнити розміщення кореня.

Більш регулярним способом відділення дійсних коренів є метод бісекції (розподілу навпіл). Припустимо, що на (а, b) роміщений лише один корінь х рівняння (2.7). Тоді f(а) і f(b) мають різні знаки. Нехай для визначеності f(а)>0, f(b)<0. Покладемо x₀=0,5 × (a+b) і обчислимо f(x₀). Якщо f(x₀)<0, то шуканий корінь знаходиться на інтервалі (a,x₀), якщо ж f(х₀)>0, то на (х₀, b). Далі, із двох інтервалів (a, x₀) і (х₀,b) вибираємо той, на кінцях якого функція f(х) має різні знаки, знаходимо точку х₁-середину обраного інтервалу, обчислюємо f(х₁) і повторюємо зазначений процес. У результаті одержуємо послідовність інтервалів, що містять шуканий корінь х_1, причому довжина кожного наступного інтервалу вдвічі менша за попередній. Процес закінчується, коли довжина знову отриманого інтервалу стане менше заданого числа e >0, і за корінь х приблизно береться середина цього інтервалу.

Помітимо, що якщо на (а, b) міститься кілька коренів, то зазначений процес зійдеться до одного з коренів, але заздалегідь невідомо, до якого саме. Можна використовувати прийом виділення коренів: якщо корінь х=х^* кратності m знайдений, то розглядається функція g(х)=f(х)/(x-x^*)^т і для неї повторюєтьсяпроцес визначення кореня.

                     y

                     O   ax^*b                       x

Рис. - 2.1

Обмеження кореня функції, якщо вона визначення на необмеженому інтервалі здійснюється так.

1 Для початкового наближення x₀, знайти f₀=f(x₀), задати інтервал пошуку D і його інкремент d>1.

2 Обчислити a=x₀-D, b=x₀+D; f_a = f(a), f_b = f(b).

3 Збільшити інтервал пошуку: D=D d.

4a Якщо знаки f_a і f₀ різні, то вважати корінь обмеженим на [a,x₀] -> вихід.

4b Якщо знаки f_b і f₀ відрізняються, то вважати корінь обмеженим на [x₀,b] -> вихід.

5 Перевіряється, яке з f_a і f_b найменше. Якщо вони однакові, то переходимо до 6a (двосторонній пошук), якщо f_b – робимо пошук вправо 6b, інакше - пошук уліво 6c.

 6a Знаходимо a=a-D, b=b+D, f_a=f(a), f_b=f(b), йдемо до пункту 3.

    6b Присвоюємо послідовно a=x₀, x₀=b, f_a=f₀, f₀=f_b; знаходимо b=b+D, f_b=f(b), йдемо до пункту 3.

 6c. Аналогічно 6b, тільки напрямок пошуку - вліво.

Метод простих ітерацій

Замінимо рівняння  еквівалентним йому рівнянням .

                     y

                 O  a x₁ x^* x₀ b                  x

Рисунок 2.2

Виберемо деяке наближення  кореня і підставимо його в праву частину. Одержимо . Далі обчислюємо за формулами: . Отримуємо послідовність наближень { } до кореня, що у випадку її збіжності до кореня  може дати наближене його значення із заданою точністю .

Теорема 6 Нехай функція j (x) визначена і диференційована на відрізку [a,b], причому всі значення j (х) Î [a,b].Тоді якщо існує правильний дріб q, такий, що

        ½ j ^¢ (x) ½ £ q < 1               (2.9)

при a<x<b, то: процес ітерації

                    x_n= j (x_n-1) (n = 1,2,…)     (2.10)

1) збігається незалежно від початкового значення x₀ Î [a,b];

2) граничне значення  є єдиним коренем рівняння                             x= j (x)                          (2.11)

на відрізку [a,b].

Доведення. Розглянемо два послідовних наближення x_n= j (x_n-1) і x_n+1= j (x_n) (які внаслідок умов теореми існують). Звідси x_n+1 - x_n= j (x_n) - j (x_n-1).

Застосовуючи теорему Лагранжа, будемо мати:

x_n+1 - x_n   = (x_n - x_n-1) j ^¢ (), де  .

Отже, на підставі умови (2.9) одержимо

               (2.12)

Звідси, надаючи значення n=1,2,3,…, отримаємо:

;

          ..............................................

                 (2.13)

Розглянемо ряд:

x₀ + (x₁- x₀) + (x₂- x₁) + … + (x_n – x_n-1) + …, (2.14)

для якого наші послідовні наближення x_n є (n+1) -ми частковими сумами, тобто x_n=S_n+1. За нерівністю (2.13) члени ряду (2.14) за абсолютною величиною менші відповідних членів геометричної прогресії зі знаменником q<1, тому ряд (2.14) збігається, до того ж абсолютно. Отже, існує , причому, вочевидь, Î [a,b]. Переходячи до границі в рівності (2.10), зважаючи на неперервність функції j (x) одержуємо

  = j (  ).                         (2.15)

У такий спосіб  є корінь рівняння (2.11). Іншого кореня на відрізку [a,b] рівняння (2.11) не має. Дійсно, якщо

                   ,                          (2.16)

то з рівностей (2.15) і (2.16) одержимо

і отже,              ,                   (2.17)

де c Î . Оскільки вираз у квадратній дужці в рівності (2.17) не дорівнює нулю, то , тобто корінь  - єдиний.

Зауваження 1 Теорема залишається правильною, якщо функція j (x) визначена і диференційована на інтервалі , причому при x Î (- ¥;+ ¥) виконана нерівність (2.9).

Зауваження 2 В умовах теореми метод ітерації збігається при будь-якому виборі початкового значення x₀ Î [a,b]. Завдяки цьому він є самовиправним, тобто окрема помилка в обчисленнях, що не виводить за межі відрізка [a,b,] не вплине на кінцевий результат, тому що помилкове значення можна розглядати як нове початкове значення x₀. Можливо, зросте лише обсяг роботи. Властивість самовиправлення робить метод ітерації одним із найнадійніших методів обчислень.

Оцінка наближення. З формули (2.13) маємо:

Застосувавши формулу суми геометричної прогресії, одержимо:

Спрямовуючи число р до нескінченності і з огляду на те, що , знаходимо остаточно:

                        .             (2.18)

Звідси ясно, що збіжність процесу ітерації буде тим швидшою, чим менше число q.

Для оцінки наближення можна дати іншу формулу, корисну в деяких випадках. Представимо f(x)=x - j (x).

Очевидно, що   Звідси, з огляду на те, що f(x)=0, одержимо:

де , і, отже,

                                         (2.19)

тобто

                            (2.20)

Використовуючи формулу (2.12), маємо також

                  .           (2.21)

Звідси, зокрема, випливає, що якщо q £  , то . В цьому випадку з нерівності  випливає нерівність  .

Зауваження. Існує поширена думка, що якщо при застосуванні методу ітерації два послідовні наближення x_n-1 і x_n збігаються між собою із заданою точністю e (наприклад, для цих наближень установилися т перших десяткових знаків), то з тією самою точністю справедлива рівність x» x_n (тобто, зокрема, у наведеному прикладі т знаків наближеного числа x_n є правильними!). У загальному випадку це твердження помилкове. Більше того, легко показати, що якщо j '(х) близька до 1, то величина | x - x_n | може бути великою, хоча |x_n - x_n-1| дуже мала.

Формула (2.20) дає можливість оцінити похибку наближеного значення x_n за різницею двох послідовних наближень x_n-1 і x_n.

Процес ітерації варто продовжувати доти, поки для двох послідовних наближень x_n-1 і x_n не буде забезпечене виконання нерівності

,

де e - задана гранична абсолютна похибка кореня x і ½ j ^¢ (x) ½ £ q. Тоді за формулою (2.21) будемо мати нерівність , тобто x = x_n ± e.

Зауважимо, що якщо x_n= j (x_n-1) і = j ( ), то , , тобто  .

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

На практиці здебільшого буває так, що грубим прийомом встановлюється існування кореня рівняння (2.7) і методом ітерації потрібно одержати досить точне наближене значення кореня, причому нерівність (2.9) виконується лише в деякому околі (a, b) цього кореня. Тут при невдалому виборі початкового значення x₀ послідовні наближення x_n= j (x_n-1) (n = 1,2,…) можуть залишити інтервал (a, b) чи навіть втратити сенс.

Приклад. Розв’язати рівняння f(x)=0 на заданому відрізку [a,b]=[0, ], де =0,

Аналітичне розв’язання задачі. Розкладемо функцію . Точні значення коренів =1.31811607652818, =1.738244406014586.

Чисельне розв’язання задачі. Локалізація кореня для чисельного розв’язання задачі

Метод бісекції, зреалізований у пакеті Mathcad, дає

Перший корінь

bisec .

Обравши - задання початкового наближення, користуємось убудованою функцією пакета MATHCAD

.

Значення кореня відрізняється від знайденого за допомогою функції bisec, тому що за замовчуванням величина похибки при роботі вбудованих функцій дорівнює 0.001.

Перевизначимо параметр для задання похибки

.

Значення кореня із заданою точністю 1.3181160717.

Другий корінь

bisec .

Значення кореня із заданою точністю 1.7382444060, число ітерацій 32; - задання початкового наближення; .

Значення кореня у межах заданої точності збігаються.

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

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

,              (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))

3 else

4 min:=abs(f1(b))

5 fi

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

7 max:=abs(f2(a))

8 else

9 max:=abs(f2(b))

10 fi

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

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

13 x:=b

14 else

15 x:=a

16 fi

17 repeat

18 n++

19 if n>1 then

20 x:=xn

21 fi

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

23 until abs(xn-x)<=fault

24 return x

End

Познавательные статьи:



Алгоритмические операторы Matlab

Конструирование и порядок расчёта дорожной одежды

Исследования учёных: почему помогают молитвы?

Почему терпят неудачу многие предприниматели?