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

Якщо на проміжку похідна змінюєть­ся мало, то можна прийняти , і тоді (2.5) перетво­риться до вигляду

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

Рис. 2.4. Геометрична інтерпретація модифікованого методу Ньютона

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

Приклад 7. Знайти корінь рівняння модифікованим методом Ньютона.

Корінь належить проміжку Початкове наближенняТодідлямаємо:

Таблиця 2.4

Результати обчислень

k	0	1	2	3	4	5	6	7	8	9
	-2	-1,5455	-1,4443	-1,3911	-1,3637	-1,3480	-1,3388	-1,3333	-1,3299	-1,3279
	-	0,4545	0,1042	0,0502	0,0274	0,0157	0,0092	0,0005	0,00034	0,0020

Для маємо, а дляПорівняно з методом Ньютона збіжність сповільнюється.

2.4.2 Метод Ньютона-Бройдена

Метод дозволяє збільшити швидкість збіжності послідовних наближень завдяки застосуванню формули:

,

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

Якщо збіжність погана або зовсім відсутня, то а при гарній збіжності призадають

-

х₁

перше наближення, яке отримане за методом Ньютона.

Рис. 2.5. Геометрична інтерпретація метода Ньютона-Бройдена

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

Розглянемо рівняння (2.1) і нехай у точці виконується умова. Застосуємо в цій точці метод дотичних, а в точці х₀ =а – метод хорд. Ітераційні формули комбінованого методу мають вигляд:

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

2.6 Метод простих ітерацій

Нехай відомо, що корінь рівняння (2.1) лежить на відрізку .

Перетворимо рівняння (2.1) до вигляду

(2.7)

Таке перетворення може бути виконано різними способами, але для збіжності треба забезпечити виконання умови

<1 (2.8)

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

,(2.9)

Якщо існує границя ,тоє коренем рівняння (2.7).

Теорема 1. Нехай функція визначена та диференційована на відрізку, причому всі її значення. Тоді, якщо існує правильний дрібтакий, що виконується нерівність (2.8) при, то:

- процес ітерації (2.9) збіжний незалежно від початкового наближення ;

- граничне значення є коренем рівняння (2.7) на відрізку.

Зауваження 1. Теорема залишається вірною, якщо визначена і диференційована в нескінченому інтервалі, причомуповинна задовольняти (2.8).

Зауваження 2. В умовах теореми 1 ітерації збігаються при будь-якому виборі . Окрема похибка в обчисленнях, яка не виходить за межі проміжку, не впливає на кінцевий результат. Зростає лише об'єм обчислень. Тому це надійний метод обчислень.

Теорема 2. Нехай функція визначена і диференційована на деякому відрізку, причому рівняння (2.7) має корінь, який лежить у більш вузькому відрізку, де;. Тоді, якщо виконується (2.9) і початкове наближення, то:

- всі послідовні наближення знаходяться в інтервалі :

- процес послідовних наближень збіжний, тобто існує , причому- єдиний корінь на відрізкурівняння (2.7);

- виконується оцінка (2.11):

(2.10)

Зауваження 3. Нехай в деякому околі коренярівняння (2.7) похідназберігає сталий знак і виконана нерівність (2.8). Тоді, якщо похіднадодатна, послідовні наближення (2.9) збігаються докореня монотонно. Якщо похіднавід’ємна, то послідовні наближення коливаються біля кореня .

Метод простих ітерацій має просту геометричну інтерпретацію. Побудуємо графіки функцій і . Коренем рівняння (2.7) є абсциса точки перетину графіків. Від початкового наближення х₀ будуємо ламану, абсциси вершин якої є послідов­ними наближеннями кореня. На рис. 2.6-2.9 показано хід послідовних наближень для усіх можливих ситуацій.

Рис. 2.6. Геометрична інтерпретація Рис. 2.7. Геометрична інтерпретація

методу простих ітерацій методу простих ітерацій

для випадку для випадку

Рис. 2.8. Геометрична інтерпретація Рис. 2.9. Геометрична інтерпретація

методу простих ітерацій методу простих ітерацій

для випадку > для випадку>1

Приклад 1. Знайти дійсні корені рівняння з точністю до трьох значущих цифр.

Запишемо . Графічним способом встановлюємо, що рівняння має на відрізкуодин дійсний корінь. Дотримуючись визначень теореми 2, задаємо:і. Звідси

.

Так як і, то примаємо<1.

Якщо виберемо , то всі умови теореми 2 будуть виконані. Виберемоі граничну абсолютну похибку

4 і 5 наближення збігаються з точністю до 4 знаків. Тому .

Так як гранична абсолютна похибка приблизного кореня , включаючи похибку округлення, не перевищує: 0,0005+0,0001=0,0006, то можна прийняти.

Приклад 2. Методом простих ітерацій з точністю знайти корінь трансцендентного рівняння на відрізку.

Запишемо рівняння у вигляді: . На відрізкумаємо<1. За початкове наближення обираємо. Ітераційний процес запишемо у вигляді:

Послідовно знаходимо:

На 5 і 6 ітераціях виконується <, тому.

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

Зауваження 1. Вихідне рівняння можна записати у вигляді рівності, вибираючи різним способом. У деяких випадкахбуде менший, а в інших – більший в околі шуканого кореня. Для метода простої ітерації найкращим є такий запис, для якого<1, причому для меншихшвидкість збіжності до кореняє більшою.

Зауваження 2. Завжди можна виразити із рівняннятак, щоб для отриманого рівняння виконувалась умова збіжності<1 в околі шуканого кореня.

Зауваження 3. Загальний прийом зведення (2.1) до (2.2), для якого забезпечено виконання <1.

Нехай , причому 0<. Замінюємо (2.1) еквівалентним, де>0- константа. Тоді:. Вибираємо λ, щоб в околі ξ виконувалась нерівність:<1.

Звідси на основі попереднього: Якщо,, то<1.

Приклад 3. Знайти найбільший додатній корінь рівняння з точністю:

. (2.11)

Інтервал знаходження кореня . Рівняння (2.11) можна записати, наприклад, у видах:тощо.

Остання формула є найбільш вдалою, тому що, взявши інтервал (9;10) і визначивши матимемо:, тому. Обчислюємо послідовні наближенняз одним запасним знаком за формулами

Звідси:

Приклад 4. Знайти методом простої ітерації корінь рівняння з точністю 0,01.

Зауваження 4. Виконання умови не гарантує наближеності до точного розв’язку (Рис. 2.10).

Рис. 2.10 Немонотонний хід наближень за методом простої ітерації

Приклад 5. Для розв'язування рівняння х² =а можна прийняти абоі, відповідно, записати такі ітераційні процесиабо.

Перший процес взагалі не збігається, а другий збігається для будь-якого x > 0. Другий процес збігається дуже швидко, бо .

Оцінка похибки методу. Оцінимо похибку n-го наближення:

звідки, звівши подібні члени, отримаємо

Якщо то; тоді оцінка похибки наближеннях_п зводиться до оцінки модуля різниці двох послідовних наближень.

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

Зауваження 2. Метод простих ітерацій має лінійну швидкість збіжності.