3 Численное решение систем линейных алгебраических уравнений

Линейные системы имеют в вычислениях очень большое значение, так как к ним может быть приведено приближенное решение широкого круга задач. Так, основными источниками возникновения систем линейный алгебраических уравнений (СЛАУ) являются теория электрических цепей, уравнения балансов и сохранения в механике, гидравлике и т.п.

Пусть дана система n линейных алгебраических уравнений с n неизвестными:

a x

a x

2

a

x

n

b ,

11 1

12

1n

1

a21x1 a22 x2 a2n xn b2 ,

...

a

x

a

n2

x

2

a

nn

x

n

b .

n1 1

n

Или в матричной форме:

где

A x b;

a11

a12 ...

a1n

A aij

a

21

a

22

...

a

2n

... ... ...

...

an2 ...

an1

ann

(3.1)

(3.2)

(3.3)

- матрица коэффициентов системы (3.1);
x1				b1
x			- вектор неизвестных;	b		- вектор свободных членов.
x	2			b 2
...				...
xn				bn

Если матрица A невырожденная, то есть

15

	a11	a12	...	a1n
det A	a21	a22	...	a2n	0,	(3.4)
	... ... ... ...
	an1	an2	...	ann

то система (3.1) или эквивалентное ей матричное уравнение (3.2) имеют единственное решение. Действительно, при условии, что detA 0, суще-

ствует обратная матрица A-1. Умножая обе части уравнения (3.2) слева на A-1, получим:

A 1 A x A 1 b; x A 1 b.

(3.5)

Формула (3.5) даёт решение уравнения (3.2), причём единственное.

Пример 1 Решить систему уравнений матричным методом.

		3x x							5											3	1				0
			1					2									A	2					1 1 .
		2x1 x2 x3 0 ;
		2x x							4x 15											2	1
								2																	4
			1												3
			3			1				0
		2					1			1			[12 ( 2) 0] [(0 1 2) 8 3] 5.
			2			1				4
			4	5				1			5						4	5			1		5		5			2
	1															1
A 1	2		12		5			3			5				;	x 2	12		5		3		5		0			1 .
			1						1								1				1
																									15			3
	0			5						5						0		5
																						5

Для матрицы A порядка n > 4 непосредственное нахождение обратной матрицы A-1 требует много времени (операций). Поэтому формула (3.5) на практике употребляется достаточно редко.

Обычно значения неизвестных xi (i = 1,2, ... n) могут быть получены по известным формулам Крамера:

xi det Ai / det A.

(3.6)

Здесь матрица Ai получается из матрицы A заменой её i-го столбца столбцом свободных членов.

16

Пример 2 Решить систему уравнений по формулам Крамера:

								5	1			0					x1 2.
			1					0	1			1				20 15 5 10;
								15	1			4
						3			5			0					x2 1.
			2			2			0 1							10 45 40 5;
						2			15			4
			3	1					5								x3 3.
3			2	1					0		45 10 10 30 15;
			2	1					15

Применяемые в настоящее время методы решения СЛАУ можно раз-

бить на две группы: точные и приближённые.

Точными методами называются такие методы, которые в предположении, что вычисления ведутся точно (без округлений), за конечное число действий позволяют получить точные значения неизвестных xi.

Приближенными методами называются такие методы, которые даже в предположении, что вычисления ведутся без округлений, позволя-

ют получить решение системы (x1, x2, ..., xn) лишь с заданной точностью. Точное решение СЛАУ в этих случаях может быть получено теоретически как результат бесконечного процесса.

К приближенным методам относятся метод простой итерации, метод Зейделя и т.п.

3.1Метод Гаусса

Наиболее распространенным методом решения СЛАУ является метод Гаусса, в основе которого лежит идея последовательного исключения неизвестных.

Метод Гаусса относится к точным методам решения СЛАУ. Методы Гаусса (или методы исключения неизвестных) оптимальны для решения СЛАУ общего вида по количеству арифметических операций, необходимых для нахождения решения этой системы. Существуют различные схемы, реализующие данный метод. Рассмотрим одну из них – схему един-

ственного деления.

17

Для простоты ограничимся рассмотрением СЛАУ с четырьмя неизвестными:

a11x1 a12 x2 a13 x3 a14 x4a21x1 a22 x2 a23 x3 a24 x4a31x1 a32 x2 a33 x3 a34 x4a41x1 a42 x2 a43 x3 a44 x4

a15 ,

	a25 ,	(3.7)
	a35 ,
	a45.

Пусть a11 0 (ведущий элемент). Разделив первое уравнение на a11,

получим первую главную строку:

где b1 j a1 j / a11;	x1 b12 x2 b13 x3 b14 x4	b15,	(3.8)
	(j = 2,3,4,5).

Используя уравнение (3.8), можно исключить неизвестные x1 из 2, 3 и 4-го уравнений системы (3.7). Для этого последовательно умножим

уравнение (3.8) на a21; a31; a41 и вычитаем результат из 2, 3 и 4-го уравнений системы (3.7) соответственно.

В результате получим систему из трех уравнений:

	(1)		(1)		(1)		(1)
a22 x2			a23 x3		a24 x4		a25	,
a32(1) x2			a33(1) x3		a34(1) x4		a35(1) ,		(3.9)
a(1) x		2	a(1) x		a(1) x	4	a(1)	,
	42		43	3	44		45

где коэффициенты aij(1) вычисляются по формуле

a(1)	a	a b	(i = 2, 3, 4; j = 2, 3, 4, 5). (3.10)
ij	ij	i1 1 j

Далее первое уравнение системы (3.9) разделим на ведущий элемент

a22(1)	0 и получим		x		b(1) x		b(1) x		b(1)	,
				2		3		4			(3.11)
					23		24		25
где	b(1) a(1) / a(1)		, (j = 3, 4, 5).
	2 j	2 j 22

18

Аналогично предыдущему шагу, исключая x2, как и x1, получим си-

стему

				(2)		(2)		(2)	,
			a33		x3 a34			x4 a35		(3.12)
				(2)		(2)		(2)
			a43		x3 a44			x4 a45 .
Здесь	a(2)	a(1)	a(1)b(1)			(i = 3, 4; j = 3, 4, 5).
	ij	ij		i2	2 j
Разделив первое уравнение системы (3.12) на a33(2)										0 , получим:
				x	b(2) x		4	b(2) ,		(3.13)
где b(2)	a(2) / a(2)			3	34			35
					(j = 4, 5).
3 j	3 j	33

Теперь с помощью уравнения (3.13) исключим x3 из второго уравнения системы (3.12), окончательно получим:

		a44(3) x4	a45(3) ,	(3.14)
где a(3) a(2) a(2)b(2)			(j=4, 5).
4 j	4 j	43 3 j

Таким образом, исходную систему (3.7) приведем к составленной из

главных строк (3.8), (3.11), (3.13) и (3.14) эквивалентной системе с тре-

угольной матрицей(3.15):

x1 b12 x2 b13 x3 b14 x4 b15 ,
x		2	b(1) x			b(1) x		4	b(1)	,
			23	3		24			25	(3.15)
x			b(2) x			b(2)	,
	3		34		4	35
		(3)			(3)
a44 x4 a45 .

Из системы (3.15) последовательно найдем

x4			a45(3) / a44(3) ,
			b(2)		b(2) x				,
x															(3.16)
	3		35		34			4	b(1) x				,
x		2	b(1)		b(1) x							4
x			25		23		3		24
			b	b x		2	b x				b x			4	.
	1		15		12				13	3			14

Итак, решение СЛАУ (3.7) распадается на два этапа:

прямой ход (приведение системы (3.7) к треугольному виду (3.15));

обратный ход (определение неизвестных по формуле (3.16)).

19

Пример 3.3 Решить систему уравнений
	2.0x1 1.0x2				0.1x3	1.0x4			2.7,
					4.0x3	8.5x4			21.9,
0.4x1 0.5x2
	0.3x	1.0x	2	1.0x 5.2x			4		3.9,
	1				3
	1.0x	0.2x		2	2.5x	1.0x		4	9.9.
	1				3
Прямой ход:

x1 0.5x2 0.05x3 0.5x4							1.35;
b12	0.5;		b13		0.05; b14		0.5; b15	1.35.
Из выражений (3.10) вычислим коэффициенты a2(1j) :
a(1)	a	22	a	b		0.5 0.4 0.5 0.3;
22				21	12
a(1)	a	23	a	b		4 0.4 0.05 4.02;
23			21		13
a(1)	a	24	a	b		8.5 0.4 0.5 8.7;
24				21	14
a(1)	a	25	a	b		21.9 0.4 1.35 21.36.
25				21	15

Аналогично вычислим коэффициенты aij(1) при (i = 3, 4) и составим систему

0.3x2 4.02x3 8.7x4 21.36,

1.15x2 1.015x3 5.05x4 4.305,0.3x2 2.55x3 1.5x4 8.55.

Разделив первое уравнение системы на a22(1)			0.3, получим
	x2 13.40x3	29.00x4 71.20.
Значит,	b(1) 13.40;	b(1) 29.00;	b(1)	71.20.
	23	24	25

Из (3.12) вычислим aij(2) для i = 3 и j = 3, 4, 5:

a33(2) a33(1) a32(1)b23(1) 1.015 1.15 13.40 16.425;

a34(2) a34(1) a32(1)b24(1) 5.05 1.15 29.00 28.3;

a33(2) a33(1) a32(1)b25(1) 4.305 1.15 71.20 77.575.

Аналогично, вычислив коэффициенты для i = 4, получим:

16.425x3 28.3x4 77.575,6.570x3 10.200x4 29.910.

20