Метод Гаусса

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

Матрица называется верхнетреугольной, если ниже главной диагонали все элементы равны нулю, т.е. a_ij=0 при i>j. Аналогично, матрица называется нижнетреугольной, если все элементы выше главной диагонали (i<j) равны 0. Матрица называется диагональной, если только на главной диагонали (i=j) стоят ненулевые элементы. Метод Гаусса решения систем линейных уравнений состоит из двух этапов: прямого хода и обратного хода.

• Прямой ход.

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

Рассмотрим k-ый шаг прямого хода. На k-ом шаге матрица системы имеет вид:

(а₁₁ а₁₂ … а_1k … a_1n | b₁)

(0 a₂₂ … a_2k … a_2n | b₂)

(0 … … … … … )

(0 0 … a_kk … a_kn | b_k)

(0 … … … … … )

(0 0 … a_nk … a_nn | b_n)

Осталось n-k+1 неизвестных. Чтобы удалить х(k) из последней строчки, например, надо из нее вычесть k-ую строчку с таким коэффициентом, чтобы получить на месте а_nk ноль. Для этого коэффициент должен быть равен c_nk=a_nk/a_kk. Элемент а_kk называется разрешающим элементом k-ого шага и должен быть отличен от 0.

• Формулы прямого хода

c_mk=a_mk/a_kk где 1<=k<n

b_m=b_m-c_mkb_k, k<m<=n

a_ml=a_ml-c_mka_kl, k<=l<=n

• Обратный ход

Последовательное вычисление значения неизвестных x_n, x_n-1,..., х₁ (именно в таком порядке) для полученной после прямого хода верхнетреугольной системы называется обратным ходом.

• Формулы обратного хода. ,откуда получаем:

для k=n,n-1,…,1.

• Описание метода Гаусса для вырожденных систем.

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

• либо мы видим, что полученная система несовместна, когда в одной из последних ненулевых строк все коэффициенты левой части равны 0, а свободный член – нет

• либо система имеет бесконечное множество решений, которые можно получать следующим общим способом – задать произвольные значения всем «свободным» переменным, которые были пропущены в процессе исключения, т.е. «исключились сами по себе» и вычислить значения всех остальных переменных по формулам обратного хода.