Розділ ЧИСЕЛЬНІ МЕТОДИ РОЗВ’ЯЗАННЯ НЕЛІНІЙНИХ РІВНЯНЬ
|
|
Скачати 131.53 Kb.
|
|
Комп’ютерні системи та мережі Розділ 1. ЧИСЕЛЬНІ МЕТОДИ РОЗВ’ЯЗАННЯ НЕЛІНІЙНИХ РІВНЯНЬ 1.1. Постановка задачі Нехай потрібно розв’язати нелінійне рівняння  , (1)де функція  визначена і неперервна на деякому проміжку  . Якщо функція  — алгебраїчний многочлен, то рівняння (1) називається алгебраїчним. Якщо функція містить тригонометричні, показникові або логарифмічні функції, тоді рівняння (1) називають трансцендентним.Розв’язати рівняння означає знайти множину його коренів, тобто таких значень  , при яких рівняння (1) перетвориться в тотожність. Корінь рівняння (1) ще називається нулем функції .Знайти точні значення коренів заданого рівняння можна лише для найпростіших функцій : алгебраїчних многочленів не вище четвертого степеня, деяких многочленів степеня  і деяких трансцендентних функцій.Універсальних методів для знаходження точних значень коренів алгебраїчних рівнянь степеня і трансцендентних рівнянь не існує. Тому розв’язання нелінійних рівнянь виконується переважно чисельними методами, які базуються на ітераційності розв’язку і локальності апроксимації.Нехай  – точний корінь, а  – його наближене значення. Кажуть, що корінь обчислено з наперед заданою точністю  , якщо  . Нехай, наприклад,  і  , тоді числа  і  — наближені значення кореня  відповідно з недостачею і надлишком з точністю . У цьому випадку за наближене значення з точністю можна взяти будь-яке число з відрізка  .У загальному випадку процедура розв’язання нелінійних рівнянь складається з двох етапів:
Перший етап називають ще задачею визначення відрізків ізоляції коренів, а другий – уточненням наближених коренів. Перший етап, як правило, складніший за другий, оскільки для загального випадку немає досить ефективних методів відокремлення коренів. Для знаходження коренів з наперед заданою точністю застосовують методи, які дають можливість уточнювати знайдені наближення коренів. Такі методи називаються ітераційними. 1.2. Відокремлення коренів Перший етап (відокремлення коренів) здійснюється, як правило, графічно. Для цього будується графік функції  . Точки перетину графіка з віссю ОХ і є коренями рівняння. Часто рівняння (1) записують у вигляді  і будують графіки функцій  і  потім знаходять межі, в яких містяться абсциси точок перетину графіків функцій  і  .Інколи для відокремлення коренів можна скористатись табличним методом. Він полягає в знаходженні послідовності значень функції з певним кроком і виявлені зміни знака в значення членів послідовності. Для цього, за допомогою дискретної змінної, будують вектор із значень функції, який дає можливість побачити зміни знака функції, що свідчить про наявність коренів. Приклад 1. Відокремити корені рівняння  користуючись двома варіантами графічного та табличного методів.Лістинг двох варіантів графічного метод відокремлення коренів, реалізований в пакеті Mathcad, наведено на рис. 1, табличного методу на (рис. 2).   Рис. 2 Рис. 1 Другий етап починається з вибору початкової точки  (початкового наближення кореня) і обчислюється нев’язка  . Якщо  або достатньо близьке до нуля, то корінь знайдено. В іншому випадку, за певним алгоритмом, формується послідовність наближень  з використанням інформації про знак нев’язки, про значення самої нев’язки тощо.Вибір початкового значення є важливим етапом, який істотно впливає на ефективність процедури розв’язання і навіть на можливість одержання розв’язку.1.2. Метод поділу відрізку навпіл Метод поділу відрізку навпіл (дихотомії) передбачає послідовне обчислення значень функції в ряді точок. Перед використанням методу необхідно визначити відрізок, який містить лише один корінь рівняння. Для пошуку такого відрізку можна скористатись графічним способом. Нехай потрібно знайти корінь рівняння (1), який знаходиться на відрізку  . У випадку єдиного кореня на вказаному відрізку буде виконуватись умова . (2)Далі відрізок починають зменшувати, визначаючи на кожному кроці алгоритму координати його нових граничних точок  і  за значеннями  ,  та координати середини відрізка  : .У залежності від знаку функції в точці новий відрізок  знаходження кореня встановлюється за допомогою наступного правила: (3)де  ;  – середня точка відрізку  (рис.3). Блок-схема алгоритму поділу відрізка навпіл наведено на рис. 4 Рис. 3  Рис. 4 Довжина відрізка ізоляції кореня після виконання  кроків зменшується до величини ,а значення кореня , обумовлено координатою середньої точки, і його похибки задаються виразами: . (4)Із формули (4) випливає, що збіжність процесу обчислень дуже повільна, оскільки точність в одному десятковому розряді досягається за 3-4 кроки через те, що  . Разом з тим, цей метод має абсолютну збіжність, тому ніяких вимог до вигляду і властивостей функції не висувається.Приклад 2. Користуючись методом поділу відрізка навпіл обчислити корені рівняння  із заданою точністю та підрахунком числа ітерацій.Лістинг обчислення кореня рівняння, який знаходиться на відрізку  методом поділу відрізка навпіл, реалізованого в пакеті Mathcad, наведено на рис. 5. Рис. 5. Таким чином: при  значення кореня  , число ітерацій  ; при  значення кореня  , число ітерацій  ;1.3. Метод простої ітерації Метод простої ітерації полягає в тому, що рівняння (1) записують у канонічному вигляді:  , (5)а ітерації здійснюються за правилом  ,  (6)де початкове наближення задається з відрізка , який містить корінь рівняння.Якщо процес обчислень збігається до розв’язу рівняння (5), тобто  , то припустивши, що функція  визначена, неперервна і диференційована на відрізку, який містить шуканий корінь, можна встановити умову збіжності ітераційного процесу (зв’язок між похибками обчислень на двох сусідніх ітераціях): ,  . (7)Із рівності (7) випливає достатня умова збіжності методу простої ітерації, а саме,  буде менше  за умови . (8)Якщо покласти  , то достатня умова збіжності методу простої ітерації має вигляд  . Чим менше значення  , тим швидше збігається ітераційний процес.У випадку, коли в околі кореня похідна  задовольняє умову  похибки  і  будуть мати однакові знаки і збіжність  до буде монотонною (рис.6, а). Якщо ж виконується умова –  , похибки і матимуть різні знаки і наближення буде збігатися до , коливаючись біля (рис.6, б).У випадку, коли  , похибка за абсолютним значенням буде більшою за , і наближення буде знаходитись далі від розв’язку ніж , тобто процес буде розбіжний (рис.6, в, г). Рис. 6. Можливі варіанти збіжності ітерацій: а) – монотонна збіжність; б) – коливальна збіжність; в) – монотонна розбіжність; г) – коливальна розбіжність. Зауважимо, що коли  , то збіжність ітерацій замість лінійної, обумовленої виразом (7), стає нелінійною, зокрема квадратичною. Це має місце в методі Ньютона, який розглянемо пізніше.Оцінювання глобальної похибки  зручно виконувати на основі значень локальної похибки, тобто за значеннями наближень, отриманих на сусдніх ітераціях за аналогією з формулою (7). Для цього формулу (7) запишемо у вигляді: ,або  .Звідки отримуємо оцінку  , (9)де  .Якщо обчислення починати від початкового значення , то для поточної похибки на -й ітерації згідно з формулами (7) і (9) можна одержати оцінку . (10)Приклад 3. Користуючись методом ітерацій уточнити корінь рівняння  , який знаходиться на відрізку  .Лістинг відокремлення кореня та обчислення його методом ітерацій, реалізованого в пакеті Mathcad, наведено на рис. 7.  Рис. 7 Якщо покласти  ,  , то оцінку (10) можна записати у вигляді ,  (11)Якщо похибка обчислення кореня рівняння не повинна перевищувати наперед заданого значення , то згідно з формулою (11) можна знайти необхідну кількість ітерацій   (12)У тих випадках, коли не вдається явно розв’язати вихідне рівняння відносно невідомої  , так щоб у рівнянні (5) функція задовольняла умову збіжності (8), ітерації можна виконувати за правилом:  (13)Тут допоміжна функція  не повинна змінювати свій знак на відрізку, де шукають корінь. Зокрема, якщо  , одержимо метод релаксації: (14)для якого  і умова збіжності має вигляд , (15)Якщо в деякому околі кореня виконуються умови  ,  ,то метод релаксації збігається в разі  . Оптимальне значення параметра в такому випадку має вигляд . (16)Приклад 4. Користуючись модифікованим методом ітерацій уточнити корінь рівняння  , який знаходиться на відрізку  .Лістинг відокремлення кореня та обчислення його методом ітерацій, реалізованого в пакеті Mathcad, наведено на рис. 8.  Рис. 8. 1.4. Метод Ньютона Для прискорення збіжності ітераційного процесу методу простої ітерації (6) функцію можна вибрати у вигляді .У цьому випадку чергове наближення буде знаходитись за формулою , (17)Формулу (17) можна отримати з рівняння дотичної до графіка функції в точці  , де – -е наближення до кореня рівняння (рис.9). Рис. 9. Як відомо, рівняння дотичної має вигляд  ,де  – довільна точка на дотичній. Поклавши в рівнянні дотичної  (точка перетину дотичної з віссю ОХ) дістанемо формулу (17).Достатні умови збіжності методу Ньютона дає така теорема. Теорема. Нехай на відрізку  функція має неперервні із сталими знаками похідні  ,  і  . Тоді існує такий окіл  кореня  рівняння  , що для будь-якого  послідовність  , обчислена за формулою (17), збігається до кореня .Доведення. Для доведення збіжності послідовність до кореня досить показати, що похідна  задовольняє умов  для будь-якого  , і взяття  з околу  кореня .Для похідної маємо вираз .Оскільки  неперервна і відмінна від нуля на , то існують такі додатні  і  , що  і  для будь-якого значення  .Тоді  .З неперервності функції випливає, що існує окіл кореня , на якому функція задовольняє нерівність  , внаслідок чого,  для будь-якого  . А це і є достатня умова збіжності ітераційного процесу. Теорему доведено.Припустивши, що в околі кореня і неважко одержати оцінку швидкості збіжності обчислень за формулою (17). Для чого в околі кореня рівняння розкладемо функцію в ряд Тейлора з урахуванням третього члена, що визначає нелінійність апроксимації: ,  . (18)Врахувавши, що  рівність (18) можна перетворити до вигляду (з врахуванням (17)): .Оскільки  і  , то з умови, що  , одержуємо квадратичну залежність похибки на послідовних ітераціях: , де  . (19)Таким чином метод Ньютона має квадратичну збіжність  ,  , (20)де  .Приклад 5. Користуючись методом Ньютона для простих коренів уточнити корінь рівняння  , який знаходиться на відрізку  .Лістинг відокремлення кореня та обчислення його методом Ньютона, реалізованого в пакеті Mathcad, наведено на рис. 10.  Рис. 10. 1.5. Метод Ньютона для кратних коренів Швидкість збіжності методу Ньютона падає, якщо рівняння має кратні корені. Разом з тим квадратичну збіжність можна зберегти, якщо побудувати дещо іншу ітераційну формулу, яка базується на наступному відомому факті.Якщо функція має деякий корінь кратності  , то її похідна  має цей самий корінь кратності  .У більшості випадків кратність коренів невідома, тому для збереження квадратичної збіжності на базі заданого рівняння з кратним коренем розглядають рівняння , (21)яке має корінь кратності одиниця, незалежно від його кратності у вихідному рівнянні .Як відомо, для рівняння  ітераційний процес має вигляд , Оскільки  , то  .Враховуючи одержану рівність дістанемо формулу методу Ньютона для кратних коренів, яка має вигляд  , (22)Приклад 6. Користуючись методом Ньютона для кратних коренів уточнити корінь рівняння , який знаходиться на відрізку  . Неважко переконатись, що це є корінь  , який має кратність два.Лістинг відокремлення кореня та обчислення його методом Ньютона, реалізованого в пакеті Mathcad, наведено на рис. 11.  Рис. 11. 1.6. Застосування методу Ньютона для знаходження екстремальних точок функції Задачу обчислення значень аргументу функції  , за яких функція досягає своїх екстремальних значень (максимального чи мінімального), можна звести до задачі розв’язання нелінійних рівнянь, оскільки в даних точках похідна від функції дорівнює нулю, тобто  . При цьому ітераційна формула набуває вигляду: , (23)Приклад 7. Користуючись методом Ньютона знайти координати екстремальної точки функції  , яка знаходяться на відрізках  .Лістинг обчислення координати екстремальної точки та значення екстремуму, реалізованого в пакеті Mathcad, наведено на рис. 12. На цьому ж лістингу наведено результат, одержаний за допомогою вбудованої процедури root.  Рис. 12. 1.7. Метод хорд Нехай потрібно розв’язати рівняння (1), яке має єдиний корінь на інтервалі  , для якого виконується умова  (рис. 13). Для побудови ітераційної формули методу хорд запишемо рівняння прямої (хорди), яка проходить через дві точки  і  : Поклавши в одержаному рівнянні  ,  дістанемо формулу для обчислення наближень за методом хорд вигляду: , (24)де  – нерухома точка.  Рис. 14 Рис. 13 Можна показати, що за нерухому точку береться той із кінців відрізка , для якого виконується умова  . Інший кінець інтервалу приймається за початкове наближення  . Ітераційний процес закінчується в разі виконання умови , де  , тому що існує оцінка  . Блок-схема алгоритму показана на рис. 14.1.8. Комбінований метод О  Рис. 15 скільки в методах хорд і дотичних наближення кореня обчислюється відповідно з недостачею і з надлишком (залежно від вигляду кривої), то був розроблений метод, який об’єднав обидва підходи (рис.15). Процес закінчується, коли  .Кінцеве наближення обчислюється за формулою  ,де  і  – наближення кореня, отримані методами Ньютона та хорд.Приклад 8. Користуючись методами хорд та комбінованим знайти корені рівняння  .Лістинги обчислення коренів указаними вище методами наведено, відповідно, на рис. 16, 17. Зауважимо, що при знаходженні кореня рівняння, який знаходиться на відрізку  за нерухому точку в комбінованому методі потрібно брати лівий кінець відрізка, тобто  , а за початкове наближення правий кінець відрізка, тобто точку  . Рис. 16  Рис. 17 9. Застосування засобів пакету Mathcad для знаходження коренів алгебраїчних рівнянь Корені алгебраїчного рівняння, яке має дійсні або комплексні корені  (25)можна знайти за допомогою вбудованої процедури polyroоts, яка має вигляд: polyroоts(V), де V – вектор з коефіцієнтів многочлена  вигляду  (Т – операція транспонування).Приклад 9. На лістингу (рис. 18), наведено приклади застосування процедури polyroоts для знаходження коренів рівнянь у випадку простих та кратних коренів. З наведених прикладів бачимо, що дана процедура, у випадку кратних коренів, може працювати не зовсім надійно (випадки 2, 3). Тому, при одержанні коренів потрібно виконувати їх перевірку.  Рис. 18 |
Схожі:
|
“Чисельні методи розв’язання нелінійних рівнянь” Мета роботи: Вивчення методів розв’язання алгебраїчних і трансцендентних рівнянь і набуття навичок їх реалізації за допомогою математичного... |
ЧИСЕЛЬНІ МЕТОДИ РОЗВ’ЯЗУВАННЯ СИСТЕМ НЕЛІНІЙНИХ РІВНЯНЬ Ужгород –... Мета роботи: Вивчення методів розв’язання систем нелінійних рівнянь і набуття навичок їх реалізації за допомогою математичного пакету... |
|
Розділ РОЗВ’ЯЗАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ У цьому розділі розглянемо основні чисельні методи розв’язання задач лінійної алгебри. Наведемо математичне описання, блок-схеми... |
ЧИСЕЛЬНІ МЕТОДИ РОЗВ’ЯЗАННЯ ЖОРСТКИХ ДИФЕРЕНЦІАЛЬНИХ РІВНЯНЬ ТА ЇХ СИСТЕМ Розглянемо спочатку питання умовної та абсолютної стійкості на простому прикладі. Задача Коші |
|
“Ітераційні методи розв’язання систем лінійних рівнянь” Мета роботи: Вивчення ітераційних методів розв’язання систем лінійних рівнянь і набуття навичок їх реалізації за допомогою математичного... |
ФІЗИКО-МАТЕМАТИЧНІ НАУКИ На ступінь доктора наук Бартіш М. Я. Методи типу Ньютона для розв’язування нелінійних операторних рівнянь і задач на екстремум: (01. 05. 02) / Київ нац ун-т... |
|
Урок №80 Тема. Розв'язування задач за допомогою систем лінійних рівнянь Мета: відпрацювати навички застосування схеми розв'язання текстових задач на складання системи лінійних рівнянь із двома змінними... |
Тема: Різні способи розв'язання ірраціональних рівнянь Мета Мета: Систематизувати знання про ірраціональні рівняння, ознайомити з новими способами їх розв'язання, розвивати культуру мислення,... |
|
Тема: Розв’язування задач за допомогою рівнянь Мета: Розширити знання учнів про практичне застосування рівнянь, зокрема до розв’язання задач. Вдосконалити навики встановлення залежностей... |
Урок №73 Тема. Системи двох лінійних рівнянь із двома змінними та... Ня щодо залежності кількості розв'язків системи лінійних рівнянь від співвідношення коефіцієнтів a, b, c цих рівнянь; вироблення... |
При копіюванні матеріалу обов'язкове зазначення активного посилання © 2013
звернутися до адміністрації
bibl.com.ua
звернутися до адміністрації
bibl.com.ua