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

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

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

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

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

    

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

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

.

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

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

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

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

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

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

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

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

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

    

     4.3.2 Метод хорд

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

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

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

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

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

          (4.4)

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

          (4.5)

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

     .

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

          (4.6)

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

          (4.7)

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

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

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

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

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

    

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

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

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

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

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

     4.3.3 Метод Ньютона (метод дотичних)

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

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

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

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

     .

Перший випадок. Нехай f(a)<0, f(b)>0, fў(x)>0, f''(x)>0 (рис. 4.13, а) або f(a)>0, f(b)<0, f'(x)<0, f''(x)<0 (рис. 4.11, б). Проведемо дотичну до кривої в точці B₀(v; f(b)) і знайдемо абсцису точки перетину дотичної з віссю . Відомо, що рівняння дотичної в точці B₀(b; f(b)) має вид: y-f(b)=f'(b) (x-b).

Припускаючи y=0, x=x₁, отримаємо

          (4.8)

Тепер корінь рівняння знаходиться на відрізку [a, x₁]. Застосовуючи знову метод Ньютона, проведемо дотичну до кривої в точці B₁(x₁; f(x₁)) і отримаємо

     ,

і так далі (рис. 4.13).

    

а) функція, яка досліджується, ввігнута (f'(x)>0, f''(x)>0)

б) функція, яка досліджується, опукла (f'(x)<0, f''(x)<0)

Даний процес ітераційний, тому формула для будь-якого n-го кроку ітерації має вигляд:

     .     (4.9)

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

Другий випадок. Нехай f(a)<0, f(b)>0, fў(x)>0, fўў(x)<0 (рис. 4.14, а) або f(a)>0, f(b)<0, f'(x)<0, f''(x)>0 (рис. 4.14).

    

а) функція, яка досліджується, опукла (f'(x)>0, f''(x)<0)

б) функція, яка досліджується, ввігнута (f'(x)<0, f''(x)>0)

Якщо провести дотичну до кривої в точці B, то вона перетне вісь абсцис в точці, яка не належить відрізку . Тому проведемо дотичну в точці А₀(a; f(a)) і запишемо її рівняння для даного випадку: y - f(a) = f'(a) (x - a).

Припускаючи, що y = 0, x = x₁, отримаємо

          (4.10)

Корінь x знаходиться тепер на відрізку [x₁, b]. Застосовуючи знову метод Ньютона, проведемо дотичну до кривої в точці A₁(x₁; f(x₁)) і отримаємо

     ,

     і загалом     .     (4.11)

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

Порівнюючи формули (4.10), (4.11) з раніше виведеними, (а також враховуючи випадки, які розглядаються на рисунках 4.14а,б помічаємо, що вони відрізняються одна від одної тільки вибором початкового наближення: в першому випадку за x₀ приймався кінець b відрізка, в другому - кінець а.

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

Для оцінки похибки можна користуватися загальною формулою

     ,     (4.12)

де (ця формула підходить і до метода хорд).

В тому випадку, коли відрізок настільки малий, що на ньому виконується умова М₂<2m₁ , де M₂, а , точність наближення на n-му кроці інтерполяційного процесу оцінюється наступним чином: якщо .

Якщо похідна f'(x) мало змінюється на відрізку , то для спрощення обчислень можна користуватися формулою

     ,     (4.13)

тобто значення похідної в початковій точці достатньо обчислити тільки один раз.

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

    

     Правила визначення рухомого кінця для метода Ньютона

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

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

     4.3.4 Комбінований метод

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

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

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

Використаємо комбінований метод хорд і дотичних з урахуванням поведінки функції на відрізку . Якщо f'(x)Чf''(x)>0, то метод хорд дає наближення кореня з недостачею, а метод дотичних – з залишком (рис.4.16.а,б). Якщо ж f'(x)Чf''(x)<0, то методом хорд отримуємо значення

    

методом дотичних – з недостачею (рис.4.16.в,г). Однак в усіх випадках справжній корінь знаходиться між наближеними коренями, які отримані за методом хорд і методом дотичних, тобто виконується нерівність а< х_n < x < х_n<b, де х_n – наближене значення кореня з недоліком, `- з надлишком.

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

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

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

     .     (4.14)

Для методу дотичних рухомим є кінець , і наближене значення кореня обчислюється за формулою дотичних:

     .     (4.15)

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

     .     (4.16)

Для методу дотичних рухомим є кінець a, і наближене значення кореня обчислюється за формулою дотичних:

     .     (4.17)

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

Схема алгоритму методу представлено на рисунку 4.17.

    

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

Суть методу полягає у заміні початкового рівняння

          (4.18)

еквівалентним йому рівнянням

     ,     (4.19)

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

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

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

Приведемо без доказу теорему, яка виражає умову, при якій ітераційний процес розв’язку нелінійного рівняння методом ітерацій на ЕОМ збігається.

    

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

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

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

    

Таким чином, необхідна точність буде досягнута, якщо виконується нерівність |х_n – x_{n - 1} | 0,00002. За нульове наближення можна прийняти будь-який із кінців відрізка (-0,725; -0,7) і будь-яку точку усередині нього. Нехай х₀= -0,7. Обчислення зводимо в наступну таблицю:

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

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

Розглянемо алгоритм методу Ньютона.

Нехай дана система нелінійних рівнянь виду

          (4.20)

де – неперервно-диференційні функції.

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

члени рядів вищих порядків ( тощо).

1. Початкова система буде мати вигляд:

     (4.21)

2. Припустимо, що прирости вибрані таким чином, що точки з координатами є коренями даної системи рівнянь з заданим степенем наближення . Тоді ліву частину рівнянь системи (4.21) можна прирівняти до нуля, тобто система рівнянь (4.21) буде мати вигляд:

          (4.22)

Або в матричній формі система (4.22) буде мати вигляд:

          (4.23)

     де – матриця Якобі .

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

     ,

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

          (4.24)

Дану задачу можна розв'язати з будь-якої точки, вибравши вектор початкових наближень.

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

Схема алгоритму метода Ньютона представлена на рисунку 4.20.

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

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

Розв’язок. Для того, щоб розв’язати дану систему нелінійних рівнянь методом Ньютона необхідно перетворити систему до вигляду (4.23). Для цього знайдемо спочатку частині похідні всіх рівнянь системи в початкової точці для формування матриці Якобі, яка буде мати вигляд:

За допомогою програми, що складена відповідно алгоритму, який представлений на рисунку 4.20, для знаходження вектора розв’язку Х багаторазово методом Гауса розв’яжемо на ЕОМ систему виду:

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

В результаті можна отримати наступні результати:

     Література

1. Щуп Т. Решение инженерных задач на ЕВМ. – М.: Мир, 1982. – 235с.

2. Демидович Б. П., Марон И. А. Основы вычислительной математики. – М.: Наука, 1970. – 664 с.

3. Демидович Б. П., Марон И. А., Шувалова Е. З. Численные методы анализа. – М.: Мир, 1967

4. Мак – Кракен Д., Дрон У. Численные методы и програмирование на фортране. – М.: Мир, 1977. – 584 с.

5. Бахвалов Н. С. Численные методы . Т. И. Анализ, алгебра, обычные диференциальные уравнения. – М.: Наука, 1975. – 631 с.

6. Краскевич В. Є., Зеленський К. Х., Гречко В. И. Численные методы в инженерных исследованиях. – К.: Высшая шк.., 1986. – 263 с.

7. Рисс Ф., Секефальви – Надь Б. Лекции по функциональному анализу – М.: Мир, 1979.

8. Плис А.И., Сливина Н.А. Mathcad. Математический практикум для инженеров и экономистов: – М.: Финансы и статистика, 2003. – 656с.

9. В.И. Бердышев, Ю.Н. Субботин. Численные методы приближения функций. – Средне-Уральское книжное книжное издательство, 1979.

10. Ортега Дж., Рейнболдт В. Итерационные методы решения нелинейных систем уравнений со многими неизвестными. – М.: Мир, 1975. – 558 с.

     Питання та задачі до самостійної роботи

1. Які рівняння відносяться до нелінійних?

2. Які рівняння відносяться до трансцендентних?

3. Що є розв‘язком нелінійного рівняння?

4. Відокремити корені рівняння

,

5. Класифікація рівнянь, трансцендентні та алгебраїчні рівняння.

6. Які рівняння відносяться до трансцендентних рівнянь?

7. Які рівняння відносяться до алгебраїчних рівнянь?

8. Суть відокремлення коренів нелінійних рівнянь.

9. Суть методів уточнення коренів.

10. Які способи використовуються для відокремлення коренів?

11. В чому суть аналітичного методу відокремлення коренів?

12. Які теореми використовуються для аналітичного методу відокремлення коренів?

13. В чому суть алгоритму методу половинного ділення? Дайте геометричну інтерпретацію цього методу.

14. Графічна інтерпретація методу половинного ділення та основні формули методу.

15. В чому суть алгоритму методу хорд? Дайте геометричну інтерпретацію цього методу.

16. Графічна інтерпретація методу хорд та основні формули методу.

17. В чому суть алгоритму методу січних? Дайте геометричну інтерпретацію цього методу.

18. Графічна інтерпретація методу січних та основні формули методу.

19. В чому суть алгоритму комбінованого методу? Дайте геометричну інтерпретацію цього методу.

20. Графічна інтерпретація комбінованого методу та основні формули.

21. В чому суть алгоритму автоматизації пошуку рухомого кінця хорди?

22. В чому суть алгоритму автоматизації пошуку рухомого кінця січної?

23. Покажіть особливості методу ітерацій та його обмеження.

24. Графічна інтерпретація методу ітерацій та основні формули методу.

25. Розробить підпрограму - функцію для уточнення коренів нелінійного рівняння методом ітерацій.26. 

< Зміст >