Обратный ход

7. ;

8. для k = n  1, …, 2, 1: (цикл 4 по k от n  1 до 1)

9.

(конец цикла 4).

Подставив на вход данного алгоритма элементы квадратной матрицы A = [a_ij] (i, j = 1,2,…, n) коэффициентов a_ij системы (1) и вектор свободных членов b = (b_i) (i = 1,2, …, n) и выполнив три вложенных цикла вычислений прямого хода (строки 1  6) и один цикл вычислений обратного хода (строки 7  9), на выходе алгоритма получим компоненты вектора решения x = (x_i) (i = 1, 2,…, n) в обратном порядке.

2.4 Метод Гаусса с выбором главного элемента

Так как реальные машинные вычисления производятся не с точными, а с усечёнными числами, т.е. неизбежны ошибки округления, то, анализируя, например, формулы (10), (12) можно сделать вывод о том, что выполнение алгоритма может прекратиться или привести к неверным результатам, если знаменатели дробей в формулах (10), (12) на каком-то этапе окажутся равными нулю или очень маленькими числами. Таким образом, основным ограничением рассмотренного метода Гаусса является предположение о том, что все числа в формулах (10), (11) отличны от нуля.

В соответствии с формулами (10, на k - м шаге прямого хода метода Гаусса производится деление на величину , а также деление на производится и при вычислении в соответствии с формулой (11). Число − называется ведущим (или направляющим) элементом на k - м шаге исключения. Даже если какой-то ведущий элемент не равен нулю, а просто близок к нему, в процессе вычислений может происходить сильное накопление погрешностей.

Чтобы избежать указанных трудностей производят «модернизацию», т.е. доработку рассмотренной выше вычислительной схемы решения СЛАУ методом Гаусса. Указанная модернизация заключается в добавлении специального алгоритма, реализующего выбор главного элемента. Такой (модернизированный) метод Гаусса в литературе называется методом Гаусса с выбором главного элемента. Основная идея этого метода состоит в том, чтобы на очередном шаге исключать не следующую по номеру переменную, а ту, коэффициент при которой является наибольшим по модулю. То есть чтобы уменьшить влияние ошибок округления и исключить деление на нуль, на каждом этапе (т.е. на текущем k - м шаге) прямого хода уравнения обрабатываемой подсистемы обычно переставляют так, чтобы деление производилось на наибольший по модулю в данном обрабатываемом подстолбце элемент .

Найденный максимальный по модулю элемент (если det A ≠ 0, то этот главный элемент всегда отличен от нуля) называется k - м главным элементом. После его нахождения осуществляются преобразования k - го шага по формулам (10).

Так, например, в соответствии со сказанным, на первом шаге прямого хода метода Гаусса уравнения исходной системы:

целесообразно переставить местами так, чтобы на первом месте оказалось i -ое уравнение, у которого коэффициент имеет максимальное значение среди элементов первого столбца исходной системы: = max [ ], (i = 1,2,…, n).

Аналогично, на втором этапе прямого хода метода Гаусса уравнения обрабатываемой подсистемы:

целесообразно переставить местами так, чтобы на первом месте оказалось i -ое уравнение, у которого коэффициент имеет максимальное значение среди элементов первого столбца обрабатываемой подсистемы:

= max [ ], (i = 2,…,n), и т.д.

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

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

 вставка

Найти m > k такое, что ; Если  , остановить работу алгоритма (т.к. однозначного решения нет); Иначе  поменять местами и , и при всех j = k ,…,n – т.е. поменять первую строку обрабатываемой подсистемы на строку с первым элементом .

Иногда для поиска главного элемента на k - м шаге прямого хода производится и перестановка столбцов (на первое место выносится столбец, содержащий максимальный коэффициент при неизвестной). При этом, если переставляются столбцы, то соответствующая перестановка и перенумерация производятся и в уравнениях, которые на k - м шаге не преобразуются, т.е. при i = 1 ,2, …, k  1.