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

а)

б)

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

Microsoft Excel

1.6. Метод ітерацій

Нехай дано систему рівнянь:

a

11

x

1

+ a

12

x

2

+ ...+ a

1n

x

n

= b

1

a21

x1 + a22 x2 + ...+ a2n xn

= b2

(2.23)

........................................................

a

n1

x

1

+ a

n2

x

2

+ ...+ a

nn

x

n

= b

n

Припускаючи, що діагональні коефіцієнти aii

≠ 0

(i = 1,2,...,n) розв’яжемо перше рі-

вняння системи (2.23) відносно

x1 , друге – відносно x2 і т.д. Одержимо еквівалентну сис-

тему:

x1 = β1 +α12 x2 +α13 x3 + ...+α1n xn

= β2 +α21 x1 +α23 x3 + +α2n

xn

x2

(2.24)

..................................................................

= βn +αn1 x1 +αn2 x2 + +αnn−1 xn−1

xn

50

	b		= −	aij	при i ≠ j й αij	= 0 при i = j	(i , j = 1,2,...,n).
де βi =	i	, αij
				aii
	aii

Будемо вирішувати систему (2.24) методом послідовних наближень. За нульове наближення приймемо стовбець вільних членів x(0) = β (β1 ,β2 ,...,βn ). Нове наближення оде-

ржимо, підставляючи значення x(0) в систему (2.24). Запишемо формули наближень у розгорнутому вигляді:

x	(0) = β
	i		i	n
	(k +1)	= βi			(k )	(2.25)
xi				+ ∑αij xj
				j=1
(αii = 0;				i = 1,...,n; k = 0,1,2,....)
Таким чином, одержимо послідовність наближень xi(0) , xi(1) ,						xi(2) , …, xi(n) яка схо-

диться, якщо xi(n+1) − xin < ε . Цей метод називається методом ітерацій.

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

Приклад. Вирішити систему методом ітерацій:

4 x1 +0,24 x2 −0,08 x3			= 8
	x1	+ 3 x2 −0,15 x3	= 9	(2.26)
0,09
	x1	−0,08 x2 + 4 x3	= 20
0,04

Діагональні коефіцієнти 4; 3; 4 системи значно переважають над іншими коефіцієнтами при невідомих. Приведемо цю систему до нормального виду (2.24):

x1	= 2 −0,06 x2 +0,02 x3
	= 3 −0,03 x1 +0,05 x3	(2.27)
x2
	= 5 −0,01 x1 +0,02 x2
x3

За нульові наближення коренів системи (2.26) приймаємо:

x1(0) = 2 ;

x2(0) = 3 ;

x3(0) = 5

Підставляючи ці значення в праві частини рівнянь (2.27), одержимо перші наближення коренів:

x1(1) = 2 −0,06 3 + 0,02 5 = 1,92x2(1) = 3 −0,03 2 +0,05 5 = 3,19x3(1) = 5 −0,01 2 + 0,02 3 = 5,04

Далі, підставляючи ці знайдені наближення у формулу (2.27) одержимо другі наближення коренів:

x1(2) = 1,9094 ;

x2(2) = 3,1944 ;

x3(2) = 5,0446

Далі виконуємо третю підстановку і т.д. Результати обчислень наведено в таблиці 2.2

51

Таблиця 2.2

Обчислення рішення системи лінійних рівнянь методом ітерацій

k	x1(k )	x2(k )	x3(k )
0	2	3	5
1	1,92	3,19	5,04
2	1,9094	3,1944	5,0446
3	1,90923	3,19495	5,04485

ЗВЕРНІТЬ УВАГУ! NB !

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

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

шення цієї системи виробляється, як у випадку точних чисел, з точністю до m = p знаків.

1.7. Приведення системи до вигляду, зручного для ітерацій.

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

Теорема про достатню умову (2.16)

Теорема. Якщо для наведеної системи (2.24) виконано хоча б одну з умов:

	n
1)	∑	αij	< 1	(i = 1,2,...,n)
або	j=1
	n
2)	∑	αij	< 1	( j = 1,2,...,n)
	i=1

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

Наслідок. Для системи (2.23) метод ітерацій збігається, якщо виконано нерівності:

	n
aii	> ∑	aij	(i = 1,2,...,n)
	i=1
	( j≠i )

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

52

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

	2 x1 + 3 x2 − 4 x3 + x4 = 3	(A)
		(Б)
x1 − 2 x2 −5 x3 + x4 = 3
	5 x1 − 3 x2 + x3 − 4 x4 = 1	(B)
	10 x1 + 2 x2 − x3 + 2 x4 = −4	(Г)

У рівнянні (Б) коефіцієнт при x3 за модулем більше суми модулів інших коефіцієнтів, тому можна прийняти це рівняння за третє рівняння в перетвореній системі. Коефіцієнт при x1 в рівнянні (Г) також більше суми модулів інших коефіцієнтів, тому можна прийняти це рівняння за перше рівняння перетвореної системи. Таким чином, нова система має вигляд:

10 x1 + 2 x2 − x3 + 2 x4 = −4	(I )
	(II )
.................................................
	(III )
x1 − 2 x2 −5 x3 + x4 = 3
	(IV )
................................................
Аналізуючи дану систему, можна помітити, що для одержання рівняння (II )		з мак-
симальним за модулем коефіцієнтом при x2 достатньо скласти різницю (A)−(Б):
x1 + 5 x2 + x3 + 0 x4 = 0	(II )
Тепер у нову систему увійшли рівняння (A), (Б), (Г), тому в рівняння (IV )		обов’я-
зково повинне увійти рівняння (B) вихідної системи. Підбором можна переконатися, що за
рівняння (IV ) можна взяти лінійну комбінацію: 2 (A)−(Б)+ 2 (В)−(Г), тобто
3 x1 +0 x2 +0 x3 − 9 x4 = 10	(IV )

Таким чином, перетворену систему отримано за наступними перетвореннями:

(I )		(Г)
(II )	(А)−(Б)
(III )		(В)
(IV )		2 (A)−(Б)+ 2 (В)−(Г)

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

x1 = −0,4 +0 x1 −0,2 x2 + 0,1 x3 −0,2 x4
	= 0 +0,2 x1 +0 x2 −0,2 x3 + 0 x4
x2
	= −0,4 +0,2 x1 −0,4 x2 + 0 x3 + 0,2 x4
x3
	= −1,111 +0,333 x1 +0 x2 + 0 x3 + 0 x4
x4

до якої можна застосувати метод ітерацій.

1.8. Метод Зейделя

Метод Зейделя являє собою деяку модифікацію методу ітерацій. Основна ідея методу полягає в тому, що при обчисленні (k + 1)-го наближення невідомої xi враховувати вже об-

числені (k + 1)-е наближення невідомих x1 , x2 ,..., xi−1 .

53

Нехай дано наведену систему лінійних рівнянь:

n
xi = βi + ∑αij x j	(i = 1,2,...,n)
j=1

Обираємо початкове наближення:

x1(0) , x2(0) ,..., xn(0)

Далі припускаючи, що k -те наближення відомо, будемо будувати ження коренів за наступними формулами:

n

x1(k +1) = β1 + ∑αij x(jk ) j=1

n

x2(k +1) = β2 +α21 x1(k +1) + ∑α2 j x(jk ) j=2

(2.28)

(k + 1)-е набли-

	........................................		(2.29)
	i−1	n
	xi(k +1) = βi + ∑αij x(jk +1)	+ ∑αij x(jk )
	j=1	j=i
	........................................
	n−1
	xn(k +1) = βn + ∑αnj x(jk +1) +αnn xn(k )		(k = 0,1,2,...)

j=1

Або в розгорнутому вигляді:

x1(k+1) =α11 x1(k ) +α12 x2(k ) +α13 x3(k ) + ...+α1n xn(k ) + β1

x2(k+1) =α21 x1(k+1) +α22 x2(k ) +α23 x3(k ) + ...+α2n xn(k ) + β2

(2.30)

x3(k+1) =α31 x1(k+1) +α32 x2(k+1) +α33 x3(k ) + ...+α3n xn(k ) + β3

M

xn(k+1) =αn1 x1(k+1) +αn2 x2(k+1) +αn3 x3(k+1) + ...+αnn−1 xn(k−+11) +αnn xn(k ) + βn

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

Звичайно, але не завжди, метод Зейделя дає кращу збіжність.

Розглянемо геометричну інтерпретацію метода Зейделя на прикладі розв’язання системи рівнянь:

2 x + y = 2x − 2 y = −2

для якої необхідні і достатні умови збіжності виконуються

Оскільки під час обчислення змінної х зберігається незмінним значення y, то геометричним еквівалентом методу є рух по горизонталі до перетину з прямою, що відображує перше рівняння (рис. 2.3). Потім рух здійснюється по вертикалі за збереження незмінним знайденого значення х до перетину з прямою, що зображує друге рівняння і т.д.

54

2,5

2

1,5 хy1

y3

1 y2

2x+y=2

x 2y= 2

0,5

0

0

х2 0,5х3

1 х1

1,5

0,5

1

Рис. 2.3. Геометрична інтерпретація методу Зейделя

Приклад. Методом Зейделя розв’язати систему рівнянь:

10 x1 + x2 + x3 = 122 x1 + 10 x2 + x3 = 13

2 x1 + 2 x2 + 10 x3 = 14

Приведемо систему до виду, зручному для ітерацій:

		x1 = 1,2 −0,1 x2 −0,1 x3
			= 1,3 −0,2 x1 −0,1 x3
		x2
			= 1,4 −0,2 x1 −0,2 x2
		x3
За нульові наближення коренів візьмемо:
x1(0) = 1,2			x2(0) = 0	x3(0) = 0
Застосовуючи метод Зейделя послідовно одержимо:
Перший крок:
	x1 = 1,2 −0,1 0 −0,1 0 = 1,2
		= 1,3	−0,2 1,2 −0,1 0 = 1,06
	x2
		= 1,4	−0,2 1,2 −0,2 1,06 = 0,948
Другий крок:	x3
x1	= 1,2 −0,1 1,06 −0,1 0,948 = 0,9992
	= 1,3	−0,2	0,9992 −0,1 0,948 = 1,00536
x2
	= 1,4	−0,2	0,9992 −0,2 1,00536 = 0,999098
x3

і т.д.

Результати обчислень із точністю до чотирьох знаків наведено в таблиці 2.3

55

Обчислення рішення системи лінійних рівнянь методом Зейделя						Таблиця 2.3
k		x1(k )		x2(k )		x3(k )
0		1,2000		0,0000		0,0000
1		1,2000		1,0600		0,9480
2		0,9992		1,0054		0,9991
3		0,9996		1,0001		1,0001
4		1,0000		1,0000		1,0000
5		1,0000		1,0000		1,0000
Точні значення корені:		x1 = 1 , x2 = 1 ,	x3 = 1

1.9. Реалізація метода Зейделя в MS Excel

Приклад розрахунку по методу Зейделя в MS Excel наведено на рис. 2.4.

§2. Методи обробки даних: інтерполяція

Узагальному вигляді задача інтерполяції (2.17) полягає в тому, щоб знайти таку, аналітично висловлену (тобто у вигляді формули), функцію, щоб вона приблизно була ін-

шою функцією, заданою таблицею на відрізку [a,b].

Інтерполяція (2.17)

Інтерполяція (від лат. inter – між і polio – виправляти, згладжувати), в математиці і статистиці – відшукування проміжних значень величини по деяких відомих її значеннях.

2.1. Постановка задачі

Нехай функція y = f (x) задана таблицею своїх значень на деякій кінцевій безлічі значень аргументу x0 , x1 ,..., xn (вузли інтерполяції).

	x		x1	x2	…		xn
	у		y1	y2	…		yn
де yi = f (xi ) (i = 0,1,			...,n)
Потрібно знайти функцію F (x) (інтерполююча функція), що належить певному кла-
су і приймає у вузлах		інтерполяції		x0 , x1 ,..., xn	задані	значення y0 , y1 ,..., yn , тоб-
тоF (x0 )= y0 , F (x1 )= y1 ,…, F (xn )= yn				або в загальному вигляді:

F (xi )= f (xi )= yi (i = 0,1,...,n).

Геометрично це означає, що потрібно знайти криву певного типу, що проходить через задану систему точок на площині з координатами (xi , yi ) (i = 0,1,...,n). На графіку це виглядає таким чином (рис.2.5):

56

а)

б)

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

57

y = F (x)

X0 X1

X2

Xn

Рис. 2.5. Геометрична інтерпретація постановки задачі інтерполяції

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

У наведеній загальній постановці задача інтерполяції має незліченну безліч рішень. Якщо ж функцію F (x) шукати у вигляді функції певного вигляду, то задача стає од-

нозначною. Найчастіше функцію F (x) представляють у вигляді алгебраїчного багаточлена

деякого ступеню:

F (x)= Pn (x)= an xn + an−1 xn−1 + ...+ a0 .

Інтерполяція за допомогою багаточленів називається алгебраїчною інтерполяцією, а багаточлен Pn (x) називається інтерполяційним багаточленом.

Одержану інтерполяційну формулу y = F (x) звичайно використовують для наближеного обчислення значень даної функції f (x) при значеннях аргументу, відмінних від ву-

злів інтерполяції. Така операція називається інтерполяцією функції f (x). Більш точно, розрізняють інтерполяцію у вузькому значенні, коли x x0 , xn і екстраполяцію (2.18), коли x x0 , xn .

Екстраполяція (2.18)

Екстраполяція (від екстра... і лат. polio — пригладжую, змінюю):

1)поширення висновків, отриманих із спостереження над однією частиною явища, на іншу частину його.

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

Щоб знайти значення функції при будь-якому значенні аргументу х, необхідно побудувати аналітичну функцію F (x), яка співпадала би з невідомою функцією f (x) у вузлах таблиці і наближалася до неї поза вузлами. Тим самим, буде, як би відновлена невідома функція f (x) замінена тепер на відому – F (x). Ступінь погрішності інтерполяції, тобто різни-

ця f (x)− F (x) при заданому значенні x залежить від ширини інтервалу h = xi+1 − xi і від вигляду інтерполюючої функції.

58

ЗВЕРНІТЬ УВАГУ! NB !

Тобто:

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

якого в n + 1 -ій точці x0 , x1 ,..., xn співпадають із заданими

значеннями y0 , y1 ,..., yn .

Pn (xi )= yi

(i = 0,1,...,n)

(2.31)

Задача алгебраїчної інтерполяції має єдине рішення і це рішення дається інтерполяційним багаточленом Ж.Л. Лагранжа (2.19).

Ж.Л.Лагранж (2.19)

ЛАГРАНЖ (Lagrange) Жозеф Луї (25 січня 1736, Турін — 10 квітня 1813, Париж), французький математик і механік, іноземний почесний член Петербурзької АН (1776).

У 1754 у віці 18 років став професором артилерійської школи Туріну. Організував гурток, з якого згодом виросла академія наук Туріну. У 1766 став президентом Берлінської академії наук, в 1787 – дійсним членом Паризької академії наук. Брав участь в розробці метричної системи заходів в паризькому Інституті і Бюро довгот. Під час Великої французької революції (1789) одержав посаду сенатора.

Автор праць по варіаційному численню, де їм розроблено основні поняття і методи, математичному аналізу, теорії чисел, алгебри, диференціальним рівнянням. Його твори по математиці, астрономії і механіці складають 14 томів.

2.2. Інтерполяційний багаточлен Лагранжа

Лагранжем введено формулу для інтерполяції, яка є загальнішою, оскільки її можна застосовувати для випадку довільного розташування вузлів інтерполяції (нерівномірно розташованих).

Так, рішення сформульованої вище задачі алгебраїчної інтерполяції можна легко оде-

ржати після рішення наступної окремої задачі:	побудувати багаточлени Li (x) ступеняn ,
такі, що:
1, якщо i = j		(2.32)
Li (xj )=	≠ j
0, якщо i

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

Оскільки багаточлен Li (x) обертається в нуль в n крапках x0 , x1 ,..., xi−1

то він має вигляд:

Li (x)= Ci (x − x0 ) (x − x1 ) ... (x − xi−1 ) (x − xi+1 ) ... (x − xn )

де Ci – постійний коефіцієнт; незалежний від x . Вважаючи x = xi і враховуючи, що Li (xi )= 1 , одержимо:

Ci (xi − x0 ) (xi − x1 ) ... (xi − xi−1 ) (xi − xi+1 ) ... (xi − xn )= 1

Звідси знаходимо вираз для постійної Ci :

Ci = ( − ) ( − ) ( −1 ) ( − ) ( − ) xi x0 xi x1 ... xi xi−1 xi xi+1 ... xi xn

, xi+1 ,..., xn ,

(2.33)

Після підстановки цього виразу у формулу (2.33), одержимо рішення окремої задачі у вигляді:

59