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

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

Системой m линейных уравнений с n неизвестными называется система m алгебраических уравнений первой степени вида

(4.1.1)

где – неизвестные, подлежащие определению;

– числа, называемые коэффициентами при неизвестных;

– числа, называемые свободными членами.

Решением системы уравнений (4.1.1) называется совокупность n чисел таких, что если в каждое уравнение системы вместо неизвестных подставить эти числа ( вместо , вместо вместо ), то все уравнения обратятся в тождества.

Если система линейных уравнений (4.1.1) имеет хотя бы одно решение, то она называется совместной. В противном случае система называется несовместной.

Совместная система, имеющая единственное решение, называется определенной, а система, имеющая более одного решения – неопределенной.

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

Две произвольные несовместные системы считаются эквивалентными.

Системе линейных уравнений (4.1.1) поставим в соответствие матрицу и расширенную матрицу

,

полученную присоединением к матрице А столбца свободных членов.

 

Методы решения системы n линейных уравнений с n неизвестными

 

Рассмотрим систему n линейных уравнений с n неизвестными

(4.2.1)

Определитель | A | матрицы А называется определителем системы (4.2.1).

Теорема Крамера. Если определитель | A | системы (4.2.1) отличен от нуля, то система совместна и имеет единственное решение.

Доказательство. Пусть система (4.2.1) совместна и – одно из ее решений. Тогда получим n тождеств:

(4.2.2)

Умножим обе части первого из равенств (4.2.2) на алгебраическое дополнение , обе части второго равенства умножим на алгебраическое дополнение и т.д. и обе части n -ого равенства – на . Складывая левые и правые части полученных выражений, придем к следующему равенству:

(4.2.3)

Коэффициент при равен определителю | A | системы (4.2.1), коэффициент при равен нулю, а правая часть равенства (4.2.3) является определителем, полученным из определителя | A | путем замены j -го столбца столбцом свободных членов.

Обозначим данный определитель через

Тогда равенство (4.2.3) примет вид: , откуда

(4.2.4)

Из формулы (4.2.4) следует, что если система (4.2.1) совместна, то она обладает единственным решением.

Формулы (4.2.4) называются формулами Крамера.

Непосредственной подстановкой значений , во все уравнения системы убедимся в том, что они образуют ее решение:

.

При , при , .

Таким образом, получим

.

Теорема доказана.

Пример. Решить систему линейных уравнений методом Крамера:

 

Решение. Вычислим определитель :

,

,

,

откуда

Решение системы линейных уравнений с определителем | A |, отличным от нуля, можно найти с помощью обратной матрицы. Для этого запишем систему (4.2.1) в виде матричного уравнения

АХ=В

(4.2.5)

где .

Решение матричного уравнения (4.2.5) имеет вид

(4.2.6)

Пример. Решить систему линейных уравнений с помощью обратной матрицы

Решение. Вычислим для матрицы

ее обратную матрицу

.

Определим неизвестную матрицу-столбец Х:

,

откуда

Формулы Крамера (4.2.4) могут быть получены из выражения (4.2.6). Действительно, запишем матричное равенство в развернутом виде:

.

Из полученного выражения непосредственно следуют формулы Крамера:

.

Теорема Кронекера-Карелли

Теорема. Система линейных уравнений (4.1.1) совместна тогда и только тогда, когда .

Доказательство.

Необходимость. Пусть система (4.1.1) совместна и пусть числа – одно из ее решений. Подставляя эти числа вместо неизвестных в систему (4.1.1), получим m тождеств, которые показывают, что последний столбец матрицы является линейной комбинацией всех остальных столбцов, взятых соответственно с коэффициентами . Всякий другой столбец матрицы входит и в матрицу А. Поэтому максимальное число линейно независимых столбцов матриц А и совпадает. Следовательно, .

Достаточность. Пусть дано, что . Отсюда следует, что максимальное число линейно независимых столбцов матриц А и совпадает и равно r. Для определенности предположим, что первые r столбцов матриц А и линейно независимы, а остальные (n-r) столбцов является их линейными комбинациями. Выражая последний столбец матрицы А как линейную комбинацию первых r столбцов, получим:

откуда следует, что числа являются решением системы (4.1.1), т.е. система (4.1.1) совместна. Теорема доказана.

На основании теоремы Кронекера-Капелли имеем:

1. Если , то система (4.1.1) несовместна;

2. Если , то система (4.1.1) совместна.

Пусть для определенности базисный минор порядка r расположен в верхнем левом углу матрицы А. Тогда первые r строк матрицы А линейно независимы, а остальные ее строки являются линейной комбинацией первых r строк. Но это означает, что первые r уравнений системы (4.1.1) линейно независимы, а остальные (m-r) ее уравнений являются их линейными комбинациями. Поэтому достаточно решить систему r уравнений; решения такой системы будут, очевидно, удовлетворять и остальным (m-r) уравнениям.

При этом возможны два случая:

1. . Тогда систему, состоящую из первых r уравнений системы (4.1.1)

можно решить, например, по правилу Крамера. В этом случае система имеет единственное решение, т.е. система совместна и определена;

2. . Рассмотрим первые r уравнений системы (4.1.1). Оставив в левых частях первые r неизвестных, перенесем остальные в правые части. Получим систему:

Очевидно, что полученная система и, следовательно, система (4.1.1) являются совместными и неопределенными.

Таким образом, если , то система (4.1.1) совместна (определенная или неопределенная), если , то система (4.1.1) несовместна.

Если в системе n линейных уравнений с n неизвестными определитель системы равен нулю, то . Тогда если , то система является совместной и неопределенной. Если , то система несовместна.

Теорема Кронекера-Капелли устанавливает необходимое и достаточное условие совместности системы (4.1.1), но не дает способа нахождения решения этой системы. Рассмотрим метод Жордана-Гаусса – метод решения системы m линейных уравнений с n неизвестными.

 

Метод Жордана-Гаусса

 

Метод Жордана-Гаусса основан на элементарных преобразованиях (п.3.2) строк расширенной матрицы

системы (4.1.1).

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

Пусть дана система m линейных уравнений с n неизвестными. Применяя элементарные преобразования, построим эквивалентную систему специального вида. Для этого выберем в качестве первого уравнений одно из тех уравнений системы, где коэффициент при х ₁ отличен от нуля. Не нарушая общности, предположим, что . Тогда первым уравнением системы будет уравнение

.

Умножим первое уравнение на . Затем умножим это же уравнение на , и прибавим его почленно к уравнениям системы с номерами i=2,3,…,m. После этого преобразования в уравнениях с номерами i >1 будет исключено неизвестное х ₁. Первый шаг метода Жордана-Гаусса закончен.

.

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

.

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

.

Продолжая процесс, после r шагов получим матрицу , содержащую r единичных столбцов на месте первых n столбцов матрицы А (r – ранг матрицы А системы).

При этом возможны три случая:

1. Если , то матрица преобразуется в матрицу

Система имеет единственное решение: .

2. Если и r<n, то

Система имеет бесконечное множество решений. Общее решение имеет вид:

Неизвестные называются базисными. – свободными неизвестными.

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

Среди частных решений системы выделим базисные решения, которые получают при равенстве нулю всех свободных неизвестных. Очевидно, что одним из базисных решений является следующее:

.

В общем случае число базисных решений не превышает .

3. Если , то

где хотя бы один из элементов отличен от нуля. В этом случае система (4.1.1) несовместна.

Таким образом, метод Жордана-Гаусса состоит из r итераций (r шагов). На каждой S -ой итерации выбирается направляющий элемент соответственно направляющие строка и столбец. С помощью элементарных преобразований столбец преобразуется в единичный с единицей в строке .

Рассмотрим алгоритм произвольной итерации метода Жордана-Гаусса. Положим .

Шаг 1. Сформировать множество .

Шаг 2. Если , то процесс элементарных преобразований закончить. В противном случае перейти к шагу 3.

Шаг 3. Если для , то процесс элементарных преобразований закончить. В противном случае найти направляющий элемент и перейти к шагу 4.

Шаг 4. Разделить направляющую строку на .

Шаг 5. К i -ой строке, , прибавим строку , умноженную на .

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

	(4.4.1)
	(4.4.2)
	(4.4.3)
	(4.4.4)

Полагая j=k, из (4.4.1) и (4.4.3) имеем

.

Пример. Решить систему линейных уравнений методом Жордана-Гаусса.

а)

Решение. Составим из данной системы расширенную матрицу

Полагаем .

Итерация 1.

Шаг 1. .

Шаг 2. , переходим к шагу 3.

Шаг 3. Находим .

Шаг 4. Делим третью строку на .

Шаг 5. К первой, второй и четвертой строкам прибавляем третью строку, соответственно умноженную на -2, -2, -3. В результате матрица преобразуется в матрицу

.

Итерация 2.

Шаг 1. .

Шаг 2. , переходим к шагу 3.

Шаг 3. Находим .

Шаг 4. Делим первую строку на .

Шаг 5. Ко второй, третьей и четвертой строкам прибавляем первую строку, соответственно умноженную на -4, -3, 1. Получим матрицу

.

Итерация 3.

Шаг 1. .

Шаг 2. , переходим к шагу 3.

Шаг 3. Находим .

Шаг 4. Делим четвертую строку на .

Шаг 5. К первой, второй, третьей строкам прибавляем четвертую строку, соответственно умноженную на 0, -5, -2. Получим матрицу

.

Итерация 4.

Шаг 1. .

Шаг 2. , переходим к шагу 3.

Шаг 3. Находим .

Шаг 4. Делим четвертую строку на .

Шаг 5. К первой, третьей и четвертой строкам прибавляем вторую строку, соответственно умноженную на -1, 2, 0. Получим матрицу

.

Итерация 5.

Шаг 1. .

Шаг 2. , поэтому процесс элементарных преобразований закончен. На основании вида матрицы получаем единственное решение исходной системы: .

 

б)

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

.

В результате итерации 1, полагая , получим матрицу

После итерации 2, полагая , получим матрицу

Итерация 3.

Шаг 1. .

Шаг 2. .

Шаг 3. Так как , то процесс элементарных преобразований закончен.

Матрица определяет общее решение системы:

– базисные, – свободные переменные.

Получим одно из базисных решений:

.

 

в)

Решение. Матрицы , , имеют вид:

 

 

Очевидно, что процесс элементарных преобразований следует закончить, так как . Из первой (или третьей) строки матрицы следует, что исходная система линейных уравнений несовместна. Действительно, первой строке соответствует уравнение , которое не может быть удовлетворено ни при каких значениях неизвестных .

Используя метод Жордана-Гаусса, рассмотрим еще один метод вычисления обратной матрицы .

Рассмотрим матричное уравнение

,

(4.4.5)

где , Е – единичная матрица.

Очевидно, что матричное уравнение (4.4.5) имеет единственное решение .

Решение матричного уравнения (4.4.5) сводится к решению n систем n линейных уравнений с n неизвестными вида

(4.4.6)

Системе линейных уравнений (4.4.6) соответствует расширенная матрица . Применяя к матрице алгоритм метода Жордана-Гаусса, получим матрицу . Покажем, что . Расширенной матрице соответствует матричное уравнение , которое имеет единственное решение Х=В. Матрица получена из матрицы методом Жордана-Гаусса. Поэтому системы линейных уравнений, соответствующие матрицам и , равносильны, т.е. имеют одно и то же решение. Отсюда следует, что , следовательно, .

Таким образом, чтобы для невырожденной матрицы А вычислить обратную матрицу , необходимо составить матрицу . Методом Жордана-Гаусса в матрице преобразовать матрицу А к виду единичной матрицы Е, тогда на месте единичной матрицы Е получим обратную матрицу .

Пример. Вычислить обратную матрицу для матрицы

.

Решение. Составим матрицу

.

На итерации 1, полагая , получим

.

На итерации 2, полагая , получим

.

На итерации 3, полагая , получим

,

откуда .