Метод ділення проміжку навпіл

Поможем в ✍️ написании учебной работы

Имя

Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Нажимая кнопку "Продолжить", я принимаю политику конфиденциальности

Нехай і відомо, що рівняння (1) має єдиний корінь . Покладемо a₀=a, b₀=b, x₀=(a₀+b₀)/2. Якщо , то . Якщо , то покладемо

(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) з будь-якою степінню точності.