4. Системы линейных уравнений.

4.1. Основные определения.

Системой линейных уравнений над полем k от неизвестных (или относительно неизвестных) x₁ , x₂ ,...,x_n называется набор выражений вида

$$a_{i1} x_1 +a_{i2} x_2 +...+a_{in} x_n = b_i\ (i = 1,2,...,m),$$ (1)

где $a_{ij} , b_i\in k$. Каждое из этих выражением называется линейным уравнением, a_ij -- коэффициентами при неизвестных, b_i -- свободными коэффициентами уравнений. Решением системы (1) называется строка $x^0 = (x_1^0 ,x_2^0 ,...,x_n^0 )\ \in k$ , для которой

$$a_{i1} x_1^0 +a_{i2} x_2^0 +...+a_{in} x_n^0 = b_i\ (i = 1,2,...,m).$$

Система совместна, если у нее есть хотя бы одно решение. Две системы равносильны (или эквивалентны), если у них одно и то же множество решений: любое решение первой системы является решением второй и любое решение второй является решением первой.

4.2. Векторная и матричная формы записи системы.

4.2.1. Для системы (1) положим

$a_j= \left[ \begin{array}{l} a_{1j}\\ a_{2j}\\ \vdots\\ a_{mj} \end{array}... ...eft[ \begin{array}{l} b_{1}\\ b_{2}\\ \vdots\\ b_{m} \end{array} \right].$

Тогда выражение

a₁ x₁ +a₂ x₂ +...+a_n x_n = b (2)

называется векторной формой записи системы (1). Отметим, что $x^0\ =\ (x_1^0 ,x_2^0 ,...,x_n^0 )$ тогда и только тогда является решением системы (1), когда b -- линейная комбинация столбцов a₁ ,a₂ ,...,a_n с коэффициентами x₁⁰ ,x₂⁰ ,...,x_n⁰.

4.2.2. Для системы (1) положим $A = (a_{ij} )_{m\times n}$ и назовем A матрицей системы (1). Отметим, что столбцами матрицы A служат столбцы a_j из векторной формы (2). Если в качестве (n+1)-го столбца к матрице A добавить столбец b из (2), то получим расширенную матрицу B= (A|b) системы (1). Матричной формой системы (1) назовем выражение

$$Ax^{\prime} = b,$$ (3)

где x = (x₁ ,x₂ ,...,x_n ), а $x^{\prime}$ -- транспонированная строка x -- столбец высоты n, составленный из неизвестных. Отметим, что $x^0\in k$ тогда и только тогда является решением системы (1), когда $A\cdot (x^0 )^{\prime} = b$ или, что то же самое, $x^0\cdot A^{\prime} = b^{\prime}$ (здесь $^\prime$ означает транспонирование, умножение $\cdot$ -- умножение матриц), то есть когда произведение матрицы A (размера $m\times n$) на матрицу $(x^0 )^{\prime}$ (размера $n\times 1$) равно матрице b (размера $m\times 1$).

4.3. Квадратные системы с невырожденной матрицей.

4.3.1. Система (1) называется квадратной, если число m ее уравнений равно числу n неизвестных, то есть когда ее матрица A -- квадратная матрица.

4.3.2. Теорема. Квадратная система (1) с невырожденной матрицей A совместна и имеет единственное решение $x^0\ =\ (x_1^0 ,x_2^0 ,...,x_n^0 )$, где $x_i^0\ =\ d_i /d,\ d$ -- определитель матрицы $A,\ d_i$ -- определитель матрицы, полученной из A заменой ее i-го столбца на столбец b свободных коэффициентов.

Доказательство. Рассмотрим строку $x^0\ =\ (A^{-1}b)^{\prime}$. Покажем, что она -- решение (1). Действительно, $(x^0 )^{\prime}\ =\ A^{-1}b$ и $A(x^0 )^{\prime}\ =\ AA^{-1}b\ =\ Eb\ =\ b$. Если теперь y -- решение (1), то $Ay^{\prime} = b$, откуда $y^{\prime}\ =\ A^{-1}b\ =\ (x^0)^{\prime}$, то есть $y\ =\ x^0$ -- единственное решение системы (1). Осталось заметить, что $x_i^0\ =\ d_i /d$. Для этого нужно вспомнить, как вычисляются элементы матрицы A^-1 и разложить определитель d_i по i-му столбцу.

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

4.4.1. Лемма. 1. Если к системе (1) добавить уравнение, которое является линейной комбинацией уравнений системы (1), то есть уравнение вида

c₁ x₁ +c₂ x₂ +...+c_n x_n = d,

где

c_j = l₁ a_1j +l₂ a_2j +...+l_m a_mj, d = l₁ b₁ +l₂ b₂ +...+l_m b_m,

$l_1 ,l_2 ,...,l_m\in k$ -- коэффициенты этой линейной комбинации, то получится система, равносильная (1). 2. Если к одному уравнению системы прибавить линейную комбинацию других уравнений системы, а остальные уравнения оставить без изменения, то получится система, эквивалентная исходной. 3. Если уравнения системы умножить на скаляры, отличные от 0, то получится система, эквивалентная исходной. 4. Если в системе переставить уравнения, то получится система, равносильная исходной.

Доказательство -- непосредственная проверка по определению равносильности систем.

Прежде, чем читать следующий текст, полезно вспомнить, метод Гаусса для матриц наборов векторов (пункт 2.4.5). Скажем, что уравнение

$$a_{i1} x_1 +a_{i2} x_2 +...+a_{in} x_n\ =\ b_i$$

системы (1) начинается с x_s, если для всех t<s коэффициент a_it равен 0, а $a_{is}\neq 0$. Преобразованием системы относительно x_s называется следующая процедура: 1. Если ни одно уравнение системы не начинается с x_s , то на этом процедура заканчивается. 2. Если существует уравнение, которое начинается с x_s , то выберем первое уравнение с этим условием, скажем,

a_i1 x₁ +a_i2 x₂ +...+a_in x_n = b_i,

умножим его на 1/a_is (в результате система заменится на эквивалентную, коэффициент при x_s в i-ом уравнении станет равным 1 и по-прежнему это уравнение будет начинаться с x_s ), а затем каждое из остальных уравнений

a_r1 x₁ +a_r2 x₂ +...+a_rn x_n = b_r

(здесь $r\neq i$) преобразуем следующим образом: вычтем из него преобразованное i-е уравнение, умноженное на a_rs (в результате система заменится на эквивалентную, а во всех уравнениях, кроме i-го, коэффициент при x_s станет равен 0). В любом случае в преобразованной системе будет не более одного уравнения, которое начинается с x_s .

4.4.2. Алгоритм Гаусса:

Преобразуем систему (1) относительно x₁ , затем преобразованную систему преобразуем относительно x₂ , полученную систему -- относительно x₃ и.т.д., пока не переберем все неизвестные. В результате система заменится на эквивалентную и для каждой неизвестной в системе будет не более одного уравнения, с которой оно начинается. Пусть x_i1 ,x_i2 ,...,x_ir -- неизвестные, с которых начинаются уравнения преобразованной системы, а x_j1 ,x_j2 ,...,x_jn-r -- неизвестные, с которых не начинается ни одно уравнение преобразованной системы (эти неизвестные назовем свободными). После перестановки уравнений система приобретет вид:

$$\left.\begin{array}{r} 0=c_{i_{r+1}}\\ ......\\ 0=c_{i_m} \end{... ...й нет }\\ \mbox{неизвестных, с которых}\\ \mbox{они начинаются.}\end{tabular}$$

Здесь f_t (x_j1 ,x_j2 ,...,x_jn-r) -- некоторая линейная комбинация свободных неизвестных с коэффициентами из $k,\ c_{i_t}\in k$. Если среди элементов $c_{i_t},\ t = r+1,...,m$ найдется хотя бы один, отличный от 0, то, очевидно, система (4), а вместе с ней и система (1) несовместны. Если же все эти элементы равны 0, то соответствующие уравнения можно отбросить. Теперь при любых $\alpha _1,\alpha _2,...,\alpha _{n-r}\in k$ строка x⁰ = (x₁⁰ ,x₂⁰ ,...,x_n⁰ ), где

$$\begin{array}{l} x_{j_s}^0 = \alpha_s\ \mbox{для } s = 1,..... ... ,...,\alpha_{n-r})\\ \mbox{ для }u = 1,...,r, \end{array}$$ (5)

является решением системы (4) (а значит, и решением системы (1)). Наоборот, любое решение x⁰ = (x₁⁰ ,x₂⁰ ,...,x_n⁰ ) системы (1) может быть получено по формулам (5) для подходящих $\alpha _1,\alpha _2,...,\alpha _{n-r}\in k$.

4.5. Критерий совместности системы.

Теорема. Система (1) совместна тогда и только тогда, когда ранг ее матрицы A равен рангу расширенной матрицы B= (A|b).

Доказательство. Как отмечалось в пункте 4.2.1, система совместна тогда и только тогда, когда столбец b свободных коэффициентов линейно выражается через столбцы матрицы A, то есть, когда набор столбцов матрицы A эквивалентен набору столбцов матрицы B, то есть когда ранг набора столбцов матрицы B равен рангу столбцов матрицы A, то есть, по теореме о ранге, когда r(A) = r(B). Теорема доказана.

4.6. Общее решение.

Строка

(y₁ (t₁ ,...t_p ),..., y_n (t₁ ,t₂ ,...t_p )),

составленная из n функций y_i от переменных t₁ ,...t_p, называется общим решением системы (1), если при любых $\alpha _1 ,...\alpha _p\in k$ строка

$$(y_1 (\alpha _1 ,...,\alpha _p ),..., y_n (\alpha _1 ,...\alpha _p )),$$

составленная из значений функций y_i в точке $(\alpha _1 ,...,\alpha _p )$ является решением системы (1) и, наоборот, для любого решения x⁰ = (x₁⁰ ,...,x_n⁰ ) системы (1) найдутся $\alpha _1 ,...,\alpha _p \in k$, для которых при всех i = 1,2,...,n имеет место равенство

$$x_i^0 = y_i (\alpha _1 ,...,\alpha _p).$$

Таким образом, общее решение является формулой, описывающей все множество решений системы.

4.6.1. Теорема. Совместная система (1) от n неизвестных, ранг матрицы которой равен r, обладает общим решением, зависящим от n-r переменных.

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

x_i1 + f₁ (x_j1 ,x_j2 ,...,x_jn-r) = c_i1

............................. (6)

x_ir + f_r ( (x_j1 ,x_j2 ,...,x_jn-r) = c_ir.

Участвующее в этой записи число r является рангом матрицы системы (6), поскольку минор порядка r матрицы этой системы, расположенный в столбцах с номерами i₁ ,...,i_r -- единичная матрица, определитель которой равен $1\neq 0$, а миноров большего порядка нет. Теперь очевидно, что строка

(y₁ (t₁ ,t₂ ,...t_n-r ),y₂(t₁ ,t₂ ,...t_n-r),..., y_n (t₁ ,t₂ ,...t_n-r )),

где

$$\begin{array}{l} y_{j_s} (t_1 ,...,t_{n-r}) = t_s \mbox{ дл... ... ...\alpha _{n-r}) \\ \mbox{ для }u = 1,...,r \end{array}$$ (7)

(ср. с формулами (5) из пункта 4.4 ), является общим решением системы (1). Теорема доказана.

4.7. Однородная система. Система (1) называется однородной, если столбец b ее свободных коэффициентов нулевой, то есть свободный коэффициент каждого из уравнений системы равен 0. Однородная система всегда совместна, поскольку строка подходящей длины, составленная из нулей, является ее решением (это решение называется тривиальным решением).

4.7.1. Теорема. а) Множество решений однородной системы от n неизвестных с матрицей ранга r над полем k является подпространством размерности n-r в пространстве kⁿ(это подпространство называется пространством решений системы, а база пространства решений называется фундаментальным набором решений системы). б) Если x¹ ,x² ,...,x^n-r -- фундаментальный набор решений однородной системы с матрицей A, то строка

Y = t₁ x¹ +...+t_n-r x^n-r

является общим решением этой системы. в) Если (1) -- произвольная (неоднородная) система с той же матрицей A и x -- одно из ее решений, то строка Y+x -- общее решение системы (1).

Доказательство. а) Непосредственно проверяются свойства подпространства. Далее, можно считать, что система имеет гауссов вид

x_i1 + f₁ (x_j1 ,x_j2 ,...,x_jr) = 0

............................. (8)

x_ir + f_r ( (x_j1 ,x_j2 ,...,x_jr) = 0

и ее общее решение -- это строка

(y₁ (t₁ ,...t_n-r ),y₂(t₁ ,...t_n-r),..., y_n (t₁ ,...t_n-r )),

где

$$\begin{array}{l} y_{j_s} (t_1 ,...,t_{n-r}) = t_s\mbox{ для... ....., \alpha _{n-r})\\ \mbox{ для }u = 1,...,r. \end{array}$$ (9)

Зафиксировав s, придадим t_s значение 1, а остальным t_v -- значение 0. В результате получим некоторое решение x^s системы (8). Составим матрицу X размера $(n-r)\times n$, строками которой служат решения $x_s,\ s = 1,2,...,n-r$. Эта матрица имеет вид

$$X = \left[ \begin{array}{lllllllll} \ast & 1&\ast&0&\ast&0&... ...ots\\ \ast & 0&\ast&0&\ast&0&...&1&\ast\end{array} \right] ,$$

где символ $\ast$ записан в столбцах с номерами i₁ ,i₂ ,...,i_r , элементы которых нас в данный момент не интересуют (любой желающий их может выписать, использовав формулы (9)). Очевидно, что минорный ранг этой матрицы равен r, откуда по теореме о ранге следует, что набор решений ${\cal X}\ =\ \{ x^1 ,x^2 ,...,x^{n-r}\}$ линейно независим. Покажем, что ${\cal X}$ является фундаментальным набором, то есть покажем, что любое решение z системы (8) является линейной комбинацией набора ${\cal X}$. Пусть

$$z = (\ast \alpha \ast \alpha \ast \alpha ...\alpha \ast ),$$

где символ $\ast$ стоит на тех же местах, что и в матрице X (напомним, что ее строки составляют набор ${\cal X}$). Тогда линейная комбинация

$$v = \alpha _1 x^1 +\alpha _2 x^2 +...+\alpha _{n-r}x^{n-r} -z$$

решений системы (8), во-первых, имеет вид $(\ast 0\ast 0\ast 0...0\ast )$, то есть компоненты строки v с номерами j₁ ,j₂ ,...,j_n-r равны 0, а во-вторых, v -- решение системы (8). Если компоненты этого решения мы подставим вместо неизвестных в (8), то, вспомнив о том, что f_t (x_j1 ,x_j2 ,...,x_jn-r) -- линейная комбинация неизвестных x_j1 ,x_j2 ,...,x_jn-r и, следовательно f_t(0,...,0)=0, мы обнаружим, что и остальные компоненты строки v равны 0. Это означает, что v -- нулевая строка, т.е. $z = \alpha _1 x^1 +\alpha _2 x^2 +...+ \alpha _{n-r} x^{n-r}$ -- линейная комбинация набора ${\cal X}$. Пункт а) теоремы доказан. Пункт б) сразу следует из определений общего решения и фундаментального набора. Для доказательства в) достаточно заметить, что разность двух решений одной и той же системы является решением однородной системы с той же матрицей, а затем воспользоваться пунктом б). Теорема доказана.

4.8. Системы линейных уравнений с точки зрения линейных отображений. Пусть дана система линейных уравнений

$$Ax^{\prime} = b\mbox{ (или, в транспонированной форме, }xA^{\prime} = b^{\prime}),$$

где A -- $(m\times n)$-матрица над k. Рассмотрим линейное отображение $\varphi :\ v\rightarrow vA^{\prime}$ пространства V=kⁿ в пространство U=k^m . Как мы уже знаем, матрица отображения $\varphi$ относительно стандартных баз V и U равна $A^{\prime}$:

$$[\varphi]= A^{\prime}.$$

Множество решений однородной системы $xA^{\prime}=0$ -- это ядро $K=Ker\varphi$ отображения $\varphi$. Мы знаем, что K -- подпространство в V, размерность которого равна $n-r(A^{\prime}) = n-r(A)$. Это дает другое доказательство пунктов а) и б) теоремы 4.7.1. Если x -- решение системы (3), то $x\varphi =b^{\prime}$ , а вся совокупность решений системы (3) совпадает со смежным классом x +K. Отсюда вытекает пункт в) теоремы 4.7.1 и теорема 4.6.1 об общем решении произвольной системы.

4.8.1. Упражнение. Пусть дана система (3). Построим матрицу

$$\left[ \begin{array}{ll} A&b\\ ...&...\\ E&o \end{array} \right]$$

размера $(m+n)\times (n+1)$, где E -- единичная $(n\times n)$-матрица, o -- нулевой столбец. Элементарными преобразованиями столбцов, в которых последний столбец играет пассивную роль, приведем ее к виду

$$\left[ \begin{array}{lll} X&O&o\\ ...&...&...\\ Y&F&z \end{array} \right] ,$$

где горизонтальная пунктирная линия проходит в том же месте, столбцы матрицы X линейно независимы, O -- нулевая матрица, o -- нулевой столбец, возникающий на месте b (если столбец b не зануляется, то система (3) несовместна). Тогда столбец -z (вернее, строка $-z^{\prime}$ ) -- одно из решений системы (3), а столбцы матрицы F (вернее, строки матрицы $F^{\prime}$ ) составляют фундаментальный набор решений однородной системы $Ax^{\prime} = O$. Доказать.

4.8.2. Упражнение (теоремы Фредгольма). Пусть дана система линейных уравнений

$$Ax^{\prime} = b,$$ (10)

Рассмотрим соответствующую однородную систему

$$Ax^{\prime} =O,$$ (11)

и транспонированную однородная систему

$$A^{\prime} y^{\prime} =O.$$ (12)

Доказать следующие утверждения: 1. Система (10) совместна тогда и только тогда, когда для любого решения y системы (12) имеет место равенство y b=0 (любое решение транспонированной однородной системы ортогонально столбцу свободных коэффициентов). 2. Если (10) совместна, то она в том и только в том случае имеет единственное решение, когда (11) имеет только тривиальное решение. 3. Если A -- квадратная матрица, то (11) и (12) имеют одинаковое число линейно независимых решений.