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

Пусть требуется решить систему n линейных алгебраических уравнений с n неизвестными:

 

(3.9)

 

Прямой ход метода Гаусса преобразует систему (3.9) к треугольному виду исключением соответствующих неизвестных. Пусть a ₁₁ ≠ 0. Первый шаг заключается в исключении переменной x ₁ с помощью первого уравнения из остальных уравнений. Разделим первое уравнение на a ₁₁:

 

(3.10)

 

Затем от второго уравнения отнимем первое уравнение, умноженное на a ₂₁. В результате, на месте второго уравнения получим уравнение, не содержащее x ₁. Чтобы исключить x ₁ из третьего уравнения отнимем от него первое уравнение, умноженное на a ₃₁. Аналогично исключаем x ₁ из четвертого и последующих уравнений. Для исключения x ₁ из i -го уравнения (i = 2, 3, …, n) применим формулы:

 

(3.11)

 

В результате этих вычислений получим систему вида:

 

(3.12)

 

На втором шаге исключаем переменную x ₂ с помощью второго уравнения из третьего и последующих уравнений. Предположим, что . Разделим второе уравнение на :

 

(3.13)

 

В системе (3.12) с помощью второй строки исключим x ₂ из i -го уравнения(i = 3, 4, …, n), применяя формулы:

 

(3.14)

 

Система (3.12) преобразуется к следующему виду:

 

(3.15)

 

1. В общем случае, на шаге m, для m = 1, 2, …, n – 1, делим сначала m -ое уравнение на :

 

(3.16)

 

а затем исключаем переменную x_m с помощью m -ого уравнения из i -го,
где i = m + 1, …, n:

 

(3.17)

 

Здесь предполагается, что на каждом шаге выполняется условие .

В результате (n – 1)-го шага система (3.9) приобретает вид:

 

(3.18)

 

2. Обратный ход метода Гаусса вычисляет неизвестные x_i в обратном порядке. Из последнего уравнения в (3.18) находим

 

(3.19)

 

Неизвестные x_i определяем по следующим формулам:

 

(3.20)

 

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

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

Метод Гаусса с выбором главного элемента по столбцам отличается от алгоритма (3.16) — (3.20) только тем, что перед преобразованием (3.16) надо выполнить поиск максимального по модулю элемента в m -ом столбце и переставить строки системы уравнений так, чтобы максимальный элемент стал диагональным элементом матрицы коэффициентов.