Теорема. Метод Гаусса

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

Теорема

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

Доказательство

Будем использовать матричную запись системы уравнений. Расположим строки так, чтобы первая содержала коэффициент $a_{11}\ne 0$. Прибавим первую строку с коэффициентом $-\frac{a_{i1}}{a_{11}}$ к остальным строкам $(i=2,\dots ,m)$ :

$$\left(\begin{array}{rrrrr}{a}_{11}& a_{12}& \dots & a_{1n}& b_1\\ a_{21}& a_{22}& \dots & a_{2n}& b_2\\ \dots & & & & \\ a_{m1}& a_{m2}& \dots & a_{mn}& b_m\end{array}\right)\sim \left(\begin{array}{rrrrr}{a}_{11}& a_{12}& \dots & a_{1n}& b_1\\ 0& a_{22}^{\prime }& \dots & a_{2n}^{\prime }& b_2^{\prime }\\ \dots & & & & \\ 0& a_{m2}^{\prime }& \dots & a_{mn}^{\prime }& b_m^{\prime }\end{array}\right)$$

Расположим строки так, чтобы вторая вторым элементом имела $a_{22}^{\prime }\ne 0$. Если у всех строк, начиная со второй, на этом месте ноль, перенумеруем переменные (т.е. переставим столбцы) так, чтобы ненулевой элемент появился. Если это невозможно (всюду нули), процесс завершён.

После этого повторим процедуру с предыдущего шага: прибавим вторую строку с коэффициентом $-\frac{a_{i2}^{\prime }}{a_{22}^{\prime 2}}$ к последующим строкам $(i=3,\dots ,m)$ :

$$\left(\begin{array}{rrrlll}{a}_{11}& a_{12}& a_{13}& \dots & a_{1n}& b_1\\ 0& a_{22}^{\prime }& a_{23}^{\prime }& \dots & a_{2n}^{\prime }& b_2^{\prime }\\ 0& a_{32}^{\prime }& a_{33}^{\prime }& \dots & a_{3n}^{\prime }& b_3^{\prime }\\ \dots & & & & & a_{m2}^{\prime }\\ 0& a_{m3}^{\prime }& \dots & a_{mn}^{\prime }& b_m^{\prime }& \end{array}\right)\sim \left(\begin{array}{rrrrrr}{a}_{11}& a_{12}& a_{13}& \dots & a_{1n}& b_1\\ 0& a_{22}^{\prime \prime }& a_{23}^{\prime \prime }& \dots & a_{2n}^{\prime \prime }& b_2^{\prime \prime }\\ 0& 0& a_{33}^{\prime \prime }& \dots & a_{3n}^{\prime \prime }& b_3^{\prime \prime }\\ \dots & & & & a_{m3}^{\prime \prime }& a_{mn}^{\prime \prime }\\ 0& 0& a_{m3}^{\prime \prime }& \dots & a_{mn}^{\prime \prime }& \end{array}\right)$$

будем повторять эту последовательностей действий (прибавлять строку с коэффициентов к последующим и при необходимости перенумеровывать переменные, переставляя столбцы), пока не приведём матрицу к виду:

$$\begin{array}{rl}& \left(\begin{array}{rrrrrrr}{a}_{11}^{\ast }& a_{12}^{\ast }& \dots & a_{1r}^{\ast }& \dots & a_{1n}^{\ast }& b_1^{\ast }\\ 0& a_{22}^{\ast }& \dots & a_{2r}^{\ast }& \dots & a_{2n}^{\ast }& b_2^{\ast }\\ \dots & & & & & & \dots \\ 0& 0& \dots & a_{rr}^{\ast }& \dots & a_{rn}^{\ast }& b_r^{\ast }\\ 0& 0& \dots & 0& \dots & 0& b_{r+1}^{\ast }\\ \dots & & & & & & \dots \\ 0& 0& \dots & 0& \dots & 0& b_m^{\ast }\end{array}\right),\\ & \\ & \text{ либо }\left(\begin{array}{rrrrrrr}{a}_{11}^{\ast }& a_{12}^{\ast }& \dots & a_{1r}^{\ast }& \dots & a_{1n}^{\ast }& b_1^{\ast }\\ 0& a_{22}^{\ast }& \dots & a_{2r}^{\ast }& \dots & a_{2n}^{\ast }& b_2^{\ast }\\ \dots & & & a_m^{\ast }& & a_{mn}^{\ast }& \dots \\ 0& 0& \dots & a_{mr}^{\ast }& \dots & b_m^{\ast }& \end{array}\right)\text{, }\\ & \\ & \text{ либо }\left(\begin{array}{rrrrrrrr}{a}_{11}^{\ast }& a_{12}^{\ast }& \dots & a_{1k}^{\ast }& \dots & a_{1(n-1)}^{\ast }& a_{1n}^{\ast }& b_1^{\ast }\\ 0& a_{22}^{\ast }& \dots & a_{2k}^{\ast }& \dots & a_{2(n-1)}^{\ast }& a_{2n}^{\ast }& b_2^{\ast }\\ \dots & & & & & & a^{\ast }& \\ 0& 0& \dots & 0& \dots & a_{(n-1)(n-1)}^{\ast }& a_{(n-1)n}^{\ast }& b_{n-1}^{\ast }\\ 0& 0& \dots & 0& \dots & 0& a_{nn}^{\ast }& b_n^{\ast }\end{array}\right)\text{ при }\mathrm{rank}A=n\text{. }\end{array}$$

Количество ненулевых строк расширенной матрицы $A$ будет равно $\mathrm{rank}A$, а число ненулевых $b_i^{\ast }$ (при $i>r$ ) будет равно рангу $\mathrm{rank}\bar{A}-\mathrm{rank}A$.

Итак, система приведена к ступенчатому виду. Она имеет решение, если все $b_i^{\ast }$ при $i>r$ равны нулю.
Если система совместна и $\mathrm{rank}A=n$, матрица $A$ будет иметь треугольный вид (нулевые строки, т.е. тривиальные уравнения, можно откинуть).
Описанные в теореме действия называют прямым ходом метода Гаусса.
Далее для решения системы совершаем действия из доказательства теоремы Кронекера Капелли:

1. Переменные не вошедшие в Базисный минор (т.е. в подматрицу $r\times r$ в левом верхнем углу) объявляем свободными и придаём им произвольные значения: $x_{r+1}={\alpha }_{r+1},\dots ,x_n={\alpha }_n$.

2. Из последнего $r$-го уравнения выражаем $x_r$ : $x_r=\frac{1}{a_{rr}^{\ast }}\left(b_r^{\ast }-a_{r(r+1)}{\alpha }_{r+1}-\dots -a_{rn}{\alpha }_{rn}\right)$

3. С учётом найденного $x_r$ из предпоследнего уравнения выражаем $x_{r-1}$.

4. Повторяем процедулу вплоть до $x_1$.

Действия по определению $x_r,x_{r-1},\dots ,x_1$ называют обратным ходом метода Гаусса.
В конце результат записывают с использованием столбцов фундаментальной системы решений.

Примеры

1. Рассмотрим пример:

$$\{\begin{array}{l}7x_1-5x_2-2x_3-4x_4=8,\\ -3x_1+2x_2+x_3+2x_4=-3,\\ 2x_1-x_2-x_3-2x_4=1,\\ -x_1+x_3+2x_4=1,\\ -x_2+x_3+2x_4=3.\end{array}$$

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

$$\left(\begin{array}{ccccc}7& -5& -2& -4& 8\\ -3& 2& 1& 2& -3\\ 2& -1& -1& -2& 1\\ -1& 0& 1& 2& 1\\ 0& -1& 1& 2& 3\end{array}\right)\sim \left(\begin{array}{ccccc}-1& 0& 1& 2& 1\\ 0& -1& 1& 2& 3\\ 0& -1& 1& 2& 3\\ 0& 2& -2& -4& -6\\ 0& -5& 5& 10& 15\end{array}\right)\sim \left(\begin{array}{ccccc}-1& 0& 1& 2& 1\\ 0& -1& 1& 2& 3\\ 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0\end{array}\right)$$

$\mathrm{rank}A=\mathrm{rank}\bar{A}=2$. Переменные, не вошедшие в Базисный минор, т.е. $x_3$ и $x_4$ объявляем свободными и придаём им произвольные значения: $x_3=\alpha ,x_4=\beta$. Затем выражаем через них $x_1,x_2$ :

$$x_2=\alpha +2\beta -3,x_1=\alpha +2\beta -1$$

Записываем результат:

$$\left(\begin{array}{l}{x}_1\\ x_2\\ x_3\\ x_4\end{array}\right)=\left(\begin{array}{c}\alpha +2\beta -1\\ \alpha +2\beta -3\\ \alpha \\ \beta \end{array}\right)=\alpha \left(\begin{array}{l}1\\ 1\\ 1\\ 0\end{array}\right)+\beta \left(\begin{array}{l}2\\ 2\\ 0\\ 1\end{array}\right)+\left(\begin{array}{c}-1\\ -3\\ 0\\ 0\end{array}\right)$$

Здесь фундаментальная система решений содержит два элемента: $(1,1,1,0{)}^T,(2,2,0,1{)}^T$. Частным решением является столбец $(-1,-3,0,0{)}^T$.

Замечание

В случае двух и более свободных переменных результат неоднозначен и в фундаментальную систему решений могут входить разные наборы столбцов, но всегда в одном и том же количестве, $n-r$.

2. Рассмотрим другой пример:

$$\{\begin{array}{l}{x}_1+x_2-x_3=1\\ 2x_1+3x_2-3x_3=2\\ -x_1-2x_2+2x_3=3\end{array}$$ $$\left(\begin{array}{cccc}1& 1& -1& 1\\ 2& 3& -3& 2\\ -1& -2& 2& 3\end{array}\right)\sim \left(\begin{array}{cccc}1& 1& -1& 1\\ 0& 1& -1& 0\\ 0& -1& 1& 4\end{array}\right)\sim \left(\begin{array}{cccc}1& 1& -1& 1\\ 0& 1& -1& 0\\ 0& 0& 0& 4\end{array}\right)$$

$\mathrm{rank}A=2,\mathrm{rank}\bar{A}=3$ и система не имеет решений. Это также легко видеть из последнего уравнения, в котором сумма нулей приравнивается к 4.

системыуравнений матрица