Теорія нелінійних рівнянь та метод половинного поділу. Метод дихотомії чи метод половинного поділу
Метод половинного поділу(інші назви: метод бісекцій, метод дихотомії) для вирішення рівняння 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,
отже, продовжуємо обчислення;
f ( х 1) = -0,173;
= 1,190;
|х 2- x 1 | = 0,04 > e,
f (х 2) = -0,036;
= 1,198;
| x 3- x 2 | = 0,008 < e .
Отже, можна прийняти x = 1,198 з точністю e = 0,01.
Зауважимо, що точний корінь рівняння x = 1,2.
Метод дихотоміїмає назву від давньогрецького слова, що у перекладі означає поділ надвоє. Саме тому ці метод має ще другу назву: метод половинного поділу. Його ми використовуємо досить часто. Допустимо, граючи в гру "Вгадай число", де один гравець загадує число від 1 до 100, а інший намагається його відгадати, керуючись підказками "більше" або "менше". Логічно припустити, що першим числом буде названо 50, а другим якщо воно менше - 25, якщо більше - 75. Таким чином, на кожному етапі (ітерації) невизначеність невідомого зменшується в 2 рази. Тобто. навіть найнещасливіший у світі людина відгадає загадане число в даному діапазоні за 7 припущень замість 100 випадкових тверджень.
Метод половинного поділу у вирішенні рівняння
Правильне рішення рівняння шляхом половинного поділу можливе лише тому випадку, якщо відомо, що у заданому інтервалі є корінь і є єдиним. Це зовсім не означає, що метод дихотомії може використовуватися тільки для вирішення лінійних рівнянь. Для знаходження коренів рівнянь вищого порядку шляхом половинного поділу потрібно спочатку відокремити коріння по відрізкам. Процес відділення коренів здійснюється шляхом відшукання першої та другої похідної від функції та прирівнюванні їх нулю f"(x)=0 і f""(x)=0. Далі визначаються знаки f(x) у критичних та граничних точках. Інтервал, де функція змінює знак |a,b|, де f(a)*f(b)< 0.
Алгоритм методу дихотомії
Алгоритм методу дихотомії дуже простий. Розглянемо відрізок | a, b | в межах якого є один корінь x 1
На першому етапі обчислюється х 0 =(a+b)/2
Далі визначається значення функції у цій точці: якщо f(x 0)< 0, то , если наоборот, то ,т.е происходит сужение интервала. Таким образом в результате формируется последовательность x i , где i - номер иттерации.
Обчислення припиняються, коли різниця b-a менша за необхідну похибку.
Як приклад використання методу половинного поділу знайдемо корінь на інтервалі рівняння x 3 -3 * x + 1 = 0 з точністю 10 -3
Як очевидно з таблиці коренем є 0,347. Кількість ітерацій дорівнює 10. Умова завершення: a-b = 0,0009< 10 -3
Метод половинного поділу або метод дихотоміїє найпростішим на вирішення рівняння у чисельних методах.
Завантажити:
Рішення рівняння методом дихотомії - Рішення рівняння методом половинного поділу у Паскалі.
Існує досить очевидна теорема: "Якщо безперервна функція на кінцях деякого інтервалу має значення різних знаків, то всередині цього інтервалу вона має корінь (як мінімум, один, але м.б. і кілька)". За підсумками цієї теореми побудовано чисельне перебування наближеного значення кореня функції. Узагальнено цей метод називається дихотомією, тобто. розподілом відрізка на дві частини. Узагальнений алгоритм виглядає так:
Поки не буде досягнуто потрібної точності.
Варіанти способу дихотомії відрізняються вибором точки поділу. Розглянемо варіанти дихотомії: метод половинного поділуі метод хорд.
Метод половинного поділу
Метод половинного поділувідомий також як метод бісекції. У цьому методі інтервал ділиться рівно навпіл.
Такий підхід забезпечує гарантовану збіжність методу незалежно від складності функції – і це дуже важлива властивість. Недоліком методу те саме - метод будь-коли зійдеться швидше, тобто. збіжність методу завжди дорівнює збіжності у найгіршому випадку.
Метод половинного поділу:
- Один із простих способів пошуку коренів функції одного аргументу.
- Застосовується для знаходження значень дійсно значної функції, що визначається за яким-небудь критерієм (це може бути порівняння на мінімум, максимумчи конкретне число).
Метод половинного поділу як метод пошуку коренів функції
Виклад методу
Перед застосуванням методу пошуку коренів функції необхідно відокремити коріння одним з відомих способів, наприклад, графічним методом. Відділення коренів необхідно, якщо невідомо на якому відрізку потрібно шукати корінь.
Вважатимемо, що корінь функції відокремлений на відрізку . Завдання полягає в тому, щоб знайти та уточнити цей корінь методом половинного поділу. Інакше кажучи, потрібно знайти наближене значення кореня із заданою точністю .
Нехай функція безперервна на відрізку
і - єдиний корінь рівняння.(Ми не розглядаємо випадок, коли коріння на відрізку кілька, тобто більше одного. Як можна взяти й інше досить мале позитивне число, наприклад, .)
Розділимо відрізок навпіл. Отримаємо крапку і два відрізки.
Новий відрізок ділимо навпіл. Отримуємо середину цього відрізка і таке інше.Щоб знайти наближене значення кореня з точністю до 0" alt=" \eps >0">, необходимо остановить процесс половинного деления на таком шаге , на котором и вычислить . Тогда можно взять .!}
Реалізація методу на С++ та числовий приклад
Розв'яжемо рівняння методом половинного поділу. Графічним методомзнаходимо відрізок , якому належить шуканий корінь. Бо, то приймаємо.
Нижче наведено приклад програми на С++, яка вирішує поставлене завдання.
Програма 1. Корінь рівняння
#include
Шуканий корінь. Обчислення проводилися з точністю.
Проміжні обчислення представлені у таблиці нижче.
| n | a n | b n | c n | b n -c n |
|---|---|---|---|---|
| 1 | 0 | 1 | 0.5 | 0.5 |
| 2 | 0.5 | 1 | 0.75 | 0.25 |
| 3 | 0.75 | 1 | 0.875 | 0.125 |
| 4 | 0.875 | 1 | 0.9375 | 0.0625 |
| 5 | 0.875 | 0.9375 | 0.90625 | 0.03125 |
| 6 | 0.875 | 0.90625 | 0.890625 | 0.015625 |
| 7 | 0.875 | 0.890625 | 0.8828125 | 0.0078125 |
Метод половинного поділу як метод оптимізації
Однопараметрична оптимізація (Пошук екстремумів функцій однієї змінної) є самостійним завданням, що часто зустрічається. Крім того, до неї зводиться набагато складніше завдання - пошук екстремуму функції багатьох змінних.
Розглянемо метод половинного поділу як найпростіший однопараметричний метод безумовної оптимізації. Даний метод є методом прямого пошуку. У ньому при пошуку екстремуму цільової функції використовуються лише обчислені значення цільової функції.
Дана функція. Необхідно знайти , що доставляє мінімум (чи максимум) функції інтервалі із заданою точністю , тобто. знайти
.Запишемо словесний алгоритм методу.
Схема алгоритму методу представлена на рис.
- Константа,При виведенні координата точки, в якій функція має мінімум (або максимум), значення функції в цій точці.
Метод хорд
Недолік поділу відрізка суворо походить від того, що він використовує лише знак функції, ігноруючи відхилення (абсолютну величину). Але очевидно, що менше (по абсолютній величині) значення функції, тим ближче ми перебуваємо до кореня. Метод хордпропонує ділити відрізок у точці, що віддаляється від країв відрізка пропорційно до абсолютного значення функції на краях. (Назва "метод хорд" походить від того, що точка поділу є перетином відрізка - хорди - з віссю абцис.)
Виклад методу
Метод заснований на заміні функції на кожному кроці пошуку хордою, перетин якої з віссю дає наближення кореня.
При цьому в процесі пошуку сімейство хорд може будуватися:
В результаті ітераційний процес сходження до кореня реалізується рекурентною формулою:
- для випадку а):
- для випадку б):
Процес пошуку триває доти, доки не виконається умова або .
Метод забезпечує швидку збіжність, якщо %200" alt="f(z)\cdot f""(z) > 0">, т.е. хорды фиксируются в том конце интервала , где знаки функции и ее кривизны совпадают.!}
Схема алгоритму уточнення кореня методом хорд подано на рис. 4.
Комбінація методу хорд та методу половинного поділу
Метод хорд можна застосувати як "останній штрих" після того, як метод половинного поділу гарантує необхідну точність - це не покращить суттєво гарантованої точності, але, швидше за все, на кілька порядків підвищить точність рішення.
Його ще називають методом дихотомії. Цей метод розв'язання рівнянь відрізняється від вище розглянутих методів тим, що для нього не потрібно виконання умови, що перша та друга похідна зберігають знак на інтервалі. Метод половинного поділу сходиться для будь-яких безперервних функцій 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
if f(a)*f(c)<0 then
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).
