‹-- Назад


Алгоритм нахождения решений произвольной системы линейных уравнений (метод Гаусса)

Пусть дана система $ m$ линейных уравнений с $ n$ неизвестными $ {Ax=b}$ . Требуется найти ее общее решение, если она совместна, или установить ее несовместность. Метод, который будет изложен в этом разделе, близок к методу вычисления определителя 5.1.с и к методу нахождения ранга матрицы (раздел 5.8). Предлагаемый алгоритм называется методом Гаусса или методом последовательного исключения неизвестных.

Выпишем расширенную матрицу системы

$\displaystyle A^*=\left(\begin{array}{ccccc}a_{11}&a_{12}&\dots&a_{1n}&b_1\\
...
...{2n}&b_2\\
\hdotsfor{5}\\
a_{m1}&a_{m2}&\dots&a_{mn}&b_m\end{array}\right).$

Назовем элементарными операциями следующие действия с матрицами:

  1. перестановка строк;
  2. умножение строки на число, отличное от нуля;
  3. сложение строки с другой строкой, умноженной на число.

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

Читатель легко проверит, что если по матрице, полученной из $ A^*$ выполнением элементарной операции, восстановить систему уравнений, то новая система будет равносильна исходной.

Цель алгоритма -- с помощью применения последовательности элементарных операций к матрице $ A^*$ добиться, чтобы каждая строка, кроме, быть может, первой, начиналась с нулей, и число нулей до первого ненулевого элемента в каждой следующей строке было больше, чем в предыдущей.

Шаг алгоритма заключается в следующем. Находим первый ненулевой столбец в матрице $ A^*$ . Пусть это будет столбец с номером $ i$ . Находим в нем ненулевой элемент и строку с этим элементом меняем местами с первой строкой. Чтобы не нагромождать дополнительных обозначений, будем считать, что такая смена строк в матрице $ A^*$ уже произведена, то есть $ {a_{1i}\ne0}$ . Тогда ко второй строке прибавим первую, умноженную на число $ \left(-\dfrac{a_{2i}}{a_{1i}}\right)$ , к третьей строке прибавим первую, умноженную на число $ \left(-\dfrac{a_{3i}}{a_{1i}}\right)$ , и т.д. В результате получим матрицу

$\displaystyle A^*_1=\left(\begin{array}{cccccccc}0&\dots&0&a_{1i}&a_{1i+1}&\dot...
...\\
0&\dots&0&0&a_{mi+1}^{(1)}&\dots&a_{mn}^{(1)}&b_m^{(1)}\end{array}\right).$

(Первые нулевые столбцы, как правило, отсутствуют.)

Если в матрице $ A^*_1$ встретилась строка с номером $ k$ , в которой все элементы $ a_{kj}^{(1)}$ равны нулю, а $ {b_k^{(1)}\ne0}$ , то выполнение алгоритма останавливаем и делаем вывод, что система несовместна. Действительно, восстанавливая систему уравнений по расширенной матрице, получим, что $ k$ -ое уравнение будет иметь вид

$\displaystyle 0\cdot x_1+0\cdot x_2+\ldots0\cdot x_n=b_k^{(1)}.$

Этому уравнению не удовлетворяет ни один набор чисел $ {x_1,x_2,\dots,x_k}$ .

Матрицу $ A^*_1$ можно записать в виде

$\displaystyle A^*_1=\left(\begin{array}{ccc}{\begin{array}{ccc}0&\dots&0\end{ar...
...begin{array}{c}0\\ \vdots\\ 0\end{array}}&\mbox{\Huge\it B*}\end{array}\right),$

где

$\displaystyle B^*=\left(\begin{array}{ccccc}
a_{2i+1}^{(1)}&a_{2i+2}^{(1)}&\do...
...
a_{mi+1}^{(1)}&a_{mi+2}^{(1)}&\dots&a_{mn}^{(1)}&b_m^{(1)}\end{array}\right).$

По отношению к матрице $ B^*$ выполняем описанный шаг алгоритма. Получаем матрицу

$\displaystyle B_1^*=\left(\begin{array}{cccccccc}
0&\dots&0&a_{2j}^{(2)}&a_{2j...
...\\
0&\dots&0&0&a_{mj+1}^{(2)}&\dots&a_{mn}^{(2)}&b_m^{(2)}\end{array}\right),$

где $ j>i$ , $ a_{2j}^{(2)}\ne0$ . Эту матрицу снова можно записать в виде

$\displaystyle B^*_1=\left(\begin{array}{ccc}{\begin{array}{ccc}0&\dots&0\end{ar...
...begin{array}{c}0\\ \vdots\\ 0\end{array}}&\mbox{\Huge\it C*}\end{array}\right),$

и к матрице $ C^*$ снова применим описанный выше шаг алгоритма.

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

Если бы мы не уменьшали матрицу, то в итоге пришли бы к матрице вида

$\displaystyle \tilde A^*=\left(\begin{array}{ccccccccccccc}
0&\dots&0&a_{1i}^{...
...
\hdotsfor{13}\\
0&\dots&0&0&\dots&0&0&\dots&0&0&\dots&0&0\end{array}\right).$

Далее выполняется так называемый обратный ход метода Гаусса. По матрице $ \tilde A^*$ составляем систему уравнений. В левой части оставляем неизвестные с номерами, соответствующими первым ненулевым элементам в каждой строке, то есть $ {x_i,\,x_j,\,\dots,x_r}$ . Заметим, что $ {r={\rm Rg}A}$ . Остальные неизвестные переносим в правую часть. Считая неизвестные в правой части некоторыми фиксированными величинами, несложно выразить через них неизвестные левой части.

Теперь, придавая неизвестным в правой части произвольные значения и вычисляя значения переменных левой части, мы будем находить различные решения исходной системы $ {Ax=b}$ . Чтобы записать общее решение, нужно неизвестные в правой части обозначить в каком-либо порядке буквами $ {C_1,\,C_2,\dots,C_{n-r}}$ , включая и те неизвестные, которые явно не выписаны в правой части из-за нулевых коэффициентов, и тогда столбец неизвестных можно записать в виде столбца, где каждый элемент будет линейной комбинацией произвольных величин $ {C_1,\,C_2,\dots,C_{n-r}}$ (в частности, просто произвольной величиной $ C_k$ ). Эта запись и будет общим решением системы.

Если система была однородной, то получим общее решение однородной системы. Коэффициенты при $ C_1$ , взятые в каждом элементе столбца общего решения, составят первое решение из фундаментальной системы решений, коэффициенты при $ C_2$  -- второе решение и т.д.

Фундаментальную систему решений однородной системы можно получить и другим способом. Для этого одному переменному, перенесенному в правую часть, нужно присвоить значение 1, а остальным -- нули. Вычислив значения переменных в левой части, получим одно решение из фундаментальной системы. Присвоив другому переменному в правой части значение 1, а остальным -- нули, получим второе решение из фундаментальной системы и т.д.

        Замечание 15.4   У читателя может возникнуть вопрос: "Зачем рассматривать случай, когда некоторые столбцы матрицы $ A^*$ нулевые? Ведь в этом случае соответствующие им переменные в системе уравнений в явном виде отсутствуют." Но дело том, что в некоторых задачах, например, при нахождении собственных чисел матрицы, такие системы возникают, и игнорировать отсутствующие переменные нельзя, так как при этом происходит потеря важных для задачи решений.         

        Пример 15.2   Найдите общее решение системы уравнений

$\displaystyle \left\{\begin{array}{l}2x_2+x_3-2x_4+4x_5+x_6=2,\\ 8x_2+4x_3-8x_4+13x_5+2x_6=14,\\
6x_2+3x_3-6x_4+6x_5-x_6=18,\end{array}\right.$

где неизвестными являются $ x_1,\ldots,x_6$ .

Решение. Выпишем расширенную матрицу системы

$\displaystyle A^*=\left(\begin{array}{rrrrrrr}0&2&1&-2&4&1&2\\ 0&8&4&-8&13&2&14\\ 0&6&3&-6&6&-1&18\end{array}\right).$

Прибавим ко второй строке первую, умноженную на число $ {\left(-\dfrac82\right)=-4}$ , к третьей строке прибавим первую, умноженную на $ {\left(-\dfrac62\right)=-3}$ . В результате получим

$\displaystyle A^*_1=\left(\begin{array}{rrrrrrr}0&2&1&-2&4&1&2\\ 0&0&0&0&-3&-2&6\\ 0&0&0&0&-6&-4&12\end{array}\right).$

Прибавим к третьей строке вторую, умноженную на число $ {\left(-\dfrac{-6}{-3}\right)=-2}$ . Получим

$\displaystyle A^*_1=\left(\begin{array}{rrrrrrr}0&2&1&-2&4&1&2\\ 0&0&0&0&-3&-2&6\\ 0&0&0&0&0&0&0\end{array}\right).$

Прямой ход метода Гаусса закончен. Выписываем по матрице $ A^*_2$ систему уравнений

$\displaystyle \left\{\begin{array}{r@{\;=\;}l} 2x_2+x_3-2x_4+4x_5+x_6&2,\\
-3x_5-2x_6&6.\end{array}\right.$

Переносим в правую часть неизвестные $ {x_1,\,x_3,\,x_4,\,x_6}$ (неизвестное $ x_1$ реально в ней присутствовать не будет, коэффициент перед ним равен нулю). Получаем

$\displaystyle \left\{\begin{array}{r@{\;=\;}l} 2x_2+4x_5&2-x_3+2x_4-x_6,\\ -3x_5&6+2x_6.\end{array}
\right.$

Пусть $ {x_1=C_1}$ , $ {x_3=C_2}$ , $ {x_4=C_3}$ , $ {x_6=C_4}$ . Из уравнений находим:

$\displaystyle x_5=-2-\frac23C_4,$

$\displaystyle x_2=-2x_5+1-\frac12 C_2+C_3-\frac12C_4=4+\frac43C_4+1-\frac12C_2+C_3-\frac12
C_4=5-\frac12C_2+C_3+
\frac56C_4.$

Ответ: $ {x_1=C_1}$ , $ {x_2=5-\dfrac12C_2+C_3+\dfrac56C_4}$ , $ {x_3=C_2}$ , $ {x_4=C_3}$ , $ {x_5=-2-\dfrac23C_4}$ , $ {x_6=C_4}$ , где $ C_1$ , $ C_2$ , $ C_3$ , $ C_4$  -- произвольные числа.         

        Замечание 15.5   В процессе решения можно также установить, какие ранги у матриц $ A$ и $ A^*$ и где расположены их базисные миноры. В предыдущем примере $ {{\rm Rg}A={\rm Rg}A^*=2}$ , базисный минор расположен в строках с номерами 1, 2, столбцах с номерами 2, 5.         

        Пример 15.3   Найдите общее решение системы уравнений

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

Решение. Запишем расширенную матрицу системы:

$\displaystyle A^*=\left(\begin{array}{rrrrr}
1&1&2&-1&3\\ 2&-1&3&4&-1\\ 4&1&7&2&6\\ 5&-1&3&2&-3\end{array}\right).$

Ко второй строке прибавим первую, умноженную на $ (-2)$ , к третьей строке прибавим первую, умноженную на $ (-4)$ , к четвертой строке прибавим первую, умноженную на $ (-5)$ :

$\displaystyle A^*_1=\left(\begin{array}{rrrrr}
1&1&2&-1&3\\ 0&-3&-1&6&-7\\ 0&-3&-1&6&-6\\ 0&-6&-7&7&-18\end{array}\right).$

Вторую строку, умноженную на $ (-1)$ , прибавим к третьей:

$\displaystyle A^*_2=\left(\begin{array}{rrrrr}
1&1&2&-1&3\\ 0&-3&-1&6&-7\\ 0&0&0&0&1\\ 0&-6&-7&7&-18\end{array}\right).$

В третьей строке все элементы $ a_{3j}^{(2)}$ равны нулю, а элемент $ {b_3^{(2)}\ne0}$ . Значит, система несовместна.

Ответ: Система несовместна.         

        Пример 15.4   Решите систему

$\displaystyle \left\{\begin{array}{l}2x_1-x_2+3x_3-x_4=1,\\
3x_1+2x_2-x_3+x_4=2,\\ 2x_1+x_2+2x_3-3x_4=1,\\ 4x_1-2x_2-x_3-3x_4=2.\end{array}\right.$

Решение. Имеем:

$\displaystyle A^*=\left(\begin{array}{rrrrr} 2&-1&3&-1&1\\
3&2&-1&1&2\\ 2&1&2&-3&1\\ 4&-2&-1&-3&2\end{array}\right).$

Первую строку, умноженную на числа $ \left(-\frac32\right)$ , $ (-1)$ , $ (-2)$ , прибавим соответственно ко второй, третьей и четвертой строкам:

$\displaystyle A^*_1=\left(\begin{array}{rrrrr} 2&-1&3&-1&1\\ 0&\vphantom{\dfrac...
...&-\frac{11}2&
\frac52&\frac12\\
0&2&-1&-2&0\\ 0&0&-7&-1&0\end{array}\right).$

К третьей строке прибавим вторую, умноженную на $ \left(-\frac47\right)$ . Получим

$\displaystyle A^*_2=\left(\begin{array}{rrrrr} 2&-1&3&-1&1\\ 0&\vphantom{\dfrac...
...tom{\dfrac11}\frac{15}7&-\frac{24}7&-\frac27\\
0&0&-7&-1&0\end{array}\right).$

К четвертой строке прибавим третью, умноженную на $ \frac{49}{15}$ :

$\displaystyle A^*_3=\left(\begin{array}{rrrrr} 2&-1&3&-1&1\\ 0&\vphantom{\dfrac...
...ac27\\
0&0&0&\vphantom{\dfrac11}-\frac{61}5&-\frac{14}{15}\end{array}\right).$

Выписываем по матрице $ A^*_3$ систему уравнений:

$\displaystyle \left\{\begin{array}{r@{\,\,=\,}r}2x_1-x_2+3x_3-x_4&1,\\
\vphan...
...frac27,\\
\vphantom{\dfrac11}-\frac{61}5x_4&-\frac{14}{15}.\end{array}\right.$

Находим последовательно значения неизвестных:

$\displaystyle x_4=\frac{14}{183},\quad x_3=\left(-\frac27+\frac{24}7x_4\right):...
...
=\left(-\frac27+\frac{24}7\cdot\frac{14}{183}\right):\frac{15}7=-\frac2{183},$

$\displaystyle x_2=\left(\frac12+\frac{11}2x_3-\frac52x_4\right):\frac72=
\left...
...1}2\cdot\frac2{183}-\frac52\cdot\frac{14}{183}
\right):\frac72=\frac{13}{183},$

$\displaystyle x_1=(1+x_2-3x_3+x_4):2=\left(1+\frac{13}{183}+\frac6{183}+\frac{14}{183}
\right):2=\frac{108}{183}.$

Ответ: $ x_1=\frac{108}{183},\quad x_2=\frac{13}{183},\quad
x_3=-\frac2{183},\quad x_4=\frac{14}{183}$ .         

        Замечание 15.6   Так же, как и при решении системы уравнений по правилу Крамера, при использовании метода Гаусса приходится выполнять большой объем вычислительной работы. Из-за этого вполне возможно, что будет допущена какая-либо ошибка в вычислениях. Поэтому желательно после решения системы выполнить проверку, то есть подставить полученные значения неизвестных в уравнения системы. Для выполнения полной проверки подстановку нужно произвести во все уравнения системы. Если же по каким-то причинам это не выполнимо, то можно подставить найденные значения в одно уравнение. В отличие от правила Крамера в методе Гаусса эту подстановку нужно производить в ПОСЛЕДНЕЕ уравнение исходной системы. При наличии в этом уравнении всех неизвестных эта подстановка почти всегда покажет наличие ошибки, если таковая была допущена.         

        Пример 15.5   Найдите фундаментальную систему решений и общее решение однородной системы линейных уравнений:

$\displaystyle \left\{\begin{array}{l}x_1+x_2-x_3+2x_4-x_5=0,\\ 2x_1-x_2-x_3-x_4...
...
-5x_1+7x_2+x_3+10x_4-11x_5=0,\\ -x_1+5x_2-x_3+8x_4-7x_5=0.\end{array}\right.$

Решение. Составляем расширенную матрицу системы:

$\displaystyle A^*=\left(\begin{array}{rrrrrr}
1&1&-1&2&-1&0\\
2&-1&-1&-1&2&0\\ -5&7&1&10&-11&0\\ -1&5&-1&8&-7&0\end{array}\right).$

Умножим первую строку последовательно на $ (-2)$ , 5 и 1 и прибавим соответственно ко второй, третьей и четвертой строкам. Получим матрицу

$\displaystyle A^*_1=\left(\begin{array}{rrrrrr}
1&1&-1&2&-1&0\\ 0&-3&1&-5&4&0\\
0&12&-4&20&-16&0\\ 0&6&-2&10&-8&0\end{array}\right).$

Вторую строку умножим последовательно на числа 4 и 2 и прибавим соответственно к третьей и четвертой строкам. Получим матрицу

$\displaystyle A^*_2=\left(\begin{array}{rrrrrr}
1&1&-1&2&-1&0\\ 0&-3&1&-5&4&0\\ 0&0&0&0&0&0\\ 0&0&0&0&0&0\end{array}\right).$

Прямой ход метода Гаусса закончен. У полученной матрицы легко определить ранг, ее базисный минор $ \left\vert\begin{array}{rr}1&1\\
0&-3\end{array}\right\vert$ . Отсюда следует, что $ {{\rm Rg}A={\rm Rg}A^*_2=2}$ . По  теореме 15.3 число решений в фундаментальной системе равно разности между числом неизвестных и рангом матрицы, в нашем случае фундаментальная система состоит из трех решений.

Переходим к системе уравнений

$\displaystyle \left\{\begin{array}{r@{\;=\;}l}x_1+x_2-x_3+2x_4-x_5&0,\\
-3x_2+x_3-5x_4+4x_5&0.\end{array}\right.$

Неизвестные $ x_1$ и $ x_2$ оставляем в левой части, остальные переносим в правую часть:

$\displaystyle \left\{\begin{array}{r@{\;=\;}l}x_1+x_2&x_3-2x_4+x_5,\\
-3x_2&-x_3+5x_4-4x_5.\end{array}\right.$

Положим $ {x_3=1}$ , $ {x_4=x_5=0}$ . Получим $ {x_2=\frac13}$ , $ {x_1=\frac23}$ . Первое решение из фундаментальной системы: $ {x^{(1)}=\left(\begin{array}{r}\vphantom{\dfrac11}\frac23\\ \vphantom{\dfrac11}\frac13\\
1\\ 0\\ 0\end{array}\right)}$ .

Положим $ {x_3=x_5=0}$ , $ {x_4=1}$ . Получим $ {x_2=-\frac53}$ , $ {x_1=-\frac13}$ . Второе решение из фундаментальной системы решений: $ {x^{(2)}=\left(\begin{array}{r}\vphantom{\dfrac11}-\frac13\\ \vphantom{\dfrac11}-\frac53\\
0\\ 1\\ 0\end{array}\right)}$ .

Положим $ {x_3=x_4=0}$ , $ {x_5=1}$ . Получим $ {x_2=\frac43}$ , $ {x_1=-\frac13}$ . Третье решение из фундаментальной системы решений: $ {x^{(3)}=\left(\begin{array}{r}\vphantom{\dfrac11}-\frac13\\ \vphantom{\dfrac11}\frac43\\
0\\ 0\\ 1\end{array}\right)}$ . Фундаментальная система решений найдена. Общее решение имеет вид

$\displaystyle x=C_1x^{(1)}+C_2x^{(2)}+C_3x^{(3)}.$

Ответ: Фундаментальная система решений:
$ {x^{(1)}=\left(\begin{array}{r}\vphantom{\dfrac11}\frac23\\ \vphantom{\dfrac11}\frac13\\
1\\ 0\\ 0\end{array}\right)}$ , $ {x^{(2)}=\left(\begin{array}{r}\vphantom{\dfrac11}-\frac13\\ \vphantom{\dfrac11}-\frac53\\
0\\ 1\\ 0\end{array}\right)}$ , $ {x^{(3)}=\left(\begin{array}{r}\vphantom{\dfrac11}-\frac13\\ \vphantom{\dfrac11}\frac43\\
0\\ 0\\ 1\end{array}\right)}$ , общее решение: $ {\left(\begin{array}{c}x_1\\ x_2\\ x_3\\ x_4\\ x_5\end{array}\right)=C_1
\lef...
...frac11}-\frac13\\ \vphantom
{\dfrac11}\frac43\\
0\\ 0\\ 1\end{array}\right)}$ .         

        Замечание 15.7   Если решения, составляющие фундаментальную систему, умножить на любые ненулевые числа, то вновь полученные решения снова будут образовывать фундаментальную систему. Поэтому в предыдущем примере фундаментальную систему образуют и такие решения:
$ \hat x^{(1)}=\left(\begin{array}{r}2\\ 1\\ 3\\ 0\\ 0\end{array}\right)$ , $ \hat x^{(2)}=\left(\begin{array}{r}-1\\ -5\\ 0\\ 3\\ 0\end{array}\right)$ , $ \hat x^{(3)}=\left(\begin{array}{r}-1\\ 4\\ 0\\ 0\\ 3\end{array}\right)$ . Общее решение можно записать так: $ \left(\begin{array}{c}x_1\\ x_2\\ x_3\\ x_4\\ x_5\end{array}\right)=
C_1\left...
...d{array}\right)+C_3
\left(\begin{array}{r}-1\\ 4\\ 0\\ 0\\ 3\end{array}\right)$ .