book1989

Исключая таким же образом неизвестные х3, xt, ..., хт, придем окончательно к системе уравнений вида

xi ci2x2 +		• • •	+ с1т т —уъ
	Х2 I	• ■•	"1' С2тХт		У21
					(8)
	х т —1 “1 Ст—1 ,т х т —				У -1,
эквивалентной исходной системе (2).				хт— Утп|
Матрица этой системы
—1 C12		•		C\m
0	1	•	c2,m-i	C2m	(9>
с =
0	0		1
0	0	• • •	0	1

содержит нули всюду ниже главной диагонали. Матрицы такого вида называются верхними треугольными матрицами. Нижней тре­ угольной называется такая матрица, у которой равны нулю все элементы, расположенные выше главной диагонали.

Получение системы (8) составляет прямой ход метода Гаусса. Обратный ход заключается в нахождении неизвестных хи х2, . ■., х„, из системы (8). Поскольку матрица системы имеет треугольный: вид, можно последовательно, начиная с хт, найти все неизвестные.

Действительно, хт= ут, хт_,	и т. д. Общие формулы.'
обратного хода имеют вид
xi = yi— 2 Ciixh	i = m — 1........ 1, х.п = ут.	(10)

/=г+1

2.Расчетные формулы. При реализации на ЭВМ прямого хода

метода Гаусса нет необходимости действовать с переменными Xi, х2, ... , хт. Достаточно указать алгоритм, согласно которому ис­ ходная матрица А преобразуется к треугольному виду (9), и ука­ зать соответствующее преобразование правых частей системы. По­ лучим эти общие формулы. Пусть осуществлены первые k—1 ша­

гов, т. е. уже исключены переменные хи х2, ...,					xh~i. Тогда имеем
систему
Х 1 ~Т Cl2X 2 ~f"	• • • ~Г CykX k +			С1т х т	—У и
Х2~^~ • • ■ + C2kXk +		. . . +		С2тХт. = Угл
x k—\	Ck—i,kxk		Ск-\,тх т — Ук- i »
					(И)
	atk 1)xk +	. ..	+C& 1)xm = f t 1\
	U-mk xk +	• •	I	п	_f<*-D
			Т"	и т т Лт ■— / т
					51

Рассмотрим 6-е уравнение этой системы
п{к~1)у,Л.	Л-п{к~1К
U-kk Jt* —f— . . .	“Г а кт Х ,п = f k

и предположим, что а£-1) =£ 0.		Поделив обе части этого уравнения на
йй-11»получим				(12)
%h"b^/t.ft+i-^A+i “Ь			l/ht
где
Ckj=	,	j = 6 +	1, 6 + 2, ... ,	m,
	< “L)
Ук —	f t *
	----- .
	akk
Далее, умножим, уравнение (12) па			и вычтем полученное со­
отношение из t'-ro уравнения системы			(11), где t'= 6 + 1, 6 + 2, ..., т.

В результате последняя группа уравнений системы (11) примет вид

Xk +	Ck,k+lx k+ l +			■• • + CkmXm —			У к ,
йй+1,£+1^>6+1 “Ь		• • •		"Ь Gk+i,mXm		= = :fk + it
л < + у _ 1_			• •	4 -	п {к) у —		f(&)
“ т,я+1Л/г+1		1		• “Т"	и т т Л т	—	/ т »
где
afi = atr i) ~	аТк1)сЫ'		Г / = 6+1,			6 + 2, .... т,
f?' = f t *	~ a t %	,	i = 6 + 1, 6 +				2, ..., т.

Таким образом, в прямом ходе метода Гаусса коэффициенты уравнений преобразуются по следующему правилу:

a f,= a ki, 6, /' = 1, 2, . . т,

Сц — —-j-— , / = 6 +	1,	6	+ . 2,. . , т,	6 =	1 , 2.......т,	(13)
л(к—1)
akk
of' — atj~*						(14)
i, /'= 6+1, 6 + 2,	...,	m,	6 = 1, 2,	...,	m— 1.

Вычисление правых частей системы (8) осуществляется по фор­ мулам

/10, = /ь	=	Л	=........1, 2т,		(15)
f t ] = / f ' 1’- 4	' V	/ - 6 +1, 6	+ ------2	т.	(16)

Коэффициенты Сц и правые части yh i= 1, 2, ..., т, j — i+1, /+ 2, ...

52

. . . , m, хранятся в памяти ЭВМ и используются при осуществлении

обратного хода по формулам (10).

Основным ограничением метода является предположение о

том, что все элементы	на которые проводится деление, от­
личны от нуля. Число	называется ведущим элементом на k-м

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

ДиТ1', а другое число (т. е. на k-м шаге исключается не xk, а дру­ гое переменное xh j=£k). Наиболее последовательно такая страте­ гия выбора ведущих элементов осуществлена в методе Гаусса с вы­ бором главного элемента (см. § 3).

3. Подсчет числа действий. Подсчитаем число арифметических действий, необходимых для решения системы (2) с помощью мето­ да Гаусса. Поскольку выполнение операций умножения и деления на ЭВМ требует гораздо больше времени, чем выполнение сложе­ ния и вычитания, ограничимся подсчетом числа умножений и де­ лений. Читатель по аналогии может самостоятельно найти требуе­ мое число действий сложения и вычитания.

1.	Вычисление	коэффициентов	ckj,	k = \,	2,	.. ., m, j = k+ l,
k + 2, ..., m, по формулам (13) требует
	S ( « - * ) = 1 + 2 + ... + ( m - l )				=	- - ^ P ^
	h=i
делении.				af) по формулам (14) тре­
2.	Вычисление всех коэффициентов
бует
	У (m — k f =	I2 + 22 + ... +	(т — I)2 =		(- — ^-т(—— -
						6

умножений.

Таким образом, вычисление ненулевых элементов сч треуголь­ ной матрицы С требует

m ( m — 1) . (m — 1) m (2m — 1)	(m2 — 1 )m
+ ------------- ---------------- =	----------- з--------

операций умножения и деления. При больших m это число действий равно приблизительно т3/3.

3.Вычисление правых частей yk по формулам (15) требует т

делений, а нахождение /f* по формулам (16)

2 ("* -*)	т (т— 1}
	2
£=i

53

умножений. Следовательно, вычисление правых частей преобразо­ ванной системы (8) требует

1 т(m— 1) _ т (т+ 1)

* 1 "

2

2

действий умножения и деления.

В итоге для осуществления прямого хода метода Гаусса необхо­ димо выполнить

(т г — В т	. т (т +	1) __т ( т +	1) (2т + 1)
3	2	_	6

действий, из которых основное число действий (порядка тп3/3) при­ ходится на вычисление элементов матрицы С.

4. Для осуществления обратного хода метода Гаусса по фор­ мулам (10) требуется

^т ( т — 1)

2 (т 0 =	g
1=1

умножений.

Итак, для реализации метода Гаусса требуется выполнить

т ( т + 1) (2т +	1)	,	т ( т —	1)	т (ma + Зт — 1)
6		^	2	_	3
действий умножения и деления. Подчеркнем, что основное						время
расчета затрачивается	на		осуществление прямого хода.			Д л я

б о л ь ш и х т ч и с л о д е й с т в и й у м н о ж е н и я и д е л е н и я в м е т о д е Г а у с с а б л и з к о к т 3/3. Это означает, что на вы­ числение одного неизвестного тратится в среднем тп2/3 действий. По затратам времени и необходимой машинной памяти метод Гаус­ са пригоден для решения систем уравнений (2) общего вида с чис­ лом неизвестных т порядка 100.

§2. Условия применимости метода Гаусса

1.Связь метода Гаусса с разложением матрицы на множители.

Впредыдущем параграфе было показано, что метод Гаусса преоб­ разует исходную систему уравнений

A x= f	(1)
в эквивалентную систему	(2)
Сх=у,

где С — верхняя треугольная матрица с единицами на главной диа­ гонали. Выясним теперь, как связаны между собой векторы правых частей f и у. Для этого обратимся к формулам (16) из § 1, из ко­ торых последовательно получим

fi = auylt U = апуг + а%у2, ...
и вообще	(3)
fj=bjlyl-1rb]2y2+ ... + bSjyh j= 1, 2, .... т,
Б4

где	— числовые коэффициенты, причем	Соотношения
(3)	можно записать в матричном виде
	f = By,		(4)
где В — нижняя треугольная матрица с		элементами	/ =

= 1, 2, т , (а<®> = аи) на главной диагонали. Напомним, что ос­

новное допущение при формулировке метода Гаусса состояло в том, что все a<-jrl) 0. Поэтому на диагонали матрицы В стоят ненуле­

вые элементы, и, следовательно, матрица В имеет обратную. Подставляя в уравнение (2) выражение для у в виде y = B~lf,

приходим к уравнению

Cx=B~'f,
или, что то же самое, к уравнению
BCx = f.	(5)

Сопоставляя (5) с уравнением (1), приходим к выводу, что в ре­ зультате применения метода Гаусса получено разложение исход­ ной матрицы А в произведение А = ВС, где В — нижняя треуголь­

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

Теперь мы имеем право трактовать метод Гаусса следующим образом. Пусть заданы матрицы А и вектор f. Сначала проводится

разложение А в произведение двух треугольных матриц,	А = ВС.
Затем последовательно решаются две системы уравнений
ву = 1	(6)
Сх=у	(7)

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

Разложение	А = ВС соответствует прямому	ходу метода Гаусса,
а решение	системы (6) —(7) — обратному	ходу. Заметим, что в
алгоритме, изложенном в § 1, разложение		А = ВС и решение си­
стемы (6) проводится одновременно.

Далее, следуя стандартным обозначениям, нижние треугольные матрицы будем обозначать буквой L (от английского lower — ниж­

ний)	и верхние треугольные — буквой		U (от английского upper —
верхний).
2.	Теорема об /.{/-разложении. Обозначим через Д} угловой
минор порядка j матрицы А, т. е.
	Ai = an , A2 = <1et аи	4)2~|	Ат =detA.
	а 21	а 22 J

Теоретическое обоснование возможности разложения матрицы

впроизведение двух треугольных матриц содержит следующая

Те о р е м а 1 (теорема об L/7-разложении). Пусть все угловые миноры матрицы А отличны от нуля, Д ^О , /= 1, 2........т. Тогда

55

матрицу А можно представить, причем единственным образом, в ви­ де произведения

A = LU,

(8)

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

Д о к а з а т е л ь с т в о . Докажем сформулированное утверждение сначала для матриц второго порядка. Будем искать разложение матрицы

^ а1 аП

.°21 а11

в виде

Л= In h\

где liU /2Ь /22, ц12— неизвестные пока числа. Для их нахождения при­ дем к системе уравнений

/ц-—ailt l-ilUi2 Ц]2)			^21" ^21>
	^21^12 + ^22 ~ ^22,
которая имеет единственное решение
In — o-u, ui2 — a^lau,			l2i~ a 2i,
l22	д11а22	а21а]2
	Оц
По предположению теоремы апфО,		апа2гф а г1а1г, следовательно,
элементы /и и /22 отличны от нуля.

Дальнейшее доказательство проведем методом индукции. Пусть утверждение теоремы справедливо для матриц порядка k—1; дока­ жем, что оно справедливо и для матриц порядка к. Представим

матрицу А порядка k в виде
Оц	•	“l,4—1	“l4
Л = “4-1,1 • * ak-l,k~\			“4-1,4	(9)
ак\	••	“4,4-1	“44 _

и обозначим

~“ u	• ■ “ 1,4 -1		~“ l 4 '
A k ~ i =		>	# 4 - 1 —
- “ 4 -1 ,1 • ■ “ 4 - 1 ,4 - 1 -			- “ 4- 1,4 -
	бк—1	)	Щ,й—1)«

Согласно предположению индукции существует требуемое разло­ жение матрицы Ак- и т. е.

Л*-1= Lk-iUk-i,

где Lh_u Uк- 1— соответственно нижняя и верхняя треугольные мат-

56

рицы, обладающие указанными в теореме свойствами. Будем искать разложение матрицы (9) в виде

	Л =	0 '	'Jk-,	«А-Л	( 10)
		hi-i hik	, 0	1 J

где /й_ь и,,-1— неизвестные пока векторы,

4 - i = (4 i, /а2 , • • ■! K,k-i) , Uk- i = (ulk, U-ik,. . . , Uh- i h) T.

Перемножая матрицыв правой части уравнения		(10) иучитывая
(9), приходим к системе уравнений
Lk-iUk-i =	Як-и	(11)
h-iUk-i =	Ьи~1,	(12)
Ik-iU-k-i + Ikk =	0,kk.	(13)

Из предположения индукции следует существование матриц Lk-U Uk-i. Поэтому из (И) и (12) получим

U к -1 = = T v - l'T - 1,I k - 1 b k —i U k —i

и, далее,

/аА= Ща Ik-lU-h-t-

Таким образом, /.//-разложение матрицы Л порядка k сущест­ вует. Остается доказать, что 1ккФ 0. Рассмотрим определитель мат­ рицы Л. Из разложения (10) следует, что

del Л = (det Lk- t)lhh(det //„-О = (det /.„_,)/**•

По условию теоремы бе1:Л=5^0, следовательно, 1кк=£0. Тем самым индукция завершена и доказана возможность требуемого разло­ жения.

Покажем теперь, что такое разложение единственно. Предполо­ жим, что матрицу Л можно разложить двумя способами:

A = LiUi~ L 2U2.

Тогда L2 = LJJJJ~2 и

(14)

Матрица в левой части уравнения (14) является верхней треуголь­ ной, а в правой части — нижней треугольной. Такое равенство воз­

можно лишь в случае, если матрицы и L[LL2 диагональные. Но на диагонали матрицы UyU21 (а следовательно, и матрицы LilL2) стоят единицы, следовательно, эти матрицы единичные:

UхЩ1= l^~Li = Е.

Отсюда получаем и { = 1!2, L, = L2, т. е. разложение (8) единственно. Теорема об /.(/-разложении полностью доказана.

З а м е ч а н и е . Если хотя бы один из угловых миноров матрицы А равен нулю, то указанное /.//-разложение невозможно. Это легко видеть на примере матриц второго порядка.

57

С л е д с т в и е . Метод Гаусса можно применять тогда и только тогда, когда все угловые Шиноры матрицы. А отличны от нуля.

3. Элементарные треугольные матрицы. Мы уже видели, что ме­ тод Гаусса приводит к разложению исходной матрицы в произве­ дение двух треугольных. Более детально описать структуру этих треугольных матриц можно с помощью так называемых элемен­ тарных треугольных матриц.

Матрица Lj называется элементарной нижней треугольной мат­ рицей, если она имеет вид

- 1 —

0	.	■	1П		о
		*
0	. ■		lj+i.i	1
_0	.	•	lmi	0	\_

В матрице L; все элементы главной диагонали кроме равны еди­ нице. Из остальных элементов отличными от нуля могут быть толь­ ко элементы /-го столбца, расположенные ниже lj}. Обратной к Lj является элементарная нижняя треугольная матрица

0 .	•	•	1П	0
0 ...	-	‘h u r t		l
0 ...	_/.		./“1	0	l
	— 1 ■/"•			.
0 ...				0 . . . 0	1
		nij1И
Рассмотрим для наглядности сначала систему Ax=f, состоящую
из трех уравнений:
апхг + а12х2+ а13х3= /ь
^2lM + ^22^2 "Ь ^2:1Х3==fit					0^)
&31Х 1	®32Х 2 "Ь a 33X 3 ==/3-

После первого шага исключения по методу Гаусса преобразован­ ная система принимает вид

*i	+ ^ * 2			an		an
	an
a22-	a^ )	x	2+ ( a 23-	a^ )	x	3 = f2 -	a- ^ f l,	(16)
	an	1	\	all	1		au
			+	—	) x 3 = f3~		-a^ f 1.
	al l	1	\	ali	}		al l

Отсюда видно, что матрица А, системы (16) получается из исход-

58

ной матрицы А путем умножения А слева на элементарную мат­ рицу

1/ап	0		0‘	(17)
Li = —^21/^11	1	0 »
— а31/аи	О		1.
так что Al= LlA. При этом систему (16)			можно записать в виде
LlAx = Llf.

Матрицу (17) будем называть элементарной треугольной мат­ рицей, соответствующей первому шагу исключения метода Гаусса. Перепишем систему (16) в виде

М	“Ь С13ЛГ3—У11
	а^х2+ ^ х 3 = /<1),	(18)
	а[2X2 + a$x3 = f f )

и осуществим второй шаг метода Гаусса, т. е. исключим неизвестное хг из последнего уравнения. Тогда получим систему вида

-' i “Г Су2х2“Г Суах3—- у\ ,

Х2 -(- С2З^д = У2,

(19)

Нетрудно видеть, что переход от (18) к (19) осуществляется путем

умножения системы (18) на	элементарную			треугольную матрицу
	1	0	0
Т2 =	о	i/4V	0	(20)
	о		1

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

к системе			(21)
ULyAx = L2Uf,
где матрицы L, и L2 определены согласно (17),			(20). Наконец, ум­
ножая (21) на матрицу
1 0		0 - 1
7-з = 0	1 0
о	о	1 /^J
получаем систему
LyLzLyAx— LyL-yLif,			(22)

матрица которой U— L3LzLyA является верхней треугольной матри­ цей с единичной главной диагональю. Отсюда следует, в частности,

что A = LU, где L = Ly1L21L21— нижняя треугольная матрица. Таким образом, LH-разложение матрицы А может быть получено с по­ мощью элементарных треугольных матриц: сначала строятся мат­ рицы L,, Т,2, Т-з и вычисляется U= L3L2LIA и затем находится L =

59

= L^L^L^.Отметим, что матрицы

~ап	0	0'
1ЛХ=	1	0
_а31	0	1_

L~k

i f

имеют простой вид:

1	0	0“
0	u2-2	0
0	U3flU)2	1

	r l	0	о	-	а и	0	0 '
	0	1	0	, L =	а 21	а (1)	0
						U22	(2)
	_0	0				а (1)
			зз	3	а 31		U33 J
						32

причем на диагонали матрицы L расположены ведущие элементы метода исключения.

Запись метода Гаусса в виде (22) детально описывает процесс исключения.

Все сказанное выше переносится без изменения и на системы уравнений произвольного порядка (2). Процесс исключения можно записать формулой

L mL*Tn—1■ ■ ■ L i A x

l^mL/TTi— i . . • l l

(23)

где элементарная нижняя треугольная матрица Lk на k-м шаге исключения имеет вид

-1	0	0	. .	о-
0	1/< -1(	0	. .	0
0		1	. .	0
0		0	. .	1

Матрица Lh осуществляет исключение неизвестного xhиз уравнений

с номерами k+ l, k +2, ..., т. Матрицы				L*1 существуют и имеют
вид
~ 1		0	0	...	о-
0	• •'	а(к~1)	0	...	0
		akk
0		(А-1)	I	...	0
		ak + lk
0	• • •	amk	0	...	1

§3. Метод Гаусса с выбором главного элемента

1.Основная идея метода. Может оказаться, что система

Ах=! О)

имеет единственное решение, хотя какой-либо из угловых миноров матрицы А равен нулю. Кроме того, заранее обычно неизвестно, все ли угловые миноры матрицы А отличны от нуля. В этих случа-

60