3. Общие системы линейных уравнений.

Рассмотрим систему уравнений Ax =b с произвольной матрицей A. Исследуем вопрос о ее совместности и количестве решений.

ТЕОРЕМА КРОНЕКЕРА – КАПЕЛЛИ.

Для того, чтобы система уравнений Ax =b была совместной, необходимо и достаточно, чтобы ранг матрицы этой системы равнялся рангу ее расширенной матрицы.

ДОКАЗАТЕЛЬСТВО.

1) Пусть система уравнений Ax =b является совместной. Докажем, что ранг r _A матрицы A равняется рангу r _Ã расширенной матрицы Ã.

Представим матрицы A и Ã как системы их векторов столбцов

A 1,A 2, … ,A n

(1)

и

A 1, A 2, … ,A n , b

(2)

соответственно. Ранг матрицы A равен рангу системы векторов (1), а ранг матрицы Ã равен рангу системы векторов (2). Поскольку система векторов (1) является подсистемой системы векторов (2), то r _A  r _Ã.

Так как система Ax =b является совместной, то существует вектор x ^ = , координаты которого удовлетворяют данной системе, или, в векторном виде, имеет место равенство x ₁^*A ₁ + x ₂^*A ₂ + … + x _n^*A _n =b. Отсюда следует, чтоb  L (A ₁,A ₂ , … ,A _n ) и, следовательно,

A ₁,A ₂ , … ,A _n ,b  L (A ₁,A ₂ , … ,A _n ). По свойствам ранга системы векторов r _Ã  r _A. Но так как r _A  r _Ã , то r _A = r _Ã .

2) Пусть теперь r _A = r _Ã = r. Докажем, что система Ax =b является совместной. Согласно определению базиса системы векторов базисы систем (1) и (2) содержат по r векторов. ПустьA ₁, A ₂ , … ,A _r — базис системы (1). Тогда эти же векторы будут являться и базисом системы (2). Действительно, векторыA ₁,A ₂ , … ,A _r образуют линейно независимую подсистему системы (2), а поскольку их количество совпадает с рангом системы (2), то они являются базисом этой системы. Следовательно, векторb можно представить в виде линейной комбинации векторовA ₁,A ₂ , …,A _r :

b =  ₁A ₁ +  ₂A ₂ + … +  _rA _r, а также в виде линейной комбинации

b =  ₁A ₁ +  ₂A ₂ + … +  _rA _r + 0A _{r + 1} + … + 0A _n. Справедливость последнего равенства означает, что векторx ^*, координатами которого являются числа  ₁,  ₂ , … ,  _r , 0, … , 0 является решением системы уравнений Ax =b, то есть система Ax =b совместна. Теорема доказана.

ТЕОРЕМА ОБ ОПРЕДЕЛЕННОСТИ СЛУ.

Пусть система уравнений Ax =b является совместной, имеет n неизвестных и r _A = r _Ã = r.

Тогда если r = n, то система Ax =b имеет единственное решение, если r < n, то система Ax =b имеет бесконечно много решений.

Переменные, соответствующие линейно независимым столбцам матрицы A, называются базисными переменными. Количество базисных переменных равно r — рангу матрицы A

Остальные переменные системы линейных уравнений называются свободными, количество свободных переменных равно n – r.

Решение системы, в котором ненулевые значения имеют только базисные переменные, называется базисным решением.

В справедливости теоремы об определенности убедимся, рассмотрев алгоритм решения СЛУ с помощью ОЖИ.

АЛГОРИТМ РЕШЕНИЯ СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ.

Пусть дана система уравнений Ax =b. Перепишем ее в табличном виде:

	x 1	x 2	…	x n	1
0 =	a 11	a 12	…	a 1 n	– b 1
0 =	a 21	a 22	…	a 2 n	– b 2
…	…	…	…	…	…
0 =	a m 1	a m 2	…	a m n	– b m

Столбцы под переменными образуют матрицу A, а все столбцы таблицы — расширенную матрицу Ã, ранги которых обозначим r _A и r _Ã соответственно.

Выполним максимально возможное число шагов ОЖИ, выбирая разрешающие элементы в столбцах под переменными.

Заметим, что столбец, являющийся разрешающим на некотором шаге ОЖИ, на последующих шагах разрешающим являться не может и, следовательно, не повлияет на величину остальных элементов таблицы. Его собственные элементы не представляют никакого интереса, так как при выполнении одного шага ОЖИ над столбцом, являвшимся разрешающим, вместо переменной x _s окажется 0. Поэтому рекомендуется на каждом шаге ОЖИ сокращать таблицу на разрешающий столбец.

Пересчет таблицы для системы Ax =b означает реализацию обычного метода подстановки, а для матрицы A и расширенной матрицы этой системы — вычисление их рангов. Поскольку разрешающие элементы выбираются только в столбцах под переменными, пересчет будет закончен после выполнения r _A шагов ОЖИ. По окончании пересчета получим жорданову таблицу одного из следующих видов:

1. а) r _A = n.

	1
x1 =	 1
…	…
x n =	 n
0 =	0

В этом случае r _A = n и r _Ã = n, так как выполнено n шагов ОЖИ, и больше нельзя сделать ни одного шага (у матрицы A все столбцы использованы, а у расширенной матрицы в неиспользованном столбце под 1 невозможно выбрать ненулевой разрешающий элемент в неиспользованной строке). Система совместна и имеет единственное решение, которое можно получить, выписав выражения для переменных из таблицы: x ₁ =  ₁, …, x _n =  _n, то есть x ^*=.

1.б) r _A = n.

	1
x 1 =	 1
…	…
x n =	 n
0 =	  0

В этом случае r _A = n и r _Ã = n + 1, так как выполнено n шагов ОЖИ, у матрицы A все столбцы использованы, а у расширенной матрицы в неиспользованном столбце под 1 можно выбрать ненулевой разрешающий элемент  в неиспользованной строке. Система несовместна, так как r _A  r _Ã .

2. а) r _A < n.

	x r +1	…	x n	1
x 1 =	 1 r +1	…	 1 n	 1
…	…	…	…	…
x r =	 r r + 1	…	 r n	 r
0 =	0	…	0	0

В этом случае r _A = r и r _Ã = r, так как выполнено r шагов ОЖИ, и больше нельзя сделать ни одного шага (у матрицы A и у расширенной матрицы в неиспользованных столбцах невозможно выбрать ненулевой разрешающий элемент в неиспользованной строке). Так как r _A = r _Ã , то система уравнений совместна.

Переменные x ₁, …, x _r соответствуют линейно независимым столбцам матрицы A и являются базисными.

Переменные x _{r + 1}, … , x _n , оставшиеся наверху таблицы, являются свободными.

Для получения решений системы выпишем из таблицы соотношения между переменными: . Придавая свободным переменнымx _{r +1}, …, x _n , стоящим в правой части, произвольные значения, можно получить бесконечно много различных решений системы Ax =b. Например, базисное решение системы имеет вид =.

2. б) r _A < n.

	x r +1	…	x n	1
x 1 =	 1 r +1	…	 1 n	 1
…	…	…	…	…
x r =	 r r + 1	…	 r n	 r
0 =	0	…	0	  0

В этом случае r _A = r и r _Ã = r + 1, так как выполнено r шагов ОЖИ, у матрицы A в неиспользованных столбцах невозможно выбрать ненулевой разрешающий элемент в неиспользованной строке, а у расширенной матрицы в столбце под 1 можно выбрать ненулевой разрешающий элемент  в неиспользованной строке и сделать еще один шаг ОЖИ.

Система несовместна, так как r _A  r _Ã .