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

Способы решения систем линейных уравнений делятся на две группы:

1. Точные методы, представляющие собой алгоритмы для вычисления

корней системы (решение систем с помощью обратной матрицы, правило

Крамера, метод Гаусса и др.),

2. Итерационные методы, позволяющие получить решение системы с

заданной точностью путем сходящихся итерационных процессов (метод

итерации, метод Зейделя и др.).Вследствие неизбежных округлений результаты даже точных методов

являются приближенными. При использовании итерационных методов

дополнительно добавляется погрешность метода.

Метод Гаусса

Рассмотрим систему n линейных алгебраических уравнений относительно

n неизвестных х1, х2, …, хn:

В соответствии с правилом умножения матриц рассмотренная система

линейных уравнений может быть записана в матричном виде AX=B,

Идея метода Гаусса состоит в том, что систему (8.1) представляют в виде

матрицы

которую последовательным исключением неизвестных приводят к

эквивалентной системе с треугольной матрицей вида

Эта процедура называется прямой ход. Все коэффициенты (включая d) на

каждом шаге прямого хода пересчитываются по формулам

Если в матрице встретилась строка с номером m, в которой все элементы

сmj равны нулю, а dm≠0, то выполнение алгоритма останавливаем и делаем

вывод о том, что система несовместна. Действительно, восстанавливая систему

уравнений по матрице, получим, что m-ое уравнение будет иметь вид

0 x1 + 0 x2 + 0 x3 + …. + 0 xn= dm

Этому уравнению не удовлетворяет ни один набор чисел.

Если в матрице имеются строки, содержащие одни нули, то мы имеем

альтернативные решения данной системы.

При обратном ходе последовательно вычисляются неизвестные, начиная

с xn.

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

первых местах стояли нули, то необходимо найти строку, в которой в самом

левом столбце содержится элемент, отличный от нуля и поменять ее с первой

строкой местами.