Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
МЕТОДИ УТОЧНЕННЯ КОРЕНІВ НЕЛІНІЙНИХ РІВНЯНЬ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Управління інформацією
Кафедра:
Не вказано
Інформація про роботу
Рік:
2011
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Інформаційні технології
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА"
МЕТОДИ УТОЧНЕННЯ КОРЕНІВ
НЕЛІНІЙНИХ РІВНЯНЬ
Методичні вказівки
до лабораторної роботи № 1
з курсу
"Комп’ютерні методи дослідження інформаційних процесів та систем"
для студентів базових напрямів 6.170101 "Безпека інформаційних і комунікаційних систем", 6.170102 "Системи технічного захисту інформації",
6.170103 "Управління інформаційною безпекою"
Затверджено
на засіданні кафедри
«Безпека інформаційних технологій»
Протокол № 12 від 12.05.2011р.
Львів – 2011
Методи уточнення коренів нелінійних рівнянь: Методичні вказівки до лабораторної роботи №1 з курсу "Комп’ютерні методи дослідження інформаційних процесів та систем" для студентів базових напрямів 6.170101 "Безпека інформаційних і комунікаційних систем", 6.170102 "Системи технічного захисту інформації", 6.170103 "Управління інформаційною безпекою" /Укл.: Л.В. Мороз, А.Я. Горпенюк, Н.М. Лужецька - Львів: Видавництво НУ “ЛП”, 2011.- 18 с.
Укладачі: Л.В. Мороз, к.т.н., доц.
А.Я. Горпенюк, к.т.н., доц.
Н.М. Лужецька, асист.
Відповідальний за випуск: В.М. Максимович, д.т.н., проф.
Рецензенти: В.В. Хома, д.т.н., проф.,
А.Е. Лагун, к.т.н., доц.
Мета роботи – ознайомлення з методами уточнення коренів нелінійних рівнянь з одним невідомим.
ВСТУП
Нехай задане рівняння
, (1)
де – неперервна функція. Необхідно знайти всі або деякі корені рівняння (1).
Подібна задача розв’язується за два етапи.
Перший етап. На цьому етапі розв’язується задача відокремлення коренів нелінійного рівняння. Задача полягає у виокремленні достатньо малої області, що належить області допустимих значень функції , у якій існує один і тільки один корінь рівняння (1).
Відокремлення або ізоляція коренів рівняння (1) грунтується на теоремі Больцано-Коші: якщо неперервна функція на кінцях відрізка має різні за знаком значення, тобто , то на цьому відрізку рівняння (1) має хоча б один корінь. Якщо крім цього похідна існує і зберігає знак на відрізку , тобто , або , то корінь єдиний.
Задача ізоляції коренів нелінійного рівняння (1) вирішується шляхом табулювання функції або графічно - шляхом побудови графіку функції і визначення за графіком відрізків, на яких локалізовано корені рівняння (1). Графік функції як правило будують приблизно із застосуванням методів математичного аналізу.
Результати першого етапу є вихідними даними для задачі уточнення коренів нелінійного рівняння.
Другий етап. Уточнення наближеного розв’язку до заданої точності.
Вихідними даними для задачі уточнення кореня є рівняння (1) і відрізок . Відомо, що функція має різні знаки на кінцях цього проміжку, тобто виконується умова
(2)
Крім того, та – неперервні і зберігають знак на проміжку . Необхідно знайти корінь рівняння (1) із заданою граничною абсолютною похибкою Е.
Поширеними методами розв’язку цієї задачі є метод поділу проміжку навпіл, метод хорд, метод Ньютона (дотичних), комбінований метод хорд та дотичних, метод простої ітерації, метод Ейткена–Стефенсона і метод Стефенсона.
МЕТОДИ УТОЧНЕННЯ КОРЕНІВ НЕЛІНІЙНИХ РІВНЯНЬ
Метод поділу проміжку навпіл
Цей метод відомий також за назвами методу бісекцій або методу дихотомії. Це простий і надійний алгоритм уточнення коренів рівняння (1).
Суть методу полягає в тому, що відрізок ділиться навпіл, тобто вибирається перше наближення кореня (Рис.1):
(3)
Якщо , тоді є коренем рівняння (1).
Рис.1.
Якщо , то вибирають той з відрізків чи , на кінцях якого функція має різні знаки. Обраний відрізок знову ділять навпіл і т.д. Процес обчислень проводиться доти, доки величина відрізку не стане меншою від заданої похибки Е.
Метод досить стійкий до похибок заокруглень. Але й збігається теж повільно. При збільшенні точності значно зростає об’єм обчислень. Тому на практиці метод часто використовують для грубого визначення початкового наближення кореня, а далі застосовують швидко збіжний ітераційний метод.
Метод бісекцій збігається для будь-яких неперервних функцій. Кількість ітерацій, необхідних для досягнення точності E, оцінюють співвідношенням:
Алгоритм методу половинного ділення.
Задати значення параметрів а, b та граничної абсолютної похибки Е .
Обчислити значення функцій в точці а, тобто обчислити .
Поділити проміжок навпіл, тобто знайти точку : .
Перевірити умову ? Якщо так, то перейти до п.7.
Якщо добуток , то , в протилежному випадку .
Якщо , то перейти до п.3.
Надрукувати (вивести) значення .
Закінчити виконання програми.
Значення Е задається в межах 10 –4(10 –6.
Метод хорд
Метод забезпечує швидшу збіжність, ніж метод поділу навпіл. Ідея методу в тому, що на проміжку дугу кривої заміняють хордою, яка її стягує. За наближене значення кореня приймають точку перетину хорди з віссю абсцис (точка А на Рис.2)
Рис.2
Рівняння прямої, яка проходить через точки і :
Точка А є наближеним коренем , яка була знайдена з рівняння прямої, якщо покласти , :
Далі застосовуємо метод хорд до відрізку :
Таким чином, ітераційна формула методу хорд має вигляд:
(4)
За наведеними формулами обчислюють корені також і тоді, коли ; ; ; . Тобто коли - застосовують (4).
У випадку, коли перша і друга похідні мають різні знаки, тобто , ітераційна формула має інший вигляд:
(5)
Метод хорд – це метод одностороннього наближення. Один край відрізку фіксується, а інший змінюється. Зауважимо, що формули (4) та (5) тотожні. Узагальнити їх можна так. Якщо виконується співвідношення (6):
, (6)
фіксується точка а: . В іншому випадку фіксується точка b: . При цьому ітераційна формула методу хорд має вигляд:
, (7)
де початкове значення - край відрізка , протилежний до обраного
Обчислення виконуються доти, доки різниця між черговими i не стане меншою за задану граничну абсолютну похибку Е:
Алгоритм методу хорд
Метод Ньютона
Метод послідовних наближень, розроблений Ньютоном, широко використовується при побудові ітераційних алгоритмів. Цей метод відомий своєю швидкою збіжністю (квадратичною збіжністю).
Нехай корінь рівняння відокремлений на відрізку , причому і неперервні і зберігають сталі знаки на всьому відрізку . Геометричний зміст методу Ньютона полягає в тому, що дуга кривої замінюється дотичною до цієї кривої.
Візьмемо деяку точку x0 відрізка [а, b] і проведемо в точці [x0, f(x0)] дотичну до цього графіку (в прикладі обрано x0=b).
Рис. 3
Її рівняння має вигляд:
.
Візьмемо за перше наближення кореня точку перетину дотичної з віссю ОХ (y=0; x=x1 ), одержимо:
(8)
Наступне наближення знаходимо відповідно за формулою
Узагальнена ітераційна формула методу Ньютона має вигляд
(9)
Зазначимо, що початкове наближення доцільно вибирати так, щоб виконувалась умова
(10)
В протилежному випадку збіжність методу Ньютона не гарантується.
Найчастіше або , в залежності від того, для якої із цих точок виконується умова (10).
Метод Ньютона ефективний для розв’язування тих рівнянь, для яких значення модуля похідної біля кореня достатньо велике, тобто графік функції в околі даного кореня має велику крутизну.
Метод Ньютона, як і метод хорд є методом одностороннього наближення. Причому якщо в методі хорд наближення відбувається справа, то в методі Ньютона – зліва, і навпаки.
Алгоритм методу Ньютона
Комбінований метод хорд та дотичних
Метод хорд та дотичних дають наближення кореня з різних сторін (менше і більше від істинного значення). Тому доцільно використати обидва способи одночасно, завдяки чому уточнене значення кореня одержується швидше.
Нехай – початкове наближення кореня за методом хорд, а – за методом дотичних (див.рис.4).
Тоді провівши хорду та дотичну, одержимо відповідні наближення за методом хорд
і за методом дотичних
.
Або в загальному випадку
(11)
(12)
Рис. 4
Якщо припустима абсолютна похибка E заздалегідь задана, то процес наближення припиняється, доки не буде виявлено, що
Після закінчення процесу за значення кореня х* краще взяти середнє арифметичне одержаних останніх значень
Кращий результат дає наступний порядок обчислень:
Знаходиться наближене значення кореня за методом Ньютона. При цьому початкове наближення має бути обране так, щоб виконувалась умова (10). Отже якщо в точці x=b умова (10) не виконується, на етапі введення початкових даних в поданому нижче прикладі алгоритму необхідно ввести ;
Знаходиться наближене значення кореня за методом хорд, використовуючи замість значення , знайдене за методом Ньютона, і процес повторюється до одержання бажаної похибки обчислень.
; .
Алгоритм комбінованого методу хорд та дотичних
Метод простої ітерації
У цьому методі рівняння заміняється еквівалентним йому рівнянням
(13)
Наприклад, рівняння зводимо до виду .
Виберемо за початкове наближення кореня значення і підставимо в праву частину рівняння (13). Одержимо перше наближення розв’язку - число x1:
(14)
Підставляючи в праву частину рівності (14) замість значення одержимо нове наближення:
Повторюючи процес, отримаємо ітераційну формулу методу:
(15)
Якщо ця послідовність збіжна, то границя цієї послідовності – корінь рівняння і може бути обчислений з будь-якою точністю.
Достатня умова збіжності методу простої ітерації формулюється наступним чином: якщо для всіх виконується нерівність
(16)
то на проміжку рівняння має єдиний корінь і процес ітерації збігається до цього кореня незалежно від вибору початкового наближення .
Таким чином при практичному знаходженні кореня за методом ітерації при зведенні рівняння до виду (13) необхідно зобразити так, щоб похідна за абсолютним значенням була якомога менша одиниці.
Для зведення рівняння до вигляду (13) може бути застосований загальний метод, котрий забезпечує виконання нерівності (16).
Нехай , при , де m1 – найменше значення похідної , ;
М1 – найбільше значення похідної на відрізку [a, b],
Зауваження. Якщо похідна – від’ємна, то замість рівняння розглядаємо рівняння .
Замінимо рівняння еквівалентним йому рівнянням і виберемо сталу λ так, щоб забезпечити виконання умови (16). Тобто забезпечимо:
при
Розкриваємо нерівність:
Візьмемо праву нерівність: . З неї випливає, що тобто оскільки
З лівої нерівності випливає, що Отже, значення коефіцієнта λ знаходиться в межах .
Як правило за λ приймають значення де М1 – максимальне значення похідної на проміжку .
Відповідно, ітераційна формула буде мати вигляд
Якщо то можна довести, що
(17)
І відповідний ітераційний процес має вигляд
(18)
Алгоритм методу простої ітерації
Метод Ейткена – Стефенсона
Прискорену збіжність при складних рівняннях має метод Ейткена – Стефенсена. Рівняння в цьому випадку зводять до вигляду . Обчислюється перше наближення для : , потім друге . За ними знаходиться уточнене значення кореня :
(19)
Воно присвоюється , після чого процес повторюється до тих пір, доки не буде досягнута бажана точність . В програмі слід передбачити контроль знаменника на нульове значення, котре може виникати при рівності та наприкінці ітераційного процесу. Якщо така ситуація виникне, слід перейти до видачі на друк.
Алгоритм до методу Ейткена – Стефенсена
Вибирається початкове наближення ;
; ;
Перевіряємо умову Якщо умова справджується , то переходимо до п.7.
Перевірити умову . Якщо так, то повертаємось до п.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. Остаточно відлагоджений текст програми згідно з отриманим завданням.
7. Розв’язування нелінійного рівняння в системі Maple (або Matlab).
7. Результати виконання програми.
8. Висновок.
Контрольні запитання
Що таке нелінійне алгебраїчне рівняння? Що означає відшукати розв'язок нелінійного рівняння?
Опишіть принцип уточнення коренів нелінійних рівнянь методом хорд. Які його переваги і недоліки?
Опишіть принцип уточнення коренів нелінійних рівнянь методом дотичних. Які переваги і недоліки цього методу?
Опишіть принцип уточнення коренів нелінійних рівнянь комбінованим методом. У чому полягають його переваги і недоліки у порівнянні з методом хорд? З методом Ньютона?
Опишіть принцип уточнення коренів нелінійних рівнянь методом простих ітерацій. Які в нього переваги і недоліки у порівнянні з іншими методами?
Як відшукати корінь нелінійного алгебричного рівняння у системі MatLAB?
Який з методів забезпечує кубічну збіжність?
СПИСОК ЛІТЕРАТУРИ
Корн Г., Корн Т. Справочник по математике для инженеров и научных работников. – М.: Наука, 1974. – 830 с.
Маликов В.Т., Кветный Р.Н. Вычислительные методы и применение ЭВМ: Учеб. пособие. – Киев: Выща шк., Головное изд-во, 1989. – 213 с.
Щуп Т. Решение инженерных задач на ЭВМ. – М.: Мир, 1982. – 235 с.
Каханер Д., Моулер К., Нэш С. Численные методы и программное обеспечение. – М.: Мир, 1998. –570 с.
Джон Г. Мэтьюз, Куртис Д. Финк Чисельнные методы. Использование Matlab. Издательский дом «Вильямс» Москва – Санкт-Петербург – Киев, 2001.
НАВЧАЛЬНЕ ВИДАННЯ
МЕТОДИ УТОЧНЕННЯ КОРЕНІВ
НЕЛІНІЙНИХ РІВНЯНЬ
Методичні вказівки
до лабораторної роботи № 1
з курсу
"Комп’ютерні методи дослідження інформаційних процесів та систем"
для студентів базових напрямів 6.170101 "Безпека інформаційних і комунікаційних систем", 6.170102 "Системи технічного захисту інформації",
6.170103 "Управління інформаційною безпекою"
Укладачі: Мороз Леонід Васильович
Горпенюк Андрій Ярославович
Лужецька Наталія Миколаївна
Редактор
Комп’ютерне верстання
22.01.2013 23:01-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора