Метод Гаусса

Наиболее известным и популярным прямым методом решения СЛАУ является метод Гаусса. Этот метод заключается в последовательном исключении неизвестных. Пусть в системе уравнений

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

.

Если , то, продолжая аналогичное исключение, приходим к системе уравнений с верхней треугольной матрицей

.

Из нее в обратном порядке находим все значения x_i:

.

Процесс приведения к системе с треугольной матрицей называется прямым ходом, а нахождения неизвестных – обратным. В случае если один из ведущих элементов равен нулю, изложенный алгоритм метода Гаусса неприменим. Кроме того, если какие–либо ведущие элементы малы, то это приводит к усилению ошибок округления и ухудшению точности счета. Поэтому обычно используется другой вариант метода Гаусса – схема Гаусса с выбором главного элемента. Путем перестановки строк, а также столбцов с соответствующей перенумерацией коэффициентов и неизвестных добиваются выполнения условия:

, j = i+1,i+ 2, …, m;

т.е. осуществляется выбор первого главного элемента. Переставляя уравнения так, чтобы в первом уравнении коэффициент a₁₁ был максимальным по модулю. Разделив первую строку на главный элемент, как и прежде, исключают x₁ из остальных уравнений. Затем для оставшихся столбцов и строк выбирают второй главный элемент и т.д.

Рассмотрим применение метода Гаусса с выбором главного элемента на примере следующей системы уравнений:

В первом уравнении коэффициент при =0, во втором = 1 и в третьем = -2, т.е. максимальный по модулю коэффициент в третьем уравнении. Поэтому переставим третье и первое уравнение:

Исключим из второго и третьего уравнений с помощью первого. Во втором уравнении исключать не надо. Для исключения из третьего уравнения умножим первое на 0.5 и сложим с третьим:

Рассмотрим второе и третье уравнения. Максимальный по модулю элемент при в третьем. Поэтому поместим его на место второго:

Исключим из третьего уравнения. Для этого умножим второе на -0.5 и сложим с третьим:

Обратный ход: .

Проверка: 0.5*8+0=4, -3+8-0=5, -2*(-3)+0=6.

Такая перестановка уравнений необходима для того, чтобы уменьшить влияние ошибок округления на конечный результат.

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