book1989

ях обычный метод Гаусса может оказаться непригодным. Избе­ жать указанных трудностей позволяет метод Гаусса с выбором главного элемента. Основная идея метода состоит в том, чтобы на очередном шаге исключать не следующее по номеру неизвестное, а то неизвестное, коэффициент при котором является наибольшим по модулю. Таким образом, в качестве ведущего элемента здесь вы­ бирается главный, т. е. наибольший по модулю элемент. Тем самым, если det^4^=0, то в процессе вычислений не будет происходить де­ ление на нуль.

Различные варианты метода Гаусса с выбором главного элемен­ та проиллюстрируем на примере системы из двух уравнений

anXi + а12 2—/1, а2^Х\-1- а2к2 2 j2.

( 2)

Предположим, что |а 12|> |а и |. Тогда па первом шаге будем исключать переменное х2. Такой прием эквивалентен тому, что си­ стема (2) переписывается в виде

а^2х2-{- ПцХ,

а22х2-{-a2iX\ f2

(3)

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

Применяется также метод Гаусса с выбором главного элемента по столбцу. Предположим, что | fl2i| > | аи \. Перепишем систему (2) в виде

a2ixl+ a2zx2 = f2, апХ1+ а12 2 = 1

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

Иногда применяется и метод Гаусса с выбором главного эле­ мента по всей матрице, когда в качестве ведущего выбирается мак­

симальный по модулю элемент среди всех элементов матрицы си­ стемы.

2. Матрицы перестановок. В предыдущем параграфе было по­ казано, что обычный метод Гаусса можно записать в виде

где Lk, k = \, 2, ..., m,— элементарные нижние треугольные матри­ цы. Чтобы получить аналогичную запись метода Гаусса с выбором

главного элемента, нанеобходимо познакомиться с матрицами перестановок.

О п р е д е л е н и е 1. Матрицей перестановок Р называется квад­ ратная матрица, у которой в каждой строке и в каждом столбце только один элемент отличен от нуля и равен единице.

61

О п р е д е л е н и е 2. Элементарной матрицей перестановок Ри

называется матрица, полученная из единичной матрицы переста­ новкой &-й и /-й строк.

Например, элементарными матрицами перестановок третьего порядка являются матрицы

"0 1 0'

Р п = 1 0 0

_0 0 1_

Д>

I

'0	0	г	'1	0	0"
0 1 0 >7*23--			0	0	1
.1	0	0_	_0	1 0_

Отметим следующие свойства элементарных матриц перестано­ вок, вытекающие непосредственно из их определения.

1°. Произведение двух (а следовательно, и любого числа) эле­ ментарных матриц перестановок является матрицей перестановок (не обязательно элементарной).

2°. Для любой квадратной матрицы А матрица РЫА отличается от А перестановкой k-й и I-й строк.

3°. Для любой квадратной матрицы А матрица АРЫотличается от А перестановкой k-то и I-го столбцов.

3. Пример. Поясним применение элементарных матриц переста­ новок для описания метода Гаусса с выбором главного элемента по столбцу. Рассмотрим следующий пример системы третьего по­

рядка:
*1 +	*2+	*3=fu
2*i	+	*з = /2,		(4)
Система имеет вид (1), где	5х2-f- Зх3= /3.
	1	1	Г
А = 2		0	1	(5)
	0	5	3

Максимальный элемент первого столбца матрицы А находится во

второй строке. Поэтому в системе (4)			надо поменять местами пер­
вую и вторую строки и перейти к эквивалентной системе
2xx	“Ь	х3 = f2,
X i +	*2 +	*3 =		/l.	(6)
5х2 -f- Зх3 =				f3.
Систему (6) можно записать в виде
Pl2Ax = Pl2f,					(7)
т. е. она получается из системы (4)		путем умножения			на матрицу
перестановок	п0	1	о-
Р12--
	1 0		0 .
	_0	0	1

Далее, к системе (6) надо применить первый шаг обычного ме­ тода исключения Гаусса. Этот шаг, как мы видели, эквивалентен

62

умножению системы (7) на элементарную нижнюю треугольную матрицу (см. (17) из § 2)

L1 =

-О О 1J

Врезультате от (7) перейдем к системе

	LlPi2Ax = LlPllf		(8)
или, в развернутом виде,
*i	+ ± * а =	Л
	2	2
	*2 + Y *3=7l —-J- ,		(9>
5х2 + Зх3 =		/3.

Из последних двух уравнений системы (9) надо теперь исклю­ чить переменное х2. Поскольку максимальным элементом первого столбца укороченной системы

*a + -j*3 = / i — - у ’

(Ю>

5x2 -f- Зх3 = /3

является элемент второй строки, делаем в (10) перестановку строк и тем самым от системы (9) переходим к эквивалентной системе

*i +
5-^2 Ч-	Зх3 .— /3,		(П
, 1	г	/ 2
Х п -J------x3 = f1-----— ,
2	2	2
которую можно записать в матричном виде как
P23LlPi2A x = P 23LlPl2f.			(12)

Таким образом, система (12) получена применением элементарной матрицы перестановок

		Р23 ----	1	0	0'
			0	0	I
	к системе (8).		0	1	о
		надо применить второй шаг исключения
	Далее, к системе (11)
	обычного метода Гаусса.	Это эквивалентно умножению системы
	(11) на элементарную треугольную матрицу
		Ь2 =	'1	о	0'
			о	1/5	0
			о	-1/5 1
					63

В результате получим систему
L2P23LlPl2A x = L 2P23LlPl2f						( 13)
или
,	1		fa
“1----—— >
	2	3	2
,	3					(14)
Х2“Ь g ^3
- 1 * , = ^ —А _ ± /
	10			2	5
Заключительный шаг прямого хода метода Гаусса состоит в за­
мене последнего уравнения системы (14) уравнением
,«=— !0 (Л — А2				А"
что эквивалентно умножению (13)			на матрицу
L3 =		'1 0	1	0
		0		о
		О 0		—10

Таким образом, для рассмотренного примера процесс исключе­ ния Гаусса с выбором главного элемента по столбцу записывается в виде

L3L2P23LlP12A x = L 3L2P23LlPnf.

(15)

По построению матрица

U= L3L2P23L3Pi2A

(16)

является верхней треугольной матрицей с единичной главной диа­ гональю.

Отличие от обычного метода Гаусса состоит в том, что в каче­ стве сомножителей в (16) наряду с элементарными треугольными матрицами Lk могут присутствовать элементарные матрицы пере­ становок Ры.

Покажем еще, что из (16) следует разложение

PA = LU,

(17)

где L — нижняя треугольная матрица, имеющая обратную, и Р — матрица перестановок. Для этого найдем матрицу

А ==Р2зДР2 3 -

(18)

По свойству 2° матрица P23Li получается из матрицы Lj переста­ новкой второй и третьей строк,

			1	0	0
			—
	^29^1	—	2
			0	0	1
			L—1/2	1	0J

64

Матрица L t согласно свойству 3° получается из P23LI перестановкой второго и третьего столбцов,

0 О

1 0 * О ь

т.е. Li— нижняя треугольная матрица, имеющая обратную. Из (18), учитывая равенство Р2\ = Р2а, получим

	ZiPn = P » h .		(19)
Отсюда и из (16) видим, что
	U = L 3L2Z lP23Pl2A = L -lPA,
где обозначено P = P 23Pl2, L = Z ~ l		Поскольку Р — матрица
перестановок и L — нижняя треугольная		матрица, свойство	(17)
доказано. Оно означает, что метод Гаусса с выбором главного эле­
мента	по столбцу эквивалентен обычному методу Гаусса, приме­
ненному к матрице РА, т. е. к системе, полученной из исходной си­
стемы перестановкой некоторых уравнений.
4.	Общий вывод. Результат, полученный здесь для очень част­
ного примера, справедлив и в случае общей системы уравнений (1 ).
А именно, метод Гаусса с выбором главного элемента по столбцу
можно записать в виде
	• ■■L^PijJ-iPi,f,Ax =
	= l^n Z m - \ P m - \ ,i. . . L^P-zJ^LiPijJ,		(20)

где Pkjk— элементарные матрицы перестановок такие, что k ^ j h^ .

и Lh— элементарные треугольные матрицы.

Отсюда, используя соотношения перестановочности, аналогич­ ные (19), можно показать, что метод Гаусса с выбором главного элемента эквивалентен обычному методу Гаусса, примененному к системе

PAx= Pf,

(21)

где Р — некоторая матрица перестановок.

Теоретическое обоснование метода Гаусса с выбором главного элемента содержится в следующей теореме.

Т е о р е м а 1. Если det А Ф 0, то существует матрица перестано­ вок Р такая, что матрица РА имеет отличные от нуля угловые ми­ норы.

Доказательство теоремы 1 приведено в п. 5.

С л ед с т в и е . Если det А Ф0, то существует матрица переста­ новок Р такая, что справедливо разложение

PA = LU,

(22)

где L — нижняя треугольная матрица с отличными от нуля диаго­ нальными элементами и U — верхняя треугольная матрица с еди­ ничной главной диагональю.

3 А. А. С ам арский, А. В. Гулин

65

Следует подчеркнуть, что в методе Гаусса с выбором главного элемента матрица Р не задается заранее, а строится в процессе исключения, как это было показано в примере из п. 3. Как прави­ ло, не требуется знать эту матрицу в явном виде.

5. Доказательство теоремы 1. Докажем теорему 1 индукцией по числу т — порядку матрицы А. Пусть т = 2, г. е.

	А =		Гаи	а12
			а21	022.
Если а^фО, то утверждение теоремы 1				выполняется при		Р = Е , где Е — еди­
ничная матрица второго порядка. Если ап =					0, то O2i¥=0, так как det АфО. При
этом у матрицы
	РцЛ		а 21		Я 22
			ап		о12
все угловые миноры отличны от нуля.					любых квадратных матриц		поряд­
Пусть утверждение теоремы верно для
ка т— 1. Покажем, что оно	верно		и для	матриц порядка		т. Разобьем	матри­
цу А порядка т на блоки
	А. =		°т- 1	ат- 1
				атт
где
-а„		ai,m-l
- ат-1,1	•*	ат—1,т—1-
Ьш —1— (^т|,			Om2t		| Цт, т —l).
Достаточно рассмотреть два		случая: det А т-1=£0 и det				A m- i = 0 . В	первом

случае по предположению индукции существует матрица перестановок Pm-i порядка т — 1 такая, что P m-iA m- i имеет отличные от нуля угловые миноры. Тогда для матрицы перестановок

О'

	Р =				1
имеем	~ D		А
					3	3й Т
	Г тп—\		т—\
					1
	. ^т-1				атт
причем det (РА) = ± det Ау^О. Тем		самым			все	угловые		миноры	матрицы РА
отличны от нуля.		когда deM m_i = 0. Так						как det АФО, найдется
Рассмотрим	второй случай,
хотя бы один отличный от нуля минор				порядка			т— 1	матрицы А, полученный
вычеркиванием	последнего столбца и		какой-либо				строки. Пусть,		например:

ап . . ■ai,rn-i

ai-i, 1 • • ■а1—1,т—1

(23)

°/+ i,i ■ • ■а1+1,т-1

ат1 • • • ат,т—1

66

где 1фт. Переставляя в матрице А строки с номерами I и т, получим матрицу Р 1тА, у которой угловой минор порядка т— 1 имеет вид

ап . . ■ai,m-i

ai~1.1 • • ■a/-i,m -i

“ml • • ■ l

а1+1,1 ' ' • aUl,m-l

ajn-1,1	• •	i,m—l
и отличается от (23) только перестановкой		строк. Следовательно, этот минор

не равен нулю и мы приходим к рассмотренному выше случаю.

6. Вычисление определителя. В большинстве существующих стандартных программ одновременно с решением системы линей­

ных алгебраических уравнений (1) вычисляется определитель

ма­

трицы А. Пусть в процессе исключения найдено разложение

(22),

т. е. построены матрицы L и U. Тогда

det(/M) = d et L det U— det Ь = 1ц122... lmm,

т. e. произведение диагональных элементов матрицы L равно опре­

делителю

матрицы РА.

Поскольку матрицы РА и А отличаются

только перестановкой строк, определитель матрицы РА может от­

личаться

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

матрицы А только знаком.

А

именно,

det {РА ) =

det А,

если число

перестановок

четно,

и

det(PA) =

= —det А, если число перестановок нечетно.

Таким

образом, для

вычисления определителя необходимо знать, сколько перестановок

было осуществлено в процессе исключения.

Если матрица А вырождена, то при использовании метода Гаус­

са с выбором главного элемента

по столбцу на

некотором

шаге

исключения k все элементы /г-го столбца, находящиеся ниже глав­

ной диагонали и на ней, окажутся равными нулю.

(см. (И) из

Действительно, рассмотрим

укороченную

систему

§ 1), которая получается на k-ы шаге исключения:

а^Х ьА -

. . . + a L l)xm = f t l\

a V l xk +

. . . +

= f t L1’,

(24)

„(*—1-)v

I

I

J*-1»x

№-i)

j

umm лп = /:

При решении

системы

(24)

могут возникнуть

два

случая:

1 ) хотя бы один из коэффициентов

a t 1'

'

,

отличен от

нуля; 2)

=

a t l \ = ... =

a t t = 0. Если для

всех k =

1, 2, ...

..., т реализуется первый случай, то систему (1 ) можно решить

методом Гаусса

с вы бором главного элемента

по

столбцу, и, сл ед о ­

вательно, detA=£0. Если же det/1 = 0, то при некотором к реализу­ ется второй случай. При этом дальнейшее исключение становится невозможным и программа должна выдать информацию о том, что определитель матрицы равен нулю.

з* «7

§ 4. Обращение матрицы

Нахождение матрицы, обратной матрице А, эквивалентно реше­ нию матричного уравнения

А Х = Е ,	(1)
где Е — единичная матрица и X — искомая квадратная	матрица.

Пусть А = [ а ц~\, Z=[Xjj]. Уравнение (1) можно записать в виде си­ стемы т? уравнений

т	CLikXki = Ьц, i, / = 1,2, ... , m,
2		(2)
	1
где 6 „ = 1 при i= j	и бу= 0 при i=£j.	(2) распадается
Для дальнейшего важно заметить, что система

на т независимых систем уравнений с одной и той же матрицей А, но с различными правыми частями. Эти системы имеют вид

	Axw = 6Ш,	/= 1 , 2, .... т ,	(3)
где x(j)= (x,j, x2U	xmj)T, у вектора 6Шравна единице /-я компо­
нента и равны нулю остальные компоненты.
Например, для матрицы второго порядка система (2) распадается на две
независимые системы
	а 11*11 “Ь ^12*21 — 11	а Пх 12 "Ь а 12х 22 —
	021-*11 “Г а22 21= 0	И
		^21*12 + а22*22 = 1•

Для решения систем (3) используется метод Гаусса (обычный или с выбором главного элемента). Рассмотрим применение метода Гаусса без выбора главного элемента. Поскольку все системы (3) имеют одну и ту же матрицу А, достаточно один раз совершить прямой ход метода Гаусса, т. е. получить разложение A = L U и за­ помнить матрицы L и U. Для этого, как мы знаем (см. § 1), тре­ буется сделать т(т2—1 )/3 действий умножения и деления.

Обратный ход осуществляется путем решения систем уравнений

Ly{i) =	б(,),	= (ylh yih . . ., ymi)T,		(4)
Ux<'> =	y(i),	j = 1,2, ... , m,		(5)
с треугольными матрицами L и U. Решение системы (5) при каж­
дом / требует 0,5 т(т—1)		действий. Для	решения	системы (4)

надо еще добавить т делений на диагональные элементы матрицы L, так что здесь потребуется 0,5m (m +l) умножений и делений. Всего при каждом j на обратный ход затрачивается 0,5(т— 1)т + + 0,5(т+ \)т = т г действий, а для всех / требуется т? действий.

Можно сократить число действий, принимая во внимание спе­ циальный вид правых частей системы (4). Запишем подробнее пер­

88

вые j—1 уравнений системы (4):

1цУи = О,

^2\У1/ “Ь ^22У‘У ==

^/-1.1^1/ +

+ • • ■ + ^/—J,/—1 У/-1.1 = О.

Учитывая невырожденность матрицы L, отсюда получим

Уи==Уа== - • •:= */;-1з= = 0-

При этом оставшиеся уравнения системы (4) имеют вид

1цУп — 1.

1цУц + h.i+iyj+i.i + • • • • ) “ 1иУа — О,

* = /+ 1 , У+2, .... т.

Отсюда последовательно находятся неизвестные у1} по формулам i-l

Уц = - — .-----, t = / + 1 ,/ + 2, .. ,,т,	(6)
Уа=	(7)

Подсчитаем число умножений и делений, необходимое для про­ ведения вычислений по формулам (6). При фиксированном i для вычислений по формуле (6) требуется 1 деление и i—j умножений. Вычисления по формулам (6), (7) при фиксированном j потребуют

1 +

2

( t — / + 1 ) =

■( т - / + 2н « - / +

| )

i=/+i

действий. Наконец, решение указанным способом систем (4) при всех / = 1, 2, ..., т потребует

у 2	(m - / + 2) ( m - / + 0 = ^ - 2 k(k + l ) = - m{m-+ l)6(m- + 2)
i=l	A= I

действий. Общее число действий умножения и деления, необходи­ мое для обращения матрицы указанным способом,

т (ma — 1)	,	т ? ( т — 1) ,	т ( т -f- i)(m + 2) _ ^
3	'	2	6

Тем самым обращение матрицы требует не намного больше вре­ мени, чем решение системы уравнений.

§5. Метод квадратного корня

1.Факторизация эрмитовой матрицы. Метод предназначен для

решения систем уравнений

Л х = /	(1)
	69

с симметричной (в комплексном случае — эрмитовой) матрицей. Он основан на разложении матрицы А в произведение

A = SfDS,

(2)

где S — верхняя треугольная матрица с положительными элемен­ тами на главной диагонали, S*— транспонированная к ней (или комплексно сопряженная) матрица, D — диагональная матрица, на диагонали которой находятся числа, равные ± 1 .

об

Возможность представления

(2)

можно

получить

как следствие теоремы

/.//-разложении (см. §

2). Пусть

все

угловые

миноры

матрицы А отличны

от нуля. Тогда справедливо разложение

Л =

/.//,

где

L — нижняя

треугольная

матрица,

имеющая обратную,

и

U — верхняя

треугольная

с

единичной диаго­

налью.

произведения L = M K ,

где

М — нижняя

тре­

Представим матрицу L в виде

угольная матрица с единичной главной диагональю

и К — диагональная матри­

ца,

главная диагональ которой

совпадает с главной диагональю матрицы L,

т. е.

K = d ia g

[/ц, 1x2,

. . . . Irnm].

(3)

По

условиюдиагональные

элементы

матрицы

L отличны

от

нуля, и,

следова­

тельно, разложение L= MK существует. Тогда

A = M K U ,

(4)

где

М иU— треугольные

матрицы с

единичной главнойдиагональю и

К — диа­

гональная матрица, имеющая обратную. Из

условия А‘ = А получаем

//*/C*M* =

= M K U и

=

(5)

М атр и ц а,

н а х о д я щ а я ся

в л евой

части

р авен ств а

( 5 ), я в л я ется

н и ж н ей

т р е ­

угол ь н ой ,

а

в п р авой

части —

в ер хн ей

тр еугол ь н ой .

П о эт о м у

из

р авен ств а

(5)

с л е д у е т , что

о б е м атри цы

UM‘~l и

я вл яю тся

диагон альн ы м и .

Д а л е е , п оск ол ьк у

м атр и ц а

UM*-1 и м еет

еди н и ч н ую

гл ав н ую

ди агон ал ь ,

она

я вл я ется

еди н и ч н ой м атри ц ей ,

[/Л4*_ | = £ ,

т. е. // =

Л4*.

О т сю д а

и

из

(4) п о л у ­

ч аем р а зл о ж е н и е

А = М КМ \

(6)

П р ед ст а в и м м ат р и ц у К, о п р ед е л ен н у ю

согл асн о

(3 )

в в и д е

п р ои зв ед ен и я

т р е х

ди агон ал ь н ы х м атриц:

K=\K\''‘D\K\\

г д е о б о зн а ч ен о

[ KRu]> V l k T l

...,/|7^J],

| К |'/*= d ia g

D = d i a g [ s ig n

lt\, s ig n

/22,

. . . , s ig n lmm].

Т о г д а из

(6 )

п олучи м

р а зл о ж е н и е

( 2 ), гд е

S = | K

| ViM* —

в ер хн я я тр еугол ь н ая

м ат р и ц а с

п ол ож и тел ь н ы м и

эл ем ен т ам и

на

гл авн ой д и агон ал и .

( 1)

2. Пример. Если разложение (2)

получено, то решение системы

сводится к последовательному решению двух систем уравнений

с треугольными матрицами

S'Dy=r.f,

(7)

Sx =

у.

(8)

Покажем на примере матриц второго порядка как можно полу­

чить разложение

(2 ).

Пусть

А — действительная

симметричная

матрица

ди

А =

д 12

- д12 д22.

70