Чисельні методи уточнення коренів
нелінійних рівнянь та систем.
Нехай дане рівняння
f (x) = 0 (1)
де f (x) – алгебраїчна або трансцендентна функції з одним невідомим.
Сукупність значень змінної х, при яких рівняння перетворюється в тотожність називається розв’язком. Кожне значення х* з цієї сукупності називається коренем рівняння або нулем функції.
Як відомо, прості лінійні або квадратні рівняння можна легко розв’язати з допомогою відповідних формул. Алгебраїчні рівняння 3-ї та 4-ї степені також можна розв’язати аналітичними методами, хоча й відповідні формули дуже складні. Навіть вже в цих випадках чисельні методи мають незаперечні переваги. Не мають розв’язку в елементарних функціях рівняння типу
х6 + 4х5 – 5х4 + х3 + 3х2 – 9х +11 = 0.
Практичне використання чисельних методів розв’язування нелінійних рівнянь можна продемонструвати на такому прикладі.
Рівняння термопари описується, як правило, поліномом високих порядків.
Наприклад, для термопари Ni – Cr/Ni
t? = 25,4498U – 0,559195U 2 + 0,10452439 U 3 – 8,776153?10– 3 U 4 +3,76041•10 EMBED Equation.3 EMBED Equation.3 U EMBED Equation.3 – 8,64943?10– 6 U 6 + 1,021005?10– 7 U 7 – 4,891009?10– 10 U 8
де U – термо е.р.с., mV;
t? – температура ?C.
Якщо ставиться задача – знайти значення термо е.р.с. при даній t? , то відповідь можна одержати розв’язавши рівняння
А (U ) – t? = 0.
Надалі будемо вважати, що рівняння (1) має лише ізольовані корені, тобто для кожного кореня існує проміжок, який не містить інших коренів рівняння.
Наближене обчислення ізольованих дійсних коренів рівняння (1) складається з двох етапів:
відокремлення коренів – знаходження проміжку, що належить області існування функцій f (x), на якому розміщений один і тільки один корінь.
уточнення наближених коренів, тобто обчислення їх із заданою похибкою. Є два методи відокремлення:
1. Графічний метод – а) будується графік у = f (x). Точки перетину графіка з віссю Ох дають значення кореня , і за графіком легко визначити два числа a i b, між котрими знаходиться один корінь (рис1.)
EMBED Equation.3 EMBED Equation.3 EMBED Equation.3
EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
Рис.1 Рис.2
б) Всі члени рівняння розбивають на дві групи, одну з них записують в лівій частині рівняння, а другу – в правій , тобто EMBED Equation.3 . Після цього будують графік EMBED Equation.3 і EMBED Equation.3 . Абсциси точок перетину графіків цих двох функцій і є коренями даного рівняння. (х0 – корінь рівняння, рис.2).
EMBED Equation.3 Приклад. Відокремлення коренів рівняння х3 – 3х – 1 = 0.
у у
EMBED Equation.3
EMBED Equation.3
1
х
1
Рис.4
2. Аналітичний – базується на теоремі Больцано – Коші:
якщо на проміжку [a;b] функція неперервна і набуває на кінцях проміжку значень різних знаків, тобто f(a) ? f(b) < 0, то на [a;b] рівняння f (x) = 0 має хоча б один корінь. Цей корінь буде єдиним, якщо перша похідна f /(x) існує і зберігає сталий знак у середині проміжку [a;b] .
1) похідна міняє знак f(a) ? f(b) < 0, але існує 4-и корені, тобто ця умова гарантує існування розв’язку рівняння, але не дозволяє визначити число коренів.
y
x
a b
2) Крім цього важливе значення має вимога неперервності. Існує точка розриву, тому твердження теореми про наявність хоча б одного кореня – невірне.
y
a b x
Процес відокремлення коренів починається із встановлення знаків f (x) в граничних точках х = а і х = b в області її існування. Після цього визначаються знаки функції f (x) в ряді проміжних точок х = а1, а2, ... , вибір яких враховує особливості функції f (x). Якщо виявиться, що f (аk) > 0, f (ak+1) < 0, то через розглянуту вище теорему в інтервалі [аk, ak+1] існує корінь рівняння f (x) = 0. Потрібно переконатися, чи є цей корінь єдиним.
Необхідно пам’ятати, що алгебраїчне рівняння n-ї степені
а0хn + а1хn–1 +…+ а0 = 0
має не більше n дійсних коренів. Тому, якщо для такого рівняння ми одержимо (n + 1) зміну знаків, то всі корені його відокремленні.
Приклад. Відокремити корені рівняння
f (x) = х3 – 6х + 2 = 0.
Складаємо приблизну схему
Отже, рівняння має три дійсних корені, які лежать в інтервалах (–3, –1), (0, 1), (1, 3).
Розглянемо поняття стійкості методу. Нехай за значенням вхідної величини х шукається значення вихідної величини y. Якщо х має абсолютну похибку ?х, то розв’язок має похибку ?у. Метод називається стійким за вхідним параметром х, якщо малі похибки у вхідному параметрі х викликають малі похибки і в розв’язку у. Відсутність стійкості (нестійкий метод) означає, що навіть незначні похибки у вхідних даних ведуть до значних похибок в розв’язку, або до зовсім неправильного результату.
Ітераційні (або наближені) методи – це методи послідовних наближень. В них необхідно задати деякий наближений розв’язок – так зване початкове наближення. Після цього з допомогою деякого алгоритму проводиться один цикл обчислень, котрий називається ітерацією. В результаті ітерації знаходять нове наближення. Ітерації проводять до тих пір, доки не одержать розв’язок із заданою похибкою. Об’єм обчислень при цьому наперед не відомий.
При використанні ітераційних методів виникає проблема збіжності чисельного методу. Вона (збіжність) означає близькість одержаного після проведення ітерації розв’язку до істинного розв’язку. Збіжність ітераційного процесу: якщо в результаті проведення ітерацій одержуємо деяку послідовність х1, х2, … , хn (не важливо, це скалярні чи векторні величини), та якщо ця послідовність збігається до точного розв’язку х = а, тобто існує границя цієї послідовності EMBED Equation.3 , то метод є збіжним.
Метод поділу проміжку навпіл (половинного ділення).
Алгоритм методу половинного ділення.
Ввести, задати значення параметрів а, b та граничної абсолютної похибки ? .
Обчислити значення функції f (x) в точці а, тобто обчислити f (а).
Поділити проміжок [а, b] навпіл, тобто знайти точку xs
xs = (a + b)/2.
Перевірити умову f (xs) = 0? Якщо так, то перейти до п.7.
Якщо добуток f (а)? f (x*)>0?, то a: = xs, в протилежному випадку b: = xs.
Якщо |b - a| > ? , то перейти до п.3.
Надрукувати (вивести) значення xs.
Закінчити виконання програми.
Значення ? задається в межах 10 –4?10 –6.
Початок
Ввід а, b, ?
Обчислення F(a)
b = xs xs = (a + b)/2
ні
F(а)? ?F (x*)>0?
так ні F(x) = 0 ?
a= x*s
так | b - a|>? ?
Вивід xs
Кінець
Метод, як правило використовується для грубого знаходження кореня рівняння. При підвищенні точності (тобто при зменшенні ? ) значно зростає об’єм обчислювальної роботи.
Число ітерацій значне (при |b - a| > ? EMBED Equation.3 ), тому збіжність його повільна.
Однак збіжність ця гарантована завжди (надійний метод). Крім того, простота реалізації методу зменшує число допоміжних операцій і частково компенсує затрати машинного часу через повільну збіжність.
Приклад. Методом половинного ділення уточнити корені рівняння
х4 + 2х3 – х – 1 = 0, які лежать на відрізку [0,5;1]
f(0,5) = – 1,19 f(1) = 1 f(0,8594) = – 0,043
f(0,75) = –0,59 f(0,875) = 0,05
f(0,8125) = – 0,304 f(0,8438) = – 0,135
Метод хорд (метод помилкового положення,
метод пропорційних частин)
Рівняння прямої, яка прохо-дить через точки M’[a,f(a)] і M[b,f(b)]: EMBED Equation.3 Цей метод забезпечує швидку збіжність, ніж метод половинного ділення. Ідея методу полягає в тому, що на достатньо малому проміжку [a,b] функція f(x) змінюється лінійно і тому дуга кривої f(x) замінюється хордою, яка її стягує. За наближене значення кореня можна прийняти точку перетину хорди з віссю абсцис (точка А на рис.)
EMBED Equation.3 EMBED Equation.3 y
M’
A = x1 a
b x2 x
M
Абсциса точки А, є наближеним коренем х1, яка була знайдена з рівняння прямої, якщо покласти у = 0, тоді х = х1
EMBED Equation.3 (2)
Якщо значеня кореня х1 нас не задовольняють, його можна уточнити, застосувавши метод хорд до відрізку [х1,b].
EMBED Equation.3 (3)
Ітераційна формула EMBED Equation.3 (4)
За наведеними формулами обчислюють корені і тоді, коли f(a) > 0; f(b) < 0; f’(x) < 0; f’’(x) < 0, тобто, коли f’(x) ·f’’(x) > 0.
y
b
x1 x2 x
a
У випадку, коли перша і друга похідні мають різні знаки, тобто f’(x) ·f’’(x) < 0,то ітераційна формула має вигляд
EMBED Equation.3 (5)
EMBED Equation.3 EMBED Equation.3 y y
b a
x2 x1 x2 x1 x x
a b
EMBED Equation.3 EMBED Equation.3
Відмітимо, що формули (5) і (4) тотожні.
Метод хорд має лінійну збіжність – похибка на наступній ітерації пропорційна (лінійно) похибці на попередній ітерації.
Приклад. Знайти додатній корінь рівняння х3 – 2х2 +3х –5 = 0.
Визначаємо знаки функцій в різних точках
Зміна знаку проходить на відрізку [1,8; 1,9].
Обчислюємо значення функцій f(1,8) = – 0,248; f(1,9) = 0,339.
Виходячи з того, що f’(x) = 3х2 – 4х + 3 > 0; f’’(x) = 6х – 4 > 0знаходимо наближенні значення за формулою (2)
EMBED Equation.3
Отже, це корінь рівняння розташований в інтервалі [1,842; 1,9]. Застосовуємо до цього інтервалу метод хорд
EMBED Equation.3
Обчислення значень функцій дають
f(1,843683) = – 2,978·10 –4 f(1,8437) < 0
f(1,8438) > 0 f(1,8438) > 0.
Обчислення виконуються доти, доки відмінність між двома послідовно обчисленими значеннями xn + 1 i xn не будуть меншими за ?
EMBED Equation.3 .
так D > EPS Початок
Ввід A, B, EPS
Оскільки в процесі об-числення це значення не змінюється
ні
Вивід X Обчислення R = F(B)
Кінець EMBED Equation.3
D = |X –A| A = X
Метод Ньютона (Ньютона – Рафсона, метод дотичних)
Метод послідовних наближень розробив Ньютон, він дуже широко використовується при побудові ітераційних алгоритмів. Цей метод відомий своєю швидкою збіжністю (квадратичною збіжністю).
Нехай корінь рівняння f(x) = 0 відокремлений на відрізку [а, b], причому f’(x) і f’’ (x) неперервні і зберігають сталі знаки на всьому відрізку [а, b]. Геометричний зміст методу Ньютона полягає в тому, що дуга кривої у = f(x) замінюється дотичною до цієї кривої.
Візьмемо деяку точку x0 відрізка [а, b] і проведемо в точці [x0, f(x0)] дотичну до цього графіку.
EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 EMBED Equation.3
Її рівняння має вигляд EMBED Equation.3 беремо за перше наближення кореня абсцису точки перетину дотичної з віссю ОХ, одержимо, що EMBED Equation.3 y
a
x2 x1 x0 b x
EMBED Equation.3 EMBED Equation.3
(1)
Наступне наближення знаходимо відповідно за формулою
EMBED Equation.3
...................................
EMBED Equation.3
(2)
Відмітимо, що початкове наближення х0 доцільно вибирати так, щоб
f(x0) ·f’’(x0) > 0. (3)
В протилежному випадку збіжність методу Ньютона не гарантується.
Частіше всього x0 = а і x0 = b, в залежності від того, для якої із цих точок виконується умова (3).
Метод Ньютона ефективний для розв’язування тих рівнянь, для яких значення модуля і похідної | f’(x)| біля кореня достатньо велике , тобто графік функції f(x) в околі даного кореня має велику крутизну.
Блок-схема алгоритму методу Ньютона:
Вибір початкового значення xn
Обчислення xn +1 і f(xn +1)
Чи достатньо мале значення f(xn +1) ?
так Кінець
ні
xn = xn +1
Приклад. х3 – 2х2 + 3х – 5 = 0;
f’(x) = 3х2 – 4х + 3 > 0; f’’ (x) = 6х – 4 > 0;
відрізок [1,8; 1,9] тотожний в прикладі для методу хорд. При х0 = b = 1,9 f(x0) ·f’’(x0) > 0. Тому дотичну проводимо в точці х0 = b. З формули (1) випливає, що
EMBED Equation.3
На відрізку [1,8; 1,846] знову застосовують метод Ньютона
EMBED Equation.3
Основні труднощі в методі Ньютона полягають у виборі початкового наближення х0, такого, що знаходилось би всередині інтервалу шуканого нуля х*.
Якщо графік у = f(x) має такий вигляд (див. мал.), то взятий інтервал (а, b) дає можливість знайти шуканий корінь.
Якщо ж х0 взято зовні інтервалу (а, b), то послідовні ітерації все більше віддаляються від х* і нуль не буде знайдений (поведінка алго-ритму може бути досить дивною). Внаслідок цього методу Ньютона
a b
x*
часто передує який-небудь глобально-залежний алгоритм типу половинного ділення, перш ніж перейти на швидкозбіжні Ньютонові ітерації. Таким чином, метод Ньютона часто являється лишень завершальною процедурою більш повільного, однак гарантованого початкового алгоритму. При такому комбінуванні, для прикладу, останні 25 або щось біля цього ітерацій бісекції можуть бути замінені шістьма Ньютоновими кроками.
Модифікований метод Ньютона
Зауважимо, що кожна ітерація методу Ньютона вимагає обчислення не тільки f(x), але й f’(x). Є функції для яких обчислення f’(x) після того, як знайдено f(x), дуже просте. Для інших функцій вартість обчислень f’(x) еквівалентна другому обчисленню f(x). На кінець, для третіх функцій обчислення f’(x) майже неможливе. Геометричне трактування методу Ньютона дозволяє модифікувати його – тобто замість дотичних в точках (xn , f(xn )) проводити січні, які паралельні першій дотичній, проведеній в точці х0 (див.рис.). Наступна січна, що проведена в точці xn перетинає вісь ОХ в точці:
EMBED Equation.3 .
y = f(x) Така послідовність теж збігається до кореня, однак повільніше, ніж при побудові серії дотичних. Однак є перевага – нема необхідності щоразу заново обчи- y
x
x* х1 х2 x0
слювати похідну і виконувати ділення. Цю модифікацію методу Ньютона іноді називають методом паралельних січних.
Слід відмітити, що даний метод ефективний, якщо значення f(x) мало змінюється на відрізку [а, b].
Метод січних
Якщо знаходження f’(x) коштує дорогого, або неможливе, метод січних є кращим вибором, ніж метод Ньютона.
В цьому алгоритмі починають з двома початковими числами хn та хn–1. Абсциси n, n-1 вибирають по одну сторону від кореня. На наступне уточнення хn+1 одержують з хn та хn–1 як єдиний нуль лінійної функції, що приймає значення f(хn) в хn та f(хn–1) в хn–1. Ця лінійна функція являє собою січну до кривої f(x), що проходить через її точки з абсцисами хn та хn–1 – звідси назва методу січних.
xn–1, f(xn–1) EMBED Equation.3 Легко довести, що EMBED Equation.3 y
f(x)
xn, fn
xn+1, 0 x
EMBED Equation.3
де fn = f(xn). Праву частину краще не зводити до спільного знаменника.
Оскільки крок методу січних вимагає лишень одного обчислення функції, цей метод можна оцінити як більш швидкий в порівнянні з методом Ньютона.
Схема алгоритму для цього методу така ж, як і для методу Ньютона (дещо інший вигляд має ітераційна формула).
Слід мати на увазі, що поблизу кореня х* значення f(хn) та f(хn–1) малі і близькі, при діленні на їх різницю в методі виникає втрата значущих цифр, тому краще проводити обчислення за такою формулою:
EMBED Equation.3
Комбінований метод хорд та дотичних
Метод хорд та дотичних дають наближення кореня з різних сторін (менше і більше від істинного значення). Тому доцільно використовувати обидва способи одночасно, завдяки чому уточнене значення кореня одержується швидше. Можливі чотири випадки поведінки функції на відрізку [а, b] в залежності від знаків похідної. В комбінованому методі краще застосувати метод Ньютона і метод хорд з врахуванням обчислень Ньютона.
EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 y y
EMBED Equation.3
x a EMBED Equation.3 a x1 b x b x
EMBED Equation.3
EMBED Equation.3
y y
EMBED Equation.3
EMBED Equation.3 x x
a x1 b a x1 b
Розглянемо перший випадок f’(x) > 0 f’’(x) > 0 при a ? x ? b.
Одержуємо EMBED Equation.3 ; EMBED Equation.3
За методом хорд – EMBED Equation.3 (1)
За методом Ньютона – EMBED Equation.3 (1’)
Або в загальному випадку
EMBED Equation.3 (2)
EMBED Equation.3 . (2’)
Дійсне значення кореня х* EMBED Equation.3 .
Якщо припустима абсолютна похибка ? заздалегідь задана, то процес наближення припиняється, доки не буде виявлено, що
EMBED Equation.3 (3)
Після закінчення процесу за значення кореня х* краще взяти середнє арифметичне одержаних останніх значень
EMBED Equation.3 (4)
Аналогічні формули можна привести для інших трьох випадків поведінки функції на відрізку [а, b].
Приклад. Обчислити з точністю до 0,0005 корінь рівняння х5 – х – 0,2 = 0, який знаходиться на відрізку [1; 1,1].
EMBED Equation.3 EMBED Equation.3
В заданому проміжку EMBED Equation.3 EMBED Equation.3
Одержуємо х0 = 1; х0 = 1,1;
EMBED Equation.3
Тоді EMBED Equation.3
EMBED Equation.3 .
EMBED Equation.3 точність недостатня, знаходимо наступну пару наближень.
EMBED Equation.3
EMBED Equation.3 – необхідна степінь точності.
EMBED Equation.3
Кращий результат дає наступний порядок обчислень:
Знаходиться наближене значення кореня за методом Ньютона;
EMBED Equation.3 Знаходиться наближене значення кореня за методом хорд, використовуючи замість EMBED Equation.3 значення EMBED Equation.3 , знайдене за методом Ньютона, і процес повторюється до одержання бажаної похибки обчислень.
y
II I
EMBED Equation.3 x0 x1 x
Метод простої ітерації
Для застосування цього методу рівняння f(x) = 0 представляється у вигляді
EMBED Equation.3 (1)
Виберемо за початкове наближення кореня значення EMBED Equation.3 і підставимо в праву частину рівняння (1). Одержимо деяке число
EMBED Equation.3 (2)
Підставляючи в праву частину рівності (2) замість х0 значення х1 одержимо нове число EMBED Equation.3
Повторний процес буде мати наступну послідовність
EMBED Equation.3 .
Якщо ця послідовнясть збіжна, то границя цієї послідовності EMBED Equation.3 – корінь рівняння f(x) = 0 і може бути обчислений з будь-якою точністю.
Абсциси точок А1А2; В1В2… – преставляють собою відповідно послідовне наближення кореня х*. Геометрично метод ітерації можна пояснити наступним чином. Побудуємо на площині хоу графіки функцій у = х і EMBED Equation.3 . Відштовхуючись від деякої точки EMBED Equation.3 будуємо ламану лінію А0В1А1В2… («сходинки») , вершини яких обов’язково паралельні осі х і у , вершини А0А1А2 лежать на кривій EMBED Equation.3 , а вершини В1В2…– на прямій у = х.
y
y = x
B1 A0 y = ?(x)
?(x1) ?(x0) B2 A1
?(x2) A2
x
x* x2 x1 x0
Теорема. Про збіжність методу ітерації.
Якщо для всіх EMBED Equation.3 виконується нерівність
EMBED Equation.3 (3)
то на проміжку [a, b] рівняння EMBED Equation.3 має єдиний корінь і процес ітерації EMBED Equation.3 збігається до цього кореня незалежно від вибору початкового наближення EMBED Equation.3 .
Приклад. Методом ітерації знайти додатній корінь рівняння
х3 – 5х + 1 = 0
на відрізку [0; 0,5], ще два корені на відрізку [–3; –2], [2, 3].
Корінь знаходиться на відрізку [0; 0,5].
Дане рівняння зведемо до вигляду
EMBED Equation.3
процес ітерацій збіжний.
Візьмемо за перше наближення х0 = 0,25 – середину відрізка [0; 0,5]. Обчислення будемо вести за формулою
EMBED Equation.3
При знаходженні двох інших коренів методом ітерацій вже не можна скористатись формулою EMBED Equation.3 , оскільки
EMBED Equation.3
В цьому випадку рівняння потрібно представити у вигляді, наприклад, EMBED Equation.3 Тоді на відрізках [–3; –2], [2, 3] умова EMBED Equation.3 буде виконуватись.
Таким чином при практичному знаходженні кореня за методом ітерації при переході від рівняння f(x) = 0 до (1) необхідно зобразити EMBED Equation.3 так, щоб похідна EMBED Equation.3 за абсолютною величиною була якомога менша одиниці.
Для зведення рівняння f(x) = 0 до вигляду (1) може бути застосований загальний метод, котрий забезпечує виконання нерівності (3).
Нехай EMBED Equation.3 (4)
при EMBED Equation.3 , де m1 – найменше значення похідної EMBED Equation.3 , EMBED Equation.3 ;
М1 – найбільше значення похідної на відрізку [a, b], EMBED Equation.3
Якщо похідна EMBED Equation.3 – від’ємна, то замість рівняння f(x) = 0 розглянемо рівняння – f(x) = 0.
Замінимо це рівняння f(x) = 0 еквівалентним йому рівнянням EMBED Equation.3 і виберемо сталу ? так, щоб забезпечити виконання умови (3)
EMBED Equation.3 .
1) EMBED Equation.3
Розкриваємо нерівність EMBED Equation.3
Візьмемо праву нерівність EMBED Equation.3 , з неї випливає, що EMBED Equation.3 тобто EMBED Equation.3 оскільки EMBED Equation.3
З лівої нерівності EMBED Equation.3 випливає, що EMBED Equation.3
Отже, значення коефіцієнта ? знаходиться в межах EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 < EMBED Equation.3 <0 EMBED Equation.3 як правило за ? приймають значення EMBED Equation.3 де М1 – максимальне значення похідної EMBED Equation.3 на проміжку [a, b].
Відповідно, ітераційна формула буде мати вигляд
EMBED Equation.3
2) Якщо EMBED Equation.3 то можна довести, що
EMBED Equation.3 . (5)
І відповідний ітераційний процес має вигляд
EMBED Equation.3 (6)
Приклад. Рівняння EMBED Equation.3 звести до вигляду, що допускає використання методу ітерацій. Корінь відокремлений на відрізку [1; 2].
EMBED Equation.3 .
Тоді EMBED Equation.3 , виберемо ? так, щоб EMBED Equation.3 для EMBED Equation.3
EMBED Equation.3 .
Звідси EMBED Equation.3
EMBED Equation.3
Оскільки EMBED Equation.3 .
То на [1; 2] EMBED Equation.3
Значення ? можна визначити і таким способом.
Оскільки f’(x) > 0, [1; 2], то
EMBED Equation.3
Знайдемо, що EMBED Equation.3 .
Звідси EMBED Equation.3
EMBED Equation.3 (7)
Блок-схема методу простої ітерації
Початок
Ввід хn, ?
xn+1 = ?(xn)
або EMBED Equation.3
? = xn+1 – xn xn: = xn+1
? < ?
ні
так
Вивід х
Кінець
Метод Ейткена – Стефенсона
Прискорену збіжність при складних рівняннях f(x) = 0 має метод Ейткена – Стефенсена. Рівняння в цьому випадку зводять до вигляду EMBED Equation.3 тоді обчислюється перше наближення для хn = x0: x1 = ?(x0), потім друге x2 = ?(x1). За ними знаходиться уточнене значення кореня [див. Корн Г., Корн Т. Справочник по математике, 1984]:
EMBED Equation.3 (9)
Воно присвоюється EMBED Equation.3 , після чого процес повторюється до тих пір, доки не буде досягнута бажана (потрібна) точність EMBED Equation.3 . В програмі слід передбачити контроль знаменника на нульове значення, котре може виникати при рівності х0, х1 та х2 в кінці ітерацій. Якщо така ситуація виникне, слід перейти до видачі х0 на друк.
Алгоритм до методу Ейткена – Стефенсена
Вибирається початкове наближення х0;
x1 = ?(x0); x2 = ?(x1);
Перевіряєм умову EMBED Equation.3 Якщо умова справджується , то переходимо на п.6.
EMBED Equation.3
EMBED Equation.3
Перевірити умову EMBED Equation.3 . Якщо так, то повертаємось до п.2.
6. Вивід на друк х0.
Метод випадкових спроб
Як було відмічено раніше, гарантовану збіжність має метод половинного ділення. Крім нього, такою ж властивістю володіє метод випадкових спроб. В ньому наближення х0, х1, х2, ..., хn задають випадкові значення в інтервалі (a, b), щоразу звужуючи цей інтервал. Наприклад, якщо значення EMBED Equation.3 і EMBED Equation.3 то а присвоюється значення хn, якщо EMBED Equation.3 то b присвоюється значення хn і т.д. до тих пір, доки EMBED Equation.3 .
Метод Стефенсена
Ітераційна формула : EMBED Equation.3 .
Зберігає квадратичну збіжність метода Ньютона в околі кореня без необхідності обчислення похідної EMBED Equation.3 .
Метод Уолла
EMBED Equation.3 .
Цей метод має кубічну збіжність поблизу кореня, але потребує обчислення похідних EMBED Equation.3 і EMBED Equation.3 .
Практичні рекомендації
Методу Стефенсена віддається перше місце.
EMBED Equation.3
Має прискорену (квадратичну) збіжність, просто реалізується (не потрібно обчислювати похідних, проводити вибір за спеціальними умовами нульового наближення). Допускається вибір нульового наближення по обидві сторони від кореня.
2. Метод хорд – теж один з універсальних методів, хоча поступається першому методу за збіжністю (лінійна збіжність). Решта переваг ті ж, що і першому методі. В методі хорд, який реалізується за ітераційною формулою
EMBED Equation.3 (1)
(або ж за формулою EMBED Equation.3 ) можлива реалізація методу січних:
y
a x2 x1 x0 b x
Тобто, якщо х0 вибирається таким, що EMBED Equation.3 то реалізується звичайний метод хорд, якщо ж EMBED Equation.3 то реалізується метод січних. Таким чином, якщо відомий проміжок [a, b] , на якому відокремлений один єдиний корінь, то за формулою (1) можна знайти уточнене значення кореня незалежно від вибору початкового наближення EMBED Equation.3 .
3. Якщо використовувати на практиці метод простих ітерацій, то краще вже взяти метод Ейткена – Стефенсена – тоді відпадає необхідність зводити рівняння f(x) = 0 до вигляду, що допускає використання методу простих ітерацій ( EMBED Equation.3 ). Досить будь-яким чином звести рівняння до вигляду x = ?(x).
4. Метод половинного ділення – надійний метод. Завжди дає результат (хоча збіжність повільна, однак загалом швидша, ніж в методі випадкових спроб).
