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

Нашей ближайшей целью является освоение универсальных методов линейного программирования, какими являются симплекс-метод и его модификации. Наиболее естественным представляется переход к этим методам непосредственно от задач линейной алгебры. В связи с этим рассмотрим метод Гаусса для решения систем линейных уравнений.

Метод Гаусса состоит в том, что матрица системы элементарными преобразованиями строк превращается в единичную матрицу. Если

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

1. Совместная система с квадратной матрицей.

Пусть требуется найти решение следующей системы:

Х₁ + 2Х₂ - 3Х₃ + 4Х₄ - Х₅ = -1,

2Х₁ - Х₂ + 3Х₃ - 4Х₄ + 2Х₅ = 8,

3Х₁ + Х₂ - Х₃ + 2Х₄ - Х₅ = 3, (1)

4Х₁ + 3Х₂ + 4Х₃ + 2Х₄ + 2Х₅ = -2,

Х₁ - Х₂ - Х₃ + 2Х₄ - 3Х₅ = -3.

Квадратную матрицу этой системы, расширенную матрицу и столбец правых частей обозначим соответственно А, С и В.

1.000 2.000 -3.000 4.000 -1.000

2.000 -1.000 3.000 -4.000 2.000

А = 3.000 1.000 -1.000 2.000 -1.000 (2)

4.000 3.000 4.000 2.000 2.000

1.000 -1.000 -1.000 2.000 -3.000

1.000 2.000 -3.000 4.000 -1.000 -1.000

2.000 -1.000 3.000 -4.000 2.000 8.000

С = 3.000 1.000 -1.000 2.000 -1.000 3.000 (3)

4.000 3.000 4.000 2.000 2.000 -2.000

1.000 -1.000 -1.000 2.000 -3.000 -3.000

-1.000

8.000

В = 3.000 (4)

-2.000

-3.000

Здесь после десятичной точки печатается три знака.

Ниже приведено компьютерное решение системы (1) методом Гаусса. В компьютерной выдаче результатов вычислений последовательно сменяющие друг друга матрицы печатаются без ограничивающих их круглых скобок, “ноль целых” перед десятичной точкой не печатается. Первые два числа распечатки результатов (это числа 5 и 6) указывают количество строк и столбцов в исходной расширенной матрице системы (3). Следующая за ними единица является признаком того, что производится выдача всех промежуточных вычислений. Если требуется только окончательный ответ, то вместо “1” следует указать “0”.

Gauss Method. Transformation to E - matrix.

5 6 1

1.0 2.0 -3.0 4.0 -1.0 -1.0

2.0 -1.0 3.0 -4.0 2.0 8.0

3.0 1.0 -1.0 2.0 -1.0 3.0

4.0 3.0 4.0 2.0 2.0 -2.0

1.0 -1.0 -1.0 2.0 -3.0 -3.0

Строка 1, столбец 4, ведущий элемент 4.000

.250 .500 -.750 1.000 -.250 -.250 (*)

3.000 1.000 .000 .000 1.000 7.000

2.500 .000 .500 .000 -.500 3.500

3.500 2.000 5.500 .000 2.500 -1.500

.500 -2.000 .500 .000 -2.500 -2.500

Строка 2, столбец 1, ведущий элемент 3.000

.000 .417 -.750 1.000 -.333 -.833

1.000 .333 .000 .000 .333 2.333

.000 -.833 .500 .000 -1.333 -2.333

.000 .833 5.500 .000 1.333 -9.667

.000 -2.167 .500 .000 -2.667 -3.667

Строка 1, столбец 4, ведущий элемент 3 5 -1.333

.000 .625 -.875 1.000 .000 -.250

1.000 .125 .125 .000 .000 1.750

.000 .625 -.375 .000 1.000 1.750

.000 .000 6.000 .000 .000-12.000

.000 -.500 -.500 .000 .000 1.000

4 3 6.000

.000 .625 .000 1.000 .000 -2.000

1.000 .125 .000 .000 .000 2.000

.000 .625 .000 .000 1.000 1.000

.000 .000 1.000 .000 .000 -2.000

.000 -.500 .000 .000 .000 .000

5 2 -.500

.000 .000 .000 1.000 .000 -2.000

1.000 .000 .000 .000 .000 2.000

.000 .000 .000 .000 1.000 1.000

.000 .000 1.000 .000 .000 -2.000

.000 1.000 .000 .000 .000 .000

48.000 - Result of Multiplication of the main elements

Rearrangement of lines

1.000 .000 .000 .000 .000 2.000

.000 1.000 .000 .000 .000 .000

.000 .000 1.000 .000 .000 -2.000

.000 .000 .000 1.000 .000 -2.000

.000 .000 .000 .000 1.000 1.000

Determinant = 48.000

roots

2.000

.000

-2.000

-2.000

1.000

Решение достигается элементарными преобразованиями строк матрицы С, а по сути многократным выполнением одной и той же операции, а именно: вычитания из одной строки матрицы другой ее строки, умноженной на число. После выполнения такой операции каждый раз получается система уравнений, равносильная исходной системе.

Важную роль в расчетном алгоритме играет понятие ведущего элемента. Ведущим элементом может служить любое отличное от нуля число выбранной строки, кроме крайнего справа числа, принадлежащего столбцу свободных членов.

Работа программы начинается с выбора ведущего элемента в первой строке исходной матрицы. В рассмотренном примере в качестве ведущего элемента выбрано число 4.000, расположенное в первой строке и в четвертом столбце. Информация об этом выборе содержится в строке, напечатанной под исходной матрицей. Первая цифра “1” в этой строке означает номер строки (ведущей строки), вторая цифра “4” - номер столбца (ведущего столбца). Затем печатается сам ведущий элемент.

Далее ведущая строка делится на ведущий элемент, т. е. на 4.000, и полученные числа заносятся в первую строку следующей (второй) матрицы. При ссылках на эту строку будем пользоваться значком (*).

Затем строка (*) умножается на (-4) и вычитается из второй строки исходной матрицы. В результате получается вторая строка второй матрицы. Конечно, то же самое получится, если прибавить первую строку исходной матрицы ко второй строке, но задачу ведь решает компьютер, а он все делает по единому алгоритму.

Третья строка второй матрицы получается вычитанием умноженной на 2 строки (*) из третьей строки первой матрицы. Четвертая строка второй матрицы получается вычитанием умноженной на 2 строки (*) из четвертой строки первой матрицы. Аналогично получается пятая строка второй матрицы.

Алгоритм вычислений здесь таков, что в качестве ведущего элемента из первых пяти чисел ведущей строки выбирается максимальное по модулю число. Такой выбор не является обязательным. В качестве ведущего элемента можно, например, выбрать первое отличное от нуля число ведущей строки.

Проделанные операции со строками матрицы С есть ничто иное, как исключение переменной Х₄ из всех уравнений, кроме первого.. На эту характерную особенность полученной (второй) матрицы указывает четвертый столбец, состоящий из четырех нулей и одной единицы, которая появляется на месте ведущего элемента..

При получении третьей матрицы в качестве исходной используется полученная вторая матрица. Сначала выбирается ведущий элемент 3.000 из второй строки первого столбца. Затем делением ведущей (второй) строки на 3.000 получается единица в ведущем (первом) столбце. Элементарными преобразованиями строк получаются нули вместо остальных элементов этого столбца.

Аналогично из третьей матрицы получается четвертая, из четвертой – пятая. Наконец получается матрица, содержащая только нули и по одной единице в каждом из пяти первых столбцов, т. е. из каждого уравнения исключены все неизвестные, кроме одного. Полученная предпоследняя матрица соответствует системе (равносильной исходной системе (1)), каждое уравнение которой содержит в правой части только по одному отличному от нуля (равному единице) коэффициенту при неизвестных. Поэтому решение системы содержится в крайнем правом столбце этой матрицы.

Строки предпоследней матрицы переставляются так, чтобы ее первые пять столбцов образовали единичную матрицу. После такой перестановки значения переменных в столбце результатов располагаются в порядке возрастания индекса переменной. Наконец, столбец результатов печатается отдельно.

В процессе решения задачи попутно вычисляется также определитель исходной матрицы А.