Алгоритм.
Строим расширенную матрицу размерностью n на n+1, приписав, справа к
матрицы
вектор
т.е. ci,j=ai,j , ci,n+1=bi , где i=1,2,3,…,n j=1,2,3,…,n
. Задаем номер ведущей строки k = 1
Преобразуем все строки, расположенные ниже k-ой так, чтобы элементы cik=0,
для этого вычисляем множитель β=-сi,k/ck,k и каждую i-ую строку заменяем суммой i–ой и k-ой умноженной на β, т.е. ci,j=ci,j+β*ck,j где i = k+1,k+2,k+3,….,n и j = k,k+1,k+2,…,n+1
Проверяем k = n-1 если нет, то выбираем новую ведущую строку k=k+1 и переходим на пункт 2, иначе выполняем пункт 4.
Обратный ход. Из последнего n-ого уравнения определяем последнее n-ое неизвестное. xn=cn,n+1/cn,n Последовательно, из предыдущих уравнений начиная с i=n-1, вычисляем соответствующие неизвестные xi. Последним, определяется первое неизвестное из первого уравнение.