Чисельні методи розв’язання алгебраїчних рівнянь


Лекція 2

Чисельні методи розвязання алгебраїчних рівнянь


Лекція 2. Чисельні методи розвязання алгебраїчних рівнянь


Мета: розглянути та порівняти чисельні методи для розвязування алгебраїчних рівнянь.

Нехай дано рівняння



де функція визначена та неперервна на інтервалі . Коренем рівняння називається будь-яке значення , що перетворює функцію в нуль (). Припустимо, що рівняння (*) має лише ізольовані корені, тобто для кожного кореня існує окіл, що не містить інших коренів цього рівняння.

Наближене знаходження ізольованих дійсних коренів рівняння (*) зазвичай складається з двох етапів:

)Відокремлення коренів, тобто встановлення якомога менших проміжків , в яких міститься тільки один корінь рівняння (*);

)Уточнення наближених коренів, тобто їх доведення до заданого порядку точності.

Приклад. Відокремити корені рівняння

Розвязування

У даному випадку Оскільки для всіх значень , то функція зростає на всьому проміжку Корінь вважається відділеним, якщо вказано скінчений проміжок на якому він знаходиться. Методом проб знаходимо проміжок для якого , тобто на кінцях відрізка функція приймає значення різних знаків. Для даного обчислюємо значення функції при деяких значеннях аргументу.



Оскільки то на відрізку кореня немає; оскільки то корінь знаходиться на відрізку


1.Графічний спосіб розв'язку рівнянь


Дійсні корені рівняння (*) наближено можна визначити як абсциси точок перетину графіка функції з віссю (рис. 1.1а). На практиці часто буває зручніше рівняння (*) замінити рівносильним йому рівнянням



де функції і простіші, ніж функція . Тоді, побудувавши графіки цих функцій, шукані корені отримаємо в якості абсциси точок перетину цих графіків (рис. 1.1б).


а) б)

Рис. 1.1. Графічний метод знаходження коренів рівняння


Приклад 1.1. Розв'язати рівняння .

Розвязування

Запишемо рівняння у вигляді .

Побудувавши параболу та пряму , помітимо, що вони не перетинаються (рис. 1.2) - значить рівняння не має коренів.


Рис. 1.2 Графічний розв'язок рівняння


Приклад 1.2. Медичні дослідження шансів отримання значних травм хребта у банджі-стрибунів показали відчутний ріст травматизму при швидкості вільного падіння, що перевищує 36 м/с після 4 секунд польоту. Припустимо, керівник компанії з банджі-джампінгу хоче визначити масу, при якій досягається цей критерій за умови, що коефіцієнт аеродинамічного опору (drag coefficient) дорівнює 025 кг/м.

Застосувати графічний підхід для визначення максимальної маси банджі-стрибуна. Гравітаційне прискорення дорівнює 9.81 м/с2.

Розвязування

Відомо, що наступний аналітичний розвязок можна використовувати для передбачення швидкості падіння, як функції часу


(1.1)


Альтернативний погляд на задачу передбачає віднімання від обох сторін рівняння. Нова функція матиме вигляд



Після цього можна зрозуміти, що відпоіддю на запитання є значення , при якому функція буде дорівнювати нулю.

Побудова графіку, що відображатиме залежність між швидкістю падіння та масою у середовищі Matlab вимагатиме наступного скрипту:

>> cd = 0.25; g = 9.81; v=36; t = 4;

>> mp = linspace(50, 200);

>> fp = sqrt(g*mp/cd).*tanh(sqrt(g*cd./mp)*t)-v;

>> plot (mp, fp), grid


Рис. 1.3 Графічний метод знаходження кореня рівняння (1.1)


Функція перетинає вісь маси між 140 та 150 кг. Візуальний огляд графіку забезпечує грубу оцінку кореня в 145 кг. Коректність графічної оцінки можна перевірити шляхом підстановки

>> sqrt(g*145/cd)*tanh(sqrt(g*cd/145)*t)-v= 0.0456

Її результат, як видно, близький до 0. Також перевірити це можна шляхом підстановки даного значення в рівняння (1.1) з даними, що задавалися спочатку.

>> sqrt(g*145/cd)*tanh(sqrt(g*cd/145)*t)= 36.0456

Даний результат близький до бажаної швидкості падіння в 36 м/с.

Графічний метод має обмежену практичну цінність у звязку зі своєю невеликою точністю. Проте його можна використовувати для грубої оцінки коренів, як початкове наближення для методів, що будуть розглядатися в даній лекції. Разом з тим графічні інтерпретації корисні для розуміння властивостей функцій та передбачення підводних каменів для чисельних методів.


2. Метод половинного поділу


Нехай корінь рівняння



відокремлено на відрізку . Це означає, що і зберігає знак (рис. 2.1).


Рис 2.1. Графічна інтерпретація методу половинного ділення


У якості початкового наближення кореня візьмемо точку - середину відрізка



Якщо , то - шуканий корінь рівняння. Інакше з двох отриманих відрізків і обираємо той, на кінцях якого функція набуває значення різних знаків.

Новий відрізок знову ділиться пополам і далі проводимо ті ж дії. Довжина кожного нового відрізку вдвоє менше попереднього, тобто за кроків зменшиться у разів. Отже, слід відмітити досить повільну (лінійну) збіжність методу. Проте основною перевагою цього методу є його простота та здатність забезпечити практично будь-яку точність.

Обчислення припиняються, якщо довжина відрізку стане менше заданої похибки



Блок-схема методу зображена на рис. 2.2.

Приклад 2.1. Методом половинного поділу уточнити найбільший корінь рівняння з точністю на відрізку [0.5, 1].

ньютон збіжність корень рівняння

Рис 2.2. Блок-схема методу половинного ділення

Розвязування

Виділимо найбільший корінь: ; . .



Цей проміжок назвемо проміжком існування кореня. Проведемо уточнення кореня



Згідно критерію бачимо, що



Точка називається пробною точкою.




Продовжуючи цей процес, на шостій ітерації отримаємо:



Метод половинного поділу називають методом дихотомії або бісекції. У загальному випадку пробна точка обирається випадково з проміжку існування кореня.

У результаті послідовного звуження даного проміжку прийдемо до нерівності



З одного боку, вона дозволяє стверджувати, що послідовність має границю - шуканий корінь . З іншого боку, звідси можна підрахувати кількість кроків (ітерацій) методу половинного поділу, яка буде достатньою для отримання кореня із заданою точністю . Для цього потрібно знайти натуральне , що задовольняє нерівності



Приклад 2.2. Корінь певного рівняння відокремлено на проміжку [2, 3]. Визначте, скільки кроків методу половинного поділу потрібно виконати для уточнення кореня з точністю до .



Отже, 7.


3. Метод хорд


Даний метод за таких же умов забезпечує швидше знаходження кореня, ніж метод половинного поділу. Для цього відрізок ділиться не пополам, а у співвідношенні . Геометрично метод хорд еквівалентний заміні кривої хордою, що проходить через точки і . Цей процес зображено на рис. 3.1.

Нові співвідношення будуть мати наступний вигляд



де

Надалі цей прийом буде застосовано до одного з відрізків [a, x1] або [x1, b], на кінцях якого функція має протилежні знаки. Аналогічно знаходимо друге наближення і т. д.


Рис 3.1 Геометрична інтерпретація методу хорд.


Рівняння хорди має вигляд



Враховуючи припущення, що - корінь рівняння (), маємо



Також припускаючи, що на відрізку друга похідна зберігає постійний знак, метод хорд зводиться до двох варіантів

1)З рис. 3.1а видно, що точка залишається нерухомою, а наближається до кореня . Тому


(3.2)


Остаточно перетворивши рівняння, отримаємо


(3.3а)


2)З рис. 3.1б видно, що точка залишається нерухомою, а точка наближається до кореня . Тому рекурентне рівняння набуває вигляду


(3.3б)


Як обрати нерухому точку? Рекомендується в якості нерухомої брати ту точку, в якій виконується нерівність



Приклад 3.1. Відокремити корені рівняння аналітично й уточнити один з них методом хорд з точністю до 0,01.

Розвязання

Маємо функцію . Похідна ; . Складемо таблицю знаків функції :


Рівняння має один дійсний корінь, що лежить на проміжку . Для того, щоб уточнити корінь, знаходимо другу похідну ; на проміжку виконується нерівність . Для обчислень використаємо формулу (3.3а), де ; ; .

Результати обчислень розміщуємо в таблиці.


0000001,51,71-0,1181-0,882-0,68610,77790,1556-0,4410,21730,41730,118-0,0572-0,943-0,83860,88920,1778-0,47150,01210,21210,057-0,0543-0,946-0,84660,89490,1790-0,4730,00140,20140,054-0,0544-0,946

Відповідь. .


Приклад 3.2. Відокремити корені рівняння графічно і уточнити один з них методом хорд з точністю до 0,01.

Розвязання

Відокремимо корінь графічно. Побудуємо графіки функції і (рис.2), склавши таблицю значень цих функцій


00,20,40,60,8100,040,160,360,64100,110,220,330,440,550,10,210,330,460,600,76

Таким чином, додатний корінь рівняння знаходиться на проміжку . Щоб уточнити корінь методом хорд, визначимо знаки функції на кінцях відрізка і знак її другої похідної на цьому відрізку:




при . Для обчислень застосуємо формулу (3.3б), для якої ; . Розрахунки зручно розмістити в таблиці


00,60,20,430,45860,360,0986-0,1392-0,14210,7420,0580,50810,55700,55060,0064-0,0470-0,00820,7500,500,5125056270,56250,0002-0,0408-0,000230,75020,04980,51260,56280,56280

Відповідь: .


4. Метод простої ітерації


Метод простих ітерацій уточнення коренів рівняння полягає в його заміні еквівалентним рівнянням


(4.1)

та побудова послідовності


(4.2)


де , наприклад, .

Якщо не вдається виразити із рівняння (*), то еквівалентне рівняння та еквівалентну функцію можна побудувати, наприклад, так



Послідовність (4.2) називають методом простих ітерацій уточнення коренів рівняння (*). Основним питанням є умови, при яких метод простих ітерацій збігається. Якщо припустити, що функція диференційована на відрізку , то достатньою умовою збіжності буде існування такого числа , для якого


(4.3)


на даному відрізку. Тоді послідовність (4.2) буде збігатися до єдиного кореня рівняння (4.1) при будь-якому початковому наближенні .

Наступне питання - похибка методу. Якщо позначити невідомий точний корінь рівняння через та зупинити процес на -тій ітерації, то похибка оцінюється зверху виразом


(4.4а)

або

(4.4б)


Якщо задана точність , то ітерації можна зупиняти у випадку виконання умови



що отримана з рівняння (4.4а). Звідси можна отримати , тобто оцінити мінімальну кількість ітерацій для досягнення заданої точності :



Проте нерівність (4.6) дає завищену кількість ітерацій, тому на практиці ітераційний процес зупиняють при виконанні умови



Геометричну інтерпретацію методу простих ітерацій у випадку зображено на рис. 4.1. Як видно, тангенс кута нахилу дотичної до графіку функції менше . Отже, для довільного початкового наближення у відповідності з першою ітерацією рівняння (4.2) при визначається , що дорівнює значенню на графіку функції . Оскільки трикутник ОАВ прямокутний та рівнобедрений, то ОВ=. На другій ітерації в (4.2) при визначається , що дорівнює значенню на графіку функції . Оскільки трикутник ОСD - рівнобедрений та прямокутний, то CD=OD=, тобто ітераційні значення , , прямують у напрямку точного кореня (вказано стрілкою зліва направо).


Рис. 4.1. Геометрична інтерпретація методу простих ітерацій у випадку


Випадок розглянуто на рис. 4.2.


Рис. 4.2. Геометрична інтерпретація методу простих ітерацій у випадку


Рис. 4.3 Геометрична інтерпретація збіжності ітераційного процесу з обох сторін


Рис 4.4 Блок-схема методу простих ітерацій


На рис. 4.2 і видно, що ітераційний процес розбігається (наближення кореня віддаляються від кореня ).

На рис. наведено випадок Процес ітерацій збігається з обох сторін, тобто наближення до кореня знаходяться то справа, то зліва від точно кореня .

Ітераційний процес можна використовувати у випадку, коли у еквівалентному рівнянні . Для цього повернемось до вихідного рівняння та побудуємо еквівалентне рівняння у вигляді



де береться знак мінус, якщо та плюс, коли

Приклад 4.1. Методом простих ітерацій з точністю уточнити корінь трансцендентного рівняння , причому шуканий корінь

Розвязання

Запишемо еквівалентне рівняння



В якості початкового наближення оберемо



Виконуємо послідовні дії за формулою :



Результати обчислень наведено в таблиці 4.1.


Таблиця 4.1 Результати обчислень

0123450.75000.68730.70910.70150.70420.7032-0.06270.02180.00760.00270.0010

На п'ятій ітерації виконано умову , тому процес завершено. У якості наближеного розвязку береться . Підстановка у початкове рівняння дає , тобто рівність також виконується із заданою точністю. Видно, що збіжність двостороння () та лінійна, оскільки співвідношення приблизно однакові та дорівнюють 0.35.

Приклад 4.2. Знайти розв'язок рівняння методом простих ітерацій з точністю , .

Розвязання

Оскільки многочлен третього порядку, то рівняння має три корені.

Визначимо кількість додатних та відємних коренів. Виписуємо коефіцієнти многочлена : 1, 0, -1, 1. Оскільки кількість змін знаку (нульовий коефіцієнт не враховується), то кількість додатних коренів дорівнює двом або менше на парне число, тобто вони відсутні. Далі виписуємо коефіцієнти многочлена : -1, 0, 1, 1. Оскільки кількість змін знаку , то кількість відємних коренів дорівнює одиниці.


Рис. 4.5 Графіки і


Відокремимо корені третім способом, Для цього перетворимо рівняння до рівносильного вигляду та знайдемо точки перетину графіків і (рис. 4.5). Очевидно, що корінь рівняння .

Перетворимо рівняння до вигляду


.


Легко бачити, що не задовольняє умову збіжності, оскільки , , . Тому використаємо інше перетворення.

У результаті отримаємо . На відрізку виконуються достатні умови збіжності, оскільки .

Задамо початкове наближення . Розвяжемо задачу з різною точністю , . Виконаємо обчислення за формулою



Результати наведено в таблиці 4.2.


Таблиця 4.2. Результати обчислень

012345-1.000-1.2599-1.3123-1.3223-1.3243-1.3246-0.25990.05240.01000.00200.0003

Якщо , то , а якщо , то .

Приклад 4.3. Знайти корені рівняння методом простих ітерацій з точністю .

Розвязання

Оскільки многочлен третього порядку, то рівняння має три корені. Визначимо кількість додатних та відємних коренів. Виписуємо коефіцієнти многочлена : 1, -1, -9, 9. Оскільки кількість змін знаку , то рівняння має два додатних кореня або вони відсутні. Далі виписуємо коефіцієнти многочлена : -1, -1, -9, 9. Оскільки кількість змін знаку , то кількість відємних коренів дорівнює одиниці.


Рис. 4.6 Графіки і


Відокремимо корені третім способом, Для цього перетворимо рівняння до рівносильного вигляду та знайдемо точки перетину графіків і (рис. 4.6, вказано два з трьох отриманих проміжків).

Результат відокремлення коренів - три відрізки , , . Відмітимо, що ці проміжки можливо звузити, наприклад, замість відрізка можна взяти .

Перетворимо рівняння до вигляду . Можна показати, що на відрізках , функція задовольняє умові .

На проміжку використаємо інший вигляд рівняння: . Оскільки , то на цьому проміжку виконується достатня умова збіжності . У якості початкових наближень оберемо:

Точку на відрізку ;

Точку на відрізку ;

Точку на відрізку

У поставленій задачі . Виконаємо обчислення за формулою


з початковими наближеннями та і за формулою



з початковим наближенням .


02.0000-12.35130.351322.60560.254332.76940.163842.86820.098852.92550.057362.95820.032772.97670.018582.98700.010292.99270.0057102.99590.0032112.99770.0018122.99870.0010 0-2.0000-1-2.84380.84382-2.98160.13783-2.99790.01634-2.99970.00185-2.999970.00027 00.50000-10.986110.486120.998490.0123830.999830.0013440.999980.00015

У результаті отримано наближені значення коренів: , , .

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


5. Метод Ньютона (метод дотичних)


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

1)Існування другої похідної функції на множині ;

2) для всіх ;

)Знакосталість для всіх .

Тому його бажано використовувати спільно з іншими методами, наприклад, методом половинного поділу, для того, щоб досягнути діапазону , де вказані умови виконуються.

Геометрична інтерпретація методу Ньютона полягає в наступному. Спочатку задається початкове наближення . Далі проводиться дотична до кривої у точці , тобто крива замінюється прямою лінією. В якості наступного наближення обирається точка перетину цієї дотичної з віссю абсцис. Процес побудови дотичних та знаходження точок перетину з віссю абсцис повторюється до тих пір, поки приріст не стане менше заданої величини .


Рис. 5.1 Геометрична інтерпретація методу Ньютона

Отримаємо розрахункову формулу методу Ньютона. Візьмемо замість кривої ВС (точка С відповідає кореню рівняння) ділянку АВ - дотичну, що проведено в точці . Для цього відрізка справедливе відношення



де - кут нахилу дотичної в точці до осі абсцис. Звідси отримаємо :


(5.1)


Повторюючи цей процес, знаходимо загальну формулу


(5.2)


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

Поширеним критерієм зупинки даного ітераційного процесу є перевірка того, чи перевищує абсолютне значення функції в точці наперед заданого малого значення . Тобто умовою зупинки буде



Блок-схема методу Ньютона наведена на рис. 5.2.

Слід зауважити, що похідну не завжди легко можна знайти і чисельно це досить затратна операція. Враховуючи, що наближено значення похідної - це відношення приросту функції до приросту аргументу



з формули (5.2) отримаємо


(5.3)


На практиці такий підхід досить поширений.


Рис 5.2 Блок-схема методу


Приклад 5.1 (Інвестиційний фонд). На початку кожного року клієнти банку кладуть на депозит гривень і забирають у кінці -того року прибуток розміром гривень. Обчислити середню процентну ставку цих внесків, якщо 1000 грн., а після 5 років прибуток становить 6000 грн.

Розв'язування

Оскільки повязано з відношенням


то, очевидно, - корінь алгебраїчного рівняння



Нижче наведено код Matlab для розвязування поставленої задачі. Як бачимо, після шостої ітерації різниця між двома послідовними результатами стала менше або рівною .


Рис. 5.3 Код Matlab для методу Ньютона


Рис. 5.4 Результати роботи у відсотках

Порівняємо отримані результати з методами, що було розглянуто раніше у таблиці 5.1.


Таблиця 5.1

Порівняння результатів з іншими методами для прикладу 5.1

МетодПочаткове наближенняРезультатКількість ітераційПоловинного поділу45e-26.140241153586948e-0240Хорд30e-26.140241153652555e-028Простих ітерацій30e-26.140241153622682e-0235Ньютона30e-26.140241153652573e-026

У загальному випадку метод Ньютона збігається не при всіх значеннях початкового наближення, а лише при тих, що достатньо близькі до кореня. На практиці часто отримують за допомогою виконання кількох ітерацій методу половинного поділу або за результатами графічного розвязку рівняння.

Також існують достатні умови збіжності методу Ньютона:

1) визначена та двічі диференційована на відрізку;

)відрізку належить лише один простий корінь , тому ;

)похідні , зберігають на знак, і ;

)початкове наближення задовольняє нерівність , тобто знаки і однакові.

Тоді за допомогою методу Ньютона (5.2) можна обчислити корінь рівняння (*) з будь-якою точністю.

Відносно загальної точності методу потрібно зауважити, що він характеризується квадратичною збіжністю поблизу кореня і лінійною далеко від нього.

Приклад 5.2. Методом Ньютона з точністю уточнити корінь трансцендентного рівняння , причому шуканий корінь

Розвязання

Можна переконатися, що на відрізку виконуються умови збіжності 1-3.

Задамо початкове наближення з умови 4. Оскільки для справедливо на , то , тому .

Обчислення виконуємо за формулою



Результати обрахунків поміщено в таблицю 5.2.


Таблиця 5.2 Результати обчислень

З таблиці можна зробити наступні висновки:

)для досягнення заданої точності потрібно було виконати три ітерації за умовою . Якщо вихід організовувати за умовою , то було б досить лише двох наближень.

)Поблизу кореня кількість вірних цифр у результатах подвоюється, оскільки всі цифри в є вірними, в той час як у вірними є лише три цифри після крапки.

)Швидкість збіжності методу Ньютона більша за швидкість збіжності методу простих ітерацій (та ж точність була досягнута за 5 кроків).

Приклад 5.3. Знайти корінь рівняння методом Ньютона

Розвязання

У прикладі 4.2 було відокремлено корінь Задамо початкове наближення . Оскільки , , то і . Покладемо .

Обчислення виконуються за формулою



Їх результати наведено в таблиці 5.3.


Таблиця 5.3 Результати обчислень

Знайдений наближений розвязок .

Приклад 5.4. Знайти корені рівняння методом Ньютона з точністю .

Розвязання

Процедура відокремлення коренів була виконана в прикладі 4.3. У якості відрізків , яким належать корені рівняння, обираємо , , .

Оскільки , похідні , зберігають знак при , то умови збіжності виконуються.

Оскільки , похідні , зберігають знак при , то умови збіжності також виконуються.

Оскільки , похідні , зберігають знак при , то умови збіжності виконуються.

Задамо початкові наближення:

-На відрізку обираємо , оскільки ;

-На відрізку обираємо , оскільки ;

На відрізку обираємо , оскільки ;

У поставленій задачі . Обчислення проводяться за формулою



Результати обрахунків наведено в таблицях 5.4-5.6


Таблиця 5.4. Результати обчислень для

Таблиця 5.5. Результати обчислень для

Таблиця 5.6. Результати обчислень для

Отже, отримано наближені значення коренів: ; ; .


Список використаної літератури


1.Колдаев В. Д. Численные методы и программирование: учебное пособие / Под ред. проф. Л. Г. Гагариной. - М.: ИД «ФОРУМ»: ИНФРА-М, 2009. - 336 с: ил.

2.Rao V. Dukkipati. Numerical Methods / Rao V. Dukkipati. - New Delhi: New Age International Publishers, 2010. - 352c. - ISBN (13) : 978-81-224-2978-7.

.Киреев В. И. Численные методы в примерах и задачах: Учебное пособие / В.И. Киреев, А.В. Пантелеев. - 3-е изд. стер. - М.: Высшая школа, 2008. - 480 с: ил.

.Исаков, В.Б. Элементы численных методов: Учебное пособие для студентов, обучающихся по специальности Математика группы Педагогические специал. - М.: Академия, 2003. - 192 с. : ил. - ISBN 5-7695-0795-0.

5.Кацман Ю. Я. Прикладная математика. Численные методы. Учебное пособие. - Томск: Изд. ТПУ, 2000. - 68 с.

6.Steven C. Chapra. Applied Numerical Methods with MATLAB® for Engineers and Scientists.

7.Формалев В. Ф., Ревизников Д. Л. Численные мeтоды. - М.: ФИЗМАТЛИТ, 2004. - 400 с. - ISBN 5-9221-0479-9.


Теги: Чисельні методи розв’язання алгебраїчних рівнянь  Лекция  Математика
Просмотров: 2643
Найти в Wikkipedia статьи с фразой: Чисельні методи розв’язання алгебраїчних рівнянь
Назад