Реферат на тему:
Розв’язування нелінійних рівнянь
1. Метод ділення проміжку навпіл (метод дихотомії)
Нехай і відомо, що рівняння (1) має єдиний корінь . Покладемо a0=a, b0=b, x0=(a0+b0)/2. Якщо , то . Якщо , то покладемо
(2)
(3)
(4)
і обчислимо . Якщо , то ітераційний процес зупинимо і будемо вважати, що . Якщо , то повторюємо розрахунки за формулами (2)-(4).
З формул (2), (3) видно, що і . Тому , а отже шуканий корінь знаходиться на проміжку . При цьому має місце оцінка збіжності
. (5)
Звідси випливає, що кількість ітерацій. які необхідно провести для знаходження наближеного кореня рівняння (1) з заданою точністю задовольняє співвідношенню
. (6)
де [c] ціла частина числа c.
Серед переваг даного методу слід відзначити простоту реалізації та надійність. Послідовність {xn} збігається до кореня для довільних неперервних функцій f(x). До недоліків можна віднести невисоку швидкість збіжності методу та неможливість безпосереднього узагальнення систем нелінійних рівнянь.
2. Метод простої ітерації
Метод простої ітерації застосовується до розв’язування нелінійного рівняння виду
. (7)
Перейти від рівняння (1) до рівняння(7) можна багатьма способами, наприклад, вибравши
, (8)
де довільна знакостала неперервна функція.
Вибравши нульове наближення x0, наступні наближення знаходяться за формулою
. (9)
Наведемо достатні умови збіжності методу простої ітерації.
Теорема 1. Нехай для вибраного початкового наближення x0 на проміжку
(10)
функція (x) задовольняє умові Ліпшиця
(11)
де 0<q<1, і виконується нерівність
. (12)
Тоді рівняння (7) має на проміжку S єдиний корінь , до якого збігається послідовність (9), причому швидкість збіжності визначається нерівністю
. (13)
Зауваження: якщо функція (x) має на проміжку S неперервну похідну , яка задовольняє умові
, (14)
то функція (x) буде задовольняти умові (11) теореми 1.
З (13) можна отримати оцінку кількості ітерацій. які потрібно провести для знаходження розв’язку задачі (7) з наперед заданою точністю :
. (15)
Наведемо ще одну оцінку. що характеризує збіжність методу простої ітерації:
. (16)
3. Метод релаксації
Для збіжності ітераційного процесу (9) суттєве значення має вибір функції (x). Зокрема, якщо в (8) вибрати , то отримаємо метод релаксації.
, (17)
який збігається при
. (18)
Якщо в деякому околі кореня виконуються умови
, (19)
то метод релаксації збігаються при . Збіжність буде найкращою при
. (20)
При такому виборі для похибки буде мати місце оцінка
, (21)
де .
Кількість ітерацій, які потрібно провести для знаходження розв’язку з точністю визначається нерівністю
. (22)
Зауваження: якщо виконується умова , то ітераційний метод (17) потрібно записати у вигляді
.
4. Метод Ньютона
Метод Ньютона застосовується до розв’язування задачі (1), де f(x) є неперервно-диференційованою функцією. На початку обчислень вибирається початкове наближення x0. Наступні наближення обчислюються за формулою
. (23)
З геометричної точки зору xn+1 є значенням абсциси точки перетину дотичної до кривої y=f(x) в точці (xn, f(xn)) з віссю абсцис. Тому метод Ньютона називають також методом дотичних.
Теорема 2. Якщо не змінює знака на [a,b], то виходячи з початкового наближення , що задовольняє умові , можна обчислити методом Ньютона єдиний корінь рівняння (1) з будь-якою степінню точності.
Теорема 3. Нехай простий дійсний корінь рівняння (1) і , де ,
, (24)
причому
. (25)
Тоді для метод Ньютона збігається, причому для похибки справедлива оцінка
. (26)
З оцінки (26) видно, що метод Ньютона має квадратичну збіжність, тобто похибка на (n+1)-й ітерації пропорційна квадрату похибки на n-й ітерації.
Модифікований метод Ньютона
(27)
дозволяє не обчислювати похідну на кожній ітерації, а отже і позбутися можливого ділення на нуль. Однак цей алгоритм має тільки лінійну збіжність.
Кількість ітерацій, які потрібно провести для знаходження розв’язку задачі (1) з точністю задовольняє нерівності
. (28)
Приклад 1. Розв’язати рівняння
(29)
методом ділення проміжку навпіл з точністю =104.
Розв’язання. Спочатку знайдемо проміжок, де рівняння має єдиний корінь. Оскільки похідна функції не змінює знак, то корінь у рівнянні (29) буде один. Легко бачити, що f(0)=1<0, а . Отже корінь належить проміжку . Виберемо . Згідно з формулою (6), отримаємо, що для знаходження кореня з точністю 104 необхідно провести 13 інтеграцій. Відповідні значення xn наведені в табл. 1.
Табл.
n | xn | f(xn)
0 | 0785398E+00 | 0492505E+00
1 | 0392699E+00 | 0224617E+00
2 | 0589049E+00 | 0144619E+00
3 | 0490874E+00 | 0377294E-01
4 | 0539961E+00 | 0540639E-01
5 | 0515418E+00 | 0831580E-02
6 | 0503146E+00 | 0146705E-01
7 | 0509282E+00 | 0316819E-02
8 | 0512350E+00 | 0257611E-02
9 | 0510816E+00 | 0295467E-03
10 | 0511583E+00 | 0114046E-02
11 | 0511199E+00 | 0422535E-03
12 | 0511007E+00 | 0635430E-04
13 | 0510911E+00 | 0116016E-03
Приклад 2. Знайти додатні корені рівняння
x3x1=0 (30)
методом простої ітерації з точністю =104.
Розв’язання. Графічне дослідження рівняння (30) показує, що існує єдиний дійсний додатній корінь цього рівняння і він належить проміжку [1,2]. Оскільки на цьому проміжку , то рівняння (30) можна подати у вигляді
. (31)
Позначимо . Перевіримо виконання умов теореми про збіжність методу простої ітерації. Виберемо x0=1,5, тоді =0,5. Розглянемо
,
тобто .
тоді ,
а отже умова (12) виконується. З формули (15) маємо, що кількість ітерацій, які необхідно провести для знаходження кореня з точністю =104 повинна задовольняти умові . Відповідні значення xn та xn(xn) наведені в табл.2.
Табл.2
n | xn | xn(xn)
0 | 0150000E+01 | 0209006E+00
1 | 0129099E+01 | 0411454E-01
2 | 0133214E+01 | 0901020E-02
3 | 0132313E+01 | 0193024E-02
4 | 0132506E+01 | 0415444E-03
5 | 0132464E+01 | 0892878E-04
6 | 0132473E+01 | 0191927E-04
7 | 0132471E+01 | 0417233E-05
8 | 0132472E+01 | 0953674E-06
Виходячи з нерівності (16) і отриманих результатів видно, що для досягнення заданої