Метод исключения Гаусса

Рассмотрим следующую систему линейных уравнений:

(1)

Выберем в качестве ведущего элемента a₁₁. Пусть Исключим из уравнений (1), начиная со второго. Для этого первое уравнение умножим на и прибавим ко второму . Затем первое уравнение умножим на и прибавим к третьему и т.д. После этого вместо системы линейных уравнений (1) получим эквивалентную систему

(2)

где

(3)

Выберем в качестве ведущего элемента Пусть . Тогда аналогичным образом исключая x₂ из последних n-2 уравнений системы (2), получим систему уравнений

(4)

Здесь и вычисляются из выражений

(5)

Продолжая процесс, исходная система (1) примет следующий вид:

(6)

Мы предполагаем, что

(7)

Из последнего уравнения системы (6) вычисляем x_n.

Если , система линейных уравнений (1) не имеет решение.

Если , x_n произвольное число.

Если :

Подставляя найденное решение в (n-1) -е уравнение системы (6), получим искомую переменную x_n-1. Подставляя x_n-1 и x_n в (n-2) -е уравнение получим переменную x_n-2, и т.д.

Рассмотрим случай, когда условия (7) не выполняются. Очевидно, что при перестановке строк, решение системы линейных уравнений не меняется. Поэтому, если на каком то этапе преобразования ведущий элемент равен нулю, то можно переставлять строки. Переставлять строки рекомендуется и в случае, когда ведущий элемент близок к нулю. Более того, наилучший результат при решении системы получается при выборе максимального по модулю ведущего элемента.

Представим систему линейных уравнений (1) в матричном виде:

Ax=b,

(8)

где (i=1,2...n, j=1,2,...n), b=(b₁ b₂ ... b_n)^T, x=(x₁,x₂,... x_n)^T.

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

Тогда вместо системы (8) можно рассмотреть систему

P₁Ax=P₁b.

(9)

Построим матрицу исключений:

Умножая левую и правую части системы (9) на M₁, получим:

M₁P₁Ax=M₁P₁b.

(10)

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

Во втором шаге аналогичным образом выбираются матрица перестановок P₂ и матрица исключений M₂. Вычисляются M₂P₂M₁P₁A и M₂P₂M₁P₁b . Стоится эквивалентная система

M₂P₂M₁P₁Ax=M₂P₂M₁P₁b

Через n-1 шагов получим:

MAx=Mb,

где MA верхняя треугольная матрица.

Далее, аналогично вышеизложенному, вычисляются x_n, x_n-1, ... x₁.

Пример решения систем линейных уравнений методом исключения Гаусса

Рассмотрим следующую систему линейных уравнений:

(11)

Так как ведущий элемент 5 по модулю больше чем другие элементы в первом столбце, то матрица перестановок является единичной матрицей и, следовательно, P₁A=EA=A, P₁b=Eb=b, т.е. в системе (11) ничего не меняется.

Далее построим матрицу исключений M₁: