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

Рассмотрим систему из m линейных уравнений с n неизвестными:

(2.2)

Обозначим через A=(A_ij) матрицу системы, через X=(x_j) — вектор, состоящий из неизвестных, через A₀ =(b_i) — вектор, состоящий из свободных членов; тогда систему (2.2) можно записать в виде матричного уравнения

AX = A_0. (2.3)

В начале рассмотрим случай, когда m = n. Для решения данной системы воспользуемся методом, который называется методом последовательных исключений неизвестных èëè методом Гаусса. Суть метода состоит в том, что, рассмотрев первое уравнение, а в нем неизвестное с коэффициентом, отличным от нуля (он в дальнейшем называется разрешающим элементом ), и разделив первое уравнение на этот коэффициент, с помощью первого уравнения исключают это неизвестное из всех уравнений, кроме первого. Выбрав во втором уравнении неизвестное с коэффициентом, отличным от нуля, и разделив на него второе уравнение, с помощью второго уравнения исключают другое неизвестное из всех уравнений, кроме второго, и т. д. Процесс продолжают до тех пор, пока не будут использованы все уравнения. При этом возможны следующие случаи:

1) в процессе исключений левая часть i-го уравнения системы обращается в нуль, а правая часть равна некоторому числу, отличному от нуля, т. е. имеет место равенство . Это означает, что система не имеет решений, так как i-му уравнению не могут удовлетворить никакие значения неизвестных;

2) левая и правая части i-го уравнения обращаются в нуль. Это означает, что i-е уравнение является линейной комбинацией остальных, ему удовлетворяет любое найденное решение системы, поэтому оно может быть отброшено;

3) после того, как все уравнения использованы для исключения неизвестных, либо будет получено решение, либо доказано, что система несовместна.

В случае благоприятного исхода система уравнений приводится к диагональному âèäó

(2.4)

откуда решение очевидно.

Реализация метода исключения неизвестных в среде Excel.

В данном пособии в качестве инструментария для реализации алгоритмов теории линейного программирования предлагается использовать пакет электронных таблиц Microsoft Excel 5.0 для Windows. Рассмотрим реализацию данного метода средствами пакета Excel.

З а д а ч а : решить систему линейных уравнений методом Гаусса.

И с х о д н ы е д а н н ы е : расширенная матрица системы.

Р е з у л ь т а т : вектор значений неизвестных.

С п о с о б р е ш е н и я : метод исключения неизвестных.

К р и т е р и й о ц е н к и : значение невязки R(x):

Р е а л и з а ц и я м е т о д а Г а у с с а :

1) в исходную таблицу записываем расширенную матрицу системы;

2) каждую последующую итерацию метода (шаг) начинаем с копирования предыдущей таблицы и выбора разрешающего элемента;

3) рассчитываем элементы разрешающей строки новой таблицы по формуле:

, (2.5)

где k=0, 1, 2, ... , n; p — разрешающий элемент q-ой строки;

4) вычисляем элементы остальных строк по формуле:

, (2.6)

где k=0, 1, 2, ..., n; i=1,2,...,n () ;

5) повторяем пункты 2—4 до полного разрешения системы и оформляем найденное решение в виде отдельной таблицы;

6) оцениваем точность найденного решения, вычисляя величину невязки R(x) по формуле:

, (2.7)

где x_j — полученное решение системы.

Ï ð è ì å ð 1. Решить с помощью метода Гаусса систему уравнений:

Р е ш е н и е .

A1	A2	A3	A4	A0		Исходная матрица
2	-2	0	1	-3
2	3	1	-3	-6
3	4	-1	2	0
1	3	1	-1	2
A1	A2	A3	A4	A0
1	-1	0	0,5	-1,5
0	5	1	-4	-3		Шаг 1
0	7	-1	0,5	4,5
0	4	1	-1,5	3,5
A1	A2	A3	A4	A0
1	0	0,2	-0,3	-2,1
0	1	0,2	-0,8	-0,6		Шаг 2
0	0	-2,4	6,1	8,7
0	0	0,2	1,7	5,9
A1	A2	A3	A4	A0
1	0	0	0,208	-1,375
0	1	0	-0,292	0,125		Шаг 3
0	0	1	-2,542	-3,625
0	0	0	2,208	6,625
A1	A2	A3	A4	A0
1	0	0	0	-2
0	1	0	0	1
0	0	1	0	4
0	0	0	1	3		Шаг 4
Полученнй результат
X1	X2	X3	X4
-2	1	4	3
Оценка точности вычислений
A1	A2	A3	A4
2	-2	0	1
2	3	1	-3
3	4	-1	2
1	3	1	-1			A1
						-4		A2			A3		A4	SUM		A0	(A0-SUM)^2
						-4		-2			0		3	-3		-3	0
						-6		3			4		-9	-6		-6	7,88861E-31
						-2		4			-4		6	-9E-16		0	7,88861E-31
								3			4		-3	2		2	7,88861E-31
											Величина невязки:					R(x)	2,36658E-30