Алгоритм метода Гаусса

Пусть дана система n линейных уравнений с n переменными:

Коэффициенты а_ij при переменных будем рассматривать как элементы двумерного массива A (N, N), а свободные члены b_i — как элементы одномерного массива В (N). Решение x_i(i = ) разместим в одномерном массиве В (N). Коэффициенты а_ij и свободные члены b_i будем рассматривать как элементы расширенной матрицы

.

Предписываемые методом Гаусса преобразования будем выполнять над элементами расширенной матрицы. Опишем формально алгоритм решения линейной системы методом Гаусса без выбора главного элемента.

1. Элементы первой строки расширенной матрицы (А | В)делим на а₁₁. Полученную после такого деления первую строку умножаем последовательно на a_k1(k = ) и вычитаем ее затем из k-ой строки (k = ). После этого преобразования в первом столбце массива A (кроме ) все элементы будут равны нулю, то есть получим матрицу:

2. Элементы второй строки расширенной матрицы делим на , затем умножаем ее последовательно на и вычитаем из оставшихся строк при

3. Продолжаем этот процесс исключения переменных (получения нулей) до тех пор, пока подобная процедура не будет проделана с (n — 1)-й строкой матрицы. После этого получим матрицу:

4. Элементы n-й строки делим на и в результате получаем:

На этом закончился прямой ход метода Гаусса.

5. Выполняем обратный ход метода Гаусса: в (п—1)-ю строку последней матрицы подставляем значение хn и находим значение xn-1, затем последовательно находим xn-2, xn-3,..., x2, x1 по формулам:

Этот алгоритм является экономичным в смысле использования памяти, так как все промежуточные и окончательные значения элементов в процессе преобразования матриц последовательно хранятся в тех же ячейках памяти, что и массивы А и В. Очередные значения диагональных элементов перед началом преобразования строк будем присваивать простой переменной D, что позволит хранить их до окончания преобразования очередной строки матрицы.

Значения переменных x_n, x_n-1,..., x₁ присваиваются элементам массива свободных членов В.

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

Метод вращения является разновидностью метода Гаусса. Он обладает повышенной устойчивостью к “провалам” промежуточных вычислений. Этот метод обеспечивает приведение исходной системы к системе с верхней треугольной матрицей (см. литературу).