Львів
C
» » Метод січних: опис

Метод січних: опис

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


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

Постановка завдання

В даному випадку є функція 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 етапи. Спочатку потрібно їх локалізувати. Ця операція полягає в знаходження таких відрізків на ОХ, на яких існує один корінь вирішується рівняння.
Розглянемо відрізок[a,b]. Якщо g(x) на ньому не має розривів і приймає в кінцевих точках значення різних знаків, то між a і b, або в них самих розташований принаймні 1 корінь рівняння g(x) = 0. Щоб він був єдиним, потрібно, щоб g(x) на[a,b]була монотонною. Як відомо, такою властивістю вона буде мати за умови знакопостоянства g'(x). Інакше кажучи, якщо на[a,b]g(x) не має розривів і монотонно зростає або спадає, а її значення в кінцевих точках мають не однакові знаки, то на[a, b]існує 1 та лише 1 корінь g(x). При цьому слід знати, що цей критерій не буде діяти для коренів рівнянь, які є кратними.

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

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

Приклад 1

Нехай ми хочемо вирішити рівняння g(x) = 2x 5 + x - 1 = 0. Щоб довго не шукати відповідний відрізок, будуємо графік, використовуючи, наприклад, відому програму "Ексель". Ми бачимо, що в якості відрізка для локалізації кореня краще брати значення з проміжку[0,1]. Ми можемо бути впевнені, що хоча б один корінь шуканого рівняння на ньому є.
g'(x) = 10x 4 + 1 тобто це монотонно зростаюча функція, тому на обраному відрізку є тільки 1 корінь. Підставляємо кінцеві точки в рівняння. Маємо 0 і 1 відповідно. На першому кроці за рішення беремо точку 05. Тоді g(05) = -04375. Отже ,наступний відрізок для ділення навпіл буде[0,5, 1]. Його серединна точка - 075. В ній значення функції одно 0226. Беремо для розгляду відрізок[0,5, 0,75]і його середину, яка знаходиться в точці 0625. Обчислюємо значення g(x) в 0625. Воно одно -011 тобто негативне. Спираючись на цей результат, вибираємо відрізок [0,625, 0,75]. Отримуємо x = 06875. Тоді g(x) = -000532. Якщо точність рішення 001 то можемо вважати, що шуканий результат дорівнює 06875.

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

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

Приклад 2

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

Алгоритм

Будь-яке рішення рівнянь методом дотичних починається з обчислення f '(x). Маємо:
Метод січних: опис
Тоді друга похідна буде мати вигляд x * 6. Використовуючи ці вирази, можемо записати формулу для знаходження коренів рівняння за методом дотичних у вигляді:
Метод січних: опис
Далі потрібно вибрати початкове наближення, тобто зайнятися визначенням, яку точку вважати стартовою (про. x 0 ) для ітераційного процесу . Розглядаємо кінці відрізка[0,1]. Нам підійде той, для якого вірно умова разнознаковости функції та її 2-ої похідної в x 0 . Як бачимо, при підстановці x 0 = 0 воно порушене, а от x 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- 02857 = 071429;
  • оскільки умова не виконується, йдемо далі;
  • отримуємо нове значення x 2 , яка дорівнює 0674;
  • помічаємо, що відношення значення функції до її похідної в x 2 менше 00063 припиняємо процес.
  • Метод січних: опис

    Метод дотичних в 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)».
  • Далі потрібно «розтягнути» формули в стовпцях C, D і E спочатку на два рядки, а після того, як у них з'явилися значення, вступити також зі стовпцем Ст. В конкретній задачі вже в комірці 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 . Маємо:
    Метод січних: опис
    Для точки, де хорда перетинається з віссю ОХ вираз запишеться як:
    Метод січних: опис
    Нехай друга похідна додатна при х ?[a,b] (протилежний випадок зведеться до розглянутого, якщо записати 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 якщо вони є на[a, b]. Можна застосувати будь-який з описаних вище способів. Однак краще спробувати їх комбінацію, завдяки чому значно підвищиться точність кореня. Розглядаємо випадок з початковим наближенням, відповідає умові разнознаковости першої та другої похідної в конкретній точці х. В таких умовах рішення нелінійних рівнянь методом дотичних дозволяє знайти корінь з надлишком, якщо x 0 =b, а спосіб з використанням хорд при нерухомому кінці b приводить до знаходження наближеного кореня з нестачею. Використовуються формули:
    Метод січних: опис
    Тепер шуканий корінь х потрібно шукати в інтервалі[a1, b1]. На наступному кроці потрібно застосувати комбінований метод вже до цього відрізку. Діючи так далі, отримаємо формули виду:
    Метод січних: опис
    Якщо ж має місце разнознаковость першої та другої похідних, то, розмірковуючи аналогічним чином, для уточнення кореня отримаємо наступні рекурентні формули:
    Метод січних: опис
    В якості умови використовується оціночне нерівність| b n +1 - a n +1 | < e. Иными словами, на практике приходится находить решение при помощи двух методов, но на каждом шаге требуется выяснять, насколько полученные результаты близки друг другу. Якщо вищенаведене нерівність вірно, то в якості кореня нелінійного рівняння на заданому відрізку беруть точку, яка знаходиться рівно посередині між знайденими розв'язками на конкретному итерационном кроці. Комбінований метод легко реалізується в середовищі TURBO PASCAL. При великому бажанні можна спробувати здійснити всі обчислення табличним методом у програмі "Ексель". В останньому випадку виділяють по декілька стовпців для рішення задачі з використанням хорд і окремо для способу, запропонованого Ісааком Ньютоном. При цьому кожна рядок використовується для запису обчислень на конкретному итерационном крок за двома методами. Потім, в лівій частині від області рішення на активній робочій сторінці виділяється стовпець, в якому вписується результат обчислень модуля різниці значень чергового ітераційного кроку по кожному з методів. Ще один можна використовувати для внесення результатів обчислень за формулою розрахунку логічної конструкції «ЯКЩО», використовуваної для з'ясування, чи виконується умова чи ні.
    Метод січних: опис
    Тепер ви знаєте, як вирішувати складні рівняння. Метод дотичних, як ви вже бачили, реалізується досить просто, як у Паскалі, так і в "Ексель". Тому ви завжди зможете встановити корені рівняння, яке складно або неможливо вирішити за допомогою формул.