МІНІСТЕРСТВО ОСТВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА"
МЕТОДИ УТОЧНЕННЯ КОРЕНІВ
НЕЛІНІЙНИХ РІВНЯНЬ
Інструкція до лабораторної роботи № 1
з курсу: "Комп’ютерні методи дослідження інформаційних процесів та систем"
для студентів спеціальності 6.1601
"Інформаційна безпека"
Затверджено
на засіданні кафедри
«Захист інформації»
Протокол № __ від...
Львів – 2007
Методи уточнення коренів нелінійних рівнянь: Інструкція до лабораторної роботи №1 з курсу "Комп’ютерні методи дослідження інформаційних процесів та систем" для студентів спеціальності 6.1601 "Інформаційна безпека" /Укл.: Л.В. Мороз, З.М. Стрілецький, В.М. Іванюк - Львів: НУ “ЛП”, 2007.- 16 с.
Укладачі: Леонід Васильович Мороз, к.т.н., доц.
Зеновій Михайлович Стрілецький, к.т.н., доц.
Віталій Миколайович Іванюк, асист.
Відповідальний за випуск: І.Я. Тишик, ст.вик.
Рецензенти: В.Б. Дудикевич, д.т.н., проф.,
В.В. Хома, д.т.н., проф.
Мета роботи – ознайомлення з методами уточнення коренів нелінійних рівнянь з одним невідомим.
ВСТУП
Нехай задане рівняння
, (1)
де – неперервна функція, визначена на проміжку і має різні знаки на кінцях цього проміжку, тобто виконується умова
(2)
Крім того, та – неперервні і зберігають знак на проміжку . Необхідно знайти корінь рівняння (1) із заданою граничною абсолютною похибкою Е.
Поширеним методом розв’язку цієї задачі є метод поділу проміжку навпіл, метод хорд, метод Ньютона (дотичних), комбінований метод хорд та дотичних, метод простої ітерації, метод Ейткена–Стефенсона і метод Стефенсона.
МЕТОДИ УТОЧНЕННЯ КОРЕНІВ НЕЛІНІЙНИХ РІВНЯНЬ
Метод поділу проміжку навпіл
Цей метод є простим і надійним алгоритмом знаходження коренів рівняння (1).
Суть методу полягає в тому, що відрізок ділиться навпіл, тобто вибирається перше наближення кореня /рис.1/.
(3)
Якщо , тоді є коренем рівняння (1).

Рис.1.
Якщо , то вибирають той з відрізків чи , на кінцях якого функція має різні знаки. Одержаний відрізок знову ділять навпіл і т.д. Процес обчислень проводиться доти, доки величина відрізку не стане меншою від заданої похибки Е.
Метод досить стійкий до похибок заокруглень. Але й збігається теж повільно. При збільшенні точності значно зростає об’єм обчислень. Тому на практиці метод часто використовують для грубого визначення початкового наближення до кореня, а пізніше застосовують швидко збіжний ітераційний метод.
Алгоритм методу половинного ділення.
Задати значення параметрів а, b та граничної абсолютної похибки Е .
Обчислити значення функцій в точці а, тобто обчислити .
Поділити проміжок навпіл, тобто знайти точку
.
Перевірити умову ? Якщо так, то перейти до п.7.
Якщо добуток , то , в протилежному випадку .
Якщо , то перейти до п.3.
Надрукувати (вивести) значення .
Закінчити виконання програми.
Значення Е задається в межах 10 –4(10 –6.

Метод хорд
Цей метод забезпечує швидшу збіжність, ніж метод поділу проміжку навпіл. Ідея методу полягає в тому, що на достатньо малому проміжку функція змінюється лінійно і тому дуга кривої замінюється хордою, яка її стягує. За наближене значення кореня можна прийняти точку перетину хорди з віссю абсцис (точка А на рис.2)
Рис.2

Рівняння прямої, яка проходить через точки і :

Точка А є наближеним коренем , яка була знайдена з рівняння прямої, якщо покласти , тоді :
(4)
Якщо значення кореня нас не задовольняють, його можна уточнити, застосувавши метод хорд до відрізку .
(5)
Ітераційна формула методу хорд

За наведеними формулами обчислюють корені і тоді, коли ; ; ; , тобто, коли .
У випадку, коли перша і друга похідні мають різні знаки, тобто ,то ітераційна формула має вигляд
(6)
Зауважимо, що формули (5) та (6) тотожні.
Обчислення виконуються доти, доки відмінність між двома послідовно обчисленими значеннями i не будуть меншими за Е
(7)
де Е – задана гранична абсолютна похибка.
Алгоритм методу хорд

Метод Ньютона
Метод послідовних наближень, розроблений Ньютоном, широко використовується при побудові ітераційних алгоритмів. Цей метод відомий своєю швидкою збіжністю (квадратичною збіжністю).
Нехай корінь рівняння відокремлений на відрізку , причому і неперервні і зберігають сталі знаки на всьому відрізку . Геометричний зміст методу Ньютона полягає в тому, що дуга кривої замінюється дотичною до цієї кривої.
Візьмемо деяку точку x0 відрізка [а, b] і проведемо в точці [x0, f(x0)] дотичну до цього графіку.

Рис. 3
Її рівняння має вигляд:
.
Візьмемо за перше наближення кореня точку перетину дотичної з віссю ОХ, одержимо, що
(8)
Наступне наближення знаходимо відповідно за формулою

Ітераційна формула методу Ньютона має вигляд
(9)
Зазначимо, що початкове наближення доцільно вибирати так, щоб виконувалась умова
(10)
В протилежному випадку збіжність методу Ньютона не гарантується.
Найчастіше або , в залежності від того, для якої із цих точок виконується умова (10).
Метод Ньютона ефективний для розв’язування тих рівнянь, для яких значення модуля і похідної біля кореня достатньо велике, тобто графік функції в околі даного кореня має велику крутизну.
Алгоритм методу Ньютона

Комбінований метод хорд та дотичних
Метод хорд та дотичних дають наближення кореня з різних сторін (менше і більше від істинного значення). Тому доцільно використовувати обидва способи одночасно, завдяки чому уточнене значення кореня одержується швидше.
Нехай – початкове наближення кореня за методом хорд, а – за методом дотичних (див.рис.4).
Тоді провівши хорду та дотичну, одержимо відповідні наближення за методом хорд

і за методом дотичних
.
Або в загальному випадку
(11)
(12)

Рис. 4
Якщо припустима абсолютна похибка ? заздалегідь задана, то процес наближення припиняється, доки не буде виявлено, що

Після закінчення процесу за значення кореня х* краще взяти середнє арифметичне одержаних останніх значень

Кращий результат дає наступний порядок обчислень:
Знаходиться наближене значення кореня за методом Ньютона;
Знаходиться наближене значення кореня за методом хорд, використовуючи замість значення , знайдене за методом Ньютона, і процес повторюється до одержання бажаної похибки обчислень.
; .

Рис.5.
Алгоритм комбінованого методу метод хорд та дотичних

Метод простої ітерації
Рис.6.
У цьому методі рівняння заміняється еквівалентним йому рівнянням
(13)
Наприклад, рівняння зводимо до виду .
Виберемо за початкове наближення кореня значення і підставимов праву частину рівняння (1). Одержимо деяке число
(14)
Підставляючи в праву частину рівності (2) замість значення одержимо нове число

Повторюючи процес, будемо мати наступну послідовність
(15)
Якщо ця послідовність збіжна, то границя цієї послідовності – корінь рівняння і може бути обчислений з будь-якою точністю.
Достатня умова збіжності методу простої ітерації формулюється наступним чином: якщо для всіх виконується нерівність
(16)
то на проміжку рівняння має єдиний корінь і процес ітерації збігається до цього кореня незалежно від вибору початкового наближення .
Таким чином при практичному знаходженні кореня за методом ітерації при переході від рівняння до (13) необхідно зобразити так, щоб похідна за абсолютною величиною була якомога менша одиниці.
Для зведення рівняння до вигляду (13) може бути застосований загальний метод, котрий забезпечує виконання нерівності (16).
Нехай , при , де m1 – найменше значення похідної , ;
М1 – найбільше значення похідної на відрізку [a, b],
Якщо похідна – від’ємна, то замість рівняння розглянемо рівняння – .
Замінимо це рівняння еквівалентним йому рівнянням і виберемо сталу ? так, щоб забезпечити виконання умови (16)
.
1)
Розкриваємо нерівність
Візьмемо праву нерівність , з неї випливає, що тобто оскільки
З лівої нерівності випливає, що Отже, значення коефіцієнта ? знаходиться в межах .
Як правило за ? приймають значення де М1 – максимальне значення похідної на проміжку .
Відповідно, ітераційна формула буде мати вигляд

2) Якщо то можна довести, що
(17)
І відповідний ітераційний процес має вигляд
(18)
Алгоритм методу простої ітерації

Метод Ейткена – Стефенсона
Прискорену збіжність при складних рівняннях має метод Ейткена – Стефенсена. Рівняння в цьому випадку зводять до вигляду тоді обчислюється перше наближення для : , потім друге . За ними знаходиться уточнене значення кореня :
(19)
Воно присвоюється , після чого процес повторюється до тих пір, доки не буде досягнута бажана точність . В програмі слід передбачити контроль знаменника на нульове значення, котре може виникати при рівності , , та при закінченні. Якщо така ситуація виникне, слід перейти до видачі на друк.
Алгоритм до методу Ейткена – Стефенсена
Вибирається початкове наближення ;
; ;
Перевіряємо умову Якщо умова справджується , то переходимо на п.6.


Перевірити умову . Якщо так, то повертаємось до п.2.
Виведення на друк .
Метод Стефенсона
Ітераційна формула методу:
(20)
Зберігає квадратичну збіжність методу Ньютона в околі кореня без необхідності обчислення похідної .
Метод Уолла
(21)
Даний метод має кубічну збіжність поблизу кореня, але потребує обчислення похідних і .
Система Maple дозволяє одержати чисельний розв’язок нелінійного рівняння з допомогою команди fsolve:
fsolve (eqn, var, par),
де eqn – рівняння f(х) = 0;
var – змінна;
par – додаткові параметри, котрі встановлюють місцезнаходження, тип і число шуканих розв’язків. При цьому використовується варіант методу Ньютона. Наприклад, для рівняння
х3 – 2х – 1 = 0,
відокремлені корені знаходяться на проміжках [–2; –0.9]; [–0.8;0]; [1; 2]. Наближені значення цих коренів можна одержати з допомогою таких команд:
[ > p:=x^3–2*x–1:
> fsolve(p,x,–2..–0.9);
–1
> fsolve(p,x,–0.8..0);
–.6180339887
> fsolve(p,x,1..2);
1.618033989
> fsolve(p);
–1, –.6180339887, 1.618033989
Аналітичні розв’язки для коренів рівняння в системі Maple одержуються з допомогою команди
solve (eqn, var).
[> p:=x^3–2*x–1:
> s:=solve({p},{x});

Особливо просто відшукування коренів нелінійного рівняння здійснюється у середовищі MatLAB. Покажемо, як це робиться.
Для знаходження коренів використовують процедуру fzero, яка обчислює корінь (нуль) заданої функції. Звичайне звернення до неї є таким
x = fzero(fun,x0)
x = fzero(fun,x0,options)
fun –математичний опис функціональної залежності
x0 – початкове значення або діапазон в якому міститься розв’язок
options – параметри пошуку і відображення результату
TolFun задає значення максимальної припустимої похибки при обчисленні значення шуканого кореня. Параметр iter вказує, що проміжні результати слід виводити на екран дисплея.
Приклад
f = @(x)x.^3-2*x-1;
options = optimset('Display','iter','TolFun',1e-10);
optnew = optimset(options,'TolX',1e-10);
z = fzero(f, [1 2],optnew);
fprintf('z=%6.18f\n',z)
Func-count x f(x) Procedure
2 1 -2 initial
3 1.4 -1.056 interpolation
4 1.73096 0.72442 interpolation
5 1.5963 -0.124959 interpolation
6 1.61611 -0.0112477 interpolation
7 1.61804 3.06799e-005 interpolation
8 1.61803 -4.90138e-008 interpolation
9 1.61803 -2.13163e-013 interpolation
10 1.61803 -2.13163e-013 interpolation
Zero found in the interval [1, 2]
z=1.618033988749858500
ЗАВДАННЯ ДО ЛАБОРАТОРНОЇ РОБОТИ
Знайти корінь рівняння з граничною абсолютною похибкою Е = 10–4, відокремлений на відрізку [a, b]. Методи чисельного розв’язування задаються викладачем.
Варіант
Рівняння
Відрізок

1
ех + х = 0
[-1;0]

2
ех + lnx = 0
[0.1;2]

3
sin x – 1/x = 0
[1;1.5]

4
cos x – 1/(x + 2) = 0
[–1;0]

5
cos x + 1/(x + 2) = 0
[1;2]

6
x3 + x – 3 = 0
[1;2]

7
x3 + x2 – 3 = 0
[1;2]

8
e–х – х = 0
[0;1]

9
cos x + 1/(x – 2) = 0
[0;1]

10
cos x – 1/(x – 2) = 0
[–2;–1]

11
x3 – x2 + 3 = 0
[–2;–1]

12
lnx + x = 0
[0.4;1]

13
x3 + x + 3 = 0
[–2;–1]

14
lgx + x = 0
[0.2;1]

15
x2 – cos x = 0
[–0.8;–0.7]

16
x3 + 3x2 – 3 = 0
[–3;–2.2]

17
x2 – cos x = 0
[0.7;0.8]

18
x3 – 3x – 1 = 0
[–2;–1]

19
cos(x – 1.1) – 3x + 2 = 0
[0.9;1.1]

20
x2 + sin2x – 2 = 0
[–1.5;–1.4]

21
x3 + 6x2 + 9x + 1 = 0
[–1;0]

22
4x2 – cos x – 4= 0
[1;1.2]

23
2x3 + 2x – 1 = 0
[0;1]

24
x3 – 3x2 + 1 = 0
[–1;0]

25
x3 + x2 + 3 = 0
[–2;–1]


2.1. Домашня підготовка до роботи
1. Ознайомитися з основними теоретичними відомостями.
2. Розробити детальну блок-схему алгоритму методу
3.Написати програму, яка забезпечить розв’язок та виведення на екран результатів роботи. Варіанти завдань беруть за вказівкою викладача.
2.2. Робота в лабораторії
1. Ввести в комп'ютер програму згідно з отриманим завданням.
2. Здійснити відладку введеної програми, виправивши виявлені компілятором помилки.
3. Виконати програму. Текст відлагодженої програми та отримані результати оформити у звіт з лабораторної роботи.
3. ЗМIСТ ЗВIТУ
1. Мета роботи.
2. Короткі теоретичні відомості.
3. Повний текст завдання.
4. Блок-схема алгоритму програми.
5. Список ідентифікаторів констант, змінних, процедур і функцій, використаних в програмі, та їх пояснення.
6. Остаточно відлагоджений текст програми згідно з отриманим завданням мовами С, Pascal.
7. Розв’язування нелінійного рівняння в системі Maple (або Matlab).
7. Результати виконання програми.
8. Висновок.
Контрольні запитання
Що таке нелінійне алгебричне рівняння? Що означає відшукати розв'язок нелінійного рівняння?
Опишіть принцип уточнення коренів нелінійних рівнянь методом хорд. Які його переваги і недоліки?
Опишіть принцип уточнення коренів нелінійних рівнянь методом дотичних. Які переваги і недоліки цього методу?
Опишіть принцип уточнення коренів нелінійних рівнянь комбінованим методом. У чому полягають його переваги і недоліки у порівнянні з методом хорд? З методом Ньютона?
Опишіть принцип уточнення коренів нелінійних рівнянь методом простих ітерацій. Які в нього переваги і недоліки у порівнянні з іншими методами?
Як відшукати корінь нелінійного алгебричного рівняння у системі MatLAB?
Який з методів забезпечує кубічну збіжність?
СПИСОК ЛІТЕРАТУРИ
Корн Г., Корн Т. Справочник по математике для инженеров и научных работников. – М.: Наука, 1974. – 830 с.
Маликов В.Т., Кветный Р.Н. Вычислительные методы и применение ЭВМ: Учеб. пособие. – Киев: Выща шк., Головное изд-во, 1989. – 213 с.
Щуп Т. Решение инженерных задач на ЭВМ. – М.: Мир, 1982. – 235 с.
Каханер Д., Моулер К., Нэш С. Численные методы и программное обеспечение. – М.: Мир, 1998. –570 с.
5. Джон Г. Мэтьюз, Куртис Д. Финк Чисельнные методы. Использование Matlab. Издательский дом «Вильямс» Москва – Санкт-Петербург – Киев, 2001.