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

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

Вычисления с помощью метода Гаусса заключаются в последовательном исключении неизвестных из системы для преобразования ее к эквивалентной системе с верхней треугольной матрицей. Вычисления значений неизвестных производят на этапе обратного хода.

Помимо аналитического решения СЛАУ метод Гаусса также применяется для:

• -нахождения матрицы, обратной к данной (к матрице справа приписывается единичная такого же размера, что и исходная:, после чего приводится к виду единичной матрицы методом Гаусса-Жордана; в результате на месте изначальной единичной матрицы справа оказывается обратная к исходной матрица:);
• -определения ранга матрицы (согласно следствию из теоремы КронекераКапелли ранг матрицы равен числу её главных переменных);
• -численного решения СЛАУ в вычислительной технике (ввиду погрешности вычислений используется Метод Гаусса с выделением главного элемента, суть которого заключена в том, чтобы на каждом шаге в качестве главной переменной выбирать ту, при которой среди оставшихся после вычёркивания очередных строк и столбцов стоит максимальный по модулю коэффициент)

В отличие от матричного метода и метода Крамера, метод Гаусса может быть применен к системам линейных уравнений с произвольным числом уравнений и неизвестных. Метод Гаусса — один из основных результатов линейной алгебры и аналитической геометрии, к нему сводятся множество других теорем и методов линейной алгебры (теория и вычисление определителей, решение систем линейных уравнений, вычисление ранга матрицы и обратной матрицы, теория базисов конечномерных векторных пространств и т. д.).

Алгоритм Гаусса использует элементарные преобразования матрицы двух типов.

Преобразование первого рода: две строки матрицы меняются местами, и при этом знаки всех элементов одной из строк изменяются на противоположные.

Преобразование второго рода: к одной строке матрицы прибавляется другая строка, умноженная на произвольное число.

Метод Гаусса в математическом варианте состоит в следующем:

• -ищем сначала ненулевой элемент в первом столбце. Если все элементы первого столбца нулевые, то переходим ко второму столбцу, и так далее. Если нашли ненулевой элемент в k-й строке, то при помощи элементарного преобразования первого рода меняем местами первую и k-ю строки, добиваясь того, чтобы первый элемент первой строки был отличен от нуля;
• -используя элементарные преобразования второго рода, обнуляем все элементы первого столбца, начиная со второго элемента. Для этого от строки с номером k вычитаем первую строку, умноженную на коэффициент ak1/a11.
• -переходим ко второму столбцу (или j-му, если все элементы первого столбца были нулевыми), и в дальнейшем рассматриваем только часть матрицы, начиная со второй строки и ниже. Снова повторяем пункты 1) и 2) до тех пор, пока не приведем матрицу к ступенчатому виду.

Программистский вариант метода Гаусса имеет три отличия от математического:

— индексы строк и столбцов матрицы начинаются с нуля, а не с единицы;

недостаточно найти просто ненулевой элемент в столбце. В программировании все действия с вещественными числами производятся приближенно, поэтому можно считать, что точного равенства вещественных чисел вообще не бывает. Некоторые компиляторы даже выдают предупреждения на каждую операцию проверки равенства вещественных чисел. Поэтому вместо проверки на равенство нулю числа aij следует сравнивать его абсолютную величину ijс очень маленьким числом е (например, е = 0.1). Если ij=< е, то следует считать элемент aij нулевым;

— при обнулении элементов j-го столбца, начиная со строки i + 1, мы к k-й строке, где k > i, прибавляем i-ю строку, умноженную на коэффициент r = -akj/aij:

Такая схема работает нормально только тогда, когда коэффициент r по абсолютной величине не превосходит единицы. В противном случае, ошибки округления умножаются на большой коэффициент и, таким образом, экспоненциально растут. Математики называют это явление неустойчивостью вычислительной схемы. Если вычислительная схема неустойчива, то полученные с ее помощью результаты не имеют никакого отношения к исходной задаче. В нашем случае схема устойчива, когда коэффициент r = -akj/aij не превосходит по модулю единицы. Для этого должно выполняться неравенство Отсюда следует, что при поиске разрешающего элемента в j-м столбце необходимо найти не первый попавшийся ненулевой элемент, а максимальный по абсолютной величине. Если он по модулю не превосходит е, то считаем, что все элементы столбца нулевые; иначе меняем местами строки, ставя его на вершину столбца, и затем обнуляем столбец элементарными преобразованиями второго рода.

Основная идея метода Гаусса — привести матрицу систему к диагональному виду, то есть все элементы главной диагонали — нули. Для приведения матрицы к такому виду, мы выбираем самую верхнюю строку матрицы, и вычитаем её из всех остальных строк, умножив её для каждой строки на некий коэффициент, так, что самый левый столбец ниже главной диагонали заполнен нулями.