Метод Гаусса

Основные понятия

Уравнение называется линейным, если оно содержит неизвестные только в первой степени и не содержит произведений неизвестных, т.е. если оно имеет вид:

,

где (), – числа.

называются коэффициентами уравнения, называется свободным членом. Если , то уравнение называется однородным. В противном случае уравнение называется неоднородным.

В этом параграфе мы будем рассматривать систему линейных уравнений с неизвестными, т.е. систему вида:

Обозначим через А и А* следующие матрицы:

и .

Матрицу А называют основной матрицей системы (1), а матрицу А* – расширенной матрицей системы (1).

Пусть X – матрица-столбец неизвестных, B – матрица-столбец свободных членов, т.е.

и .

Тогда систему (1) можно записать в виде матричного уравнения A*X = B. Его называют матричной формой системы (1).

Упорядоченный набор чисел называется решением системы (1), если он обращает в тождество каждое уравнение системы. Если система линейных уравнений имеет хотя бы одно решение, то ее называют совместной. Система линейных уравнений, не имеющая решений, называется несовместной.

Если система совместна, то она имеет либо одно решение, либо множество решений. Система, имеющая единственное решение, называется определенной. Система, имеющая множество решение, называется неопределенной.

Критерии совместности и определенности системы дают следующие две теоремы.

ТЕОРЕМА (Кронекера–Капелли). Система линейных уравнений (1) совместна тогда и только тогда, когда ранг матрицы системы равен рангу ее расширенной матрицы, т.е.

.

ТЕОРЕМА (критерий единственности решения). Система линейных уравнений (1) имеет единственное решение тогда и только тогда, когда ранг матрицы системы равен рангу ее расширенной матрицы и равен числу переменных, т.е.

.

Метод Гаусса

Запишем систему Ax=f, в развернутом виде

Метод Гаусса состоит в последовательном исключении неизвестных из этой системы. Предположим, что . Последовательно умножая первое уравнение на и складывая с i – м уравнение, исключим из всех уравнений кроме первого. Получим систему

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

Описанная процедура называется прямым ходом метода Гаусса. Заметим, что ее выполнение было возможно при условии, что все , не равны нулю.

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

.

Эта процедура получила название обратный ход метода Гаусса.

Метод Гаусса может быть легко реализован на компьютере. При выполнении вычислений, как правило, не интересуют промежуточные значения матрицы А. Поэтому численная реализация метода сводится к преобразованию элементов массива размерности (m×(m+1)), где m+1 столбец содержит элементы правой части системы.

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

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

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

Существует метод Гаусса с выбором главного элемента по всей матрице. В этом случае переставляются не только строки, но и столбцы[1]. Использование модификаций метода Гаусса приводит к усложнению алгоритма увеличению числа операций и соответственно к росту времени счета. Поэтому целесообразность выбора того или иного метода определяется непосредственно программистом.

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

.

Метод Гаусса позволяет найти обратную матрицу. Для этого необходимо решить матричное уравнение

,

где Е– единичная матрица. Его решение сводится к решению m систем

у вектора j ─я компонента равна единице, а остальные компоненты равны нулю