Усі люди від природи прагнуть знання. (Арістотель. Метафізика)

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

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

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

У статистиці при побудові оцінок методом найменших квадратів або методом максимальної правдоподібності також доводиться вирішувати нелінійні рівняння та системи рівнянь.

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

У найпростішому випадку ми маємо функцію , задану на відрізку ( a, b) і приймає певні значення.

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

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

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

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

Найпростішим методом знаходження коренів рівняння є метод розподілу навпіл дихотомія.

Цей метод є інтуїтивно ясним і кожен діяв би при вирішенні задачі подібним чином.

Алгоритм полягає у наступному.

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

Поділимо відрізок навпіл і введемо середнюточку.

Тоді або , або .

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

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

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

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

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

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

Метод Ньютона: теоретичні основи

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

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

У рівнянні дотичної покладемо і.

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

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

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

Запам'ятайте цей чудовий факт!

Без змін метод узагальнюється на комплексний випадок.

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

Вправа 1. Знайти за допомогою методу дотичних рішення рівняння на відрізку (0, 2).

Вправа 2.Знайти за допомогою методу дотичних рішення рівняння на відрізку (1, 3).

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

Недоліком методу Ньютона є необхідність обчислення похідних щокроку.

Візуалізація методу Ньютона

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

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

2) f(a)· f(b) < 0 (функція набуває значень різних знаків на кінцях відрізка [ 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) = 2 x > 0 і f "" (x) = 2 > 0 .

Малюнок1 . f(x) =x 2 -2

Рівняння дотичної у загальному вигляді має уявлення:

y-y 0 = f" (x 0) · (x-x 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 =

Малюнок2. Результат першої ітерації

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

Рівняння другої дотичної: y-0.25=2*1.5(x-1.5), y = 3 x - 4.25.

Точка перетину дотичної та осі Ox: x 2 =.

Малюнок3. Друга ітерація методу Ньютона

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

Малюнок4. Третій крок методу дотичних

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

= 1.5.

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

=

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

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

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

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

Рисунок 5. Корінь із 2, порахований на калькуляторі

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

Таким чином, можна обчислити значення величини "корінь квадратний з 2" з будь-яким ступенем точності. Цей чудовий метод був винайдений Ньютоном і дозволяє шукати коріння дуже складних рівнянь.

Метод Ньютона: додаток на С++

У статті ми автоматизуємо процес обчислення коренів рівнянь, написавши консольний додаток мовою C++. Розробляти його ми будемо у Visual C++ 2010 Express, це безкоштовне і дуже зручне середовище розробки С++.

Для початку запустимо Visual C++ 2010 Express. Відобразиться стартове вікно програми. У лівому кутку натиснемо "Створити проект".

Рис. 1. Початкова сторінка Visual C++ 2010 Express

У меню виберемо «Консольний додаток Win32», введемо ім'я додаток «Метод_Ньютона».

Рис. 2. Створення проекту

// Метод_Ньютона.cpp: визначає точку входу для консольної програми #include "stdafx.h" #include using namespace std; float f(double x) //повертає значення функції f(x) = x^2-2 float df(float x) //повертає значення похідної float d2f(float x) // значення другої похідної int _tmain(int argc, _TCHAR* argv) int exit = 0, i=0; // змінні для виходу та циклу double x0, xn; // наближення, що обчислюються, для кореня double a, b, eps;// межі відрізка та необхідна точність cout<<"Please input \n=>"; cin>>a>>b; // вводимо межі відрізка, у якому шукатимемо корінь cout<<"\nPlease input epsilon\n=>"; cin>>eps; // вводимо потрібну точність обчислень if (a > b) // якщо користувач переплутав межі відрізка, міняємо їх місцями if (f(a)*f(b)>0) // якщо знаки функції на краях відрізка однакові, то тут немає кореня cout<<"\nError! No roots in this interval\n"; if (f(a)*d2f(a)>0) x0 = a; // для вибору початкової точки перевіряємо f(x0)*d2f(x0)>0? xn = x0-f(x0)/df(x0); // вважаємо перше наближення cout<<++i<<"-th iteration = "< while(fabs(x0-xn) > eps) // доки досягнемо необхідної точності, буде продовжувати обчислювати xn = x0-f(x0)/df(x0); // безпосередньо формула Ньютона cout<<++i<<"-th iteration = "< cout<<"\nRoot = "< cout<<"\nExit?=>"; ) while (exit! = 1); // Поки користувач не ввів exit = 1

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

Якщо відбувається помилка компіляції «Помилка error LNK1123: збій при перетворенні в COFF: файл неприпустимий або пошкоджений», це лікується або установкою першого Service pack 1, або в налаштуваннях проекту Властивості -> Компонувальник відключаємо інкрементне компонування.

Рис. 4. Вирішення помилки компіляції проекту

Ми будемо шукати коріння у функції f(x) =x2-2.

Спочатку перевіримо роботу програми на неправильних вхідних даних. На відрізку немає коріння, наша програма має видати повідомлення про помилку.

У нас з'явилося вікно:

Рис. 5. Введення вхідних даних

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

Рис. 6. Помилка «На цьому відрізку коріння немає!»

Виходити ми поки що не збираємося, тому на повідомлення «Exit?» вводимо "0".

Тепер перевіримо роботу програми на коректні вхідні дані. Введемо відрізок та точність 0.0001.

Рис. 7. Обчислення кореня з необхідною точністю

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

Щоб вийти з програми, введемо "Exit?" => 1.

Метод сіючих

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

Ітераційний процес має вигляд:

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

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

Ця чудова величина називається золотим перетином:

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

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

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

Після підстановки маємо: і

Для збіжності необхідно, щоб було позитивним, тому .

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

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

Щойно почнеться зростання, обчислення припиняють та останню ітерацію не використовують.

Така процедура визначення моменту закінчення ітерацій називається прийомом Гарвіка.

Метод парабол

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

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

У формі Ньютона вона має вигляд:

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

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

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

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

Метод простих ітерацій

Завдання знаходження рішень рівнянь можна формулювати як задачу знаходження коріння: , або як задачу знаходження нерухомої точки.

Нехай і - стиснення: (зокрема, той факт, що - стиснення, як легко бачити, означає, що).

По теоремі Банаха існує і єдина нерухома точка

Вона може бути знайдена як межа простої ітераційної процедури

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

Якщо функція диференційована, то зручним критерієм стиснення є . Справді, за теоремою Лагранжа

Отже, якщо похідна менше одиниці, є стиском.

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

Нехай корінь рівняння f(x)=0 відділений на відрізку , причому перша та друга похідні f’(x) і f""(x)безперервні та знакопостійні при хÎ.

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

x = х n + h n. (1.2.3-6)

Вважаючи h nмалою величиною, представимо f(х n + h n) у вигляді ряду Тейлора, обмежуючись лінійними доданками

f(хn+hn) »f(хn) + hnf'(хn). (1.2.3-7)

Враховуючи, що f(x) = f(хn+hn) = 0, отримаємо f(хn) + hnf '(хn)» 0.

Звідси h n »- f (х n) / f ' (х n). Підставимо значення h nв (1.2.3-6) і замість точного значення кореня xотримаємо чергове наближення

Формула (1.2.3-8) дозволяє отримати послідовність наближень x,тобто

Геометрична інтерпретація методу Ньютонаполягає в наступному
(Рис.1.2.3-6). Приймемо за початкове наближення x 0 правий кінець відрізка b і у відповідній точці 0 на графіку функції y = f(x) побудуємо дотичну. Крапка перетину дотичної з віссю абсцис приймається за нове точніше наближення х 1 . Багаторазове повторення цієї процедури дозволяє отримати послідовність наближень х 0, х 1, х 2 , . . ., яка прагне точного значення кореня x.

Розрахункова формула методу Ньютона (1.2.3-8) можна отримати з геометричного побудови. Так у прямокутному трикутнику х 0 В 0 х 1 катет
х 0 х 1 = х 0 0 /tga. Враховуючи, що точка 0 знаходиться на графіку функції f(x),а гіпотенуза утворена дотичною до графіка f(x) у точці В 0 отримаємо

(1.2.3-9)

(1.2.3-10)

Ця формула збігається з (1.2.3-8) для n-го наближення.

З рис.1.2.3-6 видно, що вибір як початкового наближення точки а може призвести до того, що наступне наближення х 1 виявиться поза відрізком , на якому відділений корінь x. І тут збіжність процесу не гарантована. У загальному випадку вибір початкового наближення проводиться відповідно до наступного правила: за початкове наближення слід прийняти таку точку х 0 Î, у якій f(х 0)×f''(х 0)>0, тобто знаки функції та її другий похідний збігаються.

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

Якщо корінь рівняння відокремлений на відрізку, причому f'(х 0)і f''(х) відмінні від нуля і зберігають свої знаки прихÎ, то, якщо вибрати як початкове наближення таку точкух 0 Î , що f(х 0).f¢¢(х 0)>0 , то корінь рівняння f(x)=0 може бути обчислений з будь-яким ступенем точності.

Оцінка похибки методу Ньютона визначається так:

(1.2.3-11)

де - найменше значення при

Найбільше значення при

Процес обчислень припиняється, якщо ,

де - задана точність.

Крім того, умовою досягнення заданої точності при уточненні кореня методом Ньютона можуть бути такі вирази:

Схема алгоритму методу Ньютона наведено на рис. 1.2.3-7.

Ліва частина вихідного рівняння f(x) та її похідна f'(x) в алгоритмі оформлені у вигляді окремих програмних модулів.

Рис. 1.2.3-7. Схема алгоритму методу Ньютона

Приклад 1.2.3-3.Уточнити методом Ньютона корені рівняння x-ln(x+2) = 0 за умови, що коріння цього рівняння відокремлено на відрізках x 1 Î[-1.9;-1.1] та x 2 Î [-0.9;2 ].

Перша похідна f'(x) = 1 – 1/(x+2) зберігає свій знак кожному з відрізків:

f'(x)<0 при хÎ [-1.9; -1.1],

f’(x)>0 при хÎ [-0.9; 2].

Друга похідна f"(x) = 1/(x+2) 2 > 0 за будь-яких х.

Отже, умови збіжності виконуються. Оскільки f""(x)>0на всій області допустимих значень, то для уточнення кореня за початкове наближення x 1виберемо х 0 =-1,9 (оскільки f(-1,9)×f”(-1.9)>0). Отримаємо послідовність наближень:

Продовжуючи обчислення, отримаємо наступну послідовність перших чотирьох наближень: -1.9; -1.8552, -1.8421; -1.8414 . Значення функції f(x) у точці x=-1.8414 і f(-1.8414)=-0.00003 .

Для уточнення кореня x 2 Î[-0.9;2] виберемо як початкове наближення 0 =2 (f(2)×f”(2)>0). З х 0 = 2, отримаємо послідовність наближень: 2.0;1.1817; 1.1462; 1.1461. Значення функції f(x) у точці x=1.1461 і f(1.1461)= -0.00006.

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

Метод хорд

Геометрична інтерпретація методу хордполягає в наступному
(Рис.1.2.3-8).

Проведемо відрізок прямої через точки A та B. Чергове наближення x 1 є абсцисою точки перетину хорди з віссю 0х. Побудуємо рівняння відрізка прямої:

Покладемо y = 0і знайдемо значення х = х 1 (чергове наближення):

Повторимо процес обчислень для отримання чергового наближення до кореня - х 2 :

У разі (рис.1.2.11) і розрахункова формула методу хорд матиме вигляд

Ця формула справедлива, коли за нерухому точку приймається точка b, а як початкове наближення виступає точка a.

Розглянемо інший випадок (рис. 1.2.3-9), коли .

Рівняння прямої для цього випадку має вигляд

Чергове наближення х 1 за y = 0

Тоді рекурентна формула методу хорд для цього випадку має вигляд

Слід зазначити, що за нерухому точку методу хорд вибирають той кінець відрізка , для якого виконується умова f (x)∙f¢¢ (x)>0.

Таким чином, якщо за нерухому точку прийняли точку а , то як початкове наближення виступає х 0 = b, і навпаки.

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

Оцінка похибки методу хорд визначається виразом

(1.2.3-15)

Умова закінчення процесу ітерацій за методом хорд

(1.2.3-16)

Якщо M 1<2m 1 , то для оценки погрешности метода может быть использована формула | x n -x n -1 |£e.

Приклад 1.2.3-4. Уточнити корінь рівняння e x - 3x = 0, відокремлений на відрізку з точністю 10 -4.

Перевіримо умову збіжності:

Отже, за нерухому точку слід вибрати а=0, а як початкове наближення прийняти х 0 =1, оскільки f(0)=1>0 і f(0)*f"(0)>0.

Метод Ньютона (дотичних) для пошуку коренів

Це ітераційний метод, винайдений Ісааком Ньютоном(Isaak Newton) близько 1664 р. Втім, іноді цей метод називають методом Ньютона-Рафсона (Raphson), оскільки Рафсон винайшов той самий алгоритм на кілька років пізніше за Ньютона, проте його стаття була опублікована набагато раніше.

Завдання полягає у наступному. Дано рівняння:

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

Алгоритм

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

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

Неважко отримати таку формулу:

Інтуїтивно ясно, що якщо функція досить "хороша" (гладка), а знаходиться досить близько від кореня, то буде ще ближче до шуканого кореня.

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

Застосування для обчислення квадратного кореня

Розглянемо метод Ньютона з прикладу обчислення квадратного кореня.

Якщо підставити, то після спрощення виразу отримуємо:

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

double n; cin >> n; const double EPS = 1E-15; double x = 1; for (;; ) ( double nx = (x + n / x) / 2; if (abs (x - nx)< EPS) break ; x = nx; } printf ("%.15lf" , x) ;

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

int n; cin >> n; int x = 1; bool decreased = false; for (;; ) ( int nx = (x + n / x) >> 1 ; if (x == nx || nx > x && decreased) break ; decreased = nx< x; x = nx; } cout << x;

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

BigInteger n; // вхідні дані BigInteger a = BigInteger.ONE .shiftLeft (n.bitLength () / 2); boolean p_dec = false; for (;; ) ( BigInteger b = n.divide (a) .add (a) .shiftRight (1 ) ; if (a.compareTo (b) == 0 || a.compareTo (b)< 0 && p_dec) break ; p_dec = a.compareTo (b) >0; a = b; )

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

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

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

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

Постановка задачі

В даному випадку є функція g, яка задана на відрізку (a, b) і набуває на ньому певних значень, тобто кожному x, що належить (a, b) можна порівняти конкретне число g(x).

Потрібно встановити всі корені рівняння з проміжку між точками a та b (включаючи кінці), для яких функція обнулюється. Вочевидь, що це точки перетину y = g(x) з ОХ.

У деяких випадках зручніше замінити g(x)=0 на аналогічне виду g 1 (x) = g 2 (x). У такому разі як коріння виступають абсциси (значення x) точок перетину графіків g 1 (x) і g 2 (x).

Рішення нелінійного рівняння важливе і для задач оптимізації, для яких умова локального екстремуму - звернення до 0 похідної функції. Іншими словами, таке завдання може звестися до пошуку коренів рівняння p(x) = 0, де p(x) тотожна g"(x).

Методи вирішення

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

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

До них належить і так званий чисельний метод дотичних. Останній був запропонований великим ученим Ісааком Ньютоном наприкінці XVII століття. У наступні століття спосіб неодноразово вдосконалювався.

Локалізація

Численні способи розв'язання складних рівнянь, що не мають аналітичних рішень, прийнято здійснювати у 2 етапи. Спочатку потрібно їх локалізувати. Ця операція полягає у знаходження таких відрізків на ОХ, на яких існує один корінь розв'язуваного рівняння.

Розглянемо відрізок. Якщо g(x) на ньому не має розривів і приймає в кінцевих точках значення різних знаків, то між a та b або в них самих розташований принаймні 1 корінь рівняння g(x) = 0. Щоб він був єдиним, потрібно, щоб g(x) була монотонною. Як відомо, такою властивістю вона матиме за умови знакопостійності g'(x).

Говорячи інакше, якщо на g(x) не має розривів і монотонно зростає або зменшується, а її значення в кінцевих точках мають не однакові знаки, то існує 1 і тільки 1 корінь g(x).

У цьому слід знати, що це критерій нічого очікувати діяти коріння рівнянь, є кратными.

Рішення рівняння поділом навпіл

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

Для виявлення потрібно поділити відрізок навпіл і позначити середню точку як x 2 . Тоді можливі два варіанти: g(x 0) * g(x 2) або g(x 2) * g(x 1) дорівнюють або менше 0. Вибираємо той, для якого правильне одне з цих нерівностей. Повторюємо процедуру, описану вище, поки довжина стане меншою від певної, заздалегідь обраної величини, що визначає точність визначення кореня рівняння на .

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

Приклад 1

Нехай ми хочемо вирішити рівняння g(x) = 2x 5 + x - 1 = 0. Щоб довго не шукати відповідний відрізок, будуємо графік, використовуючи, наприклад, відому програму "Ексель". Ми бачимо, що як відрізок для локалізації кореня краще брати значення проміжку . Ми можемо бути впевнені, що хоча б один корінь рівняння на ньому є.

g"(x) = 10x 4 + 1, тобто це монотонно зростаюча функція, тому на вибраному відрізку є лише 1 корінь.

Підставляємо кінцеві точки рівняння. Маємо 0 та 1 відповідно. На першому кроці за рішення беремо точку 0,5. Тоді g(0,5) = -0,4375. Отже, наступний відрізок для поділу навпіл буде. Його серединна точка – 0,75. У ньому значення функції дорівнює 0,226. Беремо до розгляду відрізок та її середину, що у точці 0,625. Обчислюємо значення g(x) 0,625. Воно одно -0,11, тобто негативне. Спираючись на цей результат, вибираємо відрізок. Отримуємо x = 0,6875. Тоді g(x) = –0,00532. Якщо точність рішення 0,01, можемо вважати, що шуканий результат дорівнює 0,6875.

Теоретична база

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

Він заснований на тому доведеному факті, що якщо x n — наближення до кореня f(x)=0, такому, що f" C 1 то наступна апроксимація буде в точці, де обнулюється рівняння дотичної до f(x), тобто.

Підставляємо x = x n+1 та обнулюємо y.

Тоді дотичних виглядає так:

Приклад 2

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

Нехай потрібно виявити коріння для x 3 + 4x – 3 = 0 з деякою точністю, наприклад 0,001. Як відомо, графік будь-якої функції як многочлена непарної ступеня повинен хоча б раз перетинати вісь ОХ, т. е. сумніватися у існуванні коренів годі й говорити.

Перш ніж вирішити наш приклад методом дотичних, будуємо графік f (x) = x 3 + 4x - 3 поточково. Це дуже легко зробити, наприклад, використовуючи табличний процесор "Ексель". З отриманого графіка буде видно, що відбувається його перетин з віссю ОХ і функція y = x 3 + 4x - 3 монотонно зростає. Ми можемо бути впевнені, що на рівняння х 3 + 4х - 3 = 0 має рішення і воно єдине.

Алгоритм

Будь-яке рішення рівнянь методом дотичних починається з обчислення f"(x). Маємо:

Тоді друга похідна матиме вигляд x*6.

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

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

то якщо нас цікавить рішення методом дотичних з точністю e, то значення x n можна вважати задовольняючим вимогам завдання, за умови виконання нерівності | f (x n) / f ' (x n) |< e.

На першому етапі дотичних маємо:

• x 1 = x 0 - (x 0 3 + 4x 0 - 3) / (3x 0 2 + 4) = 1-0,2857 = 0,71429;
• оскільки умова не виконується, йдемо далі;
• отримуємо нове значення для x 2 яке дорівнює 0,674;
• помічаємо, що відношення значення функції до її похідної x 2 менше 0,0063, припиняємо процес.

Метод дотичних до Excel

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

Для цього в "Ексель" потрібно створити нову сторінку та заповнити її осередки наступними формулами:

• в C7 записуємо «= Ступінь (B7; 3) + 4 * B7 - 3»;
• в D7 вписуємо "= 4 + 3 * СТУПЕНЬ (B7; 2)";
• в E7 записуємо «= (СТУПЕНЬ (B7; 3) - 3 + 4 * B7) / (3 * СТУПЕНЬ (B7; 2) + 4)»;
• в D7 вписуємо вираз "=В7 - Е7";
• у B8 вписуємо формулу-умову «= ЯКЩО(Е7< 0,001;"Завершение итераций"; D7)».

У конкретній задачі вже в осередку B10 з'явиться напис «Завершення ітерацій», і за розв'язання задачі потрібно буде взяти число, записане в осередку, розташованому на один рядок вище. Для нього можна виділити і окремий стовпець, що «розтягується», ввівши там формулу-умову, згідно з якою там буде записаний результат, якщо вміст в тому чи іншому осередку стовпця B набуде вигляду «Завершення ітерацій».

Реалізація у Pascal

Спробуємо отримати рішення нелінійного рівняння y = х 4 - 4 - 2 * х методом дотичних у Паскалі.

Використовуємо допоміжну функцію, яка допоможе здійснити наближене обчислення f"(x) = (f(x + delta) - f(x)) / delta. Як умову для завершення ітераційного процесу виберемо виконання нерівності | x 0 - x 1 |< некого малого числа. В Паскале его запишем, как abs(x0 - x1)<= epsilon.

Програма примітна тим, що вимагає ручного обчислення похідної.

Метод хорд

Розглянемо ще один спосіб виявлення коренів нелінійних рівнянь. Процес ітерацій полягає в тому, що як послідовні наближення до шуканого кореня для f(x)=0 приймають значення точок перетину хорди з абсцисами кінцевих точок a і b з ОХ, що позначаються, як х 1 , ..., х n . Маємо:

Для точки, де хорда перетинається з віссю ОХ, вираз запишеться, як:

Нехай друга похідна позитивна при х £ (Протилежний випадок зведеться до аналізованого, якщо записати-f(x) = 0). У такому разі графік у = f(x) - крива, опукла внизу та розташована нижче хорди AB. Можуть бути 2 випадки: коли функція має позитивне значення в точці a або вона негативне в точці b.

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

У другий випадок нерухомим є кінець b при x 0 = a. Значення х, отримані кожному етапі ітерації, утворюють послідовність, яка монотонно зростає.

Таким чином, можемо констатувати, що:

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

Ітерації можна продовжувати, доки не виконається умови близькості коріння на цьому та попередньому ітераційному кроці за модулем abs(x m - x m - 1)< e.

Модифікований спосіб

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

Припустимо, необхідно знайти коріння f(x)=0, якщо вони є на . Можна застосувати будь-який із описаних вище способів. Однак краще спробувати їхню комбінацію, завдяки чому значно підвищиться точність кореня.

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

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

Використовуються формули:

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

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

Як умову використовується оцінна нерівність | b n +1 - a n +1 |< e. Иными словами, на практике приходится находить решение при помощи двух методов, но на каждом шаге требуется выяснять, насколько полученные результаты близки друг другу.

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

Комбінований метод легко реалізується серед TURBO PASCAL. За великого бажання можна спробувати здійснити всі обчислення табличним методом у програмі "Ексель".

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

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

Тепер ви знаєте, як розв'язувати складні рівняння. Метод дотичних, як ви вже бачили, реалізується досить просто як у Паскалі, так і в "Екселі". Тому ви завжди зможете встановити коріння рівняння, яке складно чи неможливо вирішити за допомогою формул.

Те саме, що апроксимація. Термін П. іноді вживається в сенсі наближувального об'єкта (напр., Початкове П.). Математична енциклопедія

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

Метод однієї дотичної

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

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

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

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

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

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

Чисельне рішення рівнянь- та їх систем полягає у наближеному визначенні кореня чи коріння рівняння чи системи рівнянь і застосовується у випадках, коли точне значення обчислити неможливо чи дуже трудомістко. Зміст 1 Постановка задачі 2 Чисельні ме … Вікіпедія

Послідовне наближення методу- метод розв'язання математичних завдань за допомогою такої послідовності наближення, яка сходиться до розв'язання і будується рекурентно (тобто кожне нове наближення обчислюють, виходячи з попереднього; початкове наближення вибирається в… Велика Радянська Енциклопедія