Метод половинного поділу(інші назви: метод бісекцій, метод дихотомії) для вирішення рівняння f(x) = 0 полягає в наступному. Нехай відомо, що функція безперервна і на кінцях приймає відрізка
[a, b] значення різних знаків, тоді корінь міститься в інтервалі ( a, b). Розділимо інтервал на дві половини і далі розглядатимемо ту половину, на кінцях якої функція набуває значень різних знаків. Цей новий відрізок знову ділимо на дві рівні частини та вибираємо з них ту, що містить корінь. Цей процес триває до того часу, поки довжина чергового відрізка стане менше необхідної величини похибки. Суворіший виклад алгоритму методу половинного поділу:
1) Обчислимо x = (a+ b)/2; обчислимо f(x);
2) Якщо f(x) = 0, то переходимо до пункту 5;
3) Якщо f(x)∙f(a) < 0, то b = xінакше a = x;
4) Якщо | b – a| > ε, переходимо до пункту 1;
5) Виводимо значення x;
Приклад 2.4.Уточнити методом бісекцій з точністю до 0,01 корінь рівняння ( x- 1) 3 = 0, що належить відрізку .
Рішення у програмі Excel:
1) У осередках A 1:F 4 введемо позначення, початкові значення та формули, як показано в таблиці 2.3.
2) Кожну формулу скопіюємо до нижніх осередків маркером заповнення до десятого рядка, тобто. B 4 - до B 10, C 4 - до C 10, D 3 - до D 10, E 4 - до E 10, F 3 - до F 10.
Таблиця 2.3
| A | B | C | D | E | F | |
| f(a)= | =(1-B3)^3 | |||||
| k | a | x | f(x) | b | b-a | |
| 0,95 | =(B3+E3)/2 | =(1-C3)^3 | 1,1 | =E3-B3 | ||
| =ЯКЩО(D3=0;C3; ЯКЩО(C$1*D3<0;B3;C3)) | =ЯКЩО(C$1*D3>0; E3;C3) |
Результати розрахунків наведено у табл. 2.4. У стовпці Fперевіряємо значення довжини інтервалу b – a. Якщо значення менше 0,01, то в даному рядку знайдено наближене значення кореня із заданою похибкою. Потрібно було 5 ітерацій для досягнення необхідної точності. Наближене значення кореня з точністю до 0,01 після округлення до трьох знаків дорівнює 1,0015625 ≈ 1,00.
Таблиця 2.4
| A | B | C | D | E | F | |
| f(a)= | 0,000125 | |||||
| k | a | x | f(x) | b | b-a | |
| 0,95 | 1,025 | -2E-05 | 1,1 | 0,15 | ||
| 0,95 | 0,9875 | 2E-06 | 1,025 | 0,075 | ||
| 0,9875 | 1,00625 | -2E-07 | 1,025 | 0,0375 | ||
| 0,9875 | 0,996875 | 3,1E-08 | 1,00625 | 0,0187 | ||
| 0,996875 | 1,0015625 | -4E-09 | 1,00625 | 0,0094 | ||
| 0,996875 | 0,9992188 | 4,8E-10 | 1,0015625 | 0,0047 | ||
| 0,99921875 | 1,0003906 | -6E-11 | 1,0015625 | 0,0023 | ||
| 0,99921875 | 0,9998047 | 7,5E-12 | 1,000390625 | 0,0012 |
Наведений алгоритм враховує можливий випадок«влучення у корінь», тобто. рівність f(x) нулю на черговому етапі. Якщо в прикладі 2.3 взяти відрізок, то на першому кроці потрапляємо в корінь x= 1. Справді, запишемо в осередку B 3 значення 0,9. Тоді таблиця результатів набуде вигляду 2.5 (наведено лише 2 ітерації).
Таблиця 2.5
| A | B | C | D | E | F | |
| f(a)= | 0,001 | |||||
| k | a | x | f(x) | b | b-a | |
| 0,9 | 1,1 | 0,2 | ||||
Створимо у програмі Excelкористувацькі функції f(x) і bisect(a, b, eps) для вирішення рівняння методом половинного поділу, користуючись вбудованою мовою Visual Basic. Їх описи наведені нижче:
Function f(Byval x)
Function bisect(a, b, eps)
1 x = (a + b) / 2
If f(x) = 0 Then GoTo 5
If f(x) * f(a)< 0 Then
If Abs(a - b) > eps Then GoTo 1
Функція f(x) визначає ліву частинурівняння, а функція
bisect(a, b, eps) обчислює методом половинного поділу корінь рівняння f(x) = 0. Звернемо увагу на те, що функції bisect(a, b, eps) використовується звернення до функції f(x). Наведемо алгоритм створення користувача функції:
1) Виконаємо команду меню «Сервіс – Макрос – Редактор Visual Basic». Відкриється вікно « Microsoft Visual Basic». Якщо в даному файліпрограми Excelще не були створені макроси або функції користувача або процедури, це вікно буде мати вигляд, зображений на рис.2.4.
2) Виконаємо команду меню "Insert - Module" і вводимо тексти програм-функції, як показано на рис 2.5.
Тепер у осередках аркуша програми Excelможна у формулах використовувати створені функції. Наприклад, введемо в осередок D 18 формулу
Bisect(0,95;1;0,00001),
то отримаємо значення 0,999993896.
Щоб вирішити інше рівняння (з іншою лівою частиною) потрібно перейти у вікно редактора за допомогою команди «Сервіс – Макрос – Редактор Visual Basicі просто переписати опис функції f(x). Наприклад, знайдемо з точністю до 0,001 корінь рівняння sin5 x + x 2 - 1 = 0, що належить інтервалу (0,4; 0,5). Для цього змінимо опис функції
на новий опис
f = Sin (5 * x) + x ^ 2 - 1
Тоді в осередку D 18 отримаємо значення 0,441009521 (порівняйте цей результат зі значенням кореня з інтервалу (0,4; 0,5), знайденим у прикладі 2.3!).
Для вирішення рівняння методом половинного поділу у програмі Mathcadстворимо підпрограму-функцію bisec(f, a, b, ε), де:
f -ім'я функції, що відповідає лівій частині рівняння f(x) = 0;
a, b- лівий та правий кінці відрізка [ a, b];
ε – точність наближеного значення кореня.
Рішення прикладу у програмі Mathcad:
1) Запускаємо програму Mathcad.Введемо визначення функції bisec(f, a, b, ε). Для цього за допомогою клавіатури та панелі інструментів «Грецькі символи» набираємо bisec(f, a, b, ε):=. Після знаку присвоювання «:=» на панелі інструментів «Програмування» покажчиком миші клацаємо лівою кнопкою «Add line». Після знаку присвоєння з'явиться вертикальна лінія. Далі вводимо текст програми, наведений нижче, використовуючи панель інструментів «Програмування» для введення знака «←», оператора циклу while, оператора breakта умовного оператора if otherwise.
2) Введемо визначення функції f(x):=sin(5*x)+x^2–1, а потім обчислимо значення кореня за допомогою функції bisecпри заданих значеннях:
bisec(f, -0.8, -0.7, 0.0001) =. Після знака "=" автоматично з'явиться обчислене програмою значення кореня -0,7266601563. Аналогічно обчислимо інше коріння.
Нижче наведено лист Mathcadз визначенням функції bisec(f, a, b, ε) та розрахунками:
Наведемо програму мовою C++ для вирішення рівняння f(x) = 0 методом половинного поділу:
#include
#include
double f(double x);
typedef double (*PF)(double);
double bisec(PF f,double a, double b,double eps);
double a, b, x, eps; PF pf;
cout<< "\n a = "; cin >> a;
cout<< "\n b = "; cin >> b;
cout<< "\n eps = "; cin >> Eps;
x = bisec (pf, a, b, eps); cout<< "\n x = " << x;
cout<< "\n Press any key & Enter "; cin >> a;
double f(double x)(
r = sin (5 * x) + x * x-1;
double bisec(PF f, double a, double b,double eps)(
do(x = (a + b)/2;
if (f(x) == 0) break;
if (f(x)*f(a)<0) b = x;
)while (fabs(b-a) > eps);
У програмі функція f(x) визначено для вирішення рівняння
sin5 x + x 2 – 1 = 0
із прикладу 2.3. Результат роботи програми визначення кореня з інтервалу (0,4; 0,5) з точністю 0,00001 представлений нижче (екран комп'ютера):
Press any key & Enter
Останній рядок потрібний для організації паузи для перегляду результату.
Нелінійні рівняння можна розділити на 2 класи - алгебраїчні та трансцендентні. Алгебраїчними рівнянняминазивають рівняння, що містять лише функції алгебри (цілі, раціональні, ірраціональні). Зокрема, багаточлен є цілою функцією алгебри. Рівняння, що містять інші функції (тригонометричні, показові, логарифмічні та інші) називаються трансцендентними.
Методи розв'язання нелінійних рівнянь поділяються на дві групи:
- точні методи ;
- ітераційні методи .
Точні методи дозволяють записати коріння як деякого кінцевого співвідношення (формули).
Як відомо, багато рівнянь та системи рівнянь не мають аналітичних рішень. Насамперед це стосується більшості трансцендентних рівнянь. Доведено також, що не можна побудувати формулу, за якою можна було б вирішити довільне рівняння алгебри ступеня вище четвертого. Крім того, в деяких випадках рівняння містить коефіцієнти, відомі лише приблизно, і, отже, сама задача точного визначення коренів рівняння втрачає сенс. Для їх вирішення використовуються ітераційні методиіз заданим ступенем точності.
Нехай дано рівняння
- Функція f(x) безперервна на відрізку [ a, b] разом зі своїми похідними 1-го та 2-го порядку.
- Значення f(x) на кінцях відрізка мають різні знаки ( f(a) * f(b) < 0).
- Перша та друга похідні f"(x) та f""(x) зберігають певний знак на всьому відрізку.
Умови 1) та 2) гарантують, що на інтервалі [ a, b] знаходиться хоча б один корінь, а з 3) випливає, що f(x) на даному інтервалі монотонна і тому корінь буде єдиним.
Розв'язати рівняння (1) ітераційним методомозначає встановити, чи має воно коріння, скільки коренів і знайти значення коріння з необхідною точністю.
Будь-яке значення, що звертає функцію f(x) у нуль, тобто. таке, що:
називається корінням рівняння(1) або нулемфункції f(x).
Завдання знаходження кореня рівняння f(x) = 0 ітераційним методом складається з двох етапів:
- відділення коренів - Знаходження наближеного значення кореня або містить його відрізка;
- уточнення наближеного коріння - Доведення їх до заданого ступеня точності.
Процес відокремлення коріння починається із встановлення знаків функції f(x) у граничних x=aі x=bточках сфери її існування.
Приклад 1 . Відокремити коріння рівняння:
|
f( x) є x 3 - 6х + 2 = 0. |
Складемо приблизну схему:
Отже, рівняння (2) має три дійсних кореня, що лежать в інтервалах [-3, -1], і .
Наближені значення коренів ( початкові наближення) можуть бути також відомі з фізичного сенсу задачі, з вирішення аналогічної задачі за інших вихідних даних, або можуть бути знайдені графічним способом.
В інженерній практиці поширений графічний спосібвизначення наближеного коріння.
Зважаючи на те, що дійсне коріння рівняння (1) - це точки перетину графіка функції. f(x) з віссю абсцис, достатньо побудувати графік функції f(x) і відзначити точки перетину f(x) з віссю Ох,або відзначити на осі Охвідрізки, що містять по одному кореню. Побудова графіків часто вдається спростити, замінивши рівняння (1) рівносильнимйому рівнянням:
Рівняння (4) зручно переписати у вигляді рівності:
Звідси ясно, що коріння рівняння (4) може бути знайдено як абсциси точок перетину логарифмічної кривої y= lg xта гіперболи y = . Побудувавши ці криві, приблизно знайдемо єдиний корінь рівняння (4) або визначимо його відрізок .
Ітераційний процес полягає у послідовному уточненні початкового наближення х 0 . Кожен такий крок називається ітерацією. В результаті ітерацій знаходиться послідовність наближених значень кореня х 1 , х 2 , ..., х n.Якщо ці значення зі збільшенням числа ітерацій nнаближаються до справжнього значення кореня, то кажуть, що ітераційний процес сходиться.
Для знаходження кореня рівняння (1), що належить відрізку [ a, b], ділимо цей відрізок навпіл. Якщо f= 0 , то x = є коренем рівняння. Якщо fне дорівнює 0 (що, практично, найбільш ймовірно), то вибираємо ту з половин або , на кінцях якої функція f(x) має протилежні знаки. Новий звужений відрізок [ а 1 , b 1] знову ділимо навпіл і робимо ті самі дії.
Метод половинного поділу практично зручно застосовувати для грубого знаходження кореня даного рівняння, метод простий і надійний завжди сходиться.
Приклад 3. Методом половинного поділу уточнити корінь рівняння
f( x) = x 4 + 2 x 3 - x - 1 = 0
що лежить на відрізку [0, 1].
Послідовно маємо:
f(0) = - 1; f(1) = 1; f(0,5) = 0,06 + 0,25 - 0,5 - 1 = - 1,19;
f(0,75) = 0,32 + 0,84 - 0,75 - 1 = - 0,59;
f(0,875) = 0,59 + 1,34 - 0,88 - 1 = + 0,05;
f(0,8125) = 0,436 + 1,072 - 0,812 - 1 = - 0,304;
f(0,8438) = 0,507 + 1,202 - 0,844 - 1 = - 0,135;
f(0,8594) = 0,546 + 1,270 - 0,859 - 1 = - 0,043 і т.д.
Можна прийняти
x = (0,859 + 0,875) = 0,867
В даному методі процес ітерацій полягає в тому, що як наближення до кореня рівняння (1) приймаються значення х 1 х 2 , ..., х nточок перетину хорди АВз віссю абсцис (Малюнок 3). Спочатку запишемо рівняння хорди AB:
.
Для точки перетину хорди ABз віссю абсцис ( х = х 1 ,y = 0) отримаємо рівняння:
Нехай для певності f""(x) > 0 при а х b(випадок f""(x) < 0 зводиться до нашого, якщо записати рівняння у вигляді - f(x) = 0). Тоді крива у = f(x) буде опукла вниз і, отже, розташована нижче за свою хорду АВ. Можливі два випадки: 1) f(а) > 0 (Малюнок 3, а) і 2) f(b) < 0 (Рисунок 3, б).
Малюнок 3 а, б.
У першому випадку кінець анерухомі та послідовні наближення: x 0 = b;x , де функція f (х) має знак, протилежний знаку її другої похідної f""(х).
Ітераційний процес триває доти, доки не буде виявлено, що
| x i - x i - 1 |< e ,
де e – задана гранична абсолютна похибка.
приклад 4. Знайти позитивний корінь рівняння
f( x) = x 3 - 0,2 x 2 - 0,2 х - 1,2 = 0
з точністю e=0,01.
Насамперед, відокремлюємо корінь. Так як
f(1) = -0,6< 0 и f (2) = 5,6 > 0,
то шуканий корінь x лежить в інтервалі. Отриманий інтервал великий, тому розділимо його навпіл. Так як
f(1,5) = 1,425 > 0, то 1< x < 1,5.
Так як f""(x) = 6 x- 0,4 > 0 при 1< х < 1,5 и f(1,5) > 0, то скористаємося формулою (5) для вирішення поставленого завдання:
= 1,15;
| x 1- x 0 |
= 0,15 > e,
отже, продовжуємо обчислення; х 1) = -0,173;
= 1,190;
f ( 2- x|х
f (х 2) = -0,036;
= 1,198;
| x 3- x 2 | = 0,008 < e .
1 |
= 0,04 > e,
Отже, можна прийняти x = 1,198 з точністю e = 0,01. f(x) Зауважимо, що точний корінь рівняння x = 1,2. a; b], .
Нехай
Отже, можна прийняти x = 1,198 з точністю e = 0,01. f(x)
- Безперервна функція на [ a;
b],
,
Метод Ньютона (метод дотичних) 
- Двічі безперервно диференційована функція на відрізку [ a;
b].
і 
не змінюють знак на [ 
Метод Ньютона (метод дотичних) 
Позначимо через той кінець відрізка, де знакизбігаються. Послідовні наближення до точного кореня
c 
.
знаходимо за формулою 
для
Тоді 
є точним коренем рівняння (1). ε
Обчислювальний процес зазвичай зупиняють, коли
виявляється менше заданої точності
. Однак це умова неспроможна суворо гарантувати, що задана точність досягнуто. Для повної гарантії можна перевірити точність, як було зазначено на початку розділу. Якщо точність не досягнуто, потрібно повторити ітерації ще кілька разів. 
Метод січучих 
Нехай є якесь початкове наближення . Отримаємо ще одну точку за формулою, де 
Метод Ньютона (метод дотичних) 
h 
Метод Ньютона (метод дотичних) 
- Невелика кількість. Вважатимемо, що ми виконали кілька кроків методу, і до цього моменту ми маємо два послідовні наближення.
,
до точного кореня (на початковому етапі – це
). Тоді наступне наближення знаходимо за формулою
Процес зупиняється за таким самим критерієм, як і в методі Ньютона. 
Метод ітерацій 
У методі ітерацій вихідне рівняння (1) перетворюється на рівносильне рівняння 
,
. Вибирається початкове наближення 
. Кожне наступне наближення виходить за формулою 
Процес зупиняється за тим самим критерієм, що й у методі Ньютона. Спосіб буде сходитися, тобто. межа
дорівнює точному значенню кореня, якщо в околиці кореня виконано нерівність
і початкове наближення досить близько до кореня.
Переваги та недоліки методів
,
Метод половинного поділу вимагає відділення кореня, і досягнення високої точності доводиться обчислювати функцію багато разів. Досягнення заданої точності у цьому методі гарантовано. той кінець відрізка, де знакиМетод Ньютона має дуже швидку збіжність (квадратична збіжність), тобто. де- Точне значення кореня;
Для гарантії збіжності методу Ньютона потрібно виконання досить багатьох умов. Взагалі кажучи, почати обчислення за методом Ньютона можна і без цих умов, але тоді збіжність може не спостерігатися.
Метод січучих забезпечує для гладких функцій швидкість збіжності, близьку до швидкості збіжності методу Ньютона. Він вимагає обчислення похідної функції. Якщо початкова точка взята далеко від кореня, то збіжність може бути відсутня.
Метод ітерацій дає швидкість збіжності значно меншу, ніж метод Ньютона. За наявності збіжності діє оцінка 
Нехай є якесь початкове наближення 
- Числа, 
,
;той кінець відрізка, де знаки-Точне значення кореня. Величини де,
qзалежать від функції та не залежать від номера ітерації. Якщо ж 
близький до 1, то qтеж близько до 1 і збіжність методу буде повільною. Рахунок за методом ітерацій можна розпочати без перевірки умов на 
Метод Ньютона (метод дотичних) 
. У цьому випадку процес може бути розбіжним, і тоді відповідь не буде отримано.
Існує багато методів знаходження коріння нелінійного рівняння, відмінних від перерахованих. У MATHCAD функція root у форматі 
використовує метод посічених, і якщо не призводить до бажаних результатів, то – метод Мюллера. В останньому, на відміну від методу січучих, на кожному кроці беруться дві додаткові точки, графік функції замінюється параболою, що проходить через три точки, і за наступне наближення береться точка перетину параболи з віссю Ox. У функції root у форматі root( f(x),
x,
a,
b) використовуються методи Ріддера та Брента. Для знаходження коріння багаточлена в MATHCAD використовується метод Лагерра.
Метод дихотоміїмає назву від давньогрецького слова, що у перекладі означає поділ надвоє. Саме тому ці метод має ще другу назву: метод половинного поділу. Його ми використовуємо досить часто. Допустимо, граючи в гру "Вгадай число", де один гравець загадує число від 1 до 100, а інший намагається його відгадати, керуючись підказками "більше" або "менше". Логічно припустити, що першим числом буде названо 50, а другим якщо воно менше - 25, якщо більше - 75. Таким чином, на кожному етапі (ітерації) невизначеність невідомого зменшується в 2 рази. Тобто. навіть найнещасливіший у світі людина відгадає загадане число в даному діапазоні за 7 припущень замість 100 випадкових тверджень.
Метод половинного поділу у вирішенні рівняння
Правильне рішення рівняння шляхом половинного поділу можливе лише тому випадку, якщо відомо, що у заданому інтервалі є корінь і є єдиним. Це зовсім не означає, що метод дихотомії може використовуватися тільки для вирішення лінійних рівнянь. Для знаходження коренів рівнянь вищого порядку шляхом половинного поділу потрібно спочатку відокремити коріння по відрізкам.< 0.
Процес відділення коренів здійснюється шляхом відшукання першої та другої похідної від функції та прирівнюванні їх нулю f"(x)=0 і f""(x)=0. Далі визначаються знаки f(x) у критичних та граничних точках. Інтервал, де функція змінює знак |a,b|, де f(a)*f(b)
Алгоритм методу дихотомії
Алгоритм методу дихотомії дуже простий. Розглянемо відрізок | a, b | в межах якого є один корінь x 1
На першому етапі обчислюється х 0 =(a+b)/2< 0, то , если наоборот, то ,т.е происходит сужение интервала. Таким образом в результате формируется последовательность x i , где i - номер иттерации.
Далі визначається значення функції у цій точці: якщо f(x 0)
Обчислення припиняються, коли різниця b-a менша за необхідну похибку.
Як приклад використання методу половинного поділу знайдемо корінь на інтервалі рівняння x 3 -3 * x + 1 = 0 з точністю 10 -3< 10 -3
Як очевидно з таблиці коренем є 0,347. Кількість ітерацій дорівнює 10. Умова завершення: a-b = 0,0009Метод половинного поділу або метод дихотомії
є найпростішим на вирішення рівняння у чисельних методах.
Завантажити:
Рішення рівняння методом дихотомії - Рішення рівняння методом половинного поділу в Паскалі.
Його ще називають методом дихотомії. Цей метод розв'язання рівнянь відрізняється від вище розглянутих методів тим, що для нього не потрібно виконання умови, що перша та друга похідна зберігають знак на інтервалі. Метод половинного поділу сходиться для будь-яких безперервних функцій f(x) у тому числі не диференційованих.
Розділимо відрізок навпіл крапкою. Якщо (що практично найімовірніше), то можливі два випадки: або f(x) змінює знак на відрізку (Мал. 3.8), або на відрізку (Мал. 3.9)
Вибираючи в кожному випадку той відрізок, на якому функція змінює знак, і продовжуючи процес половинного поділу далі, можна дійти до будь-якого малого відрізка, що містить корінь рівняння.
Приклад 4. Рівняння 5x-6x-3 = 0 має єдиний корінь на відрізку. Вирішити це рівняння шляхом половинного поділу.Рішення
: Програма мовою Паскаль може бути такою:
функція f(x: real): real;
f:=exp(x*ln(5))-6*x-3;
a, b, e, c, x: real;
while abs(b-a)>e do<0 then
if f(a)*f(c)
writeln ("x=",x:3:3,"f(x)=",f(x):4:4);
e=0.001 x=1.562 f(x)=-0.0047
20. Алгоритм методу половинного поділу.
1.Визначити нове наближення кореня ху середині відрізка [а, b]: х = (а + b) /2.
2. Знайти значення функції у точках аі х: F(a)і F(x).
3.Перевірити умову F(a)*F(x)< 0 . Якщо умова виконана, корінь розташований на відрізку [а, х] bперемістити в крапку х (b=х). Якщо умова не виконана, корінь розташований на відрізку [х, b]. У цьому випадку необхідна точка аперемістити в крапку х (а = х).
4.Перейти до пункту 1 і знову поділити відрізок навпіл. Алгоритм продовжити доти, доки не буде виконано умову /F(x)/< e (Задана точність).
21.Метод простої ітерації для пошуку коренів. Геометрична інтерпретація.
Вихідне рівняння f(x)=0 еквівалентними перетвореннями наводиться до виду з виділенням невідомого у лівій частині, тобто x=φ(x), де φ(x) – деяка функція, пов'язана з вихідною функцією f(x). Така форма запису рівняння дозволяє, задаючись початковим наближенням x 0, отримати наступне, перше наближення x 1 =φ(x 0), далі одержують друге наближення x 2 =φ(x 1) тощо x n +1 =φ(x n)… . Послідовність (x n )= x 0, x 1, x 2, …, x n ,… називається послідовністю ітерацій або наближень з початковим значенням x 0. Якщо функція φ(x) на безперервна і існує межа ξ = lim x n при n→∞, то, переходячи до межі рівності x n +1 =φ(x n), знайдемо, що з n→ ∞: lim x n +1 =lim φ(x n)=φ(lim x n), тобто ξ=φ(ξ). Отже, якщо послідовність наближень сходиться, вона сходиться до кореня рівняння (2), отже й рівняння (1). У силу збіжності ітераційного процесу цей корінь можна обчислити за досить великого nз будь-якою заданою точністю. Однак необхідно визначити за яких умов послідовність (x n) буде схожою. Отримаємо зв'язок між похибками двох сусідніх наближень - ε n і ε n +1: x n = ξ + ε n , x n +1 = ξ + ε n +1. Підставимо ці уявлення в x n +1 =φ(x n) і розкладемо функцію до ряду Тейлора в околиці кореня:ξ+ε n +1 =φ(ξ+ε n)=φ(ξ)+ε n φ'(ξ)+ (ε n 2 /2!)φ''(η), де η Î [ξ; ξ+ε n ] Ì .Оскільки ξ - корінь, то ξ=φ(ξ) , то отримуємо: ε n +1 =ε n φ'(ξ)+(φ''(η)/2)ε n 2 . Оскільки ε<1, то ε n 2 <<ε n . Поэтому если φ’(ξ) ¹ 0,то основной вклад в погрешность дает первое слагаемое, а слагаемым (φ’’(η)/2)ε n 2 можно пренебречь, то есть ε n +1 » ε n φ’(ξ).Это означает, что погрешность будет уменьшаться на каждом последующем шаге, если |φ’(ξ)|<1, тогда для любого n| n +1 |<|ε n |. Сформулируем теорему о сходимости метода простых итераций, дающую достаточные условия сходимости.
Теорема про збіжність методу простих ітерацій.Нехай ξ - корінь рівняння x=φ(x), функція φ(x) визначена і диференційована на відрізку , причому для x всі значення функції φ (x) Î . Тоді, якщо існує таке позитивне число q<1, что при x Î выполняется неравенство |φ’(ξ)|≤q<1, то на отрезке уравнение x=φ(x) имеет единственный корень x=ξ и процесс итераций, выраженный формулой x n +1 =φ(x n), где n=1,2,3… , сходится к этому корню независимо от выбора начального приближения x 0 Î .Таким образом, последовательность {x n },начинающаяся с любого x 0 Î , сходится к корню ξ со скоростью геометрической прогрессии, причем скорость сходимости тем выше, чем меньше величина q Î (1;0).Если функция φ(х) монотонно возрастает и 0<φ’(х)<1, то все приближения лежат по одну сторону от корня - такую сходимость называют монотонной (или ступенчатой) – рис.1. Если функция φ(х) монотонно убывает и 0>φ'(х)>-1, то сусідні наближення лежать по різну сторону від кореня – таку збіжність називають двосторонньою (або спіралеподібною) – рис.2. Оскільки в цьому випадку корінь укладено в інтервалі, кінцями якого є сусідні наближення – ξÎ(x n ,x n +1), виконання умови |x n +1 -x n |<ε обеспечивает выполнение условия |ξ-x n +1 |<ε.
Щоб можна було порівнювати ітераційні методи швидкості збіжності, вводять такі поняття:
Визначення 1:Східність послідовності (x n ) до ξ називається лінійної(відповідно, ітераційний процес - лінійно схожим), якщо є така постійна CÎ(0,1) і такий номер n 0 , що виконуються нерівності |ξ-x n +1 |≤C|ξ-x n | для n≥n 0.
Для введених похибок це означає |ε n+1 |≤C|ε n |. У методі простої ітерації ролі постійної C виступає значення q, тобто метод сходиться лінійно.
Визначення 2:Послідовність наближень (x n ) сходиться до ξ щонайменше з р-им порядком (відповідно, ітераційний процес має щонайменше p-ий порядок), якщо знайдуться такі константи C>0, p≥1 і n 0 , що всім n≥n 0 виконуються умови |ξ-x n +1 |≤C|ξ-x n | р (або інших позначеннях |ε n+1 |≤C|ε n | p).
