3.2. Метод Гаусса (метод исключения)

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

Для простоты ограничимся рассмотрением системы четырех уравнений с четырьмя неизвестными:

(1)

Пусть (ведущий элемент).

(2)

где

Пользуясь уравнением (2) можно исключить неизвестное x₁ из второго, третьего и четвертого уравнений системы (1).

Для этого из второго уравнения вычтем уравнение (2), умноженное на а₂₁, из третьего уравнения – уравнение (2), умноженное на а₃₁, из четвертого – уравнение (2), умноженное на а₄₁. В результате получим систему:

(3)

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

(4)

Отсюда видно, что значение переменной х₄ определяется из четвертого уравнения. Подставив полученное значение в третье уравнение системы (4), можно найти значение х₃, а затем из второго и первого уравнений можно найти значения переменных х₂ и х₁ соответственно.

Таким образом, решение системы распадается на два этапа:

1. Прямой ход: приведение системы (1) к треугольному виду.

2. Обратный ход: определение значений неизвестных по уравнениям системы (4).

Очевидно, что рассмотренный метод применим лишь при условии, что все «ведущие» элементы отличные от нуля. Если же какой-либо из них обращается в нуль, то в соответствующей системе достаточно провести перестановку уравнений с тем, чтобы сделать ведущий элемент отличным от нуля (считается , что матрица А неособенная).

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

Обозначим через приближенное решение системы уравнений, полученное методом Гаусса. Подставим это приближенное решение в систему и вычислим правые части:

(5)

Так как отличаются от истинного значения, то и , будут отличаться от .

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

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

Подставим в систему вместо столбца свободных членов столбец невязок, а вместо переменных х_i – неизвестные поправки:

(6)

Решая эту систему, получаем значения и новое приближенное решение системы:

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

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