9) Метод хорд

Метод хорд (метод лінійного інтерполювання)

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

Рис.3.3.

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

З’єднаємо точки А(а, f(а)) та B(b, f(b)), відрізком прямої. Очевидно, що точка x₁ перетину цього відрізка з віссю ОХ розташована ближче до кореня порівняно з кінцями відрізка. Взявши цю точку за наступне наближення, можна продовжити далі, побудувавши x₂ x₃....

, де (*)

Нерухомою точкою в цьому методі є той із кінців відрізка ізоляції, в якому знак функції збігається зі знаком другої похідної. На рис.3.3 це точка В (значення функції f(B) та знак другої похідної f’’(B) – функція опукла вниз – додатні).

Теорема (достатні умови збіжності за методом хорд). Нехай на відрізку [a,b] функція у=f(x) неперервна разом зі своїми похідними сталого знаку до другого порядку включно і на кінцях відрізка приймає значення різних знаків. Тоді існує окіл точки х*, в якому для будь-якого початкового наближення х₀ ітераційна послідовність (*) збігається до кореня х*.

Доведення приведене в [5,9].

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

10) Метод дотичних

Метод Ньютона або метод дотичних

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

Розкладемо функцію f(x) в ряд Тейлора в околі довільної точки x₀ відрізку [a,b].

f(x) = f(x₀) + f’(x₀) (x – x₀) + 0.5 f’’(x₀) (x – x₀)² + …

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

f(x₀)+f’(x₀) (x – x₀)= 0, звідки .

При обчисленні правої частини рівняння одержимо наближення x₁, потім – наближення x₂ тощо(рис.3.2).. В результаті отримаємо ітераційну послідовність

.

Рис.3.2.

Теорема (достатні умови збіжності за методом Ньютона). Нехай на відрізку [a,b] функція у=f(x) має неперервні похідні сталого знаку до другого порядку включно і на кінцях відрізка приймає значення різних знаків. Тоді існує окіл точки х*, в якому для будь-якого початкового наближення х₀ ітераційна послідовність збігається до кореня х*.

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

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

Для застосування ітераційного методу рівняння f(x)=0 перетворюють до виду:

x=(x) (3.2)

При цьому процес уточнення кореня суттєво спрощується, якщо останнє рівняння вважати рекурсивним. Взявши деяке початкове значення x₀ і підставивши його в праву частину рівняння (3.2), можна отримати ітераційну послідовність:

x_k= (x_{k – 1}).

Графічну інтерпретацію ітераційних методів розв’язування рівняння зображено на рис.3.1 (а, б, в).

а) б)

в)

Рис.3.1.

Збіжність ітераційної послідовності x_k= (x_{k – 1}), тобто існування границі забезпечує наступна теорема.

Теорема Ліпшиця (достатня умова збіжності ітераційного процесу). Якщо функція у=(x), якою задана права частина рівняння x_k=(x_k-1), має корінь х* і в деякому околі U (U={x: |x-x*| ≤ r}) задовольняє умову Ліпшиця |(x) – (x*)| ≤ q |x-x*|, де q<1, то послідовність x_k збігається до кореня х*, починаючи з будь-якого х U. При цьому швидкість збіжності визначається нерівністю |x_k-x*| ≤ q^k |x₀-x*|