КЛ по Информатике-2008-часть2_укр

f (x(0) )					В
a	C		A	α	b
0	x*	x(2)	x(1)		x(0)

Рис. 1.7 Геометричні побудови для методу Ньютона

Одержимо розрахункову формулу методу Ньютона. Замість ділянки кривої ВС (точка С відповідає x* ) візьмемо ділянку АВ – дотичну, проведену в точці з координатами

(x(0) , f (x(0) )). Для цього відрізку справедливо кінцеве співвідношення:

f (x(0) )−0

= f ' (x(0) )≡ tgα

(1.11)

x

(0)

− x

(1)

де α - кут нахилу дотичній у крапці (x(0) , f (x(0) )) до осі абсцис.

Розв’язуючи це співвідношення відносно x(1) , одержуємо:

x

(1)

= x

(0)

−

f (x(0) )

(1.12)

f ' (x(0) )

Повторюючи процес, знаходимо загальну формулу:

(k

+1)

(k )

f (x(k) )

x

= x

−

, де k = 0,1,2,...

(1.13)

f ' (x(k ) )

Відзначимо, що якщо відкинути ітераційний індекс, то (1.13) записується у вигляді нелінійного рівняння:

	x = x −	f (x)	≡ϕ (x)	(1.14)
		f ' (x)

яке, однак, на [a,b] не є еквівалентним вихідному, а є таким тільки в одній точці при x = x* . Тому даний метод не служить різновидом методу простих ітерацій.

Застосуємо тепер для одержання формули (1.13) метод лінеаризації. Покладемо, що

ітераційний процес має вигляд:
x(k +1) = x(k ) +δ (k ) , де k = 0,1,2,...		(1.15)
де δ (k ) - поправка до k -го наближення,	яку необхідно знайти. Припускаючи, що	f (x) має
безперервну другу похідну, розкладемо	f (x(k ) +δ (k) ) за формулою Тейлора щодо точки

x(k ) :

20

f (x(k ) +δ (k ) )= f (x(k ) )+δ (k ) f ' (x(k ) )+ (δ (2k ) )2 f " (ξ ) (1.16)

де ξ (x(k ) , x(k +1) ). З огляду на, те що f (x(k ) +δ (k ) )= 0 (це відповідає знаходженню точки

перетинання з віссю абсцис), і залишаючи тільки лінійну (відносно δ (k ) ) частину розкладання (звідси і назва – метод лінеаризації), записуємо лінійне рівняння відносно δ (k ) :

f (x(k ) )+δ (k ) f ' (x(k ) )= 0								(1.17)
Звідси виражається поправка δ	(k )	= −	f (x(k ) )		. Підставляючи	δ	(k )	в (1.15), одержує-
			f ' (x(k ) )

мо (1.13).

Зауваження:

1)Із графіка 1.7 можна побачити, що якщо почати будувати дотичні із точки а, то x(1) знайдеться взагалі поза відрізком [a,b], де функція може бути навіть не визначеною. Таким

чином можна вивести правило вибору початкової точки (1.13) x(0) .

Правило вибору початкової точки (1.13)

Як вихідна точка x(0) обирається той кінець інтервалу [a,b], якому відповідає ордината того ж знака, що й f " (x)

Його можна записати у вигляді формули:

	(0)
x		a, якщо f (a) f "(a)> 0	(1.18)
		=
		b, якщо f (a) f " (a)< 0

2) Із графічної аналогії методу є очевидною вимога збереження знаків f ' (x) і f " (x): функція на відрізку [a,b] не повинна мати перегинів і зміни монотонності.

Теорема (про достатні умови збіжності методу Ньютона):

Нехай виконуються наступні умови:

1. Функція f (x) визначена і двічі диференційована на ділянці [a,b].

2. Відрізку [a,b] належить тільки один простий корінь x* , так що f (a) f (b)< 0 . 3. Похідні f ' (x), f " (x) на [a,b] зберігають знак, і f ' (x)≠ 0 .

4. Початкове наближення x(0)		задовольняє нерівності	f (x(0) ) f " (x(0) )> 0 (знаки функцій
f (x) і	f " (x) в крапці x(0)	збігаються).
Тоді	за допомогою методу Ньютона (1.13)		можна обчислити корінь рівняння

f (x)= 0 з будь-якою точністю ε .

3.2. Реалізація метода Ньютона в MS Excel

Порядок розв’язання нелінійного рівняння за методом Ньютона можна звести до виконання наступної послідовності дій:

1. Задати	початкове	наближення	x(0)	так,	щоб	виконувалася	нерівність
f (x(0) ) f " (x(0) )> 0 , а також мале позитивне число ε . Покласти k = 0 .

21

Обчислити x

(k +1)

за формулою x

(k +1)

= x

(k )

−

f (x(k ) )

2.

.

f ' (x(k ) )

3.

Якщо

x(k +1)

− x(k )

≤ ε , процес

завершити

і покласти x = x(k +1) , інакше покласти

*

k = k + 1 і перейти до пункту 2.

Приклад реалізації методу Ньютона всередовищі Microsoft Excel наведено на рис. 1.8.

3.3. Модифікації методу Ньютона.

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

умова знакосталості порушена вдалині від кореня, де обрано x(0) , а поблизу кореня виконується, то однаково метод дотичних не можна застосувати (рис. 1.9), якщо не зробити звужен-

ня початкового відрізку.

y

y = f (x)

x(2)

x*1

0

x*2

x(1)

x(0) x

Рис. 1.9. Приклад незастосовності методу дотичних

Крім цього, у випадку, якщо функція f (x) досить складна, то буде складної і її похі-

дна, і тому на кожній ітерації доводиться розраховувати дві функції, що знижує ефективність методу дотичних.

У силу цього в ряді випадків можуть виявитися більш ефективними модифікації методу дотичних.

3.3.1. Спрощений метод Ньютона

Методика його застосування збігається з викладеною для методу Ньютона, але замість

формули (1.13) використовується формула:
	(k +1)		(k )		f (x(k ) )
x		= x		−		, де k = 0,1,...	(1.19)
					f ' (x(0) )
Відмінність від методу Ньютона полягає в тому, що похідна функції							f (x) підрахову-

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

22

а)

б)

Рис. 1.8. Приклад розв’язання рівняння за методом Ньютона в Microsoft Excel: а) вид листа Microsoft Excel; б) формули, що розташовано в комірках листа Microsoft Excel

23

y

y = f (x)

0

x*

x(2) x(1)

x(0)

x

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

знакосталості похідних. Збіжність спрощеного методу Ньютона лінійна.

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

Цей метод дозволяє збільшити швидкість збіжності послідовних наближень завдяки

використанню формули:

f (x(k ) )

x

(k +1)

= x

(k )

−ck

, де k = 0,1,2,...

(1.20)

f ' (x(k ) )

де

ck - число,

що обирається на кожній ітерації таким чином,

щоб зменшити значення

f (x(k +1) )

в порівнянні з

f (x(k ) )

При ck

= 1 метод Ньютона-Бройдена збігається з мето-

дом Ньютона.

Як правило, при поганій збіжності або її відсутності вважають, що 0 < ck

< 1 (рис.

1.11, а), а при гарній збіжності для

ck

= 1

вважають ck > 1

(це прискорює збіжність (рис.

1.11, б)).

x(1) ,

На

рис

1.11 прямокутниками

відзначено

точки

отримані

при

c = 1 ,

f (x(k ) )

0

δ

(k )

=

k = 0,1,... -

,

поправка,

що

відповідає

методу

Ньютона,

а

точки

f ' (x(k ) )

x(1)

= x(0)

−c δ (0) отримано за методом Ньютона-Бройдена.

0

3.3.3. Метод січних

У цьому методі похідна функції

f (x)

підраховується

за

допомогою

кінцево-

різницевих співвідношень:

f (x(0) )− f (x(0) −δ )

-

у точці x(0) використано формулу

f ' (x(0) )=

, де δ

– мала пози-

тивна величина;

δ

f (x(k) )− f (x(k −1) )

-

у точках x(k ) , k = 0,1,... використано формулу

f ' (x(k) )=

.

x

(k )

− x

(k −1)

24

a )

y

0 < ck < 1

б )

y

> 1

f (x(0) )

f (x

(0)

)

ck

y = f (x)

x(1)

x*

x*

x(0)

x(1)

x(0)

0

x

(1)

x

0

x

(1)

δ (0)

x

δ (0)

c δ (0)

c0δ

(0)

0

f (x(1) ) > f (x(0) )

Рис. 1.11. Геометричні побудови для методу Ньютона-Бройдена

Обчислене значення f ' (x(k ) ) визначає тангенс кута нахилу січної (рис. 1.12).

y

x*

x(0)

0

x

(2)

x

(1)

δ

x

y = f (x)

Рис. 1.12.

Геометричні побудови для методу січних

Методика застосування методу січних збігається з методикою застосування методу

Ньютона, але замість (1.13) використовується формула:

f

x(k )

)

x(k +1) = x(k ) −

(

(x(k )

− x(k −1) ), k = 1,2,...

(1.21)

f (x

(k )

(k −1)

)

)− f (x

Зауваження:

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

25

Стандартні форми рівняння Приклад

тільки значення f (x(k ) ), тому що величину f (x(k −1) ) вже підраховано на попередній ітерації.

2.Для всіх описаних модифікацій швидкість збіжності p в порівнянні з методом дотичних знижується: p < 2 . Однак для деяких з них (метод січних) значення p > 1 і може досягати p = 1,5 .

§4. Інші методи розв’язання нелінійних рівнянь в MS Excel

Описуючи метод ітерацій при розв’язанні нелінійних рівнянь, звичайно про нього говорять як про метод «здогаду і перевірки». Майже у всіх ітераційних методах потрібно, щоб користувач задав початкове наближення. Потім, за допомогою цього початкового наближення, вирішується рівняння і обчислюється результат, після чого виконується перевірка, у процесі якої з’ясовується, чи досить близько знайдене рішення до справжнього. Якщо точність рішення, отриманого на черговому кроці, незадовільна, процес повторюється, тобто виконується нова ітерація (1.14). Для ефективного одержання ітераційних рішень важливо скласти алгоритм, по якому обробляється початкове наближення. Розглянемо наступні ітераційні методи розв’язання нелінійних рівнянь:

Ітерація (1.14)

Ітерація (від лат. iteratio — повторення), повторне вживання якої-небудь математичної операції.

1.Пошук кореню із використанням графіка.

2.Метод здогаду і перевірки.

3.Метод прямої підстановки.

4.Метод ітерації в комірці.

5.Розв’язання рівнянь за допомогою надбудови Пошук рішення.

Перед розв’язанням рівняння ітераційними методами його потрібно привести до стан-

дартної форми. Розглянемо, наприклад, стандартні форми рівняння x3 + 4 = 12 x (табл. 1.1). Таблиця 1.1

Форма
(1) Рівняння	з	нульовою	x3 −12 x + 4 = 0
правою частиною
(2) Рівняння,	у	лівій час-	x =	x	3	+ 4
тині якого –	невідома ве-
					12
личина

Де використається Графічний метод; пакет Пошук рішення Метод прямої підстановки; метод

ітерації в осередку

У методі прямої підстановки і методі ітерації в осередку використовується форма 2. Форма 1 звичайно більше зручна для пошуку рішення графічним методом; при використанні надбудови (1.15) Пошук рішення застосовується різновид цієї форми (у правій частині рівняння може перебувати будь-яка константа, а не тільки нуль). Якщо пошук рішення методом «здогаду і перевірки» здійснюється вручну, то підійде кожна із цих двох форм.

Надбудова (1.15)

Надбудова (add-on program, plug-in) – програма, що працює разом с іншою програмою та збільшує її функціональні можливості, тобто це додаткова можливість або допоміжний по відношенню до основної програми додаток. Надбудова Excel – це допоміжна програма, що додає в програму Excel спеціальні команди та збільшує можливості Excel.

26

4.1. Пошук кореню графічним методом

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

x3 −12 x + 4 = 0 .

(1.22)

Однак при спробі вгадати значення змінної x , задовольняючої цьому рівнянню, звичайно в результаті підстановки різних значень у ліву частину рівняння точний нуль отриманий не буде (якщо тільки випадково не потрапимо на корінь). Тому перепишемо рівняння 1.22 у такому вигляді:

f (x)= x3 −12 x + 4 .	(1.23)
У ході пошуку рішення підставляємо різні значення змінної x , і обчислюємо значен-
ня функції f (x) і будуємо графік залежності функції	f (x) від x . Коренями рівняння бу-

дуть значення змінної x , при яких f (x)= 0 . Спочатку введемо в електронну таблицю стовбець значень x в інтервалі 0 ≤ x ≤ 6 (рис. 1.13).

Потім для кожного x обчислимо значення f (x) (рис. 1.14).

Рис. 1.13 Стовбець значень x в інтервалі	Рис. 1.14 Обчислені значення f (x)
0 ≤ x ≤ 6
Після цього будуємо крапкову діаграму із графіком функції f (x)		(рис. 1.15).
Із графіка можна побачити, що корені перебувають біля значень		x = 0,3	і x = 3,3 .
Для одержання більше точних результатів потрібно звузити інтервал значень x .			Наприклад,

27

щоб з більшою точністю знайти значення кореня біля точки x = 0,3 , можна обчислити значення функції f (x) при двадцятьох значеннях x , що лежать в інтервалі від 0,6 до 1,0.

Рис. 1.15.

Графік функції f (x)= x3 −12 x + 4

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

фік (рис. 1.16).

Рис. 1.16. Графік функції f (x)= x3 −12 x + 4

Здіаграми1.16 видно, щотретійкоріньперебуваєбіляточки x = −3,8 .

28

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

4.2. Простий ітераційний метод здогаду і перевірки

Якщо відомо, що біля точки x = 0,3 перебуває корінь, одним з найпростіших способів пошуку цього кореня є створення електронної таблиці, у яку вводилися б наближені значення й формула для обчислення функції f (x) (рис. 1.17).

Рис. 1.17 Обчислення функції f (x)

Після цього варто підібрати таке значення x , для якого f (x) перебуває якнайближче до нуля (у тому випадку, якщо рівняння записано у формі 1) (рис. 1.18).

Рис. 1.18 Обчислення функції f (x)

Рис. 1.18 показує, що до кореня вдалося дібратися досить близько, однак його точне значення усе ще не знайдено, тому значення функції f (x) трохи відрізняється від нуля.

Якщо зажадати, щоб значення функції f (x) точно рівнялося нулю, ітераційні методи мо-

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

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

Рис. 1.19 Підбор значення x для обчислення функції f (x)

29