Метод Ньютона нелінійні рівняння. Методи розв'язання нелінійних рівнянь

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

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

Основне гідністьметоду – він має швидку збіжність.

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

Розглянемо нелінійне рівняння в загальному вигляді:

Шукане рішення рівняння - точка, в якій крива перетинає вісь абсцис.

Задаємо початкове наближення невідомої х (0). Визначаємо значення функції у цій точці w(х (0))і проводимо дотичну до кривої в точці В. Точка перетину цієї дотичної з віссю абсцис визначає наступне наближення невідомої х (1)і т.д.

Розкладемо рівняння (1) у ряд Тейлора на околицях точки х (0). Розглянемо члени розкладання, що містять тільки 1 похідну:

(2)

х - х (0) = Δх- Поправка до невідомої. Якщо визначимо її, то зможемо визначити наступне наближення.

З (2) визначаємо поправку (3)

Тоді наступне наближення: (5)

Аналогічно отримуємо до-е наближення:

Це рекурентна формула методу Ньютонадля вирішення нелінійних рівнянь. Вона дає змогу визначати чергові наближення невідомих.

Формулу (6) можна отримати іншим способом з малюнка:

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

Коментар до геометричної інтерпретації

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

Приклад:

Приклад:

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

Простий спосіб визначення області розташування коренів - табуляція.

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

Процес або не сходиться чи сходиться дуже погано.

Метод Ньютона-Рафсона для вирішення СНАУ

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

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

замість однієї нев'язки рівняння, розглядаємо вектор нев'язокрівнянь системи:

Одна похідна (6) заміщається матрицею похідних. Операція поділу (6) заміщається множенням на зворотнуматрицю похідних. У цьому випадку метод Ньютона-Рафсона відрізняється від методу Ньютона переходом від одновимірної задачі до багатовимірної.

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

(7)

У матричному вигляді її можна записати:

де Х= х 2 – вектор – стовпець невідомих;

w 1 (х 1, х 2, … х n)

W = w 2 (х 1, х 2, ... х n) - Вектор-функція.

w n (х 1, х 2, … х n)

Нехай - Початкові наближення невідомих. Розкладемо кожне рівняння системи (7) у ряд Тейлора в околиці точки Х (0)тобто виконаємо наближену заміну вихідних нелінійних рівнянь лінійними, в яких зберігається тільки 1-а похідна (лінеаризація). У результаті система рівнянь (7) набуває вигляду:

(9)

В результаті отримали систему лінійних рівнянь(лінеаризована система), у якій невідомими є поправки. Коефіцієнти при невідомих у цій системі - перші похідні від рівнянь w jвихідної нелінійної системи за всіма невідомими Х i.. Вони утворюють матрицю коефіцієнтів - матрицю Якобі:

=

Кожен рядок матриці складається з перших похідних від чергового рівняння нелінійної системи по всіх невідомих.

Запишемо лінеаризовану систему (9) у матричній формі:

(10)

Тут - вектор нев'язок рівнянь вихідної системи. Його елементи отримуємо при підстановці в рівняння нелінійної системи чергових наближень невідомих;

- матриця Якобі. Її елементами є перші приватні виробничі від усіх рівнянь вихідної системи по всіх невідомих;

- вектор поправокдо невідомих. На кожній ітерації він може бути записаний:

Систему (10) з урахуванням прийнятих позначень можна записати:

(12)

Ця система лінійнащодо поправок ΔХ (к).

Система (13) – лінеаризована система рівнянь, якою замінюється вихідна СНАУ на кожному кроці ітераційного процесу.

Система (13) вирішується будь-яким відомим способомв результаті знаходимо вектор поправок. Потім з (11) можемо знайти чергові наближенняневідомих:

Т.о. кожен крок ітераційногопроцесу полягає у вирішенні лінійної системи (13) і визначенні чергового наближення з (14).

З (11) та (12) можна отримати загальну рекурентну формулу(у матричному вигляді), що відповідає методу Ньютона-Рафсона:

(15)

Вона має структуру, що відповідає формулі (6).

Формула (15) у практичних розрахунках використовується рідкотому що тут потрібно звертати матрицю Якобі (великої розмірності) на кожній ітерації розрахунків. У реальних розрахунках поправки визначаються результаті рішення лінійної системи (13).

Контроль завершенняітераційного процесу виконуємо по вектору нев'язок:

Ця умова повинна виконуватися для нев'язок всіхрівнянь системи.

Алгоритм рішення СНАУ методом Ньютона-Рафсона

1. Завдання вектора початкових наближень невідомих.

Завдання точності розрахунку є , інших параметрів розрахунку

2. Визначення нев'язок нелінійних рівнянь у точці наближення;

2.3. Визначення елементів матриці Якобі в точці чергового наближення невідомих;

2.4. Рішення лінеаризованої системи (13) будь-яким відомим методом. Визначення поправок до невідомих.

2.5. Визначення чергового наближення невідомих відповідно до (14).

2.6. Контролює завершення ітераційного процесу відповідно до (16). Якщо умова не виконується, повернення до пункту 2.

Прикладник:

Вирішити СЛАУ методом Ньютона-Рафсона:

(Рішення Х 1 = Х 2 = 2)

Запишемо рівняння у вигляді нев'язок:

Визначаємо елементи матриці Якобі:

Матриця Якобі:

Реалізуємо алгоритм методу Ньютона-Рафсона:

1) Перша ітерація:

Початкові наближення

Нев'язки

Матриця Якобі:

Лінеаризована система рівнянь:

1-е наближення невідомих:

2) Друга ітерація

3) Третя ітерація:

… ……… …… …… …… ……..

Рішення систем рівнянь режиму, що встановився, методом Ньютона-Рафсона

Нелінійне рівняння встановленого режиму у формі балансу потужності для -го вузла має вигляд:

(17)

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

Тут-задані потужності у вузлі;

Невідомі складові напруги у вузлах. Їх потрібно

визначити у результаті розрахунку.

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

Запишемо ці рівняння (18) у вигляді нев'язок:

Нев'язки рівнянь (19) відповідає розрахунковому небалансуактивною та реактивної потужностів-му вузлі.

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

Розв'язуватимемо методом Ньютона-Рафсона систему 2nрівнянь виду (19), тобто на вирішення завдання розрахунку встановленого режиму електричної мережі методом Ньютона - Рафсона потрібно:

1) сформувати систему 2nрівнянь виду (19) для всіх вузлів електричної мережікрім балансуючих;

2) організувати ітераційний процес методу Ньютона-Рафсона

для розв'язання цієї системи рівнянь. В результаті рішення

отримуємо шукані складові напруги у вузлах .

Запишемо цю систему рівнянь у загальному вигляді:

(20)

Отримали систему 2 нелінійних рівнянь нев'язокз 2 невідомими, якими. Невідомими в ній є складові напруги - модулі та кути.

Для вирішення системи (20) методом Ньютона-Рафсона потрібно скласти допоміжнулінеаризовану систему рівнянь виду (13), вирішуючи яку на кожній ітерації, визначаємо поправки до невідомих:

(21)

З урахуванням прийнятих позначень система (21) може бути записана:

(22)

де -матриця Якобі, її елементами є приватні похідні від рівнянь системи (20) по всіх невідомих - складових напружень

Вектор нев'язок рівнянь системи (20). Їх значення отримуємо при підстановці рівняння чергових наближень невідомих;

Вектор поправок до невідомих:

; ΔӨ i = Ψ i (к+1) - Ө i (к), ΔU i = U i (к+1) - U i (к) .

Для визначення елементів матриці Якобі застосовуємо аналітичне диференціювання , тобто. диференціюємо кожне рівняння системи (20) за шуканими величинами – кутами та модулями напруг. Щоб сформувати матрицю Якобі, потрібно отримати аналітичні вирази для наступних похідних. видів:

1) Похідна від рівняння нев'язки активної потужності го вузла по куту напруги цього ж вузла: ;

2) Похідна від рівняння нев'язки активної потужності го вузла по куту суміжної напруги j-го вузла: ;

3) Похідна від нев'язки активної потужності го вузла по модулю напруги цього ж вузла: ;

4) Похідна від нев'язки активної потужності го вузла за модулем напруги суміжного вузла: ;

Аналогічно визначаються ще чотири види похідних - похідні від рівнянь нев'язки реактивної потужності го вузла по всіх невідомих:

5) ; 6) ; 7) ; 8) .

З урахуванням цих похідних матрицю Якобі можна записати у загальному вигляді:

(23)

Визначимо аналітичні виразидля похідних, диференціюючи рівняння системи (20) за невідомими величинами. Вони мають вигляд:

(24)

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

Якщо вузли не пов'язані між собою, то відповідні вироблені в матриці матриці Якобі, розташовані поза діагоналі, дорівнюватимуть нулю (аналогічно матриці провідностей) - т.к. у відповідних форму-лах (24) взаємна провідність y ijє співмножником і. y ij =0.

Кожен рядок матриці – похідні від чергового рівняння системи (20).

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

1. Для вузлів з фіксацією модулянапруги (ФМ), в яких задані і невідомими є і , з матриці Якобі виключаєтьсярядок похідних (т.к. Q iне задана, те й рівняння балансу реактивної потужності (18), (19) скласти не можна) і стовпець похідних (т.к. модуль напруги U iвідомий і він виключається зі складу невідомих).

2. Для вузлів опорних та балансуючих – відповідні рядки та стовпці матриці виключаються;

3. Якщо вузли не пов'язані безпосередньо - відповідні вироблені в матриці дорівнюють нулю.

Матрицю Якобі можна розбити на чотири блоку:

1) - похідні від рівнянь небалансу активноюпотужності (20) кутахнапруги;

2) - похідні від рівнянь небалансу активноюпотужності по модулямнапруги;

3) - похідні від рівнянь небалансу реактивноюпотужності (20) кутахнапруги;

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

Це матриці-клітини приватних похідних небалансів активної та реактивної потужностей за невідомими кутами та модулями напруг. У загальному випадку це квадратні матрицірозмірністю n×n.

З огляду на це, матриця Якобі може бути представлена ​​у вигляді блоковиймат-риці:

Де субвектор невідомих величин.

З урахуванням цього, Тоді лінеаризовану систему рівнянь (22) можна записати у вигляді:

. (25)

Вирішуючи цю лінійну системурівнянь (будь-яким відомим методом) на

до кожної ітерації методу, знаходимо поправки до невідомих, а потім і

чергові наближенняневідомих:

(26)

Чергове наближення невідомих можна також отримати з використанням. ітераційної формулиметоду Ньютона-Рафсона, аналогічною (15):

- · (27)

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

Алгоритм вирішення систем рівнянь режиму, що встановився методом Ньютона - Рафсона

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

2. Завдання умов розрахунку: точність ε , гранична кількість ітерацій, прискорювальні коефіцієнти та ін.

3. Визначення нев'язок рівнянь відповідно до рівнянь (20) при чергових наближеннях невідомих;

4. Визначення елементів матриці Якобі відповідно до (24) при чергових наближеннях невідомих;

5. Рішення лінеаризованої системи рівнянь (25) та визначення поправок до невідомих;

6. Визначення чергових наближень невідомих відповідно до (26);

7. Перевірка завершення ітераційного процесу:

Значення нев'язок рівнянь для всіх вузлів повинні бути менше заданої точності.

Якщо умова не виконується, то повернення до пункту 3 і повторення розрахунку при нових наближеннях невідомих.

Існує ряд модифікацій методу Ньютона-РафсонаВ тому числі:

1. Модифікований метод Ньютона-Рафсона.

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

2. Розділений метод Ньютона-Рафсона.

Похідні види дуже малі і їх значеннями можна набрати. В результаті, в матриці Якобі залишаються два блоки - 1-й і 4-й, і система (25), що складається з рівнянь, розпадаєтьсяна дві незалежні системи розмірністю . Кожна з цих систем вирішується окремо від іншої. Це призводить до скорочення обсягу обчислень та необхідної пам'яті ЕОМ.

Наприклад:

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

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

Спочатку напрошується перевірити, чи наявність раціональнихкоріння. Згідно відповідної теореми, цього «звання» можуть претендувати лише числа 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) Знайдемо наближене значення кореня.

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

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

Метод Ньютона (також відомий як метод дотичних) – це ітераційний чисельний метод знаходження кореня (нуля) заданої функції. Метод був вперше запропонований англійським фізиком, математиком та астрономом Ісааком Ньютоном (1643-1727), під ім'ям якого і знайшов свою популярність.

Метод був описаний Ісааком Ньютоном у рукописі De analysi per aequationes numero terminorum infinitas (лат .Про баналізі рівняннями нескінченних рядів), адресованої в 1669 Барроу, і в роботі De metodis fluxionum et serierum infinitarum (лат.Метод флюксій і нескінченні ряди) або Geometria analytica ( лат.аналітичнагеометрія) у зборах праць Ньютона, яка була написана у 1671 році. Проте опис методу суттєво відрізнявся від його нинішнього викладу: Ньютон застосовував свій метод виключно поліномам. Він обчислював не послідовні наближення xn, а послідовність поліномів і в результаті отримував наближене рішення x.

Вперше метод був опублікований в трактаті Алгебра Джона Валліса в 1685, на прохання якого він був коротко описаний самим Ньютоном. У 1690 році Джозеф Рафсон опублікував спрощений опис у роботі Analysis aequationum universalis (лат. Загальний аналізрівнянь).Рафсон розглядав метод Ньютона як суто алгебраїчний і обмежив його застосування поліномами, проте при цьому він описав метод на основі послідовних наближень x n замість більш тяжкої для розуміння послідовності поліномів, використаної Ньютоном.

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

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

Рис.1 . Графік зміни функції

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

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

Умовою закінчення ітераційного процесу є виконання наступної умови:

де ˗ допустима похибка визначення кореня.

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

Математичне обґрунтування

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

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

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

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

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

З урахуванням цього стискаюча функція прийому наступний вид:

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

Алгоритм знаходження кореня нелінійного рівняння методом

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

2. Виконати розрахунок наближеного значення кореня функції відповідно до формули:

3. Перевіряємо наближене значення кореня щодо заданої точності, у разі:

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

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

Приклад розв'язування рівнянь

за методомНьютона для рівняння з однією змінною

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

Варіант розв'язання нелінійного рівняння у програмному комплексіMathCADпредставлений малюнку 3.

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

Рис.2. Результати розрахунку за методом Ньютона для рівняння з однією змінною

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

Рис.3 . Лістинг програми вMathCad

Модифікації методу Ньютона для рівняння з однією змінною

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

Спрощений метод Ньютона

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

Різнисний метод Ньютона

У результаті наближене значення кореня функції f(x) визначатиметься виразом різницевого методу Ньютона:

Двох кроковий метод Ньютона

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

В результаті наближене значення кореня функції f(x) визначатиметься таким виразом:

де

Рис.5 . Двох кроковий метод Ньютона

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

• назад
• Вперед

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



Ключові слова:

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

Завдання роботи:

1. Проаналізувати спеціальну літературу та вибрати найбільш раціональні способи вирішення нелінійних рівнянь, що дозволяють глибоко вивчити та засвоїти цю темуусім випускникам середньої школи.
2. Розробити деякі аспекти методики розв'язання нелінійних рівнянь із застосуванням ІКТ.
3. Вивчити методи розв'язання нелінійних рівнянь:

‒ Кроковий метод

‒ Метод поділу навпіл

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

Вступ.

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

Кроковий метод.

Нехай потрібно розв'язати нелінійне рівняння виду рівняння F(x)=0. Припустимо, що нам заданий деякий інтервал пошуку . Потрібно знайти інтервал [а,b] довжиною h, що містить перший корінь рівняння, починаючи з лівої межі інтервалу пошуку.

Мал. 1. Кроковий метод

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

Iетап. Відділення коріння.

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

• Підставляємо значення X (бажано з якимось досить дрібним кроком) і дивимося, де функція змінить знак. Якщо функція змінила знак, це означає, що на ділянці між попереднім і поточним значенням X лежить корінь (якщо функція не змінює характеру зростання/зменшення, то можна стверджувати, що корінь на цьому інтервалі один).
• Графічний метод. Будуємо графік та оцінюємо на яких інтервалах лежить один корінь.
• Досліджуємо властивості конкретної функції.

IIетап. Уточнення коріння.

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

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

Швидкий і досить простий чисельний метод розв'язання рівнянь, заснований на послідовному звуженні інтервалу, що містить єдиний корінь рівняння F(x)=0 доти, доки досягнуто задана точність Е. Даний метод зазвичай використовується під час вирішення квадратних рівняньта рівнянь вищих ступенів. Однак у даного методу є істотний недолік - якщо на відрізку [а, b] міститься більше одного кореня, то за його допомогою не вдасться досягти добрих результатів.

Мал. 2. Метод дихотомії

Алгоритм цього методу наступний:

‒ Визначити нове наближення кореня х у середині відрізка [а;b]: х=(а+b)/2.

‒ Знайти значення функції в точках а та х: F(a) та F(x).

‒ Перевірити умову F(a)*F(x)

‒ Перейти до пункту 1 і поділити відрізок навпіл. Алгоритм продовжити доти, доки буде виконано умова |F(x)|

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

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

Рівняння щодо функції f(x) у точці x n має вигляд:

У рівнянні дотичної покладемо y = 0 і x = x n +1.

Тоді алгоритм послідовних обчислень у методі Ньютона полягає у наступному:

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

Отже, збіжність методу дотичних Ньютона дуже швидка.

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

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

Метод Ньютона (метод дотичних) зазвичай застосовується у разі, якщо рівняння f(x) = 0має корінь і виконуються умови:

1) функція y= f(x)визначена і безперервна при ;

2) f(a)·f(b) (функція набуває значень різних знаків на кінцях відрізка [ a;b]);

3) похідні f"(x)і f""(x)зберігають знак на відрізку [ a;b] (тобто функція f(x)або збільшується, або зменшується на відрізку [ a;b], зберігаючи при цьому напрям опуклості);

Сенс методу полягає в наступному: на відрізку [ a;b] вибирається таке число x 0за якого f(x 0)має той самий знак, що й f""(x 0),тобто виконується умова f(x 0)·f""(x) > 0. Таким чином, вибирається крапка з абсцисою x 0, в якій стосується кривої y=f(x)на відрізку [ a;b] перетинає вісь Ox. За крапку x 0спочатку зручно вибирати один із кінців відрізка.

Розглянемо цей алгоритм на конкретному прикладі.

Нехай нам дано зростаюча функція y = f(x) = x 2-2,безперервна на відрізку (0;2) і має f "(x) = 2x> 0і f""(x) = 2> 0.

У нашому випадку рівняння дотичної має вигляд: y-y 0 = 2x 0 · (x-x 0).У як точка x 0 вибираємо точку B 1 (b; f(b)) = (2,2).Проводимо дотичну до функції y = f(x)у точці B 1 і позначаємо точку перетину дотичної і осі Oxточкою x 1. Отримуємо рівняння першої дотичної: y-2 = 2 · 2 (x-2), y = 4x-6. Ox: x 1 =

Мал. 3. Побудова першої щодо графіку функції f(x)

y=f(x) Oxчерез точку x 1, отримуємо точку У 2 = (1.5; 0.25). Знову проводимо дотичну до функції y = f(x)в точці В 2 і позначаємо точку перетину дотичної і Oxточкою x 2.

Рівняння другої дотичної: y-2.25 = 2 * 1.5 (x-1.5), y = 3x - 4.25.Точка перетину дотичної та осі Ox: x 2 =.

Потім знаходимо точку перетину функції y=f(x)та перпендикуляра, проведеного до осі Oxчерез точку x 2 отримуємо точку В 3 і так далі.

Мал. 4. Побудова другої щодо графіку функції f(x)

Перше наближення кореня визначається за такою формулою:

= 1.5.

Друге наближення кореня визначається за такою формулою:

=

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

Таким чином , i-е наближення кореня визначається за такою формулою:

Обчислення ведуться доти, доки не буде досягнуто збігу десяткових знаків, які необхідні у відповіді, або заданої точності e - до виконання нерівності |xi-xi-1|

У нашому випадку порівняємо наближення, отримане на третьому кроці з реальною відповіддю. Як видно, вже на третьому кроці ми отримали похибку менше ніж 0.000002.

Рішення рівняння за допомогою САПРMathCAD

Для найпростіших рівнянь виду f(x) = 0 рішення в MathСAD знаходиться за допомогою функції root.

root(f (х 1 , x 2 , … ) х 1 , a, b ) - повертає значення х 1 , що належить відрізку [ a, b ] , при якому вираз чи функція f (х ) звертається до 0. Обидва аргументи цієї функції мають бути скалярами. Функція повертає скаляр.

Мал. 5. Вирішення нелінійного рівняння в MathCAD (функція root)

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

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

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

Мал. 6. Вирішення нелінійного рівняння в MathCAD (функція solve)

Висновок

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

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

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

Література:

1. Мітяков С. Н. Інформатика. Комплекс навчально-методичних матеріалів. - Н. Новгород: Нижегород. держ. техн. ун-т., 2006
2. Вайнберг М. М., Треногін В. А. Теорія розгалуження розв'язків нелінійних рівнянь. М.: Наука, 1969. – 527 с.
3. Бронштейн І. Н., Семендяєв К. А. Довідник з математики для інженерів та учнів ВТНЗ - М.: Наука, 1986.
4. Омельченко В. П., Курбатова Е. В. Математика: навчальний посібник. - Ростов н/Д.: Фенікс, 2005.
5. Савін А. П. Енциклопедичний словникмолодого математика. - М: Педагогіка, 1989.
6. Корн Г., Корн Т. Довідник з математики для науковців та інженерів. - М: Наука, 1973.
7. Кір'янов Д. Mathcad 15/MathcadPrime 1.0. - С-Пб: БХВ-Петербург, 2012.
8. Черняк А., Черняк Ж., Доманова Ю. Вища математика з урахуванням Mathcad. Загальний курс. - С-Пб.: БХВ-Петербург, 2004.
9. Поршнєв С., Беленкова І. Чисельні методи з урахуванням Mathcad. - С-Пб: БХВ-Петербург, 2012.

Ключові слова: нелінійні рівняння, прикладна математика, САПР MathCAD, метод Ньютона, кроковий метод, метод дихотомії.

Анотація: Стаття присвячена вивченню методів розв'язання нелінійних рівнянь, зокрема з використанням системи автоматизованого проектування MathCAD. Розглянуто кроковий метод, методи половинного поділу та Ньютона, наведено докладні алгоритмизастосування даних методів, а також проведено порівняльний аналізвказаних методів.