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

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

Общий вид системы линейных алгебраических уравнений:

a₁₁ x₁	+	a₁₂x₂	+	...	+	a_1nx_n	=	a_1,n+1
a₂₁ x₁	+	a₂₂x₂	+	...	+	a_2nx_n	=	a_2,n+1	(4.1)
. . . .	.	. . . .	.	...	.	. . . .	.	. . . .
a_n1 x₁	+	a_n2x₂	+	...	+	a_nn x_n	=	a_n,n+1

где a_ij - заданные элементы расширенной матрицы СЛАУ ( i=1,...,n, j=1,...,n+1 );

x_i - неизвестные (искомые) величины;

n - порядок системы.

Системе (4.1) соответствует расширенная матрица размера n на n+1:

a₁₁	a₁₂	...	a_1n	a_1,n+1
a₂₁	a₂₂	...	a_2n	a_2,n+1
.	.	.	.	.
a_n1	a_n2	...	a_nn	a_n,n+1

в которой первые n столбцов состоят из коэффициентов при неизвестных, а последний столбец образован из свободных членов системы (4.1).

Решить СЛАУ - значит найти такую комбинацию значений x_i , при которой каждое уравнение (4.1) превращается в тождество.

По правилу Крамера каждое значение x_i решения системы (4.1) вычисляется по формуле x_i= D_i/D, где D - определитель матрицы коэффициентов при неизвестных, D_i - определитель матрицы, полученной из матрицы коэффициентов при неизвестных заменой i-го столбца на столбец свободных членов.

Этой формулой можно с успехом пользоваться для систем 2-го, 3-го порядков, но для более высоких порядков вычисление определителей становится довольно сложной проблемой, и поэтому метод, основанный на правиле Крамера, практически не используется.

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

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

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

a₁₁ x₁	+	a₁₂x₂	+	a₁₃x₃	=	a₁₄
a₂₁ x₁	+	a₂₂x₂	+	a₂₃x₃	=	a₂₄	(4.1’ )
a₃₁ x₁	+	a₃₂x₂	+	a₃₃x₃	=	a₃₄	.

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

x₁ = (a₁₄ - a₁₂ x₂ - a₁₃ x₃) / a₁₁,

(4.2)

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

x₁ +

x₂ +

x₃ =

(4.3)

где

= a_1j / a₁₁ , j = 2,3,4.

(4.4)

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

x₁	+	x₂	+	x₃	=
		x₂	+	x₃	=	(4.5)
		x₂	+	x₃	=	,

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

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

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

x₂ = (

x₃) /

(4.6)

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

x₂ +

x₃ =

(4.7)

где

, j = 3,4.

(4.8)

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

x₁	+	x₂	+	x₃	=
		x₂	+	x₃	=	(4.9)
				x₃	=	,

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

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

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

илиx₃ = .

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

x₁	+	x₂	+	x₃	=
		x₂	+	x₃	=	(4.10)
				x₃	=	.

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


			(4.11)
			.

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

Обратный ход метода очевиден. Третье уравнение системы (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 матрицы системы равен нулю. По правилу Крамера это значит, что система вырожденная, т.е. либо не имеет решений, либо имеет их бесконечно много.