Решение систем линейных алгебраических уравнений методом Гаусса.

Блок-схема решения СЛАУ методом Гаусса

Вначале рассмотрим выполнение алгоритма метода Гаусса на примере системы 3-го порядка

a 11 x 1	+	a 12 x 2	+	a 13 x 3	=	a 14
a 21 x 1	+	a 22 x 2	+	a 23 x 3	=	a 24	(4.1’)
a 31 x 1	+	a 32 x 2	+	a 33 x 3	=	a 34	.

Из первого уравнения (4.1’) выразим x ₁:

 

x 1 = (a 14 - a 12 x 2 - a 13 x 3) / a 11 ,

(4.2)

 

а само это уравнение запишем в виде:

 

x 1 + x 2 + x 3 = ,

(4.3)

где

= a 1j / a 11, j = 2,3,4.

(4.4)

Подставим (4.2) с учетом (4.4) во второе и третье уравнения (4.1’) и получим систему:

 

x 1	+	x 2	+	x 3	=
		x 2	+	x 3	=		(4.5)
		x 2	+	x 3	=		,

где = a _ij - a _i1 ^. , i=2,3; j = 2,3,4,

т.е. на данном этапе прямого хода из второго и третьего уравнений системы исключе­но неизвестное x ₁.

Из второго уравнения преобразованной системы (4.5) выразим x ₂:

 

x 2 = ( - x 3) / ,

(4.6)

 

а само это уравнение запишем в виде:

 

x 2 + x 3 = ,

(4.7)

где

= / , j = 3,4.

(4.8)

Подставим (4.6) с учетом (4.8) в третье уравнение (4.5) и получим систему:

 

x 1	+	x 2	+	x 3	=
		x 2	+	x 3	=		(4.9)
				x 3	=		,

где = - ^. , j = 3,4,

т.е. на данном этапе прямого хода из третьего уравнения системы исключено x ₂.

Из третьего уравнения (4.9) выразим x ₃: x ₃ = / ,

или x ₃ = .

Теперь система приобретает вид:

x 1	+	x 2	+	x 3	=
		x 2	+	x 3	=		(4.10)
				x 3	=		.

На этом заканчивается прямой ход метода Гаусса. Матрица коэффициентов полученной системы имеет вид:

 

Вычисление определителей методом Гаусса.

При выполнении прямого хода метода Гаусса при решении СЛАУ вычисление по формулам (4.15), (4.16) производится для j=1,..., n+1, т.е. преобразованию подлежат как коэффициенты при неизвестных x ₁,..., x _n, так и свободные члены системы.

Аналогичный алгоритм, но для j=1,...,n, может быть применен для вычисления оп­ре­делителя любой квадратной матрицы порядка n. Подставляя (4.15) в (4.16), полу­чим:

,

(4.17)

где k = 1,..., n-1 - номер шага преобразования матрицы; i = k+1,...,n; j = 1,2,...,n.

Так как i изменяется от k+1, то это означает, что первая строка матрицы не изменяется.

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

 

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

 

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

Для получения максимальной точности результата надо стремиться, как и при решении СЛАУ, к тому, чтобы на каждом k-ом шаге преобразования на месте элемента а _kk находился максимальный по модулю элемент из тех, что стоят в k-ом столбце ниже k-ой строки. Это достигается процедурой выбора главного элемента, поэтому при вы­числении определителя надо учитывать, что перестановка любых двух строк матрицы приводит к изменению знака определителя на противоположный.

 

8. Обращение матриц

Матрица X является обратной по отношению к заданной квадратной матрице A, если их произведение дает единичную матрицу E:

A ^. X = E.

(4.18)

В единичной матрице элементы главной диагонали равны 1, а все остальные элементы равны 0.

Как известно, произведение двух квадратных матриц A и X порядка n дает квад­рат­ную матрицу C того же порядка, элементы которой вычисляются по формуле:

(4.19)

Алгоритм обращения матриц, т.е. вычисления элементов матрицы X, удовлетворяю­щих матричному уравнению (4.18), рассмотрим на примере матриц третьего порядка:

 

;

;

 

Уравнение (4.18) с учетом формулы (4.19) для этих матриц имеет вид:

 

a 11 x 11 +a 12 x 21 +a 13 x 31	a 11 x 12 +a 12 x 22 +a 13 x 32	a 11 x 13 +a 12 x 23 +a 13 x 33		1 0 0
a 21 x 11 +a 22 x 21 +a 23 x 31	a 21 x 12 +a 22 x 22 +a 23 x 32	a 21 x 13 +a 22 x 23 +a 23 x 33	=	0 1 0
a 31 x 11 +a 32 x 21 +a 33 x 31	a 31 x 12 +a 32 x 22 +a 33 x 32	a 31 x 13 +a 32 x 23 +a 33 x 33		0 0 1

 

Фактически здесь записаны три СЛАУ третьего порядка:

 

	a 11 x 11 + a 12 x 21 + a 13 x 31	=
1)	a 21 x 11 + a 22 x 21 + a 23 x 31	=
	a 31 x 11 + a 32 x 21 + a 33 x 31	=

 

	a 11 x 12 + a 12 x 22 + a 13 x 32	=
2)	a 21 x 12 + a 22 x 22 + a 23 x 32	=
	a 31 x 12 + a 32 x 22 + a 33 x 32	=

 

	a 11 x 13 + a 12 x 23 + a 13 x 33	=
3)	a 21 x 13 + a 22 x 23 + a 23 x 33	=
	a 31 x 13 + a 32 x 23 + a 33 x 33	=

 

Их особенностью является то, что все три системы имеют одну и ту же матрицу коэффициентов при неизвестных, а именно матрицу А.

Итак, чтобы найти матрицу X, обратную к заданной матрице А порядка n, надо решить n систем линейных уравнений, матрицей коэффициентов которых является исходная матрица А, а вектор-столбцами свободных членов являются столбцы еди­ничной матрицы E.

При использовании метода Гаусса решения этих n систем прямой ход можно осу­ществить одновременно для всех систем. Расширенная матрица при этом будет иметь по­рядок n х 2n; ее левая половина есть матрица А, правая - матрица E.