4.3 Чисельні методи уточнення коренів

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

  метод половинного ділення (метод бісекції);

  метод хорд (метод пропорційних частин);

  метод дотичних (метод Ньютона);

  комбінований метод (метод хорд та дотичних);

  метод ітерацій (метод послідовних наближень).

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

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

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

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

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

    

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

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

Метод половинного ділення – це найпростіший метод уточнення кореня рівняння. Він сходиться для будь-яких неперервних функцій , в тому числі недиференційованих. Швидкість сходження невелика

.

     Алгоритм методу

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

2. Перевіряємо чи , якщо так, то – точний корінь початкового рівняння і переходимо до пункту 6.

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

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

5. У цьому випадку за наближене значення кореня вибирають .

6. Вивід результатів. Кінець алгоритму.

7. Відомо, що при цьому похибка не перевищує , де – число ітерацій.

Схема алгоритму розв'язання нелінійного рівняння методом половинного ділення представлена на рисунку 4.10.

    

     Рисунок 4.10 – Схема алгоритму розв'язання нелінійного рівняння методом половинного ділення

4.3.2 Метод хорд

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

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

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

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

     Рисунок 4.11 – Графічна інтерпретація методу хорд і процедури визначення рухомого кінця хорди

Рівняння хорди, яка проходить через точки має вигляд

          (4.4)

Знайдемо значення , для якого , тобто для нерухомого кінця:

          (4.5)

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

     .

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

          (4.6)

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

          (4.7)

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

Слід відмітити, що розглянутий випадок (рис.4.11.а) перетину функції відрізку не є єдиним. Існує ще три варіанти перетину функції, кожний з яких відрізняється напрямком побудови хорд і відповідно рухомими кінцями відрізку. Наприклад, на рис.4.11.а,б рухомий кінець відрізку а, а на рис.4.11.в,г рухомий кінець – і відповідно формула 4.5 для нього має вигляд:

    

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

Правило 1. Нерухомим кінцем відрізка є той, для якого знак функції співпадає із знаком другої похідної. Якщо , то нерухомим є кінець , а всі наближення до кореня лежать зі сторони кінця . Якщо , то нерухомим є кінець , а всі наближення до кореня лежать зі сторони кінця (рис.4.11.а,б,в,г).

Правило 2. Якщо добуток першої на другу похідну функції більший за нуль: , то рухомий кінець ; якщо добуток першої на другу похідну менший за нуль: , то рухомий кінець .Схема алгоритму розв'язання нелінійного рівняння методом хорд представлена на рисунку 4.12.

    

     Рисунок 4.12 - Схема алгоритму розв'язання нелінійного рівняння методом хорд

     Особливості розробки функцій, які реалізують алгоритм методу

1. Метод половинного ділення та метод хорд розробляються як незалежні підпрограми-функції з вхідними параметрами: a, b, та вихідними: x, k, де x – наближене значення кореня, k– кількість ітерацій.

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

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

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