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

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

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

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

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

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

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

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

a11 x1	+	a12 x2	+	...	+	a1n xn	=	a1,n+1
a21 x1	+	a22 x2	+	...	+	a2n xn	=	a2,n+1	(3.1)
. . . .	.	. . . .	.	...	.	. . . .	.	. . . .
an1 x1	+	an2 x2	+	...	+	ann xn	=	an,n+1

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

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

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

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

a11	a12	...	a1n	a1,n+1
a21	a22	...	a2n	a2,n+1
.	.	.	.	.
an1	an2	...	ann	an,n+1

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

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

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

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

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

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

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

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

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

(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) для этих матриц имеет вид:

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

	a11 x11 + a12 x21 + a13 x31	=
1)	a21 x11 + a22 x21 + a23 x31	=
	a31 x11 + a32 x21 + a33 x31	=

 

	a11 x12 + a12 x22 + a13 x32	=
2)	a21 x12 + a22 x22 + a23 x32	=
	a31 x12 + a32 x22 + a33 x32	=

 

	a11 x13 + a12 x23 + a13 x33	=
3)	a21 x13 + a22 x23 + a23 x33	=
	a31 x13 + a32 x23 + a33 x33	=

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

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

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