Інші приклади ітераційних методів.

Все це зовсім не означає, що метод Ньютона безумовно краще, ніж метод лінійного інтерполювання або метод ітерації із сталим λ; насправді кожен має свої переваги. Так, наприклад, у методі Ньютона на відміну від інших методів на кожній ітерації треба обчислювати значення похідної, що може виявитись значно складнішим від обчислення функції. Якщо похідна мало змінюється на відрізку ізоляції, то можна спробувати замість значень f ′ (x_k) в ітераціях x_k скористатись значенням f ′ (x₀) похідної у точці x₀, тобто x_k+1 = x_k – (k = 0,1,2,…). Ця формула визначає спрощений метод Ньютона. Очевидно, це метод ітерації із сталим λ = , а тому із лінійною збіжністю. Більш поширений метод полягає у тому, щоби похідну замінити її наближеним значенням: . Підставивши це наближення у формулу методу Ньютона, отримуємо x_k+1 = x_k – . Метод, що визначається такою формулою, називають методом січних. Річ у тому, що наближення x_k+1 дістають як абсцису точки перетину осі Ох і січної, що проходить через точки (x_k-1; f (x_k-1)) та (x_k; f (x_k)), тобто з рівняння = , де покладаємо у = 0.

У всіх цих методах збіг до кореня монотонний і з того боку від нього, де f (х) ∙ f ′′(х) > 0. А ітерації методу хорд збігаються з протилежного боку (див. попередній розділ). Тому іноді корисно об’єднати обидва методи і наближатися до кореня рівняння з двох боків, дістаючи наближення з недостачею і надлишком одночасно. За початкове наближення в методі хорд вибирають точку де f (а) ∙ f ′′(а) < 0, а в методі Ньютона – точку , де f (b) ∙ f ′′(b) > 0.

y

f ′′(x) > 0

0 x

 

Рисунок 1.

 

На відрізку застосовують спочатку метод дотичних, а потім – хорд. У результаті дістають нові наближення і початковий відрізок ізоляції кореня звузився. Для знаходження нових наближень застосовують метод дотичних і хорд уже на відрізку Такий процес продовжують доти, поки довжина відрізка стане меншою величини де – наперед задана точність кореня. Формули цього комбінованого методу Ньютона та лінійного інтерполювання мають виглядати так:

b_k+1 = b_k – , а _k+1 = a _k – (k = 0,1,2,…). (6)

Порівнюючи цю формулу для а _k+1 з формулою класичного метода хорд, бачимо тільки одну різницю: на місці нерухомої точки с тут точка b_k+1, яка збігається до кореня із швидкістю метода Ньютона. Отже швидкість цього метода повинна бути принаймні не меншою швидкості метода Ньютона. Перевіримо це безпосередньо на прикладі.

Для застосування цього метода необхідно забезпечити наступні передумови.

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

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

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

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

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

1. Відрізок ізоляції для єдиного кореня цього рівняння [a;b] = [0;1].

2. f′′ (х) > 0 при всіх х.

3,4. Оскільки f (0) = –2, f (1) = 4, то за початкові наближення можна взяти а = 0, b = 1.

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

 

	A	B	C	D	E
		=2^A1+5*A1–3		=2^C1+5*C1–3	=2^C1*ln(C1)+5
	=A1–B1*(A1–C2)/(B1–D2)	↓	=C1–D1/E1	↓	↓
	↓	↓	↓	↓	↓

 

Тут стовбці C, D і E ідентичні відповідним стовбцям електронної таблиці для метода Ньютона: С1 містить початкову точку b = 1, D1 значення f (b), Е1 значення f ′ (b), С2 формулу метода Ньютона. Разом з тим стовбці А, В, С і D містять інформацію, майже ідентичну відповідним стовбцям електронної таблиці методу лінійного інтерполювання: відмінність лише в тому, що у стовбцях С і D тепер змінні значення, отримані методом Ньютона. А саме у чарунку А1 початкова точка а = 0, у В1 значення f (а), у А2 формула метода хорд, де місце нерухомої точки зайняли значення з рядка 2 метода Ньютона: тобто

спочатку працює цей метод, а далі його результати використовує метод хорд. В результаті отримуємо:

 

	A	B	C	D	E	F
		-2			6,386294361
	0,345352261	-0,002777541	0,373658686	0,163927839	5,898065336	0,028306
	0,34582457	-5,85704E-09	0,345865193	0,000238894	5,880929713	4,06E-05
	0,345824571		0,345824571	5,03792E-10	5,880904909	8,57E-11
	#ДЕЛ/0!	#ДЕЛ/0!	0,345824571		5,880904909	#ДЕЛ/0!
	#ДЕЛ/0!	#ДЕЛ/0!	0,345824571		5,880904909	#ДЕЛ/0!

Тут додатково введений ще стовбець F, де підраховується різниця між значеннями у стовбцях С і А, тобто різниця ε_k між наближенням з надлишком, яке дає метод Ньютона, і наближенням з недостачею, яке забезпечує метод лінійного інтерполювання. Із цих даних безпосередньо видно, що збіжність методу квадратична: ε_k+1 ≈ ε_k², тобто кількість значущих цифр наближення подвоюється з кожним кроком. Уже у рядку 4 (скоріше навіть класичного метода Ньютона) значення у стовбцях С і А не відрізняються з максимально можливим у комп’ютері числі значущих цифр. Тому подальші обчислення величини a _k у стовбці А по формулі (6) призводять до повідомлення про помилку #ДЕЛ/0! (ділення на 0): надалі величина f (b_k+1) – f (a _k) у знаменнику цієї формули уже не відрізняється від нуля.

Всі розглянуті вище методи вимагали передумовою попереднє відокремлення коренів. Нарешті розглянемо метод, який дозволяє розв’язувати рівняння f (х) = 0 на відрізку без попередньої ізоляції. Цей метод побудований на основі ітераційного метода із сталим λ, який взагалі має найменші передумови. Візьмемо таке λ, щоби функція φ(х) = х – λ∙ f (x) була монотонно зростаючою, тобто щоби φ′(х) = 1 – λ∙ f ′ (x) ≥ 0, звідки │λ│≤ 1/М₁, де М₁ = . З таким λ ітераційний процес x_k+1 = φ(x_k) при будь – якому початковому x₀ є є монотонним: x_k+1 ≥ x_k, отже (при умові обмеженості всіх x_k) існує границя = х*. Звідси φ(х*) = х*, тобто f (x*) = 0. Справді, φ(х*) = φ( х_k) = φ(х_k) = х_k+1 = х*. Отже будь – який ітераційний процес на збігається до кореня. На рисунку корінь – це точка перетину графіка функції у = φ(х) з прямою у = х.

у

х

а а₁ х₁* а₂ х₂* х₃* а₃ b

Рисунок 2.

 

З рисунку видно, що до першого кореня х₁* збігається будь – який процес x_k+1 = φ(x_k), що починається в його околі між а та другим коренем х₂*, наприклад, у точках а₁ або а₂. Тобто х₁* – стійка нерухома точка процесу, так само і третій корінь х₃*. Другий корінь х₂* – нестійка нерухома точка, до неї не збігається жоден процес окрім того, що починається безпосередньо в точці х₂*. Легко зрозуміти, що у загальному випадку стійкі та нестійкі нерухомі точки чергуються: за стійкою нестійка і навпаки. Якщо змінити знак λ, тобто розглянути процеси x_k+1 = φ₁(x_k), де φ₁(х) = х + λ∙ f (x), то стійкі нерухомі точки перетворяться на нестійкі і навпаки. Отже або процес x_k+1 = φ(x_k), або x_k+1 = φ₁(x_k) збігається до кожного кореня f (x) на . Звичайно, такий метод при виборі сталого і неоптимального λ буде не дуже ефективним. Скоріше це алгоритм відокремлення коренів, а не пошуку його з даною точністю. Проте цей метод можна модифікувати, змінюючи λ на кожній ітерації так, щоби на цьому кроці у нього було оптимальне значення. Можна довести, що модифікований алгоритм має квадратичну збіжність до кожного кореня і швидше метода Ньютона.

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

 

Питання, тести

 

1. Відрізок [a;b] є відрізком ізоляції кореня рівняння , якщо

 

А	графік похідної перетинає вісь абсцис на (a;b)
Б	графік похідної не перетинає вісь абсцис на (a;b)
В	графік функції перетинає вісь абсцис на (a;b)
Г	умови Б та В виконані одночасно
Д	графік функції не перетинає вісь абсцис на (a;b)
Е	умови А та Д виконані одночасно
Ж	це залежить від функції

 

2. Нехай графік функції перетинає вісь абсцис по інтервалу (0;1). Тоді відрізок [0;1] є відрізком ізоляції кореня рівняння , якщо

 

А	> 2x + 1
Б	< 2x + 1
В	< 2x – 2
Г	> 2x – 2

 

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

А:

Б:

В:

Г:

4. Нехай на інтервалі (a;b) графік функції перетинає вісь абсцис, < 0. Тоді метод дихотомії на відрізку [a;b] визначають такі формули: с_n = (а_n + b_n)/2 та

 

А
Б
В
Г

 

5. Нехай на інтервалі (0;1) графік функції перетинає вісь абсцис, < 0. Тоді метод дихотомії на відрізку [a;b] визначають такі формули:

А:

	A	B	C	D
			= (A1 + B1)/2	= 2^C1 – 4*C1 + 1
	= ЕСЛИ(D1 > 0; C1; B1)	= ЕСЛИ(D1 > 0; A1;C1)	↓	↓
	↓	↓	↓	↓

Б:

	A	B	C	D
			= (A1 + B1)/2	= 2^C1 + 5*C1 – 3
	= ЕСЛИ(D1 > 0; A1; C1)	= ЕСЛИ(D1 > 0; C1; B1)	↓	↓
	↓	↓	↓	↓

В:

	A	B	C	D
			= (A1 + B1)/2	= 2^C1 – 4*C1 + 1
	= ЕСЛИ(D1 > 0; C1; B1)	= ЕСЛИ(D1 > 0; A1;C1)	↓	↓
	↓	↓	↓	↓

Г:

	A	B	C	D
			= (A1 + B1)/2	= 2^C1 + 5*C1 – 3
	= ЕСЛИ(D1 > 0; A1; C1)	= ЕСЛИ(D1 < 0; C1; B1)	↓	↓
	↓	↓	↓	↓

 

6. В наступній таблиці у стовпці А значення аргументу, у стовпці В відповідні значення функції . Чи можна стверджувати, що цими даними визначений корінь рівняння = 0 з точністю 10^-6?

	A	B
	0,34581	-8,6E-05
	0,345818	-4,1E-05
	0,345821	-1,9E-05
	0,345823	-7,5E-06
	0,345824	-1,9E-06

 

А	Б	В	Г
так	ні	це залежить від функції	це залежить від методу обчислень

 

7. В наступній таблиці у стовпці А значення аргументу, у стовпці В відповідні значення функції . Чи можна стверджувати, що цими даними визначений корінь рівняння = 0 з точністю 10^-5?

	A	B
	0,345825	1,65E-07
	0,345825	-1,9E-07
	0,345825	-1E-08
	0,34583	2,94E-05
	0,34582	-2,9E-05

 

А	Б	В	Г
так	ні	це залежить від функції	це залежить від методу обчислень

 

8. За таким варіантом наступного рисунку ітераційний процес х = φ(х) з початковою точкою А₀ (х₀, φ(х₀)) збігається:

в г

А	Б	В	Г
а	б	в	г

 

10. Нехай │φ′(х)│< 1 на відрізку [a; b], φ(х*) = х* для деякого х* Î [a; b]. Тоді

 

А	y = φ(х) є стискуючим відображенням на [a;b]
Б	[a; b] – відрізок ізоляції кореня х*
В	ітераційний процес хk = φ(хk-1) збігається до х* з довільним початковим х0 Î [a; b]
Г	збіжність характеризується нерівністю │ хk – x*│≤ q^k│х0 – x*│, де q < 1 – довільне

 

11. Для ефективних ітераційних методів (тобто з малою константою Ліпшиця q) після деякої кількості кроків

 

А	похибками метода та неусувною можна нехтувати порівняно з похибкою обчислень
Б	ітерації не збігаються до кореня, а коливаються біля нього в околі похибки обчислень
В	критерій закінчення: значення двох послідовних ітерацій співпадають з даним числом значущих цифр
Г	критерій закінчення: значення достатньої кількості послідовних ітерацій співпадають один з одним з даним числом значущих цифр

 

1. Н айкраще (тобто найменше) можливе значення константи Ліпшиця функції φ(х) = х – λ f (x) на відрізку [ a;b ] ізоляції кореня рівняння f (x) = 0 дорівнює q = 1 – m₁/М₁, де М₁ = , m₁ = . При цьому

 

А	Б	В	Г
λ = 1/М1, λ > 0	λ = 1/М1, < 0	λ = 1/М1, > 0	│λ│= 1/М1, > 0

 

13. Нехай рівняння f (x) = 0 має корінь на відрізку його ізоляції [-1;-0,6], │ f ′(-1)│≈ 3,08 │ f ′(-0,6)│≈ 2,85; графік похідної f ′(x) наведений далі.

Тоді збіг ітераційного процесу х_n+1 = φ(х_n), де φ(х) = х – λ f (x) до кореня рівняння f (x) = 0 буде найшвидшим, якщо λ =

А	Б	В	Г
1/3,08	1/2,85	– 1/3,08	– 1/2,85

 

14. Рівняння f (x) = 2sin x – x² + 2 = 0 має корінь на відрізку його ізоляції [1,8; 2,2], │ f ′(1,8)│≈ 4,05; │ f ′(2,2)│≈ 5,57; графік похідної f ′(x) наведений далі.

 

 

Тоді наступна таблиця визначає ітераційний процес х_n+1 = φ(х_n), де φ(х) = х – λ f (x), збіг якого до кореня рівняння f (x) = 0 буде найшвидшим:

 

А:

	A	B	С
	1,8	= 2 ∙ sin(А1) – А1^2 + 2	= 1/ 4,05
	= A1 – C1*B1	↓
	↓	↓

 

 

Б:

	A	B	С
	1,8	= 2 ∙ sin(А1) – А1^2 + 2	= 1/5,57
	= A1 – $C$1*B1	↓
	↓	↓

В:

	A	B	С
	1,8	= 2 ∙ sin(А1) – А1^2 + 2	= – 1/ 4,05
	= A1 – $C$1*B1	↓
	↓	↓

Г:

	A	B	С
	1,8	= 2 ∙ sin(А1) – А1^2 + 2	= – 1/5,57
	= A1 – $C$1*B1	↓
	↓	↓

 

15. Нехай х_n+1 = φ(х_n) – ітераційний процес, де φ(х) = х – λ f (x). Тоді за методом Ньютона λ =

А	Б	В	Г
1/М1	1/m1

 

16. [0; 1] є відрізком ізоляції кореня рівняння f (x) = 2^х + 5x – 3 = 0. На цьому відрізку

 

А	умови методу Ньютона не виконуються
Б	умови методу Ньютона виконуються і за початкову точку можна взяти 0
В	умови методу Ньютона виконуються і за початкову точку можна взяти 1
Г	умови методу Ньютона виконуються і за початкову точку можна взяти будь – яку точку відрізку [0;1]

 

17. [0;1] є відрізком ізоляції кореня рівняння f (x) = 2^х + 5x – 3 = 0. Наступна таблиця визначає ітераційний процес пошуку кореня рівняння f (x) = 0 методом Ньютона:

 

А:

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

Б:

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

В:

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

Г:

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

 

18. Збіг ітераційного процесу х_k = φ(х_k-1) тим швидший, чим порядок його збіжності

 

А	Б	В	Г
більший	менший	це залежить від φ(х)	це залежить від початкової точки процесу

 

19. Порядок збіжності ітераційного процесу α дорівнює

 

А	0 для методу дихотомії
Б	1 для методу простої ітерації
В	2 для методу Ньютона
Г	2 для методу хорд

 

20. [0; 1] є відрізком ізоляції кореня рівняння f (x) = 2^х + 5x – 3 = 0. На цьому відрізку

 

А	умови методу лінійного інтерполювання не виконуються
Б	умови методу хорд виконуються і за початкову точку можна взяти 0
В	умови методу хорд виконуються і за початкову точку можна взяти 1
Г	умови методу хорд виконуються і за нерухомий кінець можна взяти 1

 

21. [0;1] є відрізком ізоляції кореня рівняння f (x) = 2^х + 5x – 3 = 0. Наступна таблиця визначає ітераційний процес пошуку кореня рівняння f (x) = 0 методом хорд:

А:

	A	B	C	D
		= 2^A1 + 5*A1 – 3		= 2^C1 + 5*C1 – 3
	= A1 – B1*(A1 – C1)/(B1 – D1)	↓
	↓	↓

Б:

	A	B	C	D
		= 2^A1 + 5*A1 – 3		= 2^C1 + 5*C1 – 3
	= A1 – B1*(A1 – C1)/(B1 – D1)	↓
	↓	↓

В:

	A	B	C	D
		= 2^A1 + 5*A1 – 3		= 2^C1 + 5*C1 – 3
	= A1 – B1*(A1 – $C$1)/(B1 – $D$1)	↓
	↓	↓

Г:

	A	B	C	D
		= 2^A1 + 5*A1 – 3		= 2^C1 + 5*C1 – 3
	= A1 – B1*(A1 – $C$1)/(B1 – $D$1)	↓
	↓	↓

 

Завдання

1. Відокремити корені рівняння 2соs x – x² + 2 = 0 графічним методом.

2. Відокремити корені рівняння f (x) = sinx – x + 1 = 0 аналітичним методом.

3. Відокремити корені рівняння x² – 3 соs x – 2 комбінованим методом.

4. Розв‘язати рівняння f (x) = 3^х + 6x – 3 = 0 з точністю e = 0.5*10^-5 методом дихотомії.

5. Методом простої ітерації розв‘язати рівняння f (x) = 3 ∙ sin x – x² + 2 = 0 з точністю e = 0,5*10^-5.

6. Методом Ньютона розв‘язати рівняння f (x) = 5^х + 5x – 5 = 0 з точністю e = 0,5*10^-5.

7. Методом хорд розв‘язати рівняння f (x) = 3^х + 6x – 3 = 0 з точністю e = 0,5*10^-5.