Прямые методы решения систем линейных уравнений (СЛАУ): метод Гаусса

Значение СЛАУ в вычислительной практике

Системы линейных алгебраических уравнений (СЛАУ) составляют основу вычислительной математики. К решению СЛАУ сводятся задачи из самых разных областей: от аппроксимации функций и численного интегрирования дифференциальных уравнений до расчета электрических цепей, анализа строительных конструкций методом конечных элементов и алгоритмов машинного обучения. Огромное количество нелинейных задач в процессе линеаризации (например, в многомерном методе Ньютона) в конечном итоге требует многократного решения СЛАУ на каждой итерации.

Методы решения СЛАУ делятся на две большие группы: прямые (точные) и итерационные. Прямые методы позволяют найти точное решение (в предположении отсутствия ошибок округления) за заранее известное, конечное число арифметических операций. Итерационные методы строят последовательность приближений, которая стремится к точному решению бесконечно. Сегодня мы рассмотрим самый известный прямой метод.

Классический алгоритм Гаусса

Метод Гаусса (метод последовательного исключения неизвестных) изучается еще в школьном курсе алгебры. Его алгоритмическая суть заключается в преобразовании исходной матрицы системы к верхнетреугольному виду с помощью элементарных преобразований строк. Алгоритм Гаусса состоит из двух этапов: прямого хода и обратного хода.

Прямой ход начинается с первого уравнения. С помощью первого уравнения переменная x_1 исключается из всех последующих уравнений системы путем умножения первой строки на соответствующий коэффициент и вычитания ее из остальных строк. Затем мы переходим ко второму уравнению и исключаем переменную x_2 из всех уравнений ниже второго. Этот процесс продолжается до тех пор, пока в последнем уравнении не останется только одна неизвестная переменная x_n. После прямого хода матрица коэффициентов приобретает верхнетреугольный вид: ниже главной диагонали находятся только нули.

Обратный ход начинается с конца. Из последнего уравнения тривиально находится значение переменной x_n. Найденное значение подставляется в предпоследнее уравнение, откуда вычисляется x_{n-1}. Процесс «поднятия» по треугольной матрице продолжается вплоть до первого уравнения, в результате чего находятся все неизвестные вектора решения.

Проблема малых ведущих элементов и выбор главного элемента

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

Для решения этой проблемы применяется модификация метода Гаусса с выбором главного элемента (частичный пивотинг). На каждом шаге прямого хода программа просматривает текущий столбец (среди не преобразованных строк) и находит максимальный по модулю элемент. Затем строка с этим максимальным элементом меняется местами с текущей рабочей строкой. Это гарантирует деление на наибольшее возможное число, что минимизирует накопление ошибок округления и делает метод Гаусса исключительно надежным инструментом для решения плотных СЛАУ умеренной размерности.