Чисельні методи розв'язання нелінійних рівнянь. Метод Ньютона на вирішення рівнянь з однією змінною. Курсова робота: Метод Ньютона для вирішення нелінійних рівнянь

Наприклад:

Поставимо завдання знайти дійснікоріння цього рівняння.

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

Спочатку напрошується перевірити, чи наявність раціональнихкоріння. Згідно відповідної теореми, цього «звання» можуть претендувати лише числа 1, –1, 3, –3, і прямий підстановкою легко переконатися, що жодна з них «не підходить». Таким чином, залишаються ірраціональні значення. Ірраціональний корінь (коріння) багаточлена 3-го ступеня можна знайти точно (виразити через радикали)за допомогою так званих формул Кардано Однак цей метод досить громіздкий. А для багаточленів 5-го і більшого ступенів загального аналітичного методу не існує зовсім, і, крім того, на практиці зустрічається безліч інших рівнянь, в яких точні значеннядійсних коренів отримати неможливо (хоча вони існують).

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

Задамо для нашого прикладу точність. Що це означає? Це означає, що нам потрібно знайти ТАКЕ наближене значення кореня (коріння), в якому ми гарантовано помиляємось, не більше ніж на 0,001 (одну тисячну) .

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

З креслення випливає, що рівняння, судячи з усього, має єдиний дійсний корінь, що належить відрізку. На кінцях цього проміжку функція приймає значення різних знаків: , і з факту безперервності функції на відрізкуОдночасно видно елементарний спосіб уточнення кореня: ділимо проміжок навпіл і вибираємо той відрізок, кінцях якого функція приймає різні знаки. У разі це, очевидно, відрізок . Ділимо отриманий проміжок навпіл і знову вибираємо «різнознаковий» відрізок. І так далі. Подібні послідовні дії називають ітераціями. У разі їх слід проводити до того часу, поки довжина відрізка стане менше подвоєної точності обчислень , і за наближене значення кореня слід вибрати середину останнього «різнознакового» відрізка.

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

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

Ця дотична перетнула вісь абсцис у жовтій точці, і зверніть увагу, що на першому кроці ми вже майже «потрапили в корінь»! Це буде першенаближення кореня. Далі опускаємо жовтий перпендикуляр до графіка функції та «потрапляємо» в помаранчеву точку. Через помаранчеву точку знову проводимо дотичну, яка перетне вісь ще ближче до кореня! І так далі. Неважко зрозуміти, що, використовуючи метод дотичних, ми наближаємося до мети семимильними кроками, і для досягнення точності знадобиться буквально кілька ітерацій.

Оскільки дотична визначається через похідну функції, то цей урок потрапив до розділу «Виробні» як один з її додатків. І, не вдаючись у докладне теоретичне обґрунтування методуя розгляну технічну сторону питання. На практиці описане вище завдання зустрічається приблизно в такому формулюванні:

Приклад 1

За допомогою графічного методу знайти проміжок, на якому знаходиться дійсний корінь рівняння. Користуючись методом Ньютона, одержати наближене значення кореня з точністю до 0,001

Перед вами «щадна версія» завдання, в якій одразу констатується наявність єдиного дійсного кореня.

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

Ну, а навіщо нам зайві труднощі? Уявимо рівнянняу вигляді , АКУРАТНО побудуємо графіки та відзначимо на кресленні корінь («іксову» координату точки перетину графіків):

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

Отже, наш "клієнт" належить відрізку і "на око" приблизно дорівнює 0,65-0,7.

На другому кроціпотрібно вибрати початкове наближеннякореня. Зазвичай це один із кінців відрізка. Початкове наближення має задовольняти такій умові:

Знайдемо першуі другупохідні функції :

і перевіримо лівий кінець відрізка:

Таким чином, нуль "не підійшов".

Перевіряємо правий кінець відрізка:

- Все добре! Як початкове наближення вибираємо.

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

Процес завершується і під час умови , де – заздалегідь задана точність обчислень. Через війну за наближене значення кореня приймається «енне» наближення: .

На черзі рутинні розрахунки:

(округлення зазвичай проводять до 5-6 знаків після коми)

Оскільки отримане значення більше, то переходимо до 1-го наближення кореня:

Обчислюємо:

тому виникає потреба перейти до 2-го наближення:

Заходимо на наступне коло:

, таким чином, ітерації закінчені, і як наближене значення кореня слід взяти 2-е наближення, яке відповідно до заданої точності потрібно округлити до однієї тисячної:

Насправді результати обчислень зручно заносити в таблицю, у своїй, щоб трохи скоротити запис, дріб часто позначають через :

Самі ж обчислення по можливості краще провести в Екселе - це набагато зручніше і швидше:

Відповідь: з точністю до 0,001

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

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

Що робити у таких випадках? Перевірити виконання зазначених умов (Див. вище за посиланням), і за необхідності зменшити відрізок. Так, умовно кажучи, якби в розібраному прикладі нам не підійшов проміжок, то слід розглянути, наприклад, відрізок . Насправді мені такі випадки траплялися, І цей прийом реально допомагає! Те саме потрібно зробити, якщо обидва кінці «широкого» відрізка не задовольняють умові (Тобто жоден з них не годиться на роль початкового наближення).

Але зазвичай все працює, як годинник, хоч і не без підводного каміння:

Приклад 2

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

Умова завдання помітно посилилася: по-перше, у ньому міститься товстий натяк на те, що рівняння має не єдиний корінь, по-друге, підвищилася вимога до точності, і, по-третє, з графіком функції справитися значно складніше.

А тому рішенняпочинаємо з рятівного трюку: представимо рівняння у вигляді і зобразимо графіки:


З креслення випливає, що наше рівняння має два дійсні корені:

Алгоритм, як ви розумієте, потрібно «провернути» двічі. Але це ще на найважчий випадок, буває, досліджувати доводиться 3-4 корені.

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

Тестуємо лівий кінець відрізка:

- Підійшов!

Отже, – початкове наближення.

Уточнення кореня проведемо методом Ньютона, використовуючи рекурентну формулу:
– доти, доки дріб за модулемне стане менше необхідної точності:

І тут слово «модуль» набуває неілюзорної важливості, оскільки значення виходять негативними:


З цієї ж причини слід виявити особливу увагу при переході до кожного наступного наближення:

Незважаючи на досить високу вимогу до точності, процес знову завершився на 2-му наближенні: , отже:

З точністю до 0,0001

2) Знайдемо наближене значення кореня.

Перевіряємо на «вшивість» лівий кінець відрізка:

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

Завдання про знаходження рішень системи з n нелінійних алгебраїчних або трансцендентних рівнянь з невідомими виду

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

У векторних позначеннях систему (6.1) можна записати у більш компактній формі

вектор стовпець функцій, символом () T позначена операція транспо-

Пошук рішень системи нелінійних рівнянь – це набагато складніша, ніж рішення одного нелінійного рівняння. Проте ряд ітераційних методів розв'язання нелінійних рівнянь може бути поширений і системи нелінійних рівнянь.

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

p align="justify"> Метод простої ітерації для систем нелінійних рівнянь по суті є узагальненням однойменного методу для одного рівняння. Він заснований на тому, що система рівнянь (6.1) наводиться до вигляду

x 1 = g 1 (x 1, x 2, …, x n), x 2 = g 2 (x 1, x 2, …, x n),

……………………

x n = g n (x 1, x 2, …, x n),

та ітерації проводяться за формулами

x 1 (k + 1) = g 1 (x 1 (k), x 2 (k), …, x n (k)), x 2 (k + 1) = g 2 (x 1 (k), x 2 (k), …, x n (k)),

……………………………

x n (k + 1) = g n (x 1 (k), x 2 (k), …, x n (k)).

Тут верхній індекс свідчить про номер наближення. Ітераційний процес (6.3) починається з деякого початкового наближення

(x 1 (0 ) ,x 2 (0 ) ,… ,x n (0 ) ) і продовжуються до тих пір, поки модулі прирощень

всіх аргументів після однієї k-ітерації не стануть меншими за задану величинуε :x i (k + 1 ) − x i (k )< ε дляi = 1,2,… ,n .

Хоча метод простої ітерації прямо веде до рішення і легко програмується, він має дві істотні недоліки. Один із них – повільна збіжність. Інший полягає в тому, що якщо початкове наближення вибрано далеко від істинного рішення (X 1, X 2, ..., X n), то збіжність

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

Розв'язати систему нелінійних рівнянь:

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

Для вирішення систем нелінійних рівнянь зазвичай застосовуються ітераційні методи.

Метод Ньютона

У разі одного рівняння F(x) = 0 алгоритм методу Ньютона був легко отриманий шляхом запису рівнянь, що стосується кривої y = F(x). В основі методу Ньютона для систем рівнянь лежить використання розкладання функцій F 1 (x 1 ... x n ) в ряд Тейлора, причому члени,

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

відповідально a 1 ,a 2 ,....,a n . Завдання полягає у знаходженні прирощень (по-

Проведемо розкладання лівих частин рівнянь (4.1) з урахуванням розкладання до ряду Тейлора, обмежуючись лише лінійними членами віднос-

Підставляючи в систему (4.1), отримаємо наступну систему лінійних рівнянь алгебри щодо прирощень:

x 2 = a 2 … x n = a n .

Визначником системи (4.3) є якобіан:

… … … …

∂ F n… … ∂ F n∂ x 1 ∂ x n

x 1 = a 1,

Для існування єдиного рішення системи якобіан може бути відмінний від нуля кожної ітерації.

Таким чином, ітераційний процес розв'язання системи рівнянь методом Ньютона полягає у визначенні прирощень x 1, x 2, ..., x n до значень невідомих на кожній ітерації шляхом розв'язання системи лінійних рівнянь алгебри (4.3). Рахунок припиняється, якщо всі збільшення стають малими за абсолютною величиною: maxx i< ε . В ме-

Тоді Ньютона також важливий зручний вибір початкового наближення для забезпечення оптимальної збіжності. Збіжність погіршується із збільшенням числа рівнянь системи.

Як приклад розглянемо використання методу Ньютона на вирішення системи двох рівнянь:

∂ ∂ F 1. x

Величини, що стоять у правій частині, обчислюються при x = a, y = b.

ДЕРЖАВНИЙ ОСВІТНИЙ УСТАНОВА

«Придністровський державний університет ім. Т.Г. Шевченка»

Рибницька філія

Кафедра фізики, математики та інформатики

Курсова робота

з дисципліни: «Практикум щодо вирішення завдань на ЕОМ»

"Метод Ньютона для вирішення нелінійних рівнянь"

Виконала:

студентка ІІІ курсу;

330-ї групи

спеціальності: «Інформатика

з дод. спеціальністю англійська

Ністор А. Р..

Перевірила:

викладач Панченко Т.О.

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

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

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

Цілі та завдання.

Метою даної курсової є вивчення та реалізація в програмному продукті рішення нелінійних рівнянь за допомогою методу Ньютона. Ця робота складається з трьох розділів, висновків та додатків. Перший розділ – теоретичний і містить загальні відомості про метод Ньютона. Другий – це практична частина. Тут описується метод Ньютона, розібраний на конкретних прикладах. Третій присвячений тестуванню програми та аналізу результатів. Наприкінці подано висновок про виконану роботу.

Метою даної курсової є програмна реалізація методу Ньютона на вирішення нелінійних рівнянь.

Для цього необхідно виконати такі завдання:

1. Вивчити потрібну літературу.

2. Оглядно розглянути існуючі методи вирішення нелінійних рівнянь.

3. Вивчити метод Ньютона на вирішення нелінійних рівнянь.

4. Розглянути рішення нелінійних рівнянь методом Ньютона на конкретних прикладах.

5. Розробити програму на вирішення нелінійних рівнянь методом Ньютона.

6. Проаналізувати результати.

Розглянемо задачу знаходження коріння нелінійного рівняння

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

Алгоритм знаходження коріння наближеними методами можна розбити на два етапи. На першому вивчається розташування коренів та проводиться їх поділ. Знаходиться область , де існує корінь рівняння чи початкове наближення до кореня x 0 . Найпростіший спосіб розв'язання цієї задачі є дослідження графіка функції f(x). У випадку для її вирішення необхідно залучати всі засоби математичного аналізу.

Існування на знайденому відрізку принаймні одного кореня рівняння (1) випливає з умови Больцано:

f(a)*f(b)<0 (2)

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

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

де речові коефіцієнти.

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

б) Число позитивних речових коренів менше або дорівнює кількості змінних знаків у послідовності коефіцієнтів. Заміна х на –х у рівнянні (3) дозволяє у такий самий спосіб оцінити кількість негативних коренів.

З другого краю етапі рішення рівняння (1), використовуючи отримане початкове наближення, будується ітераційний процес, що дозволяє уточнювати значення кореня з деякою, наперед заданою точністю . Ітераційний процес полягає у послідовному уточненні початкового наближення. Кожен такий крок називається ітерацією. В результаті процесу ітерації знаходиться послідовність наближених значень коренів рівняння. Якщо ця послідовність зі зростанням n наближається до справжнього значення кореня x, то ітераційний процес сходиться. Кажуть, що ітераційний процес сходиться щонайменше з порядком m, якщо виконано умову:

, (4)

де С>0 деяка константа. Якщо m=1 , то говорять про збіжність першого порядку; m=2 - про квадратичну, m=3 - про кубічні збіжності.

Ітераційні цикли закінчуються, якщо за заданої допустимої похибки виконуються критерії по абсолютним чи відносним відхиленням:

або трохи нев'язки:

Ця робота присвячена вивченню алгоритму розв'язання нелінійних рівнянь за допомогою методу Ньютона.

1.1 Огляд існуючих методів розв'язання нелінійних рівнянь

Існує багато різних методів розв'язання нелінійних рівнянь, деякі з них представлені нижче:

1)Метод ітерацій. При вирішенні нелінійного рівняння методом ітерацій скористаємося записом рівняння як x=f(x). Визначаються початкове значення аргументу x 0 і точність ε. Перше наближення рішення x 1 знаходимо з виразу x 1 = f (x 0), друге - x 2 = f (x 1) і т.д. У випадку i+1 наближення знайдемо за формулою xi+1 =f(xi). Зазначену процедуру повторюємо поки що |f(xi)|>ε. Умова збіжності методу ітерацій | f "(x) |<1.

2)Метод Ньютона. При вирішенні нелінійного рівняння методом Ньтона задаються початкове значення аргументу х 0 і точність ε. Потім у точці (x 0 F (x 0)) проводимо дотичну до графіка F (x) і визначаємо точку перетину дотичної з віссю абсцис x 1 . У точці (x 1 F (x 1)) знову будуємо дотичну, знаходимо наступне наближення шуканого рішення x 2 і т.д. Зазначену процедуру повторюємо поки що |F(xi)| > ε. Для визначення точки перетину (i+1) дотичної з віссю абсцис скористаємося наступною формулою x i+1 =x i -F(xi) F'(xi). Умова збіжності методу дотичних F(x 0)∙F""(x)>0, та ін.

3). Метод дихотомії.Методика рішення зводиться до поступового поділу початкового інтервалу невизначеності навпіл за формулою С к = а к + в к /2.

Для того щоб вибрати з двох відрізків необхідний, треба знаходити значення функції на кінцях відрізків, що виходять, і розглядати той на якому функція буде змінювати свій знак, тобто повинна виконуватися умова f (а к) * f (в ​​к)<0.

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

в до - а до< E. Тогда в качестве приближенного решения уравнения будет точка, соответствующая середине интервала неопределённости.

4). Метод хорд. Ідея методу полягає в тому, що на відрізку будується хорда стягує кінці дуги графіка функції y=f(x), а точка c перетину хорди з віссю абсцис вважається наближеним значенням кореня

c = a - (f(a)Ч (a-b)) / (f(a) - f(b)),

c = b - (f(b)Ч(a-b)) / (f(a) - f(b)).

Наступне наближення шукається на інтервалі або в залежності від символів значень функції в точках a, b, c

x* Про якщо f(с)Ч f(а) > 0 ;

x* Про якщо f(c)Ч f(b)< 0 .

Якщо f"(x) не змінює знак на , то позначаючи c = x 1 і вважаючи початковим наближенням a або b отримаємо ітераційні формули методу хорд із закріпленою правою або лівою точкою.

x 0 =a, x i+1 = x i - f(xi) (b-xi) / (f(b)-f(xi), при f "(x) Ч f "(x) > 0;

x 0 = b, x i + 1 = x i - f (x i) (xi -a) / (f (xi) - f (a), при f "(x) Ч f "(x)< 0 .

Збіжність методу хорд лінійна.

1.2 Алгоритм методу Ньютона

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

.

(8)

Продовжуючи цей процес, отримаємо відому формулу Ньютона:

(9)

Наведемо найпростішу рекурсивну підпрограму-функцію:

function X_Newt(x,eps:real):real;

y:=x-f(x)/f1(x);

if abs(f(x)) > eps

then X_Newt:=X_Newt(y,eps)

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

Перетворимо рівняння (1) до еквівалентного рівняння виду:

У разі методу дотичних . Якщо відомо початкове наближення до кореня x=x 0 то наступне наближення знайдемо з рівняння x 1 =g(x 0), далі x 2 =g(x 1),... Продовжуючи цей процес, отримаємо рекурентну формулу методу простої ітерації

x k + 1 = g (x k) (11)

Ітераційний процес триває доти, доки не будуть виконані умови (5-7).

Чи завжди описаний обчислювальний процес призводить до шуканого рішення? За яких умов він буде схожим? Для відповіді на ці питання знову звернемося до геометричної ілюстрації методу.

Корінь рівняння є точкою перетину функцій y=x та y=g(x). Як видно із рис. 3(а), якщо виконується умова , процес сходиться, інакше – розходиться (рис3(б)).

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

Перехід від рівняння f(x)=0 до рівняння х=g(x) можна здійснювати різними способами. При цьому важливо, щоб обрана функція g(x) задовольняла умову (12). Наприклад, якщо функцію f(x) помножити довільну константу q і додати до обох частин рівняння (1) змінну х, то g(x)=q*f(x)+x . Виберемо константу q такий, щоб швидкість збіжності алгоритму була найвищою. Якщо 1

Метод Ньютона має високу швидкість збіжності, проте він не завжди сходиться. Умова збіжності , де g(x) = x – f(x)/ f'(x) зводиться до вимоги .

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

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

(13)

Інший метод модифікації – заміна похідної кінцевої різниці

(14)

Тоді (15)

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

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

1. Задати початкове наближення х (0) так, щоб виконалася умова

f(x(0))*f''(x(0))>0. (16)

Задати мале позитивне число ε як точність обчислень. Покласти до = 0.

2. Обчислити х (к+1) за формулою (9):

.

3. Якщо | x(k+1) - x(k) |< ε, то процесс вычисления прекратить и положить х* = x (k+1) . Інакше збільшити на 1 (к = до + 1) і перейти до пункту 2.

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

Приклад 1

sin x 2 + cosx 2 – 10x. = 0.

F'(x)=2x cosx 2 - 2x sinx 2 - 10.

F''(x)=2cosx 2 - 4x 2 sinx 2 - 2sinx 2 - 4x 2 cosx 2 = cosx 2 (2-4x 2) - sinx 2 (2+4x 2).

Тепер, виходячи з графіка, візьмемо перший наближений корінь і перевіримо умову (16): f(x(0)) * f'(x(0)) > 0.

Нехай x(0) = 0,565, тоді f(0.565)*f''(0.565) = -4. 387 * (-0. 342) = 1. 5 > 0,

Умова виконується, отже беремо х (0) = 0,565.

Звідси випливає, що корінь рівняння х = 0,101.

Приклад 2

Вирішити рівняння методом Ньютона.

cos x - e-x2/2 + x - 1 = 0

Обчислення з точністю ε = 0, 001.

Обчислимо першу похідну функції.

F'(x) = 1 - sin x + x * e-x2/2.

Тепер обчислимо другу похідну функції.

F''(x) = e -x2/2 * (1-x 2) - cos x.

Побудуємо наближений графік цієї функції.

Тепер, виходячи з графіка, візьмемо перший наближений корінь і перевіримо умову (16): f(x(0)) * f'(x(0)) > 0.

Нехай x(0) = 2, тоді f(2)*f’’(2) = 0. 449 * 0. 010 = 0.05 > 0,

Умова виконується, отже, беремо x(0) = 2.

Тепер складемо таблицю значень для вирішення даного рівняння.

Звідси випливає, що корінь рівняння х = 1.089.

Приклад 3

Вирішити рівняння методом Ньютона.

Обчислення з точністю ε = 0, 001.

Обчислимо першу похідну функції.

F'(x) = 2 * x + e-x.

Тепер обчислимо другу похідну функції.

F''(x) = 2 - e-x.

Побудуємо наближений графік цієї функції.

Тепер, виходячи з графіка, візьмемо перший наближений корінь і перевіримо умову (16): f(x(0)) * f'(x(0)) > 0.

Нехай x(0) = 1, тоді f(2)*f''(2) = 0. 632 * 1, 632 = 1, 031 > 0,

Тепер складемо таблицю значень для вирішення даного рівняння.

Звідси випливає, що корінь рівняння х = 0,703.

Вирішити рівняння методом Ньютона.

cos x -e-x/2 + x-1 = 0.

Обчислимо першу похідну функції.

F'(x) = -sin x + e-x/2/2+1.

Тепер обчислимо другу похідну функції.

F''(x) = -cos x - e-x/2/4.

Побудуємо наближений графік цієї функції.

Тепер, виходячи з графіка, візьмемо перший наближений корінь і перевіримо умову (16): f(x(0)) * f'(x(0)) > 0.

Нехай x(0) = 1, тоді f(2)*f''(2) = -0. 066 * (-0.692) = 0. 046> 0,

Умова виконується, отже, беремо x(0) = 1.

Тепер складемо таблицю значень для вирішення даного рівняння.

Звідси випливає, що корінь рівняння х = 1. 162.

Приклад 5

Вирішити рівняння методом Ньютона.

2+e x - e-x = 0.

Обчислимо першу похідну функції.

F'(x) = e x + e-x.

Тепер обчислимо другу похідну функції.

F''(x) = e x -e -x.

Побудуємо наближений графік цієї функції.

Тепер, виходячи з графіка, візьмемо перший наближений корінь і перевіримо умову (16): f(x(0)) * f'(x(0)) > 0.

Нехай x(0) = 1, тоді f(2)*f''(2) = 0. 350 * 2, 350 = 0. 823 > 0,

Умова виконується, отже, беремо x(0) = 1.

Тепер складемо таблицю значень для вирішення даного рівняння.

Звідси випливає, що корінь рівняння х = 0,881.

3.1 Опис програми

Ця програма створена для роботи в текстовому та графічному режимі. Вона складається з модуля Graph, Crt, трьох функцій та трьох процедур.

1. модуль Crt призначений забезпечення контролю над текстовими режимами екрана, розширеними кодами клавіатури, кольорами, вікнами і звуком;

2. модуль Graph призначений забезпечення контролю над графічними об'єктами;

3. procedure GrafInit – ініціалізує графічний режим;

4. function VF - обчислює значення функції;

5. function f1 - обчислює значення першої похідної функції;

6. function X_Newt – реалізує алгоритм розв'язання рівняння методом Ньютона.

7. procedure FGraf – реалізує побудова графіка заданої функції f(x);

Ots=35 - константа, що визначає кількість точок для відступу від меж монітора;

fmin, fmax – максимальні та мінімальні значення функції;

SetColor(4) – процедура, яка встановлює поточний колір графічного об'єкта, використовуючи палітру, у разі це червоний колір;

SetBkColor(9) – процедура, яка встановлює поточний колір фону, використовуючи палітру, в даному випадку це світло-синій колір.

8. Procedure MaxMinF – обчислять максимальні та мінімальні значення функції f(x).

Line – процедура, яка малює лінію з точки з координатами (x1, у1) у точку з координатами (х2, у2);

MoveTo - процедура, що переміщає покажчик (СР) в точку з координатами (х, у);

TextColor(5) – процедура, яка встановлює поточний колір символів, у разі – це рожевий;

Outtexty(х, у, 'рядок') – процедура, яка виводить рядок, починаючи з позиції (х, у)

CloseGraph – процедура, яка закриває графічну систему.

3.2 Тестування програми

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

1) sin x 2 + cosx 2 – 10x. = 0.

Введіть а = -1

Введіть b=1

= [-1, 1]

(виведення графіка функції)

Отримаємо: х = 0, 0000002

2) cos x - e-x2 / 2 + x - 1 = 0.

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

Введіть а = -3

Введіть b=3

= [-3, 3]

(виведення графіка функції)

Корінь рівняння, знайдений методом Ньютона:

зробимо перевірку, підставивши отриману відповідь у рівняння.

Отримаємо: х=-0,0000000

3) x 2 - e-x = 0.

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

Введіть а = -1

Введіть b=1

= [-1, 1]

Введіть точність обчислення eps=0. 01

(виведення графіка функції)

Корінь рівняння, знайдений методом Ньютона:

зробимо перевірку, підставивши отриману відповідь у рівняння.

Отримаємо: х = 0, 0000000

4) cos x -e-x / 2 + x-1 = 0.

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

Введіть а = -1,5

Введіть b=1,5

= [-1,5, 1,5 ]

Введіть точність обчислення eps=0. 001

(виведення графіка функції)

Корінь рівняння, знайдений методом Ньютона:

зробимо перевірку, підставивши отриману відповідь у рівняння.

Отримаємо: х = 0, 0008180

5) -2+e x - e-x = 0.

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

Введіть а = -0,9

Введіть b=0,9

= [-0,9, 0,9]

Введіть точність обчислення eps=0. 001

(виведення графіка функції)

Корінь рівняння, знайдений методом Ньютона:

Зробимо перевірку, підставивши отриману відповідь у рівняння.

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

1. Вивчено необхідну літературу.

2.Оглядно розглянуті існуючі методи вирішення нелінійних рівнянь.

3. Вивчений метод Ньютона на вирішення нелінійних рівнянь.

4.Розглянуто рішення нелінійних рівнянь методом Ньютона з прикладу.

5.Проведено тестування та налагодження програми.

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

1. Б.П. Демидович, І.А Марон. Основи обчислювальної математики. - Москва, вид. "Наука"; 1970.

2. В.М. Вержбицький. Чисельні методи (лінійна алгебра та нелінійні рівняння). - Москва, «Вища школа»; 2000.

3. Н.С.Бахвалов, А.В.Лапін, Є.В.Чіжонков. Чисельні методи у завданнях та вправах. - Москва, «Вища школа»; 2000.

4. Метьюз, Джон, Г., Фінк, Куртіс, Д. Чисельні методи MATLAB, 3-е видання. - Москва, «Вільяс»; 2001.