Лекция № 3 Системы линейных алгебраических уравнений проф. Дымков М.П.

33

	1	−2	1	1				1	1
Решение. Имеем A		−2	1			,	∆2 =			= −2 ≠ 0.
	= 1			−1				1	−1
			1	3
	1 −2
Все остальные миноры 3-го порядка матрицы A равны 0. Легко видеть, что в

расширенной матрице Ab все миноры 3-его порядка, включая и минор , составленный с помощью свободных членов равны нулю:

		1	−2	1
∆3 =		1	−2	−1		= 0 (так как столбцы 1 и 2 пропорциональны).
		1	−2	3

Значит, r(A) = r (Ab )= 2.

Далее, согласно общим рекомендациям, берем два первых уравнения (они входят в базисный минор), выделяем в них главные и свободные переменны, и в итоге находим общее решение:

x −2x + x + x =1,			x + x =1− x + 2x ,
1	2 3 4	= −1,	3 4	1	2
x1 −2x2 + x3 − x4			x3 − x4	= −1− x1 + 2x2

x3 = −x1 + 2x2 , − общее решение системы.

x4 =1

§ 4. Метод обратной матрицы. Метод Крамера

Рассмотрим частный случай системы (1), когда m = n (число уравнений m совпадает с числом неизвестных n). Поскольку матрица А системы

Ax = B

квадратная, то если ∆ = det A ≠ 0 (т.е, А – невырожденная), то умножая (2) на A−1 слева, имеем, что матричное уравнение (2) имеет единственное решение

x = A−1b

(3)

Отыскание решения по формуле (3) называют матричным способом или ме-

тодом обратной матрицы решения системы линейных уравнений.

Матричное равенство (3) перепишем в более подробной записи, используя формулы для нахождения обратной матрицы. Тогда получим

Лекция № 3 Системы линейных алгебраических уравнений проф. Дымков М.П.

34

x1x2 =xn

A11

A12

∆A1n1

A21

A22

A2n

An1

An2

Ann

						1				(A11 b1 + A21 b2 + + An1 bn )
		b1						∆
						1				(A12 b1 + A22 b2 + + An2 bn )	.
b2				=
							∆
						.....................................................
		bn					1			(A1n b1 + A2n b2 + + Ann bn )
							∆

Сравнивая покомпонентно полученные векторы, имеем

x1 = ∆1 (A11b1 + + An1bn ), , xn = ∆1 (A1nb1 + + Annbn ).

Преобразуем полученные формулы. Для этого рассмотрим, например, определитель ∆1 , полученный из определителя ∆ заменой первого столбца столбцом свободных членов, т.е. рассмотрим определитель вида :

b1

a12

a1n

∆ =

b2

a22

a2n

.

1

bn

an2 ann

Разложим этот определитель

по

первому

столбцу:

b1 A11 +b2 A21 + +bnAn1 .

Аналогично

можно выписать

и

соответственно

разложить

определители

∆2 ,∆3 ,...,∆n . Тогда предыдущие формулы можно переписать в виде

x1 =

∆1

, x2

=

∆2, ,

xn

= ∆n

∆

∆

∆

где

∆i

есть

определитель

матрицы,

полученной

из

исходной

заменой i -го

столбца столбцом свободных членов.

Это формулы Крамера решения систем n уравнений с n неизвестными.

Пример. Решить систему	2x − x		= 0	.
		1 2	= 7
	x1	+3x2

Имеем согласно формул Крамера

∆ =		2	−1		= 7 ,	∆ =		0	−1		= 7 ,	∆	2	=		2	0		=14,	x = 7		=1,	x = 14		= 2 .
		1	3			1		7	3							1	7			1	7		2	7

§ 5. Метод Гаусса решения систем линейных уравнений

Прежде отметим, что, как метод обратной матрицы, так и метод Крамера применимы только для случая n = m. Оба эти методы являются весьма трудо-

емкими по количеству вычислительных операций и требуют порядка n2 n!

Лекция № 3 Системы линейных алгебраических уравнений проф. Дымков М.П.

35

арифметических действий для нахождения решения системы линейных уравнений. Например, при n = 5 это составит около 3 000 действий, при n = 10 –

около 3,6 108 действий. Серьезные практические задачи имеют n = 100 и более. Даже суперкомпьютеры требуют долгое время для вычисления. Кроме того, неизбежные погрешности при компьютерном округлении действительных

чисел		1		часто ведут к значительным ошибкам.
		3	= 0,3(3)

Существуют более экономичные методы решения. В частности, одним из них является метод Гаусса или, как иначе говорят, метод последовательного исключения неизвестных. Фактически метод основан на предварительном преобразовании расширенной матрицы системы к специальному ее виду (так называемому, трапецевидному, вообще говоря, виду). Эти преобразования матрицы (или, другими словами, преобразование системы уравнений) называют еще жордановыми преобразованиями.

Что это такое? Жордановы преобразования состоят из элементарных преобразований, выполняемых в определенном порядке. Напомним, элементарными преобразованиями системы называются:

1)перемена местами любых двух уравнений системы;

2)умножение (деление) обеих частей какого-либо уравнения системы на число λ ≠ 0;

3)прибавление к одному из уравнений другого уравнения, умноженного

на произвольное число λ (λ = 0 нет смысл рассматривать, так как это ничего не изменяет);

4) удаление из системы нулевого уравнения, т.е. уравнения вида

0 x1 + +0 xn = 0.

Следовательно, раз жордановы преобразования основаны на элементарных преобразованиях, то такие преобразования, как мы упоминали уже ранее, приводят к системе уравнений эквивалентной исходной.

Схема метода.

Пусть дана система линейных уравнений :

a11x1 + + a1n xn = b1,
....................................	(1)
	+ + amn xn = bm
am1x1

Процесс решения по методу Гаусса состоит из двух этапов.

На первом этапе (называют его еще как прямой ход метода ) система с помощью жордановых преобразований сводится к ступенчатому (трапецевидному ) виду ( частности, это может быть и треугольный вид):

Лекция № 3 Системы линейных алгебраических уравнений						проф. Дымков М.П.		36
a11x1	+ a12 x2 +...+ a1k xk + + a1n xn = b1					,
′	′	′		′	′
	′	′		′		′	,
	a22 x2	+...+ a2k xk +		+ a2n xn = b2				(2)
..............................................................
	′	′	′	,
	akk xk	+ + akn xn = bk

где k ≤ n , aii′ ≠ 0, i =1,k .

На втором этапе (обратный ход) идет последовательное определение неизвестных из ступенчатой системы (2).

Опишем подробнее метод Гаусса.

Прямой ход. Будем считать, что уже в исходной системе (1) коэффициент a11 ≠ 0. (Если a11 = 0, то среди оставшихся уравнений найдем r -ое уравнение такое, что ar1 ≠ 0. Такое всегда найдется, ибо в противном случае когда все коэффициенты a11 = a21 =... = am1 = 0 переменная x1 фактически исключа-

ется вообще из рассмотрения.

Теперь, используя элементарные преобразования, преобразуем систему (1), исключив неизвестное x1 во всех уравнениях кроме первого. Для этого

умножим обе части первого уравнения на (−a21 a11 ) и сложим почленно со вторым уравнением системы. Затем умножим обе части первого уравнения на (−a31 a11 ) и сложим почленно с третьим и т.д. Продолжая процесс, пока не

дойдем до последней строки. Этим завершается первый шаг гауссового исключения. В результате получим систему, в которой, начиная со второго уравнения, отсутствуют слагаемые, содержащие неизвестное x1 :

a11x1 + a12 x2 + + a1n xn = b1,

a22(1) x2

+ + a2′(1)n xn

= b2(1) ,

(1)

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

1

( )

(1)

(1)

(1)

am2 x2 +

+ amn xn

= bm

Здесь a(1) ,

b(1)

−новые значения коэффициентов, которые получились после

ij

i

a(1)

= a

−

a1 j ai1

,

b(1)

= b

−

b

a

,i = 2,...,m; j =1,...,n

первого шага

1

i1

ij

ij

a11

i

i

a11

Замечание.

1) Выбранный коэффициент

a11 ≠ 0

называют разрешаю-

щим элементом (на первом шаге), а строка и столбец (первые в данном случае), содержащие разрешающий элемент называют разрешающей строкой и столбцом соответственно.

2) На практике, для удобства, вычисления коэффициентов преобразованной системы можно пользоваться «правилом прямоугольника»: строят прямо-

Лекция № 3 Системы линейных алгебраических уравнений проф. Дымков М.П.

37

угольник с «вершинами» a11, aij , ai1 , a1 j и новый элемент вычислят как раз-

ность произведений диагональных элементов :

aij′ = aij a11 −ai1 a1 j .

Диагональ, на которой лежат разрешающий элемент a11 и преобразуемый элемент aij − называется главной, другая диагональ – побочная.

Заметим, что коэффициенты, полученные по правилу прямоугольника, отличаются от коэффициентов из (1(1) ) на множитель a11. Другими словами,

если в (1(1) ) каждое уравнение умножить на число λ = a11 (это же есть эле-

ментарное преобразование, не изменяющее множества решений !), то тогда упомянутые коэффициенты совпадут. Этот факт легко следует из формул (*).

Вернемся, однако, к системе (1(1) ). В рамке выделена остаточная часть системы, которую будем решать аналогичным образом.

	a11		a12	a1n		b1
A(1)		0	′		′		′
	=		a22		a2n		b2
b
		0	′		′		′
			am2	amn		an

Считая разрешающим элементом a22′ ≠ 0 , исключим неизвестное x2 из всех

уравнений системы, кроме первого и второго. (Для пересчета опять можно пользоваться правилом «прямоугольника» − только уже для остаточной части).

Продолжаем этот процесс, пока это возможно. При этом, если встретится нулевая строка 0 x1 + +0 xn = 0, то ее вычеркивают (удаляют).

В итоге процесс таких преобразований приводит к одному из двух случаев:

1) либо встретится уравнение вида 0 x		+где…+0 x0 = d,	d ≠
	k	n
тогда это означает, что рассматриваемая система несовместна;
2) либо получим систему ступенчатого вида без остаточной части
b11x1 +b12 x2 + +b1r xr + +b1n xn = c1,
	b22 x2 + +b2r xr + +b2n xn = cn ,
..............................................................
	brr xr + +brn xn = cr .

, и

(2)

Если r = n, то говорят, что система (2) имеет треугольный вид, в противном случае ─ трапецевидный . Возможное уменьшение количества уравнений связано с вычеркиванием нулевых уравнений . На этом прямой ход закончен.

38

Лекция № 3 Системы линейных алгебраических уравнений проф. Дымков М.П.

Обратный ход заключается в решении ступенчатой системы (2). а) Если r = n, то последнее уравнение системы (2) имеет вид

bnn xn = cn ,	(bnn ≠ 0), откуда xn = cn bnn .
Тогда, подставив найденное xn	в предпоследнее уравнение, найдем оттуда xn−1 .

Двигаясь, таким образом, снизу вверх по уравнению системы (2), найдем все

неизвестные xn , xn−1				,	x1	.,
б)	Если	r	< n, то		в	последнем		уравнении системы		(2) переменные
xr+1, xr+2	,	xn	объявляем,			свободными (можно другие, оставив любое					одно
из перечисленных переменных) и перенося их в первую часть, находим											остав-
шееся неизвестное xr				через свободные:
						′	′		′
					xr = cr		+brr+1xr+1 + +brn xn .
Подставляя найденное xr					в предпоследнее уравнение, найдем xr−1 , которое по-
сле приведения подобных членов будет выражаться только										через свободные
переменные (xr+1, x,n ).
Таким образом,				поднимаясь снизу вверх по системе (2), мы находим в
итоге все оставшиеся неизвестные xr−2 ,								, x1 ,	каждое из которых будет вы-
ражаться только через свободные переменные (xr+1, x,n ).
Придавая свободным неизвестным (xr+1, xr+2									, xn ), произвольные значе-
ния, получим тем самым бесчисленное множество решений системы (1).

Замечание. На практике, преобразование системы значительно удобнее выполнять, если оперировать с расширенной матрицей коэффициентов (или как говорят пользоваться табличной формой), которая после первого шага имеет вид

	a11		a12	a1n
A(1)	= 0		′	′
			a22	a2n
b
		0	′	′
			am2	amn

b1

b2′ .

an′

В этой таблице строки тоже называют уравнениями.