Метод Ньютона. Порядок збіжності ітераційного процесу.

Розглянемо класичний ітераційний метод обчислення кореня х^* рівняння f (x) = 0 на відрізку ізоляції [a;b], який є простим і дуже ефективним одночасно – метод Ньютона. Нехай х_k – відоме k– е наближення кореня, треба знайти х_k+1. Будемо вважати, що f (x) двічі диференційовна на [a;b] і застосуємо формулу Тейлора в околі точки х_k:

f (x) = f (х_k) + f′ (х_k)(х – х_k) + ½ f′′ (х_k)(х – х_k)² + … = 0.

Нехтуючи нелінійними відносно х – х_k додатками, отримаємо f (х_k) + f′ (х_k)(х – х_k) = 0, звідки х = х_k – . Знайдене значення х і будемо вважати рівним х_k+1:

х_k+1 = х_k – (k = 0, 1, 2, …).

Ця формула і визначає ітераційний метод Ньютона: тут φ(х) = х – λ(х) ∙ f (x), λ(х) = . Від прикладів попередніх розділів він відрізняється лише тим, що тут λ залежить від х.

Метод Ньютона має просту геометричну інтерпретацію. Рівняння y = f (х_k) + f′ (х_k)(х – х_k) – це рівняння дотичної до графіку функції y = f (х) у точці х_k, а отже вище знайдене х_k+1 є точкою перетину цієї дотичної з віссю абсцис. Тому метод Ньютона називають ще методом дотичних. Будемо вважати, що не тільки f′ (х), але й f′′ (х) не змінює знак на [a;b], тобто що f′′ (х^*) ≠ 0 і відрізок ізоляції обрано достатньо малим. Тож можливі чотири варіанти залежно від знаків f′ (х) та f′′ (х). Наприклад, якщо f′ (х) > 0, f′′ (х) < 0, то функція f (х) є зростаючою та опуклою, як це зображено на наступному рисунку 1. З нього можна

 

Рисунок 1.

 

Рисунок 2.

 

Рисунок 3.

 

Рисунок 4.

 

безпосередньо побачити, що для всіх можливих варіантів з одного боку відрізка ізоляції ітерації монотонно збігаються до кореня х^*, а з другого можуть опинитись за межами відрізку вже на першому кроці. Легко переконатись (рисунки 1 – 4), що збіг спостерігається при всіх варіантах на тому боці, де виконується умова f (х) ∙ f′′ (х) > 0.

Отже, для застосування метода Ньютона необхідно забезпечити наступні передумови.

1. Треба знайти відрізок ізоляції шуканого кореня.

2. Треба забезпечити, щоби на відрізку ізоляції не змінювався знак у f′′ (х), зменшуючи при необхідності початковий відрізок.

3. За початкове наближення можна брати будь – яку точку х відрізку ізоляції, у якій виконується умова f (х) ∙ f′′ (х) > 0.

Розглянемо застосування методу Ньютона на прикладі задачі: розв‘язати рівняння f (x) = 2^х + 5x – 3 = 0 з точністю e = 0,5*10^-5.

1. Ця задача уже була розв’язана методом дихотомії і там був знайдений відрізок ізоляції [a;b] = [0;1] для єдиного кореня цього рівняння.

2. f′ (х) = 2^х(ln 2) + 5, f′′ (х) = 2^х(ln 2)² > 0 при всіх х. Отже на [0;1] знак f′′ (х) не змінюється.

3. Як з графіку функції у = f (x), так і обраховуючи безпосередньо, отримаємо f (0) = –2, f (1) = 4. Тому за початкове наближення можна взяти точку b = 1.

4. Нарешті знайдемо корінь на [0;1] з точністю e = 0.5*10^-5 методом Ньютона за допомогою Excel. Надамо чарункам електронної таблиці таких значень:

 

	A	B	C
		= 2^A1 + 5*A1 – 3	= 2^A1*ln2 + 5
	= A1 – B1/C1	↓	↓
	↓	↓	↓

 

Тут у А1 початкова точка b = 1, у В1 значення f (x) при х = А1, у С1 – значення f′ (х) при х = А1, у А2 задано формулу метода Ньютона х_k+1 = х_k – і далі копіюємо ці формули. В результаті отримуємо:

 

	A	B	C
			6,386294361
	0,373658686	0,163927839	5,898065336
	0,345865193	0,000238894	5,880929713
	0,345824571	5,03792E-10	5,880904909
	0,345824571		5,880904909
	0,345824571		5,880904909

 

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

 

Задача. Знайти корінь рівняння 2∙sin x –x² +2 = 0 з точністю e = 0,5*10^-5.

За змістом тут досить знайти будь – який один корінь рівняння. Як уже відомо, існує два корені у відрізках ізоляції [-1;-0,6] і [1,8;2,2]. Обираємо другий: у ньому кількість ітерацій була дещо більшою і дорівнювала 12.

1. Отже [a;b] = [1,8;2,2].

2. f′ (х) = 2 ∙ cos x – 2x, f′′ (x) = – 2 ∙ sin x – 2 ≤ 0 при всіх х. Отже на [1,8;2,2] знак f′′ (х) не змінюється.

3. З графіку функції у = f (x) бачимо, що f (1,8) > 0, f (2,2) < 0. Тому за початкове наближення можна взяти точку b = 2,2.

4. Відповідна електронна таблиця:

 

	A	B	C
		= 2*sin x – x^2 + 2	= 2*cos x – 2*x
	= A1 – B1/C1	↓	↓
	↓	↓	↓

 

В результаті отримуємо:

 

	A	B	C
	2,2	-1,22300719	-5,57700223
	1,980705271	-0,08887914	-4,75846218
	1,962027148	-0,0006697	-4,68670735
	1,961884255	-3,9295E-08	-4,68615736
	1,961884246		-4,68615733
	1,961884246		-4,68615733

 

Стабілізація знову на п’ятому кроці! Схоже на то, що метод Ньютона більш ефективний, ніж попередні. Формалізуємо це спостереження.

Означення. Нехай х_k (k = 0,1,2,…) – значення ітерації деякого процесу без урахування похибок обчислень, х_k= х^*. Порядок збіжності ітераційного процесу – це таке найбільше натуральне число α, що │х_k – х^*│≤ С│х_k-1 – х^*│^α (k = 0,1,2,…), де С > 0 – деяка стала.

Якщо α = 1, то кажуть, що ітераційний процес збігається лінійно; якщо α = 2, то квадратично і так далі. Наприклад, якщо х_k – це процес простої ітерації, тобто х_k = φ(х_k-1) (k = 0,1,2,…) і функція φ(х) задовольняє умові Ліпшиця з константою Ліпшиця q, то

│х_k – х^*│ = │φ(х_k-1) – φ(х^*)│ ≤ q│х_k-1 – х^*│. Звідси видно, що будь – який процес простої ітерації має принаймні лінійну збіжність.

 

Теорема 7. Ітераційний процес метода Ньютона збігається квадратично.

1. Спочатку розглянемо довільний процес простої ітерації: х_k = φ(х_k-1) на відрізку ізоляції [a;b] кореня х^*, х_k= х^*. Нехай в околі кореня х^* функція φ(х) має m неперервних похідних і

φ′(х*) = φ′′(х*) = … = φ^(m-1)(х*) = 0, φ^(m)(х*) ≠ 0. (3)

За формулою Тейлора

φ(х) – х* = (х – х*)φ′(х*) + φ′′(х*) + … + φ^(m-1)(х*) + φ^(m)(ξ) = = φ^(m)(ξ), де ξ є [x; x*] [a;b]. Зокрема при х = х_k-1, φ(х_k-1) = х_k маємо х_k – х* = φ^(m)(ξ_k), де ξ_k є [х_k; x*] [a;b]. Звідси

│х_k – х^*│ ≤ С│х_k-1 – х^*│^m, де С = │φ^(m)(ξ)│ ≠ 0. (4)

Отже з (3) випливає, що порядок збіжності α процесу х_k = φ(х_k-1) дорівнює m.

2. Тож для доведення теореми достатньо порахувати похідні функції φ(х) = х – , яка визначає метод Ньютона, у корені х^* (f (x*) = 0). Отже

φ′(х*) = (х – )′│_х* = 1 – │_х* = │_х* = 0.

φ′′(х*) = ()′│_х* = ( + f(x) ∙ ()′)│_х* = ≠ 0,

оскільки у методі Ньютона за умовою f′ (x*) ≠ 0, f′′ (x*) ≠ 0. Теорема доведена.

З формули (4) випливає також, що │х_k – х^*│ ≤ С ∙│х_k-1 – х^*│², де С = │ │. Отже, якщо наближення х_k-1 має m правильних десяткових знаків, то х_k у методі Ньютона щонайменше матиме 2m правильних десяткових знаків. Однак, у теоремі 7 врахована тільки похибка методу і згідно з висновком теореми 6 цей найшвидший збіг триватиме лише доти, доки похибка методу за величиною не зрівняється з похибкою обчислень.