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

Значительно более простым и эффективным по быстродействию является метод Гаусса. Алгоритм этого метода состоит из двух этапов, называемых, соответ­ственно, прямым и обратным ходом. Целью прямого хода является последовательное исключе­ние неизвестных из уравнений системы; и только в обратном ходе производится непосредственное определение значений неизвестных.

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

a11 x1	+	a12 x2	+	a13 x3	=	a14
a21 x1	+	a22 x2	+	a23 x3	=	a24	(4.1’ )
a31 x1	+	a32 x2	+	a33 x3	=	a34	.

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

x1 = (a14 - a12 x2 - a13 x3) / a11 ,

(4.2)

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

x1 + x2 + x3 = ,

(4.3)

где

= a1j / a11 , j = 2,3,4.

(4.4)

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

x1	+	x2	+	x3	=
		x2	+	x3	=		(4.5)
		x2	+	x3	=		,

где = a_ij - a_i1 ^. , i=2,3; j = 2,3,4 ,

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

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

x2 = ( - x3) / ,

(4.6)

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

x2 + x3 = ,

(4.7)

где

= / , j = 3,4.

(4.8)

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

x1	+	x2	+	x3	=
		x2	+	x3	=		(4.9)
				x3	=		,

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

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

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

или x₃ = .

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

x1	+	x2	+	x3	=
		x2	+	x3	=		(4.10)
				x3	=		.

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

1
0	1		(4.11)
0	0	1	.

Это треугольная матрица. На ее главной диагонали расположены единицы, а элементы под главной диагональю равны нулю.

Обратный ход метода очевиден. Третье уравнение системы (4.10) уже явно опре­деляет значение x₃

.

(4.12)

Подставляя это значение во второе уравнение (4.10), получаем:

.

(4.13)

Подставляя найденные значения x₂,x₃ в первое уравнение (4.10), получаем значение x₁:

.

(4.14)

Соотношения (4.12), (4.13), (4.14) и являются решением системы ( 4.1’ ).

Теперь обобщим рассмотренный алгоритм на произвольную систему n-го поряд­ка. На каждом k-ом шаге (k=1,2,3,...,n) прямого хода выполняются операции:

,	j = 1,2,...,n+1,	(4.15)
,	i = k+1,...,n; j = 1,2,...,n+1.	(4.16)

На последнем шаге, т.е. при k=n, выполняются только операции (4.15), так как для выполнения (4.16) уже исчерпаны все значения i.

При выполнении операций (4.15) производится деление на диагональные эле­менты a_kk. Поэ­тому может возникнуть критическая ситуация, если этот элемент ока­зывается равным нулю. Избежать этой ситуации можно путем перестановки урав­не­ний преобразуемой системы, начиная с k-го и по n-е таким образом, чтобы на месте a_kk ока­зался ненулевой элемент. Более того, доказано, что для дости­же­ния макси­мальной точности решения системы надо перестановку уравнений осуществлять таким об­разом, чтобы на месте a_kk оказывался максимальный по модулю элемент из тех, что находятся в k-м столбце матрицы системы начиная с диагонального и ниже. Эта процедура называется выбором глав­ного элемента. Если же в результате этой про­цедуры на главной диагонали окажется все-таки нулевой элемент, то это означает, что главный определитель D матрицы системы равен нулю. По правилу Крамера это значит, что система вырожденная, т.е. либо не имеет решений, либо имеет их беско­нечно много.