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

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

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

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

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

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

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

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

a ₁₁ x ₁	+	a ₁₂ x ₂	+	...	+	a _{1 n} x_n	=	a _{1, n +1}
a ₂₁ x ₁	+	a ₂₂ x ₂	+	...	+	a _{2 n} x_n	=	a _{2, n +1}	(3.1)
....	.	....	.	...	.	....	.	....
a_n ₁ x ₁	+	a_n ₂ x ₂	+	...	+	a_nn x_n	=	a_n,n+1

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

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

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

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

a ₁₁	a ₁₂	...	a _{1 n}	a _{1, n +1}
a ₂₁	a ₂₂	...	a _{2 n}	a _{2, n +1}
.	.	.	.	.
a_n ₁	a_n ₂	...	a_nn	a_n,n ₊₁

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

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

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

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

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

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

a ₁₁ x ₁	+	a ₁₂ x ₂	+	a ₁₃ x ₃	=	a ₁₄
a ₂₁ x ₁	+	a ₂₂ x ₂	+	a ₂₃ x ₃	=	a ₂₄	(3.1′)
a ₃₁ x ₁	+	a ₃₂ x ₂	+	a ₃₃ x ₃	=	a ₃₄	.

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

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

(3.2)

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

(3.3)

где

, j = 2,3,4.

(3.4)

Подставим (3.2) с учетом (3.4) во второе и третье уравнения (3.1′) и получим систему:

(3.5)

где , i =2,3; j = 2,3,4,

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

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

(3.6)

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

(3.7)

где

, j = 3,4.

(3.8)

Подставим (3.6) с учетом (3.8) в третье уравнение (3.5) и получим систему:

(3.9)

где , j = 3,4,

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

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

или .

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

(3.10)

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

(3.11)

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

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

(3.12)

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

(3.13)

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

(3.14)

Соотношения (3.12), (3.13), (3.14) и являются решением системы (3.1′).

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

,	j = 1,2,..., n +1,	(3.15)
,	i = k +1,..., n; j = 1,2,..., n +1.	(3.16)

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

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

Вычисление определителей

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

Аналогичный алгоритм, но для j = 1,..., n, может быть применен для вычисления определителя порядка n.

Подставляя (3.15) в (3.16), получим:

(3.17)

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

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

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

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

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

Таким образом, окончательная формула вычисления определителя после его преобразования по (3.17) выглядит так:

где p – количество перестановок строк, произведенных при выполнении процедуры выбора главного элемента.

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

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

A ^. X = E.

(3.18)

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

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

(3.19)

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

;

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

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

	a ₁₁ x ₁₁ + a ₁₂ x ₂₁ + a ₁₃ x ₃₁	=
1)	a ₂₁ x ₁₁ + a ₂₂ x ₂₁ + a ₂₃ x ₃₁	=
	a ₃₁ x ₁₁ + a ₃₂ x ₂₁ + a ₃₃ x ₃₁	=

	a ₁₁ x ₁₂ + a ₁₂ x ₂₂ + a ₁₃ x ₃₂	=
2)	a ₂₁ x ₁₂ + a ₂₂ x ₂₂ + a ₂₃ x ₃₂	=
	a ₃₁ x ₁₂ + a ₃₂ x ₂₂ + a ₃₃ x ₃₂	=

	a ₁₁ x ₁₃ + a ₁₂ x ₂₃ + a ₁₃ x ₃₃	=
3)	a ₂₁ x ₁₃ + a ₂₂ x ₂₃ + a ₂₃ x ₃₃	=
	a ₃₁ x ₁₃ + a ₃₂ x ₂₃ + a ₃₃ x ₃₃	=

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

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

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