Метод лінійного інтерполювання.

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

 

 

Рисунок 1.

 

Рисунок 2.

 

 

Рисунок 3.

 

 

Рисунок 4.

 

Як і у методі Ньютона, будемо вважати, що не тільки f′ (х), але й f′′ (х) не змінює знак на [a;b] (тобто що f′′ (х^*) ≠ 0 і відрізок ізоляції обрано достатньо малим). Тож можливі ті ж чотири варіанти залежно від знаків f′ (х) та f′′ (х). У всіх варіантах метод полягає в тому, що спочатку на [a;b] графік функції у = f (x) замінюється хордою АВ і абсциса точки перетину хорди з віссю Ох х₁ є першим наближенням кореня. Далі те ж саме треба повторити на відрізку [a;х₁] або [х₁;b] залежно від того, якому з цих відрізків належить корінь х*, отримати друге наближення х₂ і так далі. Із рисунку безпосередньо видно, що збіг ітерацій до кореня є монотонним для всіх чотирьох варіантів, як і у методі Ньютона. Тому всі відрізки, над якими графік замінюється хордою, мають одну спільну кінцеву точку: а або b залежно від варіанту. Не важко перевірити, що у всіх випадках нерухомим буде той кінець відрізку ізоляції, де знак f (x) збігається із знаком f′′ (х), тобто f (x) ∙ f′′ (х) > 0. У методі Ньютона саме ця умова була критерієм для вибору початкового наближення: отже збіг у методі хорд відбувається з протилежного боку і початкова точка – це довільна точка з [a;b], у якій виконується умова f (x) ∙ f′′ (х) < 0.

Для виведення формули методу хорд запишемо рівняння прямої, що проходить через точки А_k(х_k, f (x_k)) і С(с, f (с)) (тут х_k – це k – е наближення; с = а, якщо f (а) ∙ f′′ (а) > 0 або с = b, якщо f (b) ∙ f′′ (b) > 0):

.

Поклавши у = 0, знайдемо звідси точку перетину хорди A_kC з віссю Ох – це і буде наступне наближення x_k+1:

 

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

Ця формула визначає ітераційний метод: тут

φ(х) = х – (х – с) = х – λ(х) ∙ f (x), де λ(х) = .

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

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

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

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

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

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

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

2. f′′ (х) = 2^х(ln 2)² > 0 при всіх х.

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

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

 

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

 

Тут у чарунці А1 початкове наближення а = 0, у В1 f (a), у C1 нерухомий кінець b = 1, у D1 f (b). Зауважимо, що формулу у D1 можна просто скопіювати з В1. У чарунці А2 задана формула методу лінійного інтерполювання (5). Нерухомий кінець не змінюється, отже для його завдання використана абсолютна адресація (після набору С1 треба натиснути F4, так само з D1). Формули у стовбцях А і В копіюються. В результаті отримуємо:

 

 

	A	B	C	D
		-2
	0,333333333	-0,073412283
	0,345348204	-0,0028014
	0,345806369	-0,000107047
	0,345823876	-4,09071E-06
	0,345824545	-1,56323E-07
	0,34582457	-5,97374E-09
	0,345824571	-2,28281E-10
	0,345824571	-8,72369E-12
	0,345824571	-3,33067E-13
	0,345824571	-1,28786E-14
	0,345824571

 

Для стабілізації тут знадобилось 8 ітерацій. Це дещо поступається за швидкістю методу Ньютона, де їх було 5, але значно перевищує метод дихотомії, де в тому ж прикладі до стабілізації було 23 ітерації. Розглянемо другий приклад: знайти корінь рівняння 2∙sin x – x² + 2 = 0 з точністю e = 0,5*10^-5.

1. За змістом тут достатньо знайти один будь – який корінь. Обираємо той самий відрізок ізоляції [a;b] = [1,8;2,2].

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

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

Надамо чарункам електронної таблиці таких значень:

 

	A	B	C	D
	1,8	= 2*sin(A1) – A1^2 + 2	2,2	= 2*sin(C1) – C1^2 + 2
	= A1 – B1*(A1 – $C$1)/(B1 – $D$1)	↓
	↓	↓

 

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

 

	A	B	C	D
	1,8	0,707695262	2,2	-1,2230072
	1,946619229	0,071085379
	1,960537606	0,00630708
	1,961766184	0,000553234
	1,961873901	4,84788E-05
	1,96188334	4,24772E-06
	1,961884167	3,72184E-07
	1,961884239	3,26106E-08
	1,961884246	2,85732E-09
	1,961884246	2,50358E-10
	1,961884246	2,19358E-11

 

Тут 9 ітерацій при 5 у методі Ньютона і 12 для метода простої ітерації із сталим λ. Який порядок збігу у ітераційного процесу метода лінійного інтерполювання? Згідно з доведенням теореми 7 достатньо порахувати похідні функції, яка визначає метод хорд: φ(х) = х – λ(х) ∙ f (x), де λ(х) = , у корені х^* (f (x*) = 0). Отже

φ′(х*) = 1 – λ′(х*) ∙ f (x*) – λ(х*) ∙ f ′ (x*) = 1 – f ′ (x*) ∙ = 1 – f ′ (x*) / f ′ (),

де за теоремою Лагранжа є (x*; c). Звідси маємо φ′(х*) = ≠ 0, оскільки f ′ (x*) – f ′ () = f ′′ (ξ) ∙ (х* – ), де ξ є (x*; ), а f ′′ (х) ≠ 0 на всьому відрізку ізоляції за передумовою методу лінійного інтерполювання. Отже метод хорд збігається лінійно так само, як і метод простої ітерації із сталим λ, однак, як бачимо на прикладах, за рахунок несталості λ швидкість збігу дещо підвищилась.