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

Пусть требуется решить систему 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-ом столбце и переставить строки системы уравнений так, чтобы максимальный элемент стал диагональным элементом матрицы коэффициентов.