Alg i metodi vichisl / matr_oper_Excel

31

Рис. 2.8. Розв’язання СЛАР за методом квадратного кореня

32

2.7. Розв’язання систем лінійних рівнянь за схемою Халецького

Метод Халецького ґрунтується на факторизації матриці A системи рівнянь Ax=b, тобто у поданні її у вигляді добутку нижньої трикутної матриці L ( lij = 0,i < j ) і верхньої трикутної матриці R з одиничною

діагоналлю ( rij = 0,i > j, rii =1 ), тобто A=LR.

Тоді елементи матриць L і R визначаються з системи n2 рівнянь

aij = ∑n lik rkj , i, j =1, n k =1

Специфічний вигляд матриць L і R дозволяє розв’язок цієї системи записати у явному вигляді

			li1 = ai1 ,
			j−1				(i ≥ j >1)
	lij = aij −∑lik rkj
	і		k =1
						a1 j
			r		=
			1 j			l11
		1			i−1
	rij =		aij	−∑lik rkj , i < j
		lii
					k =1

Після визначення матриць L і R розв’язок системи зводиться до знаходження розв’язку двох систем рівнянь Ly=b, Rx=y. Так як матриці L і R

– трикутні, ці системи легко розв’язуються, а саме:

				yi	=	b1	,
						l
					11
			1		i−1
	yi	=		bi −∑lik yk , (i >1)
			lii
					k =1

і

xn = yn

xi = yi − ∑n lik xk , (i < n)

k=i+1

Зцих формул видно, що числа yi зручно обчислювати разом з

коефіцієнтами lij . Ця схема обчислень називається схемою Халецького.

Застосуємо її до розв’язання наступного прикладу (рис. 2.9).

Введемо в електронну таблицю в комірки A4:A7; D4:D7; F4:F7; H4:H7 матрицю A, в I4:I7 – стовпець вільних членів b.

Оскільки діагональні елементи матриці R дорівнюють одиниці, заповнимо комірки В10, D11, F12, H13 числом 1.

Так як li1 = ai1 (i =1,2,3,4), то елементи стовпця x1 з першого розділу таблиці

(діапазон комірок A4:A7) переносимо в стовпець x1 другого розділу (діапазон комірок A10:A13).

33

Щоб отримати перший рядок другого розділу ділимо всі елементи першого рядка першого розділу (комірки D10, F10, H10, І10) на елемент l11 (комірка A10), у нашому випадку на 3.

Переходимо до заповнення стовпця x2 з другого розділу, починаючи з другого рядка. Застосовуємо формули для обчислення l j 2 (j = 2,3,4) в

комірках С11:С13.

Рис. 2.9. Розв’язання СЛАР за схемою Халецького

Далі визначаючи r2 j (j = 3,4), y2 заповнюємо другий рядок другого розділу

(комірки F11, H11, І11).

Потім переходимо до стовпця x3, обчислюючи його елементи l33 , l43 (комірки Е12:Е13).

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

Таким чином, заповнення другого розділу здійснюється способом “ялинки”: стовпець – рядок, стовпець – рядок і т.д.

В третьому розділі в комірках І16:І19 обчислюємо значення невідомих x4 , x3 , x2 , x1 .

Всі формули, використані в таблиці, відображені на рис. 2.10.

34

Рис. 2.10. Формули для обчислень за схемою Халецького

35

Робота №13. Розв’язати систему рівнянь за схемою Халецького

№

Система

№

Система

0,63x1 +1,00x2

+ 0,71x3 + 0,34x4

= 2,08

3,51x1 +0,17x2

+3,75x3 −0,28x4

= 0,75

1.

1,17x1 + 0,18x2

−0,65x3 + 0,71x4

= 0,17

2.

4,52x1 + 2,11x2

−0,11x3 −0,12x4

=1,11

2,71x

−0,75x

2

+1,17x

3

− 2,35x

4

=1,28

− 2,11x +3,17x

2

+ 0,12x

3

−0,15x

4

= 0,21

1

1

3,58x

+ 0,21x

2

−3,45x

3

−1,18x

4

= 0,05

3,17x

+1,81x

2

−3,17x

3

+ 0,22x

4

= 0,05

1

1

0,17x1 + 0,75x2

−0,18x3 + 0,21x4

= 0,11

−1,00x1 + 0,13x2

− 2,00x3 −0,14x4 = 0,15

3.

0,75x1 + 0,13x2

+ 0,11x3 +1,00x4

= 2,00

4.

0,75x1 + 0,18x2

−0,21x3 −0,77x4

= 0,11

−0,33x

+ 0,11x

2

+3,01x

3

− 2,01x

4

= 0,11

0,28x

−0,17x

2

+ 0,39x

3

+ 0,48x

4

= 0,12

1

1

0,11x

+1,12x

2

+1,11x

3

−1,31x

4

= 0,13

1,00x

+3,14x

2

−0,21x

3

−1,00x

4

= −0,11

1

1

3,01x1 −0,14x2

+1,00x3 −0,15x4

=1,00

1,15x1 + 0,62x2

−0,83x3 + 0,92x4

= 2,15

5.

−1,75x1 +1,11x2

+ 0,13x3 −0,75x4

= 0,13

6.

0,82x1 −0,54x2

+ 0,43x3 −0,25x4

= 0,62

0,17x1 − 2,11x2

+ 0,71x3 −1,71x4

=1,00

0,24x1 +1,15x2

−0,33x3 +1,42x4

= −0,62

0,21x

+ 0,21x

2

+ 0,35x

3

+ 0,33x

4

= 0,17

0,73x

−0,81x

2

+1,27x

3

−0,67x

4

= 0,88

1

1

1,00x1 −0,17x2

+0,11x3 −0,15x4

= 0,17

0,64x1 + 0,72x2

−0,83x3 + 4,2x4

= 2,23

7.

0,14x1 + 0,21x2

−0,33x3 + 0,11x4

=1,00

8.

0,58x1 −0,83x2

+1,43x3 −0,62x4

=1,71

0,22x1 +3,44x2

−0,11x3 + 0,12x4

= 2,00

0,86x1 + 0,77x2

−1,83x3 + 0,88x4

= −0,54

0,11x

+ 0,13x

2

+ 0,12x

3

+ 0,14x

4

= 0,13

1,32x

−0,52x

2

−0,65x

3

+1,22x

4

= 0,65

1

1

1,42x1 + 0,32x2

−0,42x3 + 0,85x4

=1,32

0,73x1 +1,24x2

−0,38x3 −1,43x4

= 0,58

9.

0,63x1 −0,43x2

+1,27x3 −0,58x4

= −0,44

10.

1,07x1 −0,77x2

+1,25x3 + 0,66x4

= −0,66

0,84x1 − 2,23x2

−0,52x3 + 0,47x4

= 0,64

1,56x1 + 0,66x2

+1,44x3 + −0,87x4

=1,24

0,27x

+1,37x

2

+ 0,64x

3

−1,27x

4

= 0,85

0,75x

+1,22x

2

−0.83x

3

+ 0,37x

4

= 0,92

1

1

1,32x1 −0,83x2

−0,44x3 + 0,62x4

= 0,68

0,11x1 −0,17x2

+ 0,72x3 −0,34x4

= 0,17

11.

0,83x1 + 0,42x2

−0,56x3 + 0,77x4

=1,24

12.

0,81x1 + 0,12x2

−0,91x3 + 0,17x4

=1,00

0,58x

−0,37x

2

+1,24x

3

−0,62x

4

= 0,87

0,17x

−0,18x

2

+1,00x

3

+ 0,23x

4

= 0,21

1

1

0,35x

+ 0,66x

2

−1,38x

3

−0,93x

4

= −1,08

0,13x + 0,17x

2

−0,99x

3

+ 0,35x

4

= 2,71

1

1

0,18x1 + 2,11x2

+ 0,13x3 −0,22x4

= 0,22

2,00x1 + 0,05x2

−3,01x3 −0,11x4

= 0,21

13.

0,33x1 −0,22x2 −1,00x3 + 0,17x4

= 0,11

14.

1,00x1 − 2,00x2

+3,02x3 + 0,05x4

= 0,18

−1,00x

+ 0,11x

2

+ 2,00x

3

−0,45x

4

=1,00

0,17x

+ 0,99x

2

− 2,00x

3

−0,17x

4

= 0,17

1

1

7,00x

−0,17x

2

−0,22x

3

+ 0,33x

4

= 0,21

0,33x −0,07x

2

+ 0,33x

3

+ 2,00x

4

= −0,17

1

1

0,17x1 −0,13x2

−0,11x3 −0,12x4 = 0,22

0,11x1 +1,13x2

−0,17x3 + 0,18x4

=1,00

15.

1,00x1 −1,00x2

−0,13x3 + 0,13x4

= 0,11

16.

0,13x1 −1,17x2 + 0,18x3 + 0,14x4

= 0,13

0,35x1 + 0,33x2

+ 0,12x3 + 0,13x4

= 0,12

0,11x1 −1,05x2

−0,17x3 −0,15x4

= 0,11

0,13x

+ 0,11x

2

−0,13x

3

−0,11x

4

=1,00

0,15x −0,05x

2

+ 0,18x

3

−0,11x

4

=1,00

1

1

36

2.8. Розв’язання систем лінійних рівнянь методом ітерацій

Зведемо систему лінійних алгебраїчних рівнянь до вигляду x=Ax+b. Виходячи з довільного вектору x(0), за який можна взяти, наприклад,

стовпець вільних членів x(0) =b , будуємо ітераційний процес x(k +1) = Ax(k ) +b (k =1,2,K)

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

xi(0) =bi ,

xi(k +1) = ∑n aij x(jk ) +bi j=1

(i =1,K, n; k = 0,1,2,K)

Дана схема реалізує метод послідовних наближень або метод ітерацій. Здійснюючи ітерації, отримуємо послідовність векторів x(1), x(2),K, x(k ),K Для успішного застосування методу ітерацій елементи матриці А повинні бути малі за модулем. Процес ітерацій завершують, якщо

виконуються відповідні оцінки похибки наближеного розв’язку.

Введемо в електронну таблицю в комірки В3:Е6 матрицю A, в F3:F6 – стовпець вільних членів b (рис. 2.11).

Рис. 2.11. Розв’язання СЛАР методом ітерацій

37

Умови збіжності ∑n aij ≤α <1 (i =1,2,L, n) для даної системи виконані.

j=1

За початковий вектор x(0) візьмемо стовпець вільних членів. Розташуємо початкові наближення в комірках діапазону B11:D11. Введемо в комірки

діапазону B12:D12 формули, що визначають перше наближення розв’язків

x1(0), x2(0), x3(0), x4(0) :

=B$3*B11+C$3*C11+D$3*D11+E$3*E11+F$3 =B$4*B11+C$4*C11+D$4*D11+E$4*E11+F$4

=B$5*B11+C$5*C11+D$5*D11+E$5*E11+F$5, =B$6*B11+C$6*C11+D$6*D11+E$6*E11+F$6

відповідно. Далі використовуючи першу формулу в діапазон комірок D11:D20. Обчислення проводимо до

стануть меншими ε=10-4.

механізм автозаповнення копіюємо B11:В20, другу – в С11:С20, третю – в тих пір, поки величини xi(k +1) − xi(k ) не

Робота №14. Методом ітерацій розв’язати систему лінійних рівнянь

№					Система																		№						Система
	x			= 0,23x	−0,04x		2		+ 0,21x		3				−0,18x				4			+1,24		x			= 0,21x		+ 0,12x	2			−0,34x	3			−0,16x	4			−0,64
		1		1																					1		1
1.	x2			= 0,45x1 −0,23x2					+ 0,06x3 −0,88														2.	x2			= 0,34x1 −0,08x2						+ 0,17x3 −0,18x4								+1,42
	x		3	= 0,26x	+ 0,34x			2	−0,11x		3				+ 0,62									x		3	= 0,16x		+ 0,34x		2		+ 0,15x	3			−0,31x	4			−0,42
				1																							1
	x		4	= 0,05x	−0,26x			2	+ 0,34x				3		−0.12x					4		−1,17		x		4	= 0,12x		−0,26x		2		−0,08x		3		+ 0,25x			4	+ 0,83
				1																							1
	x			= 0,32x	−0,18x	2			+ 0,02x		3				+ 0,21x				4			+1,83		x			= 0,42x		−0,52x		2		+ 0,03x		3		+ 0,44
		1		1																					1		1
3.	x2			= 0,16x1 + 0,12x2					−0,14x3 + 0,27x4													−0,65	4.	x2			= 0,31x1 −0,26x2						−0,36x3 +1,42
	x		3	= 0,37x	+ 0,27x			2	−0,02x				3		−0,24x					4		+ 2,23		x		3	= 0,12x		+ 0,08x		2		−0,14x	3			−0,24x		4		−0,83
				1																							1
	x		4	= 0,12x	+ 0,21x		2		−0,18x		3				+ 0,25x				4			−1,13		x		4	= 0,15x		−0,35x		2		−0,18x	3			−1,42
				1																							1
	x			= 0,18x	−0,34x	2			−0,12x	3				+ 0,15x			4				−1,33			x			= 0,13x		+ 0,23x	2			−0,44x	3			−0,05x		4		+ 2,13
		1		1																					1		1
5.	x2			= 0,11x1 + 0,23x2					−0,45x3 + 0,32x4													+ 0,84	6.	x2			= 0,24x1 −0,31x3 +0,15x4										−0,18
	x		3	= 0,05x	−0,12x		2		+ 0,14x		3				−0,18x			4			−1,16			x		3	= 0,06x		+ 0,15x		2		−0,23x		4		+1,44
				1																								1
	x		4	= 0,12x	+ 0,08x		2		+ 0,06x			3			+ 0,57									x		4	= 0,72x		−0.08x			2	−0,05x			3	+ 2,42
				1																								1
	x			= 0,17x	+ 0,31x	2			−0,18x	3				+ 0,22x				4			−1,71			x			= 0,13x		+0,27x	2			−0,22x		3		−0,18x		4		+1,21
		1		1																					1		1
7.	x2			= −0,21x1 + 0,33x3 + 0,22x4												+ 0,62							8.	x2			= −0,21x1 −0,45x3 + 0,18x4 −0,33
	x		3	= 0,32x	−0,18x		2		+ 0,05x		3				−0,19x				4			−0,89		x		3	= 0,12x		+ 0,13x	2			−0,33x	3			+ 0,18x	4			−0,48
				1																							1
	x		4	= 0,12x	+ 0,28x		2		−0,14x		3				+ 0,93									x		4	= 0,33x		−0,05x		2		+ 0,06x			3	−0,28x			4	−0,17
				1																								1
	x			= 0,19x	−0,07x		2		+ 0,38x		3				−0,21x				4			−0,81		x			= 0,22x	2	−0,11x	3			+ 0,31x	4			+ 2,7
		1		1																					1
9.	x2			= −0,22x1 + 0,08x2 + 0,11x3 + 0,33x4 −0,64																			10.	x2			= 0,38x1 −0,12x3 + 0,22x4										−1,5
	x		3	= 0,51x	−0,07x		2		+ 0,00x			3			−0,11x				4			+1,71		x		3	= 0,11x		+ 0,23x	2			−0,51x	4			+1,2
				1																							1
	x		4	= 0,33x	−0,41x		2		−1,21															x		4	= 0,17x		−0,21x		2		+ 0,31x	3			−0,17
				1																							1

38

№				Система													№				Система
	x		= 0,07x	−0,08x		2		+ 0,11x		3			−0,18x	4		−0,51		x		= 0,05x	−0,06x		2	−0,12x	3		+ 0,14x	4		− 2,17
	1		1															1		1
11.	x2		= 0,18x1 + 0,52x2					+ 0,21x4					+1,17				12.	x2		= 0,04x1 −0,12x2				+ 0,68x3 + 0,11x4						+1,4
	x	3	= 0,13x	+ 0,31		−0,21x			4		−1,02							x	3	= 0,34x	+ 0,08x		2	−0,06x		3	+ 0,44x		4	− 2,1
			1	2																1
	x	4	= 0,08x	−0,33x		3		+ 0,28x				4	−0,28					x	4	= 0,11x	+ 0,12x	2		−0,03x	4		−0,8
			1																	1
	x		= 0,08x	−0,03x	2			−0,04x			4		−1,2					x		= 0,12x	−0,23x	2		+ 0,25x	3		−0,16x	4		+1,24
	1		1															1		1
13.	x2		= 0,51x2	+ 0,27x3 −0,08x4									+ 0,81				14.	x2		= 0,14x1 + 0,34x2				−0,18x3 + 0,24x4						−0,89
	x	3	= 0,33x	−0,37x		3		+ 0,21x			4		−0,92					x	3	= 0,33x	+ 0,03x		2	+ 0,46x		3	−0,32x		4	+1,15
			1																	1
	x	4	= 0,11x	+ 0,03x	3			+ 0,58x		4			+ 0,17					x	4	= 0,12x	−0,05x		2	+ 0,15x	4		−0,57
			1																	1
	x		= 0,23x	−0,14x	2			+ 0,06x		3			−0,12x	4		+1,21		x		= 0,14x	+ 0,23x	2		+ 0,18x	3		+ 0,17x	4		−1,42
	1		1															1		1
15.	x2		= 0,12x1 + 0,32x3 −0,18x4										−0,72				16.	x2		= 0,12x1 −0,14x2				+ 0,08x3 + 0,09x4						−0,83
	x	3	= 0,08x	−0,12x	2			+ 0,23x			3		+ 0,32x		4	−0,58		x	3	= 0,16x	+ 0,24x		2	−0,35x		4	+1,21
			1																	1
	x	4	= 0,25x	+ 0,22x			2	+ 0,14x				3	+1,56					x	4	= 0,23x	−0,08x		2	+ 0,55x		3	+ 0,25x		4	+ 0,65
			1																	1

2.9. Розв’язання систем лінійних рівнянь методом Зейделя

Метод Зейделя є деякою модифікацією методу ітерацій. Він полягає в тому, що при обчисленні (k+1)-го наближення невідомого xi при i>1 використовуються вже обчислені раніше (k+1)-і наближення невідомих x1, x2, ..., xi-1. Таким чином, для системи рівнянь x=Ax+b обчислення ведуться за формулами

i−1	n
xi(k +1) = ∑aij x(jk +1) + ∑aij x(jk ) +bi
j=1	j=i

(i =1,K, n; k = 0,1,2,K)

Якщо подати матрицю А у вигляді суми двох матриць A = A− + A+ , де A− та A+ – ліва та права трикутна відповідно, тобто

−	aij ,i > j
A− = (aij− ), aij	= 0, i ≤ j ,
	0, i >	j
A+ = (aij+ ), aij+ =		j	,
	aij, i ≤

то тоді ітераційний процес Зейделя можна записати у матричному вигляді x(k +1) = A− x(k +1) + A+ x(k ) +b .

Як правило, метод Зейделя дає кращу збіжність, ніж метод простої ітерації. Крім того, при його застосуванні при обчисленні xi(k +1) не має

необхідності зберігати значення x1(k ), ..., xi(−k1).

39

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

Розв’яжемо методом Зейделя систему, матриця А якої введена в комірки діапазону B3:D5, стовпець вільних членів b – в E3:E5 електронної таблиці (рис. 2.12). За початковий вектор x(0) візьмемо стовпець вільних членів. Розташуємо початкові наближення в комірках діапазону B10:D10. Введемо в комірки діапазону B11:D11 формули, що визначають перше наближення розв’язків:

=B$3*B10+C$3*C10+D$3*D10+E$3 =B$4*B11+C$4*C10+D$4*D10+E$4, =B$5*B11+C$5*C11+D$5*D10+E$5

відповідно. Далі використовуючи механізм автозаповнення копіюємо першу формулу в діапазон комірок B11:В20, другу – в С11:С20, третю – в D11: D 20. Обчислення проводимо з точністю до 10-4.

Рис. 2.12. Розв’язання СЛАР методом Зейделя

40

Робота №15. Методом Зейделя розв’язати систему лінійних рівнянь

№										Система
1.	x			= 0,24x		+0,21x	2			+ 0,06x			3			−0,34x				4			+1,42
		1			1
	x2			= 0,05x1 + 0,32x2						+ 0,12x4						−0,57
	x		3	= 0,356x −0,27x						2	−0,05x					4	+ 0,68
						1
	x		4	= 0,12x		−0,43x		2		+ 0,34x			3			−0,21x				4			− 2,14
					1
2.	x			= 0,17x		+0,27x	2			−0,13x		3			−0,11x			4				−1,42
		1		1
	x2			= 0,13x1 −0,12x2						+ 0,09x3 −0,−6x4													+ 0,48
	x		3	= 0,11x		+ 0,05x	2			−0,02x		3			+ 0,12x				4				− 2,34
				1
	x		4	= 0,13x		+ 0,18x	2			+ 0,24x			3		+ 0,43x					4			+ 0,72
					1
3.	x			= 0,15x		+0,05x	2			−0,08x		3			+ 0,14x				4				−0,48
		1		1
	x2			= 0,32x1 −0,43x2						−0,12x3 + 0,11x4													+1,24
	x		3	= 0,17x		+ 0,06x		2		−0,08x			3			+ 0,12x				4			+1,15
					1
	x		4	= 0,21x		−0,16x	2			+ 0,36x			3			−0,88
					1
4.	x			= 0,28x		−0,17x	3			+ 0,06x			4			+ 0,21
		1			1
	x2			= 0,52x1 + 0,12x3 + 0,17x4												−1,17
	x		3	= 0,17x		−0,18x	2			+ 0,21x		3			−0,81
					1
	x		4	= 0,11x		+ 0,22x	2			+ 0,03x			3			+ 0,05x				4			+ 0,72
					1
5.	x			= 0,52x	2	+ 0,08x		3		+ 0,13x			4			−0,22
		1
	x2			= 0,07x1 −0,38x2						−0,05x3 + 0,41x4													+1,8
	x		3	= 0,04x		+ 0,42x			2	+ 0,11x			3			−0,07x				4			−1,3
					1
	x		4	= 0,17x		+ 0,18x	2			−0,13x		3			+ 0,19x			4				+ 0,33
					1
6.	x			= 0,01x		+ 0,02x	2			−0,62x			3		+ 0,08x					4			−1,3
		1		1
	x2			= 0,03x1 + 0,28x2						+ 0,33x3 −0,07x4													+1,1
	x		3	= 0,09x		+ 0,13x	2			+ 0,42x			3			+ 0,28x					4		−1,7
					1
	x		4	= 0,19x		−0,23x		2		+ 0,08x			3			+ 0,37x					4		+1,5
					1
7.	x			= 0,17x	2	−0,33x	3			+ 0,18x		4			−1,2
		1
	x2			= 0,18x2		+ 0,43x3 −0,08x4										+ 0,33
	x		3	= 0,22x		+ 0,18x		2		+ 0,21x			3			+ 0,07x				4			+ 0,48
					1
	x		4	= 0,08x		+ 0,07x			2	+ 0,71x				3		+ 0,04x					4		−1,2
					1
8.	x			= 0,03x		−0,05x	2			+ 0,22x			3			−0,33x				4			+ 0,43
		1			1
	x2			= 0,22x1 + 0,55x2						−0,88x3 + 0,07x4													−1,8
	x		3	= 0,33x		+ 0,13x	2			−0,08x		3			−0,05x					4			−0,8
					1
	x		4	= 0,08x		+ 0,17x		2		+ 0,29x				3		+ 0,33x					4		+1,7
					1