CKT_l.r.01_SLAU / Решение СЛАУ

16

2.2.Визначені системи m лінійних алгебраїчних рівнянь

зn невідомими ( m > n )

Нагадаємо, що система m лінійних алгебраїчних рівнянь з n невідомими

має вигляд:

a

x

1

+ a

12

x

2

+ ... + a

1n

x

n

= b

11

1

a

21x1 + a 22 x2

+ ... + a 2n xn

= b2

.

(2.9)

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

a

m1

x

1

+ a

m 2

x

2

+ ... + a

mn

x

n

= b

n

Якщо здійснити наступні дії:

∙з коефіцієнтів при невідомих даної системи сформувати матрицю А;

∙з шуканих невідомих – вектор Х;

∙з вільних членів – вектор В,

тобто

									17
a		11	a	12	a	13	...	a	1n			x					b
														1				1
a 21			a 22		a 23		...	a 2n				x 2					b2
A =	...		...		... ... ...					.	;	X =	...			;	B =	...		,
			a m2		a m3		...	a mn
a m1												x n					bm

то цю систему рівнянь можна представити в матричному вигляді:

A × X = B .

(2.10)

В прямокутній матриці A сумісної системи m лінійних алгебраїчних рівнянь з n невідомими ( m > n ) завжди можна підібрати будь-які n рядків і створити з них квадратну матрицю n -го порядку. Загальна кількість усіх так створених квадратних матриць може бути великою, але скінченою.

Якщо визначники всіх цих матриць дорівнюють нулю, то дана сумісна система є невизначеною, тобто має нескінченну кількість розв'язків.

Якщо серед усіх цих матриць існує хоча б одна, визначник якої не дорівнює нулю, то дана сумісна система є визначеною, тобто буде мати єдиний розв'язок. При цьому отриманий розв'язок системи рівнянь буде задовольняти всім m рівнянням. На такому підборі n рядків для створення квадратної матриці n -го порядку, визначник якої не дорівнює нулю, базується один з підходів до розв'язання систем, у яких m > n . Однак складність його реалізації істотно зростає з ростом значень m та n .

При великих значеннях m та n на практиці частіше використовується підхід,

заснований на методі найменших квадратів. Однією з переваг цього підходу є прос-

тота його програмної реалізації на комп'ютері. Ідея даного підходу та технологія розв'язання систем за його допомогою в пакеті Mathcad наведена нижче.

Для отримання за допомогою цього підходу розв'язку системи рівнянь слід здійснити наступні дії:

·обидві частини матричного рівняння системи слід помножити зліва на транспоновану матрицю системи AT : AT × A × X = AT × B;

·якщо для матриці AT × A існує обернена матриця (AT × A)−1 , то обидві части-

ни отриманого співвідношення слід помножити зліва на матрицю (AT × A)−1 :

(AT × A)−1 × AT × A × X = (AT × A)−1 × AT × B ;

·з урахуванням того, що (AT × A)−1 × (AT × A) = (AT × A) × (AT × A)−1 = E , де E –

одинична матриця, отримаємо розв'язуючу формулу

X = (AT × A)−1 × AT × B ,

(2.11)

за якою визначається розв'язок системи m лінійних рівнянь з n невідомими при m > n .

18

Крім того, в Mathcad такі системи лінійних алгебраїчних рівнянь можна розв’язати за допомогою вбудованої блокової структури Given – Find, що базується на одному з градієнтних методів, а також за допомогою вбудованої блокової струк-

тури Given – MinErr, в якій реалізовано алгоритм методу найменших квадратів.

Таким чином, в середовищі Mathcad розв’язок визначеної системи лінійних алгебраїчних рівнянь (випадок m > n ) можна знайти:

1)За допомогоюметоду найменших квадратів.

2)За допомогою блокової структури Given – Find.

3)За допомогою блокової структури Given – MinErr.

4)За допомогою вбудованої системи програмування Mathcad.

Нижче наведено приклади розв’язання таких систем за допомогою вище-

згаданих можливостей Mathcad.

Задача 7. Розв’язати систему лінійних алгебраїчних рівнянь

	5 x	1	+ x 2		+ 2 x 3			= 195
	3 x		+ 5 x		2 + 2 x 3			= 265
		1
		+ 2 x 2			+ 5 x 3		= 185
x 1
	2 x	1	+ x	2	+ x	3	= 100
	2 x 1		+ 2 x 2 + x 3					= 130

за допомогою методу найменших квадратів.

Розв’язання задачі

19

Задача 8. Розв’язати систему лінійних алгебраїчних рівнянь попередньої

задачі за допомогою блокової структури Given – Find.

Розв’язання задачі

Задача 9. Розв’язати систему лінійних алгебраїчних рівнянь задачі 7 за

допомогою блокової структури Given – MinErr.

Розв’язання задачі

				20
2.3. Дослідження систем			m лінійних рівнянь з n невідомими
Якщо в заданій прямокутній матриці
a		11	a	12	a	13	...	a	1n
a21			a22		a23		...	a2n
A =	... ...				... ... ...					.	,
			am2		am3		...	amn
am1

яка має m рядків і n стовпців, виділимо k довільних рядків і k довільних стовпців ( k £ m , k £ n ), то визначник k -го порядку, який складається з елементів матриці A , що розташовані на перетині виділених рядків і стовпців, називається мінором k -го порядку.

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

Якщо ранги двох матриць A і B є рівними: rank(A) = rank(B) , то матриці A і B називаються еквівалентними: A ~ B .

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

Нагадаємо, що під елементарними перетвореннями матриці розуміють:

∙Заміну рядків стовпцями, а стовпців – рядками (транспонування матриці).

∙Переставлення рядків матриці.

∙Множення будь-якого рядка матриці на довільне, відмінне від нуля число.

∙Додавання до елементів будь-якого рядка відповідних елементів іншого рядка, помноженого на довільне число.

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

В середовищі Mathcad ранг будь-якої матриці A можна обчислити за допомогою вбудованої функції rank(A) .

Перейдемо до розв'язання довільної системи m лінійних алгебраїчних рівнянь з n невідомими, матричний вигляд якої має вид:

						A × X = B											(2.11)
де
a	11	a	12	a	13	...	a	1n				b			x
												1				1
a	21	a 22		a 23		...	a 2n				b2				x	2
A =		...		...		... ...			.	;	B =			;	X =		.
...											...				...
		a m2		a m3		...	a mn
a m1											bm				x n

21

Якщо до матриці A приєднати праворуч вектор B , то отримаємо розширену матрицю системи

		a	a	...	a	b
	=	11	12		1n	1
A		a21	a22	...	a2n	b2
r				... ...		...	.
		... ...
			am2	...	amn
		am1				bm

Розглянемо тепер таке важливе питання як сумісність системи лінійних алгебраїчних рівнянь (2.11).

Теорема 1 (Кронекера – Капелі). Необхідною і достатньою умовою сумісності системи лінійних алгебраїчних рівнянь A × X = B є рівність рангів матриці A і розширеної матриці Ar , тобто rank(A) = rank(Ar ) .

Звідси випливає: якщо rank(A) ¹ rank(Ar ) , то система A × X = B є несумісною. Теорема 2. Сумісна система лінійних алгебраїчних рівнянь A × X = B є невизначеною, якщо ранг матриці A менше кількості невідомих ( rank(A) < n ), і є визначеною, якщо ранг матриці A дорівнює кількості невідомих ( rank(A) = n ). Таким чином, процес розв’язання будь-якої системи лінійних алгебраїчних

рівнянь A × X = B складається з трьох етапів:

1)На першому етапі слід виконати наступні дії:

∙Сформувати для матриці A розширену матрицю системи Ar .

∙ Обчислити ранг матриць A і Ar , тобто rank(A) і rank(Ar ) .

∙Здійснити порівняння рангів матриць A і Ar , а також зробити відповідні висновки щодо сумісності системи:

o якщо rank(A) ¹ rank(Ar ) , то система є несумісною;

oякщо rank(A) = rank(Ar ) , то система є сумісною.

2)На другому етапі у випадку сумісності системи слід виконати наступні дії:

∙Здійснити порівняння рангу матриці A з кількістю її стовпців, тобто з величиною n , а також зробити відповідні висновки щодо визначеності системи, тобто кількості її розв’язків:

oякщо rank(A) = n , то сумісна система є визначеною, тобто має єди-

ний розв’язок;

oякщо rank(A) < n , то сумісна система є невизначеною, тобто має нескінчену кількість розв’язків.

3)На третьому етапі у випадку визначеності системи, тобто у випадку єдиного розв’язку системи, слід виконати наступні дії:

∙Здійснити порівняння рангу матриці A з кількістю її рядків, тобто з величиною m , а також зробити відповідні висновки щодо методів (засобів) для подальшого розв’язання системи:

22

o якщо rank(A) = m , то систему з квадратною матрицею можна

розв’язувати одним з методів (засобів), що наведено в підрозділі 2.1; o якщо rank(A) < m , то систему можна розв’язувати одним з методів

(засобів), що наведено в підрозділі 2.2.

Розглянемо тепер третій етап у випадку невизначеної системи лінійних алгебраїчних рівнянь A × X = B , коли ранг матриці системи r = rank(A) менше кількості невідомих, тобто r < n . Для розв’язання такої системи слід виконати наступні дії:

·Виділити r лінійно незалежних рівнянь системи.

·В лівих частинах цих рівнянь залишити такі r невідомих, щоб визначник з коефіцієнтів при них був відмінним від нуля. Ці невідомі називають базисними.

·Решту невідомих перенести в праві частини рівнянь. Ці невідомі називають вільними.

·Розв’язати отриману визначену систему r рівнянь з r невідомими, вважаючи, що вільні невідомі є заданими константами, тобто отримати розв'язок цієї системи, в якому базисні невідомі виражені через вільні невідомі.

·Додаючи в отриманий розв’язок, який є вектором з r базисних невідомих, додатково n − r вільних невідомих, отримати загальний розв'язок системи, який буде функцією вільних невідомих.

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

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

Ця методика розв’язання невизначених систем нижче буде реалізована на прикладі

Слід зауважити, що вищенаведений процес розв’язання довільної системи лінійних алгебраїчних рівнянь A × X = B у випадку, якщо матриця A є квадратною, значно спрощується:

·Якщо визначник матриці А системи не дорівнює нулю, тобто D = A ¹ 0 ,

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

·Якщо D = A = 0 , то маємо дві можливості:

o	Хоча б один з визначників 1,	2 , ... n −1, n з формули (2.6) є від-
	мінним від нуля, то ця система є несумісною, тобто не має розв'язків.
o	Усі визначники 1, 2 , ... n −1,	n з формули (2.6) дорівнюють нулю,

то ця система є сумісною, але невизначеною, тобто має нескінченну кількість розв'язків. Ці розв'язки обчислюються за вищенаведеною в цьому підрозділі методикою.

Нижче розглянемо приклади розв’язання таких систем за допомогою ви-

щезгаданих можливостей Mathcad.

23

Задача 10. Дослідити систему лінійних алгебраїчних рівнянь A X = B на сумісність. Матриця A і вектор B мають вигляд:

	1	1	0				40
1		1	2			70
A =	0 1		1		;	B =	50	.
	2	3	1			140
		3	1
3						150

1.У випадку несумісності системи знайти такий вектор X, для якого величина нев'язки r(X) = A X − B є мінімальною.

2.У випадку сумісності системи визначити, скільки розв'язків вона має:

∙якщо система має єдиний розв'язок (визначена система), то розв'язати си-

стему за допомогою одного з чисельних методів;

∙якщо система має нескінченну кількість розв'язків, знайти вигляд загаль-

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

Розв'язання задачі в Mathcad

24

Задача 11. Розв'язати задачу 10 за умови, що матриця A і вектор B мають вигляд:

	1	1	0				50
1		1	2			70
A =	0 1		1		;	B =	40	.
	2	3	1			140
		3	1
3						160

Розв'язання задачі в Mathcad

25