Метод Гаусса

Ме́тод Га́усса, метод решения системы линейных алгебраических уравнений; назван в честь К. Гаусса.

Метод Гаусса состоит в приведении системы линейных алгебраических уравнений

${\displaystyle \left\{{\begin{aligned}a_{11}x_{1}+a_{12}x_{2}+\ldots +a_{1n}x_{n}&=b_{1},\\a_{21}x_{1}+a_{22}x_{2}+\ldots +a_{2n}x_{n}&=b_{2},\\&\ \vdots \\a_{m1}x_{1}+a_{m2}x_{2}+\ldots +a_{mn}x_{n}&=b_{m}.\end{aligned}}\right.}$ (1)

к ступенчатому (треугольному) виду

${\displaystyle \left\{{\begin{aligned}p_{1j_{1}}x_{j_{1}}+p_{1j_{2}}x_{j_{2}}+\ldots +p_{1j_{r}}x_{j_{r}}+\ldots +p_{1j_{n}}x_{j_{n}}&=\beta _{1},\\p_{2j_{2}}x_{j_{2}}+\ldots +p_{2j_{r}}x_{j_{r}}+\ldots +p_{2j_{n}}x_{j_{n}}&=\beta _{2},\\&\ \vdots \\p_{rj_{r}}x_{j_{r}}+\ldots +p_{rj_{n}}x_{j_{n}}&=\beta _{r},\\0&=\beta _{r+1},\\&\ \vdots \\0&=\beta _{m}.\end{aligned}}\right.}$ (2)

путём последовательного исключения неизвестных «сверху вниз» (прямой ход) и последовательное нахождение неизвестных «снизу вверх» из системы (2) (обратный ход).

Для преобразования системы используются элементарные преобразования, не меняющие множества решений: перестановка уравнений и прибавление к одному уравнению другого, умноженного на число. На первом шаге прямого хода выбирается неизвестная ${\displaystyle x_{j_{1}}}$, у которой хотя бы в одном уравнении системы (1) коэффициент отличен от нуля. Далее уравнения переставляются так, чтобы в первом уравнении ${\displaystyle a_{1j_{1}}\neq 0}$. Исключается неизвестная ${\displaystyle x_{j_{1}}}$ из остальных уравнений системы путём прибавления к ${\displaystyle k}$-му уравнению первого, умноженного на ${\displaystyle -a_{kj_{1}}/a_{1j_{1}}}$. На втором шаге оставляется без изменения первое уравнение и проделывается аналогичная процедура с остальными ${\displaystyle n-1}$ уравнениями. Через конечное число шагов (не превышающее ${\displaystyle m}$) система принимает ступенчатый вид (2).

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

Если неоднородная система уравнений, приведённая к ступенчатому виду (2), содержит хотя бы одно уравнение вида

${\displaystyle 0=\beta _{k},\qquad \beta _{k}\neq 0}$

то система несовместна; если таких уравнений нет, система совместна.

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

Если в совместной системе (2) число нетривиальных уравнений ${\displaystyle r}$ равно числу неизвестных ${\displaystyle n}$, то матрица системы является треугольной и система имеет единственное решение. Если ${\displaystyle r<n}$, система имеет бесконечное множество решений. Переменные ${\displaystyle x_{j_{1}},x_{j_{2}},\ldots ,x_{j_{r}}}$ называются главными или зависимыми, остальные переменные – свободными или независимыми. </n<></math>

В ступенчатой системе (2) перенесём слагаемые со свободными переменными в правую часть уравнений. Получаем систему

${\displaystyle \left\{{\begin{aligned}p_{1j_{1}}x_{j_{1}}+p_{1j_{2}}x_{j_{2}}+\ldots +p_{1j_{r}}x_{j_{r}}&=\beta _{1}-p_{1j_{r+1}}x_{j_{r+1}}-\ldots -p_{1j_{n}}x_{j_{n}},\\p_{2j_{2}}x_{j_{2}}+\ldots +p_{2j_{r}}x_{j_{r}}&=\beta _{2}-p_{2j_{r+1}}x_{j_{r+1}}-\ldots -p_{2j_{n}}x_{j_{n}},\\&\ \vdots \\p_{rj_{r}}x_{j_{r}}&=\beta _{r}-p_{rj_{r+1}}x_{j_{r+1}}-\ldots -p_{rj_{n}}x_{j_{n}}.\end{aligned}}\right.}$ (3)

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

Для минимизации вычислительной погрешности используется метод Гаусса с выбором главного элемента. На каждом шаге прямого хода перестановкой строк и столбцов преобразуемой матрицы добиваются того, чтобы главным элементом ${\displaystyle p_{kj_{k}}}$ оказался максимальный по модулю элемент матрицы из всех с индексами больше либо равными ${\displaystyle k}$. При частичном выборе главного элемента в качестве главного элемента ${\displaystyle p_{kj_{k}}}$ выбирается максимальный по модулю элемент ${\displaystyle k}$-й строки матрицы.

Имеются различные модификации метода Гаусса для решения задач с матрицами специального вида (симметричными, ленточными и т. д.). Доказано, что метод Гаусса – один из наиболее экономичных точных методов решения систем линейных алгебраических уравнений с точки зрения количества требуемых операций. В общем случае для решения системы ${\displaystyle n}$ уравнений требуется примерно ${\displaystyle {n^{3}}/{3}}$ операций.

Важной модификацией метода Гаусса является метод Гаусса – Жордана (метод полного исключения неизвестных), позволяющий получить систему (3) с единичной матрицей. Этот метод применяется также для нахождения обратной матрицы.