Розробка програми мовою програмування С++ по пошуку коренів нелінійних рівнянь (стр. 2 из 4)

(2)

(3)

(4)

і обчислимо

. Якщо , то ітераційний процес зупинимо і будемо вважати, що . Якщо , то повторюємо розрахунки за формулами (2)-(4).

З формул (2), (3) видно, що

і . Тому , а отже шуканий корінь знаходиться на проміжку . При цьому має місце оцінка збіжності

. (5)

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

. (6)

де [c] - ціла частина числа c.

Серед переваг даного методу слід відзначити простоту реалізації та надійність. Послідовність {x_n} збігається до кореня

для довільних неперервних функцій f(x). До недоліків можна віднести невисоку швидкість збіжності методу та неможливість безпосереднього узагальнення систем нелінійних рівнянь.

Метод простої ітерації

Метод простої ітерації застосовується до розв’язування нелінійного рівняння виду

. (7)

Перейти від рівняння (1) до рівняння(7) можна багатьма способами, наприклад, вибравши

, (8)

де

- довільна знакостала неперервна функція.

Вибравши нульове наближення x₀, наступні наближення знаходяться за формулою

. (9)

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

Теорема 1. Нехай для вибраного початкового наближення x₀ на проміжку

(10)

функція j(x) задовольняє умові Ліпшиця

(11)

де 0<q<1, і виконується нерівність

. (12)

Тоді рівняння (7) має на проміжку S єдиний корінь

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

. (13)

Зауваження: якщо функція j(x) має на проміжку S неперервну похідну

, яка задовольняє умові

, (14)

то функція j(x) буде задовольняти умові (11) теореми 1.

З (13) можна отримати оцінку кількості ітерацій. які потрібно провести для знаходження розв’язку задачі (7) з наперед заданою точністю e:

. (15)

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

. (16)

Метод релаксації

Для збіжності ітераційного процесу (9) суттєве значення має вибір функції j(x). Зокрема, якщо в (8) вибрати

, то отримаємо метод релаксації.

, (17)

який збігається при

. (18)

Якщо в деякому околі кореня виконуються умови

, (19)

то метод релаксації збігаються при

. Збіжність буде найкращою при

. (20)

При такому виборі t для похибки

буде мати місце оцінка

, (21)

де

.

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

. (22)

Зауваження: якщо виконується умова

, то ітераційний метод (17) потрібно записати у вигляді

.

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

Метод Ньютона застосовується до розв’язування задачі (1), де f(x) є неперервно-диференційованою функцією. На початку обчислень вибирається початкове наближення x₀. Наступні наближення обчислюються за формулою

. (23)

З геометричної точки зору x_n+1 є значенням абсциси точки перетину дотичної до кривої y=f(x) в точці (x_n, f(x_n)) з віссю абсцис. Тому метод Ньютона називають також методом дотичних.

Теорема 2. Якщо

не змінює знака на [a,b], то виходячи з початкового наближення , що задовольняє умові , можна обчислити методом Ньютона єдиний корінь рівняння (1) з будь-якою степінню точності.

Теорема 3. Нехай

- простий дійсний корінь рівняння (1) і , де ,

, (24)

причому

. (25)

Тоді для

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

. (26)

З оцінки (26) видно, що метод Ньютона має квадратичну збіжність, тобто похибка на (n+1)-й ітерації пропорційна квадрату похибки на n-й ітерації.

Модифікований метод Ньютона

(27)

дозволяє не обчислювати похідну

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

Кількість ітерацій, які потрібно провести для знаходження розв’язку задачі (1) з точністю e задовольняє нерівності

. (28)

1.1 Розробка методу виконання основного завдання

Розглянемо один з найпростіших методів уточнення відділеного кореня – метод половинного ділення.

Обчислюємо значення f(x) в середині відрізка [a;b], тобто в точці

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

Зрозуміло, що другий етап наближеного відшукання кореня бажано виконувати за допомогою комп’ютера.

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

ввід інтервалу (a;b) та потрібної точності (D)

поки |a-b| < D виконувати

пц

якщо f(a)×f(b) > 0

то a:=c

інакше b:=c

кц

вивід значення кореня

1.2 Структура даних і функцій

Згідно завдання наш проект складається з 4 додаткових модулів, та основного модуля, в якому міститься головна функція main() нашого проекту.