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

ЗАДАЧИ ЛИНЕЙНОЙ АЛГЕБРЫ

Общая характеристика методов решения

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

Методы решения СЛАУ можно разбить на две основные группы. К первой относятся так называемые точные или прямые методы - это алгоритмы, позволяющие получить решение за конечное, заранее известное число арифметических действий. Сюда входят: метод, основанный на правиле Крамера, метод исключений Гаусса и ме­тод прогонки. Вторую группу составляют приближенные (или итерационные) методы, основанные на многократном повторении одной и той же группы действий, каждая из которых дает все более точный результат. Из этой группы методов ниже будут рас­смотрены метод простых итераций и метод Зейделя.

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

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

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

a 11 x 1	+	a 12 x 2	+	...	+	a 1n x n	=	a 1,n+1
a 21 x 1	+	a 22 x 2	+	...	+	a 2n x n	=	a 2,n+1	(4.1)
....	.	....	.	...	.	....	.	....
a n1 x 1	+	a n2 x 2	+	...	+	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 11	a 12	...	a 1n	a 1,n+1
a 21	a 22	...	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-го порядков, но для более высоких порядков вычис­ление определителей становится довольно сложной проблемой, и поэтому метод, ос­но­ванный на правиле Крамера, практически не исполь­зуется.

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

Вначале рассмотрим выполнение алгоритма метода Гаусса на примере системы 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.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’).

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

Блок-схема фрагмента «Выбор главного элемента» Блок-схема фрагмента «Обратный ход»

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

На рис.4.1 представлена укрупненная схема алгоритма, реализующего метод Гаусса. В ней до­статочно подробно отражен прямой ход метода и схемы фрагментов “выбор главного элемен­та” и “обрат­ный ход”.