==Системы линейных уравнений==
~~TOC~~
Обозначим через $ \mathbb A_{} $ любое из множеств $ \mathbb Q_{}, \mathbb R_{} $ или $ \mathbb C_{} $.
**Системой линейных (алгебраических) уравнений** (СЛАУ или просто СЛУ) над $ \mathbb A_{} $ называется совокупность (набор) из нескольких уравнений вида
$$
\left\{
\begin{array}{lllll}
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,\\
\dots & & & & \dots \\
a_{m1}x_1 &+a_{m2}x_2&+ \ldots&+a_{mn}x_n &=b_m
\end{array} \right.
$$
от одного и того же набора переменных (неизвестных) $ x_{1},\dots,x_n $.
Здесь числа $ \left\{a_{j k} \right\}_{j=1,\dots,m \atop k=1,\dots,n } $ и $ \{ b_{j} \}_{j=1,\dots,m} $ --- из $ \mathbb A_{} $ ; они называются **коэффициентами системы**.
Первый индекс у коэффициента $ a_{j k} $ отвечает за номер уравнения, а второй --- за номер переменной.
!!П!! **Примеры** систем уравнений над $ \mathbb R $.
$$
\left\{\begin{array}{rrrr}
2\,x & + y & + z &=1, \\
x &+ 2\, y &+ z & = 2.
\end{array}
\right.
$$
Допустимо, чтобы в системе были одинаковые уравнения; также формально не запрещается записывать взаимно противоречивые уравнения:
$$
\left\{\begin{array}{rrrr}
x_1 & + x_2 & + x_3 &=1, \\
x_1 & + x_2 & + x_3 &=1, \\
x_1 & + x_2 & + x_3 &=2, \\
x_1 & + x_2 & + x_3 &=3.
\end{array}
\right.
$$
Более того, подобные --- очевидно "бессмысленные" --- системы имеют право не только на формальное существование --- см.
☞
((#Псевдорешение_системы_линейных_уравнений ЗДЕСЬ)). В следующей системе
$$
\left\{\begin{array}{rrrrrr}
\sqrt[3]{3}x_1 & & & + x_4 & + e^{\pi} x_5 &=0, \\
x_1 & & & -2\, x_4 & &=3/9, \\
-57\,x_1 & & & & &=2, \\
& & & & &0=1 \\
\end{array}
\right.
$$
надо специально договариваться относительно каких переменных она рассматривается. Формально в ней присутствуют только переменные $ x_1, x_4 $ и $ x_5 $. Однако, возможно, что на самом деле в этой системе предполагается, что имеются еще и переменные $ x_2,x_3 $ с нулевыми коэффициентами при этих переменных. Последнее уравнение не содержит переменных вовсе; тем не менее, этот случай также формально допустим.
♦
Относительно числа $ m_{} $ уравнений не делается ни какого предположения: оно может быть меньше, больше или равно числу переменных $ n_{} $. Если $ m_{}>n $ то система называется **переопределенной**. **Решением системы уравнений** называется любой набор значений переменных
$ x_1=\alpha_{1},\dots, x_n = \alpha_n $, обращающий каждое из уравнений в истинное равенство. Система называется **совместной** если она имеет хотя бы одно решение и **несовместной** в противном случае.
!!!!! Можно доказать (см. результаты
☟
((#установление_множества_решений НИЖЕ)) ), что все возможности для произвольной системы ограничиваются следующими вариантами:
1.
система совместна и имеет единственное решение;
2.
cистема совместна и имеет бесконечное множество решений;
3.
cистема несовместна.
При этом все решения будут находиться в том же множестве $ \mathbb A_{} $, что и коэффициенты системы.
Задача о существовании __целочисленных__ решений системы уравнений с коэффициентами из $ \mathbb Z_{} $ рассматривается
☞
((:modular/vspom4 ЗДЕСЬ)). У задачи имеется специфика, требующая дополнительной модификации алгоритмов, излагаемых в настоящем разделе.
===Матричная форма записи==
Для системы линейных уравнений относительно переменных $ x_1,x_2,\dots,x_n $
$$
\left\{
\begin{array}{lllll}
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,\\
\dots & & & & \dots \\
a_{m1}x_1 &+a_{m2}x_2&+ \ldots&+a_{mn}x_n &=b_m.
\end{array} \right.
$$
**матрицей системы** называется ((:algebra2#определение_обозначения матрица))
$$
A=\left(
\begin{array}{llcl}
a_{11} & a_{12} & \dots & a_{1n} \\
a_{21} & a_{22} & \dots & a_{2n} \\
\dots &&& \dots \\
a_{m1} & a_{m2} & \dots & a_{mn}
\end{array}
\right)_{m\times n} \ ;
$$
cтолбец
$$
{\mathcal B} =
\left(
\begin{array}{l}
b_{1} \\
b_{2} \\
\vdots \\
b_{m}
\end{array}
\right)
$$
называется **столбцом правых частей** системы, а столбец
$$
X=
\left(
\begin{array}{l}
x_{1} \\
x_{2} \\
\vdots \\
x_{n}
\end{array}
\right)
$$
--- **столбцом неизвестных**.
Используя правило ((:algebra2#умножение умножения матриц)), систему можно записать в матричном виде:
$$
AX={\mathcal B} \ .
$$
Любое решение $ x_1=\alpha_1,\dots,x_n=\alpha_n $ системы можно также записать в виде столбца:
$$
X=\left( \begin{array}{l} \alpha_1 \\ \vdots \\ \alpha_n \end{array} \right) \in \mathbb A^n \ .
$$
Матрица, составленная из всех коэффициентов системы уравнений:
$$
[A \mid \mathcal B ]=
\left(
\begin{array}{rrrrr}
a_{11} & a_{12} & \dots & a_{1n} & b_1 \\
a_{21} & a_{22} & \dots & a_{2n} & b_2 \\
\dots &&& & \dots \\
a_{m1} & a_{m2} & \dots & a_{mn} & b_m
\end{array}
\right)_{m\times (n+1)} \ ,
$$
т.е. ((:algebra2#конкатенация конкатенацией)) матрицы $ A_{} $ и столбца правых частей $ {\mathcal B}_{} $ называется **расширенной матрицей системы** л.у.
===Исключение переменных (метод Гаусса)==
====Идея==
метода достаточно проста.
!!П!! **Пример.** Решить систему уравнений
$$
\left\{
\begin{array}{rrrr}
2x_1&-3x_2&-x_3&=3 \\
4x_1&-3x_2&-5x_3&=6 \\
3x_1&+5x_2&+9x_3&=-8
\end{array}
\right.
$$
**Решение.** Выразим из первого уравнения $ x_{1} $
$$ x_1=\frac{3}{2} x_2+\frac{1}{2} x_3 + \frac{3}{2} $$
и подставим в оставшиеся уравнения
$$ 4 \left(\frac{3}{2} x_2+\frac{1}{2} x_3 + \frac{3}{2}\right) -3\,x_2-5\,x_3=6 \ {\color{Red} \iff } \ 3x_2-3x_3 = 0
$$
$$
\ {\color{Red} \iff } \ x_2-x_3=0 \ ;
$$
$$ 3 \left(\frac{3}{2} x_2+\frac{1}{2} x_3 + \frac{3}{2}\right) +5x_2+9x_3=-8 \ {\color{Red} \iff } \ \frac{19}{2} x_2 +\frac{21}{2}x_3=-\frac{25}{2}
$$
$$
{\color{Red} \iff } 19x_2 +21x_3=-25 \ .
$$
Два получившихся уравнения не зависят от неизвестной $ x_{1} $ --- она оказалась __исключенной__ из этих
уравнений. Иными словами, мы получили новую подсистему уравнений
$$
\left\{
\begin{array}{rrl}
x_2&-x_3&=0 \\
19x_2&+21x_3&=-25,
\end{array}
\right.
$$
которой должны удовлетворять неизвестные $ x_{2} $ и $ x_{3} $. Продолжаем действовать по аналогии:
выразим из первого уравнения $ x_{2} $ через $ x_{3} $:
$$x_2=x_3 $$
и подставим во второе:
$$ 40 x_3 =-25 \ \ {\color{Red} \iff } \ \ x_3=-\frac{5}{8} \ . $$
Итак, значение одной компоненты решения получено. Для нахождения оставшихся подставим значение
$ x_{3} $ в полученные по ходу решения соотношения:
$$
x_2=x_3=-\frac{5}{8} \ {\color{Red} \Rightarrow } \ x_1=\frac{3}{2} x_2+\frac{1}{2} x_3 + \frac{3}{2}=\frac{1}{4} \ .
$$
**Ответ.** $ x_{1}=1/4, x_2=-5/8, x_3=-5/8 $.
Теперь осталось формализовать изложенную идею метода (сформулировав допустимые правила действия над уравнениями ---
те, что в принципе, очевидны из ((references:newton#торжество_науки_над_здравым_смыслом здравого смысла)) ), а также исследовать возможные последствия его применения к системам общего вида.
====Исключение переменных==
**Элементарными преобразованиями системы л.у.** называются преобразования следующих трех типов:
1.
перестановка двух уравнений;
2.
умножение обеих частей уравнения на любое отличное от нуля число;
3.
прибавление к одному уравнению любого другого, умноженного на произвольное число: пара уравнений
$$
\begin{array}{lcl}
a_{j1}x_1 +a_{j2}x_2+ \ldots+a_{jn}x_n &=&b_j,\\
a_{k1}x_1 +a_{k2}x_2+ \ldots+a_{kn}x_n &=&b_k
\end{array}
$$
заменяется парой
$$
\begin{array}{rrrrcr}
(a_{j1}+ {\color{RubineRed} \lambda } a_{k1}) x_1 &+ (a_{j2}+ {\color{RubineRed} \lambda } a_{k2}) x_2 &+
\ldots &+ (a_{jn}+ {\color{RubineRed} \lambda } a_{kn}) x_n &=&b_j + {\color{RubineRed} \lambda } b_k\, , \\
a_{k1}x_1 &+a_{k2}x_2&+ \ldots &+a_{kn}x_n &=&b_k \, .
\end{array}
$$
!!Т!! **Теорема.** //Любое элементарное преобразование системы л.у. переводит эту систему в ей эквивалентную, т.е. имеющую то же множество решений, что и исходная.//
**Задача.** С помощью элементарных преобразований привести систему
л.у. к наиболее простому виду: такому, из которого легко было
бы установить множество решений.
Предположим, что первое уравнение системы содержит явно неизвестную $ x_{1} $, т.е. $ a_{11}^{} \ne 0 $. Исключим эту неизвестную из всех оставшихся уравнений. С этой целью вычтем из второго уравнения первое, домноженное на $ a_{21}/a_{11}^{} $. Получим
$$\left(a_{22}- \frac{a_{21}}{a_{11}} a_{12} \right)x_2 + \dots +
\left(a_{2n}- \frac{a_{21}}{a_{11}} a_{1n} \right)x_n =
b_2 - \frac{a_{21}}{a_{11}} b_1 \ , $$
Аналогичное преобразование --- вычитание из третьего уравнения системы первого,
умноженного на $ a_{31}/a_{11}^{} $, позволяет исключить $ x_{1} $ из этого
уравнения, т.е. заменить его на
$$\left(a_{32}- \frac{a_{31}}{a_{11}} a_{12} \right)x_2 + \dots +
\left(a_{3n}- \frac{a_{31}}{a_{11}} a_{1n} \right)x_n =
b_3 - \frac{a_{31}}{a_{11}} b_1 \ . $$
Продолжаем процесс далее. В конечном итоге исключаем $ x_{1} $ из всех уравнений
кроме первого:
$$
\left\{
\begin{array}{lllll}
a_{11}x_1 &+a_{12}x_2&+ \ldots&+a_{1n}x_n &=b_1,\\
&a_{22}^{[1]}x_2&+ \ldots&+a_{2n}^{[1]}x_n &=b_2^{[1]},\\
&\dots & & & \dots \\
&a_{m2}^{[1]}x_2&+ \ldots&+a_{mn}^{[1]}x_n &=b_m^{[1]}.
\end{array} \right. \
\ npu \ \
\begin{array}{lcr}
a_{jk}^{[1]} &= & \displaystyle a_{jk} - \frac{a_{j1}a_{1k}}{a_{11}} ,\\
b_j^{[1]} &= & \displaystyle b_j - \frac{a_{j1}b_1}{a_{11}} .
\end{array}
$$
Полученная система эквивалентна исходной системе, однако она
имеет более простой вид: в ней выделилась //подсиcтема//
$$
\left\{
\begin{array}{llll}
a_{22}^{[1]}x_2&+ \ldots&+a_{2n}^{[1]}x_n &=b_2^{[1]},\\
\dots & & & \dots \\
a_{m2}^{[1]}x_2&+ \ldots&+a_{mn}^{[1]}x_n &=b_m^{[1]},
\end{array} \right.
$$
которая не зависит от переменной $ x_{1} $. К этой новой подсистеме можно
применить те же рассуждения, что и к исходной системе,
поставив теперь целью исключение переменной $ x_{2} $.
Понятно, что процесс исключения может быть продолжен и далее. Теперь посмотрим,
где он может прерваться. Может так случиться, что очередная, $ \ell_{} $-я
подсистема имеет коэффициент $ a_{\ell \ell}^{[\ell-1]} $ равным нулю, что
не позволит алгоритму идти дальше --- т.е. исключить переменную $ x_{\ell}^{} $
из оставшихся уравнений (в принципе, такое могло случиться уже на первом
шаге, если бы коэффициент $ a_{11}^{} $ был бы равен нулю). Возможные варианты
дальнейших действий:
1.
если хотя бы один коэффициент при $ x_{\ell}^{} $ в одном из оставшихся уравнений отличен от нуля: $ a_{j \ell}^{[\ell-1]}\ne 0^{} $, то это уравнение переставляется с $ \ell_{} $-м;
2.
если при всех $ j\ge \ell^{} $ коэффициенты $ a_{j \ell}^{[\ell-1]} $ равны нулю, то переменная $ x_{\ell}^{} $ не входит ни в одно оставшееся уравнение, и можно перейти к исключению переменной $ x_{\ell+1}^{} $.
Поскольку число переменных конечно, то алгоритм исключения должен завершиться
за конечное число шагов. Чем он может завершиться? Окончательная система
должна иметь вид:
$$
\left\{
\begin{array}{llllllrl}
a_{11}x_1 +&a_{12}x_2&+ \ldots& +a_{1 {\mathfrak r}}x_{\mathfrak r}&
+a_{1 ,{\mathfrak r} +1}x_{{\mathfrak r}+1}&+ \ldots + & a_{1n}x_n &=b_1,\\
&a_{22}^{[1]}x_2&+ \ldots& +a_{2 {\mathfrak r}}^{[1]} x_{\mathfrak r}&
+a_{2 ,{\mathfrak r}+1}^{[1]} x_{{\mathfrak r}+1}&+ \ldots + & a_{2n}^{[1]} x_n &=b_2^{[1]},\\
& & \ddots & & & & & \dots \\
& & & a_{{\mathfrak r} {\mathfrak r}}^{[{\mathfrak r}-1]}x_{\mathfrak r} &
+ a_{{\mathfrak r} ,{\mathfrak r} +1}^{[{\mathfrak r}-1]}x_{{\mathfrak r}+1}& + \ldots + &
a_{{\mathfrak r} ,n}^{[{\mathfrak r}-1]}x_n &=b_{\mathfrak r}^{[{\mathfrak r}-1]}, \\
& & & & & & 0 &=b_{{\mathfrak r}+1}^{[{\mathfrak r}-1]}, \\
& & & & & & \dots & \\
& & & & & & 0 &=b_{m}^{[{\mathfrak r}-1]}, \\
\end{array} \right.
$$
при $ {\mathfrak r}\le n_{} $. Заметим, что все коэффициенты этой системы будут
принадлежать тому же множеству, что и коэффициенты исходной
системы.
Предположение
. Мы будем считать, что каждое из первых $ {\mathfrak r}_{} $ уравнений системы содержит в своей левой части хотя бы одну переменную с ненулевым коэффициентом.
Процесс получения системы такого вида из исходной системы уравнений называется **прямым ходом метода Гаусса**.
!!И!! **Исторический комментарий** о Гауссе
☞
((:biogr#гаусс ЗДЕСЬ)).
====Установление множества решений==
!!Т!! **Теорема.** //Если хотя бы одно из чисел//
$$ b_{{\mathfrak r}+1}^{[{\mathfrak r}-1]},\dots , b_{m}^{[{\mathfrak r}-1]} $$
//отлично от нуля, то исходная система линейных уравнений несовместна.//
Для простоты мы будем иллюстрировать наши рассуждения на системах л.у.
над $ \mathbb R_{} $, в этом же множестве искать решения.
Каждое из преобразований метода Гаусса будем обозначать $ \to_{} $.
!!П!! **Пример.** Решить систему л.у.
$$
\left\{
\begin{array}{rrrr}
x_1&+x_2&-3\, x_3 =& -1 \\
2\,x_1&+x_2&-2\, x_3 =& 1 \\
x_1&+x_2&+ x_3 =& 3 \\
x_1&+2\,x_2&-3\, x_3 =& 1.
\end{array}
\right.
$$
**Решение.**
$$
\ \to \
\left\{
\begin{array}{rrrr}
x_1&+x_2&-3\, x_3 =& -1 \\
&-x_2&+4\, x_3 =& 3 \\
&&4\, x_3 =& 4 \\
&x_2&=& 2
\end{array}
\right.
\ \to \
\left\{
\begin{array}{rrrr}
x_1&+x_2&-3\, x_3 =& -1 \\
&-x_2&+4\, x_3 =& 3 \\
&&4\, x_3 =& 4 \\
&&4\, x_3=& 5
\end{array}
\right.
\ \to \
$$
$$
\to \
\left\{
\begin{array}{rrrr}
x_1&+x_2&-3\, x_3 =& -1 \\
&-x_2&+4\, x_3 =& 3 \\
&&4\, x_3 =& 4 \\
&&0=& 1
\end{array}
\right.
$$
Последнее равенство абсолютно противоречиво.
**Ответ.** Система несовместна.
Пусть теперь $ b_{{\mathfrak r}+1}^{[{\mathfrak r}-1]}=0,{}\dots, b_{m}^{[{\mathfrak r}-1]}=0 $.
Возможны два случая: $ {\mathfrak r}=n_{} $ и $ {\mathfrak r}
предположения