Системы линейных алгебраических уравнений

Общие определения

Рассмотрим систему \(m\) линейных алгебраических уравнений с \(n\) неизвестными, \[ a_{11}x_1+a_{12}x_2+ ....+a_{1n}x_n=b_1, \quad \quad (28) \] \[ a_{21}x_1+a_{22}x_2+...+a_{1n}x_n=b_2,\quad \quad (29) \] \[ .............................................................. \] \[ a_{m1}x_1+a_{m2}x_2+...+a_{mn}x_n=b_m, \quad \quad(30) \]

Матрицей коэффициентов системы уравнений назовем матрицу \[ A=\left( \begin{array}{ccccc} a_{11} & a_{12} & a_{13} &\ldots & a_{1n} \\ a_{21} & a_{22} & a_{23} &\ldots & a_{2n} \\ \vdots & \vdots & \vdots & \ddots & \vdots\\ a_{m1} &a_{m2} & a_{m3} & \ldots & a_{mn} \end{array} \right) , \] образуем столбец правых частей системы \[ B=\left (\begin{array}{cccc} b_1 & b_2 & \ldots &b_m \end{array} \right)^T. \]

Определение. Решением системы уравнений (28)-(30) называют такой набор чисел \(x_1,x_2,...,x_n\), который при подстановке в уравнения обращает все эти уравнения в равенства.

Определение. Система уравнений (28)-(30) называется однородной , если столбец правых частей нулевой. Если столбец \(B\) ненулевой, система называется неоднородной .

Вообще говоря, система уравнений (28)-(30) может не иметь решений.

Пример. Рассмотрим систему уравнений \[ x_1+x_2=1, \] \[ x_1+x_2=2. \]

Очевидно, что она не имеет решений.

Далее, система линейных уравнений может иметь бесконечно много решений.

Пример. Рассмотрим систему уравнений \[ x_1+x_2=0. \]

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

Кроме того, как следует из теоремы Крамера, система уравнений может иметь единственное решение. Таким образом, следует развить теорию, позволяющую выяснить в общих терминах, когда система несовместна, когда она имеет решение и сколько решений она имеет, и представить аппарат, позволяющий построить эти решения.

Метод Гаусса

Метод Гаусса позволяет в рамках единого подхода построить решения произвольной системы линейных алгебраических уравнений. Исходным является построение расширенной матрицы, которая получается так: к матрице коэффициентов системы \(A\) добавляют справа столбец правых частей \(B\). При этом имеется естественное взаимно-однозначное соответствие: каждой строке расширенной матрицы отвечает уравнение системы.

Метод Гаусса опирается на следующие простые соображения: существуют преобразования системы уравнений, которые не меняют набора решений системы. Перечислим эти преобразования с указанием того, как они влияют на расширенную матрицу.

1. Перестановка уравнений (перестановка строк расширенной матрицы).

2. Умножение уравнения на ненулевое число (умножение строки расширенной матрицы на ненулевое число).

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

4. Перестановка двух неизвестных (с учетом необходимости обратной замены переменных ) (перестановка столбцов расширенной матрицы).

Опишем теперь процедуру решения системы линейных уравнений с помощью метода Гаусса. Она включает 2 шага: прямой и обратный.

1. Прямой ход метода Гаусса. Выпишем расширенную матрицу системы уравнений, \[ A=\left( \begin{array}{cccccc} a_{11} & a_{12} & a_{13} &\ldots & a_{1n}& b_1\\ a_{21} & a_{22} & a_{23} &\ldots & a_{2n}& b_2\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ a_{m1} &a_{m2} & a_{m3} & \ldots & a_{mn}& b_m \end{array} \right) , \] и найдем среди чисел \(a_{ik}\) число, отличное от 0. Перестановкой строк и столбцов переместим это число в позицию \((1,1)\), \[ A \mapsto \left( \begin{array}{cccccc} a^{(1)} & \ldots & \ldots &\ldots & \ldots & \ldots \\ \ldots & \ldots & \ldots &\ldots & \ldots & \ldots \\ \vdots & \vdots & \vdots & \ddots & \vdots &\vdots\\ \ldots &\ldots & \ldots & \ldots & \ldots & \ldots \end{array} \right) . \] Затем из второй, третьей и последующих строк вычитаем первую с подходящим множителем, так, чтобы под числом \(a^{(1)}\) появились нулевые элементы, \[ A \mapsto \left( \begin{array}{cccccc} a^{(1)} & \ldots & \ldots &\ldots & \ldots & \ldots \\ 0 & \ldots & \ldots &\ldots & \ldots & \ldots \\ \vdots & \vdots & \vdots & \ddots & \vdots &\vdots\\ 0 &\ldots & \ldots & \ldots & \ldots & \ldots \end{array} \right) . \] Затем в части матрицы, не включающей первую строку и последний столбец, вновь ищем ненулевой элемент \(a^{(2)}\) и, переставляя строки и столбцы, помещаем его на позицию \((2,2)\), \[ A \mapsto \left( \begin{array}{cccccc} a^{(1)} & \ldots & \ldots &\ldots & \ldots & \ldots \\ 0 & a^{(2)} & \ldots &\ldots & \ldots & \ldots \\ \vdots & \vdots & \vdots & \ddots & \vdots &\vdots\\ 0 &\ldots & \ldots & \ldots & \ldots & \ldots \end{array} \right) . \] Вычитая вторую строку из всех последующих с подходящими множителями, получаем 0 во всех элементах, стоящих под \(a^{(2)}\), \[ A \mapsto \left( \begin{array}{cccccc} a^{(1)} & \ldots & \ldots &\ldots & \ldots & \ldots \\ 0 & a^{(2)} & \ldots &\ldots & \ldots & \ldots \\ 0 &0 &\ldots &\ldots & \ldots & \ldots \\ \vdots & \vdots & \vdots & \ddots & \vdots &\vdots\\ 0 &0 & \ldots & \ldots & \ldots & \ldots \end{array} \right) . \] Затем в части матрицы, не включающей первую и вторую строки и последний столбец, вновь ищем ненулевой элемент \(a^{(3)}\) и, переставляя строки и столбцы, помещаем его на позицию \((3,3)\) и т.д. Продолжая нашу процедуру, мы преобразуем исходную матрицу к матрице, имеющей "трапециевидную" форму: на главной диагонали у такой матрицы стоят ненулевые элементы, а под главной диагональю - нули. Наша процедура остановится, когда 1) мы дойдем до "дна" матрицы, или 2) будет невозможно найти ненулевой элемент среди оставшихся строк, т.е. оставшиеся строки содержат только нули (за возможным исключением последнего столбца!). На этом прямой ход метода Гаусса заканчивается. Его результатом является преобразованная матрица.

2. Обратный ход метода Гаусса. Рассмотрим внимательно построенную на предыдущем шаге матрицу. Как отмечалось выше, каждая строка построенной матрицы представляет уравнение, которое однозначно по ней восстанавливается. Таким образом, следует решить систему уравнений, соответствующую матрице, построенной в результате прямого хода метода Гаусса. Возможны следующие ситуации.

а) Она содержит строки, состоящие из нулей, за исключением элементов последнего столбца, которые не равны нулю, \[ A \mapsto \left( \begin{array}{cccccc} a^{(1)} & \ldots & \ldots &\ldots & \ldots & \ldots \\ 0 & a^{(2)} & \ldots &\ldots & \ldots & \ldots \\ 0 &0 &\ldots &\ldots & \ldots & \ldots \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 &0 & 0 & \ldots & 0 & b^* \end{array} \right) , \] \(b^* \neq 0\). Как упоминалось выше, каждая такая строка матрицы соответствует уравнению, в данном случае - уравнению с нулевыми коэффициентами, в правой части которого стоит не ноль. Таким образом, в этом случае исходная система уравнений несовместна.

б) Итоговая матрица содержит полностью нулевые строки. Такие строки соответствуют тривиальному уравнению \(0=0\), их можно вычеркнуть. Далее, \(r\), число ненулевых элементов на главной диагонали равно рангу матрицы коэффициентов исходной системы уравнений. При этом возможны 2 ситуации:

б1) \(r=n\) - ранг матрицы равен числу неизвестных. Это ситуация теоремы Крамера, когда существует только одно решение системы уравнений. По построенной матрице восстанавливают систему уравнений, которую решают снизу вверх . При этом на каждом шаге уравнение тривиально.

б2) \(r < n\). В этом случае следует неизвестные с номерами, большими \(r\), положить равными произвольным константам (т.е. написать равенства \(x_{r+1}=\alpha ,x_{r+2}=\beta, ..., x_n=\gamma \), причем \(\alpha ,\beta, ...,\gamma \) могут принимать произвольные значения), подставить эти значения в построенную систему уравнений и решать эти уравнения снизу вверх . При этом мы получим набор решений, зависящий от \(n-r\) свободных параметров - \(\alpha, \beta, ..., \gamma\).

Пример. Рассмотрим систему уравнений \[ x_1-2x_2+3x_3-4x_4=4, \] \[ x_2-x_3+x_4=-3, \] \[ x_1+3x_2-3x_4=1, \] \[ -7x_2+3x_3+x_4=-3. \] Этой системе уравнений соответствует расширенная матрица \[ A=\left( \begin{array}{ccccc} 1 &-2 & 3 & -4 & 4 \\ 0 & 1 & -1 & 1 & -3 \\ 1& 3 & 0 & -3 &1\\ 0& -7 & 3 &1 & -3 \end{array} \right). \] Начинаем преобразовывать матрицу. В данном случае в позиции \((1,1)\) стоит 1, так что на первом шаге перестановку строк и столбцов можно не реализовывать. Вычитаем первую строку из третьей, так что \[ A \mapsto \left( \begin{array}{ccccc} 1 &-2 & 3 & -4 & 4 \\ 0 & 1 & -1 & 1 & -3 \\ 0& 5 & -3 & 1 & -3\\ 0& -7 & 3 &1 & -3 \end{array} \right). \] И опять, в позиции \((2,2)\) стоит 1, так что и на втором шаге перестановка строк и столбцов не требуется. Вычитаем вторую строку из третьей 5 раз, прибавляем вторую строку к четвертой 7 раз, \[ A \mapsto \left( \begin{array}{ccccc} 1 &-2 & 3 & -4 & 4 \\ 0 & 1 & -1 & 1 & -3 \\ 0& 0 & 2 & -4 & 12 \\ 0& 0 & -4 &8 & -24 \end{array} \right). \] Третью строку можно сократить на 2, четвертую - на (-4), \[ A \mapsto \left( \begin{array}{ccccc} 1 &-2 & 3 & -4 & 4 \\ 0 & 1 & -1 & 1 & -3 \\ 0& 0 & 1 & -2 & 6 \\ 0& 0 & 1 & -2 & 6 \end{array} \right). \] В позиции \((3,3)\) стоит 1, так что перестановка строк и столбцов на третьем шаге не нужна. Вычитаем третью строку из четвертой, \[ A \mapsto \left( \begin{array}{ccccc} 1 &-2 & 3 & -4 & 4 \\ 0 & 1 & -1 & 1 & -3 \\ 0& 0 & 1 & -2 & 6 \\ 0& 0 & 0 & 0 & 0 \end{array} \right). \] Последняя строка содержит только нули, что соответствует тривиальному уравнению \(0=0\). Вычеркивая ее, прибываем к окончательному виду преобразованной расширенной матрицы: \[ A \mapsto \left( \begin{array}{ccccc} 1 &-2 & 3 & -4 & 4 \\ 0 & 1 & -1 & 1 & -3 \\ 0& 0 & 1 & -2 & 6 \end{array} \right). \] Эта матрица соответствует 3 уравнениям. Ранг матрицы равен \(r=3\) (число ненулевых элементов на главной диагонали), система уравнений имеет 4 неизвестных. Согласно схеме метода Гаусса, полагаем: \(x_4=\alpha\), и начинаем решать систему уравнений снизу вверх. Третье (нижнее!) уравнение нам дает: \[ x_3=2\alpha +6. \] Подставляем во второе уравнение: \[ x_2-(2\alpha +6)+\alpha =-3, \] так что \[ x_2=\alpha +3. \] Подставляя в первое уравнение, получаем: \[ x_1-2(\alpha +3)+3(2\alpha +6)-4\alpha =4. \] В итоге \[ x_1=-8. \] Выпишем ответ целиком: \[ x_1=-8, x_2=\alpha +3,x_3=2\alpha +6, x_4=\alpha. \]

Однородные системы уравнений

Напомним, что система линейных уравнений называется однородной, если в правых частях всех уравнений стоят нули. Таким образом, мы обсуждаем систему уравнений \[ a_{11}x_1+a_{12}x_2+ ....+a_{1n}x_n=0, \quad \quad(31) \] \[ a_{21}x_1+a_{22}x_2+...+a_{1n}x_n=0, \quad \quad(32) \] \[ ........................................................... \] \[ a_{m1}x_1+a_{m2}x_2+...+a_{mn}x_n=0. \quad \quad(33) \] С использованием экономичных обозначений эту систему можно переписать в виде \[ \sum _{m=1}^na_{km}x_m=0, k=1,2,...,n. \quad \quad(34) \]

Очевидно, что у этой системы имеется решение \(x_1=x_2=....=x_n=0\), это решение называется тривиальным . Центральный вопрос, который обсуждается в данном параграфе: есть ли у системы уравнений (31)-(33) нетривиальные решения?

Теорема о нетривиальном решении. Для того, чтобы система линейных однородных уравнений имела нетривиальное решение, необходимо и достаточно, чтобы ранг матрицы коэффициентов системы был меньше числа неизвестных.

Для того, чтобы сформулировать окончательный результат, нам потребуется ввести новые понятия. Пусть \(x_1,x_2,....,x_n\) - решение системы (31)-(33). Образуем столбец решений \(X=(x_1,x_2,...,x_n)^T\).

Предложение. Пусть столбцы \(X_1,X_2,...,X_k\) представляют собой столбцы решений системы (31)-(33). Тогда любая линейная комбинация этих столбцов представляет собой столбец решений системы (31)-(33).

Теорема. Пусть \(r=rang(A)< n\), числа неизвестных системы (31)-(33). Тогда

1. Имеется \((n-r)\) линейно независимых столбцов, представляющих собой столбцы решений системы,

2. Любой другой столбец, представляющий собой столбец решений системы, является линейной комбинацией этих линейно независимых столбцов.

Утверждение этой теоремы можно выразить с помощью одной формулы. Пусть \(X_1,X_2,...,X_{n-r}\), - те линейно независимые столбцы-решения, существование которых утверждается в теореме. Тогда любой другой столбец-решение имеет вид: \[ X=\sum ^{n-r}_{k=1}\lambda_kX_k, \quad \quad(35) \] т.е. является их линейной комбинацией. Такой столбец-решение называется общим решением системы (31)-(33) (имея в виду, что константы \(\lambda_k, k=1,2,...,(n-r)\), могут принимать любое значение. Соотношение (35) описывает структуру общего решения однородной системы уравнений. Столбцы-решения \(X_k\) называются фундаментальными решениями системы (31)-(33).

Неоднородные системы уравнений

Обсудим теперь неоднородную систему уравнений, в правых частях которых не все числа равны нулю, \[ a_{11}x_1+a_{12}x_2+ ....+a_{1n}x_n=b_1, \quad \quad(36) \] \[ a_{21}x_1+a_{22}x_2+...+a_{1n}x_n=b_2, \quad \quad(37) \] \[ ............................................................ \] \[ a_{m1}x_1+a_{m2}x_2+...+a_{mn}x_n=b_m, \quad \quad(38) \] или, в более кратком виде, \[ \sum _{p=1}^na_{kp}x_p=b_k, k=1,2,...,m. \] С этой системой уравнений можно связать 2 матрицы: матрицу коэффициентов \(A\) и расширенную матрицу \(\widetilde{A}\), которая получается из \(A\) приписыванием справа столбца правых частей \(B\).

Теорема Кронекера-Капелли. Для того, чтобы неоднородная система линейных уравнений (36)-(38) имела хотя бы одно решение, небходимо и достаточно, чтобы выполнялось условие \[ rang(A)=rang(\widetilde{A}). \quad \quad (39) \] Пусть \(X_c\) - решение-столбец системы (38) и \(X\) - произвольное другое решение этой системы уравнений. Как отмечалось выше, систему уравнений(36)-(38) можно записать в виде матричного уравнения, так что тот факт, что \(X_c\) и \(X\) - решения-столбцы, можно выразить соотношениями: \[ AX=B, AX_c=B. \] Вычитая одно из другого и используя элементарные свойства матричных операций, получаем: \[ A(X-X_c)=0, \] где справа стоит нулевой столбец. Таким образом, столбец \(X-X_c\) является решением однородной системы уравнений. Выше описано общее решение однородной системы уравнений. Используя это описание, мы получаем описание общего решения неоднородной системы уравнений: \[ X=X_c+\sum ^{n-r}_{k=1}\lambda_kX_k, \quad \quad(40) \] где \(X_c\) - какое-то решение неоднородной системы уравнений, а \(X_k\), \(k=1,2,...,(n-r)\) - фундаментальные решения соответствующей (т.е. с теми же коэффициентами) однородной системы уравнений.

Предыдущий раздел

Назад

Следующий раздел