Решение произвольных систем уравнений. Совместные системы. Определенные системы. Однородная система. Элементарные преобразования систем уравнений. Теорема Кронекера Капелли. Метод Гаусса

Решение систем лицейных уравнений
Содержание:

Матричный метод решения систем уравнений.

Метод Крамера.

Решение произвольных систем уравнений.

Совместные системы.

Определенные системы.

Однородная система.

Элементарные преобразования систем уравнений.

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

Метод Гаусса.

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

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

Метод удобен для решения систем невысокого порядка.

Метод основан на применении свойств умножения матриц.

Пусть дана система уравнений:

Составим матрицы: A = ; B = ; X = .

Систему уравнений можно записать:

AX = B.
Сделаем следующее преобразование: A^-1AX = A^-1B,

т.к. А^-1А = Е, то ЕХ = А^-1В

Х = А^-1В

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

Пример. Решить систему уравнений:

Х = , B = , A =

Найдем обратную матрицу А^-1.

 = det A = 5(4-9) + 1(2 – 12) – 1(3 – 8) = -25 – 10 +5 = -30.

M₁₁ = = -5; M₂₁ = = 1; M₃₁ = = -1;

M₁₂ = M₂₂ = M₃₂ =

M₁₃ = M₂₃ = M₃₃ =

A^-1 = ;
Cделаем проверку:

AA^-1 = =E.

Находим матрицу Х.

Х = = А^-1В = = .

Итого решения системы: x =1; y = 2; z = 3.

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

Метод Крамера.

(Габриель Крамер (1704-1752) швейцарский математик)

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

Для этого необходимо, чтобы определитель матрицы системы не равнялся 0.

det A  0;

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

Теорема. (Правило Крамера):
Теорема. Система из n уравнений с n неизвестными

в случае, если определитель матрицы системы не равен нулю, имеет единственное решение и это решение находится по формулам:
x_i = _i/, где

 = det A, а _i – определитель матрицы, получаемой из матрицы системы заменой столбца i столбцом свободных членов b_i.

_i =
Пример.

A = ; ₁= ; ₂= ; ₃= ;
x₁ = ₁/detA; x₂ = ₂/detA; x₃ = ₃/detA;
Пример. Найти решение системы уравнений:

 = = 5(4 – 9) + (2 – 12) – (3 – 8) = -25 – 10 + 5 = -30;

₁ = = (28 – 48) – (42 – 32) = -20 – 10 = -30.
x₁ = ₁/ = 1;

₂ = = 5(28 – 48) – (16 – 56) = -100 + 40 = -60.

x₂ = ₂/ = 2;

₃ = = 5( 32 – 42) + (16 – 56) = -50 – 40 = -90.

x₃ = ₃/ = 3.
Как видно, результат совпадает с результатом, полученным выше матричным методом.
Если система однородна, т.е. b_i = 0, то при 0 система имеет единственное нулевое решение x₁ = x₂ = … = x_n = 0.
При  = 0 система имеет бесконечное множество решений.

Для самостоятельного решения:

; Ответ: x = 0; y = 0; z = -2.

Решение произвольных систем линейных уравнений.

Как было сказано выше, матричный метод и метод Крамера применимы только к тем системам линейных уравнений, в которых число неизвестных равняется числу уравнений. Далее рассмотрим произвольные системы линейных уравнений.

Определение. Система m уравнений с n неизвестными в общем виде записывается следующим образом:

,

где a_ij – коэффициенты, а b_i – постоянные. Решениями системы являются n чисел, которые при подстановке в систему превращают каждое ее уравнение в тождество.

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

Определение. Система называется определенной, если она имеет только одно решение и неопределенной, если более одного.
Определение. Для системы линейных уравнений матрица
А = называется матрицей системы, а матрица
А^*= называется расширенной матрицей системы

Определение. Если b₁, b₂, …,b_m = 0, то система называется однородной. однородная система всегда совместна, т.к. всегда имеет нулевое решение.
Элементарные преобразования систем.
К элементарным преобразованиям относятся:
1)Прибавление к обеим частям одного уравнения соответствующих частей другого, умноженных на одно и то же число, не равное нулю.

2)Перестановка уравнений местами.

3)Удаление из системы уравнений, являющихся тождествами для всех х.

Теорема Кронекера – Капелли.

(условие совместности системы)

(Леопольд Кронекер (1823-1891) немецкий математик)

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

RgA = RgA^*.

Очевидно, что система (1) может быть записана в виде:

x₁ + x₂ + … + x_n

Доказательство.
1) Если решение существует, то столбец свободных членов есть линейная комбинация столбцов матрицы А, а значит добавление этого столбца в матрицу, т.е. переход АА^* не изменяют ранга.
2) Если RgA = RgA^*, то это означает, что они имеют один и тот же базисный минор. Столбец свободных членов – линейная комбинация столбцов базисного минора, те верна запись, приведенная выше.
Пример. Определить совместность системы линейных уравнений:

A =
~ . RgA = 2.

A* = RgA* = 3.

Система несовместна.
Пример. Определить совместность системы линейных уравнений.
А = ; = 2 + 12 = 14  0; RgA = 2;
A* =
RgA* = 2.

Система совместна. Решения: x₁ = 1; x₂ =1/2.

Метод Гаусса.

(Карл Фридрих Гаусс (1777-1855) немецкий математик)

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

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

Разделим обе части 1–го уравнения на a₁₁  0, затем:

1) умножим на а₂₁ и вычтем из второго уравнения

2) умножим на а₃₁ и вычтем из третьего уравнения

и т.д.
Получим:

, где d_1j = a_1j/a₁₁, j = 2, 3, …, n+1.
d_ij = a_ij – a_i1d_1j i = 2, 3, … , n; j = 2, 3, … , n+1.
Далее повторяем эти же действия для второго уравнения системы, потом – для третьего и т.д.
Пример. Решить систему линейных уравнений методом Гаусса.

Составим расширенную матрицу системы.
А* =
Таким образом, исходная система может быть представлена в виде:
, откуда получаем: x₃ = 2; x₂ = 5; x₁ = 1.

Пример. Решить систему методом Гаусса.

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

Таким образом, исходная система может быть представлена в виде:

, откуда получаем: z = 3; y = 2; x = 1.

Полученный ответ совпадает с ответом, полученным для данной системы методом Крамера и матричным методом.

Для самостоятельного решения:

Ответ: {1, 2, 3, 4}.

Системы m линейных уравнений с n неизвестными
Рассмотрим систему m линейных уравнений с n неизвестными вида
, или (6.6.1.)
или же, в матричной форме , где матрица размера имеет компоненты , а столбцы и соответственно компоненты , и .

Определение

6.6.1.

Упорядоченный набор чисел будем называть частным решением системы линейных уравнений (6.6.1.), если при подстановке этих чисел в систему мы получаем верные равенства. Частное решение системы линейных уравнений может также быть записано в виде столбца . Совокупность всех частных решений системы линейных уравнений (6.6.1.) назовем общим решением системы (6.6.1.)

Определение

6.6.2.

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

Определение

6.6.3.

Матрица называется основной матрицей системы (6.6.1.), а матрица - расширенной матрицей этой системы.

Определение

6.6.4.

Система (6.6.1.) называется однородной, если , в противном случае - неоднородной системой уравнений.

Теорема

6.6.1.

(Кронекера-Капелли)

Для того чтобы система (6.6.1.) была совместна, необходимо и достаточно, чтобы ранг ее основной матрицы был равен рангу расширенной.

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

Доказательство достаточности:
Пусть ранг основной матрицы равен рангу расширенной матрицы и равен r. Без ограничения общности предположим, что базисный минор расположен в левом верхнем углу расширенной матрицы, но тогда по теореме 6.5.1. (о базисном миноре) имеет место равенство , которое можно переписать в виде

.
Однако последнее означает, что система (6.6.1.) имеет решение , то есть она совместна.
Теорема доказана.

Задача

6.6.1.

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

Фундаментальная система решений
В §6.6. было показано, что факт совместности или несовместности системы (6.6.1.) можно установить, сравнив ранги ее основной и расширенной матриц. Рассмотрим теперь случай, когда система (6.6.1.) совместна и найдем все ее решения.
При построении общего решения системы (6.6.1.) воспользуемся следующими вспомогательными утверждениями:

Лемма

6.7.1.

Любая линейная комбинация частных решений однородной системы (6.6.1.) также является ее частным решением.

	Доказательство: Пусть - частные решения однородной системы, то есть, . Рассмотрим столбец . По правилам действий с матрицами для него справедливы равенства
	. Лемма доказана.

Лемма

6.7.2.

Сумма некоторого частного решения однородной системы (6.6.1.) и некоторого частного решения неоднородной системы является частным решением неоднородной системы (6.6.1.).

Доказательство:
Пусть - частное решение однородной системы, а - некоторое частное решение неоднородной, то есть . Тогда, по правилам действий с матрицами, справедливы равенства
.
Лемма доказана.

Лемма

6.7.3.

Разность двух некоторых частных решений неоднородной системы (6.6.1.) является частным решением однородной системы (6.6.1.).

Доказательство:
Пусть и - частные решения неоднородной системы, то есть, . Тогда, по правилам действий с матрицами, справедливы равенства
.
Лемма доказана.

Замечания: 1. Из лемм 6.7.1. - 6.7.3. следует, что:

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

Теорема

6.7.1.

Однородная система (6.6.1.) имеет линейно независимых частных решений.

Доказательство:
1. Рассмотрим вначале совместную неоднородную систему (6.6.1.)

и предположим, что матрица базисного минора расширенной матрицы , имеющей ранг r  min{n,m}, расположена в левом верхнем углу последней.
По теореме 6.5.1. (о базисном миноре) последние уравнений являются линейными комбинациями первых r уравнений и, следовательно, их можно отбросить, поскольку они будут тождественно удовлетворяться решениями первых r уравнений. В оставшихся уравнениях перенесем в правые части слагаемые, содержащие неизвестные .
.
Неизвестные называются основными (главными, зависимыми), а неизвестные - свободными (параметрическими, независимыми). Присвоим свободным неизвестным некоторые конкретные значения и рассчитаем по правилу Крамера (теорема 6.4.1.) соответствующие им значения основных неизвестных

j-й столбец

, (6.7.1.)

где , а - базисный минор.

2. Заметим, что из соотношений (6.7.1.), положив , можно найти частное решение неоднородной системы (6.6.1.) . Теперь рассмотрим однородную систему. По линейному свойству определителей (теорема 6.2.3.) получаем выражения для значений неизвестных
(6.7.2.)

где

j -й столбец
Наконец, в матричной форме соотношения (6.7.2.) могут быть записаны в виде
или

^(6.7.3.)

3. Полагая , получим решение . Аналогично при найдем решение . И, продолжая этот процесс, получим на последнем шаге при решение .

Совокупность полученных решений будем называть нормальной фундаментальной системой решений.
4. Покажем теперь, что построенные n-r частных решений однородной системы уравнений (6.6.1.) являются линейно независимыми. Действительно, записав эти решения как строки, получим матрицу вида

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

Определение

6.7.1.

Фундаментальной системой решений для системы линейных уравнений (6.6.1.) называется совокупность любых частных, линейно независимых решений однородной системы (6.6.1.), где - число неизвестных в системе (6.6.1.), а - ее основная матрица. Матрица (6.7.4.) называется фундаментальной.

Теорема

6.7.2.

Каждое частное решение однородной системы (6.6.1.) может быть представлено в виде линейной комбинации частных решений, образующих нормальную фундаментальную систему решений.

Доказательство:
Пусть дано решение однородной системы (6.6.1.) Рассмотрим матрицу размера

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

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

Следствие

6.7.1.

Общее решение неоднородной системы (6.6.1.) может быть дано формулой
, где
является некоторым частным решением неоднородной системы (6.6.1.), а числа - произвольные константы.

Доказательство:
Пусть - некоторое (найденное, например, подбором) частное решение неоднородной системы (6.6.1.), а - ее произвольное решение. Тогда по лемме 6.6.3.

произвольное решение однородной системы (6.6.1.) представимо в виде . Откуда получаем .
Следствие доказано.

Из теорем 6.7.1. и 6.7.2. непосредственно вытекает

Следствие

6.7.2.

Для того чтобы однородная система (6.6.1.) с имела ненулевое решение, необходимо и достаточно, чтобы ранг ее основной матрицы удовлетворял условию .
В частном случае, когда основная матрица системы (6.6.1.) квадратная, условие существования нетривиального решения равносильно равенству .

Иное, полезное для приложений, условие совместности системы линейных уравнений дает

Теорема

6.7.3.

(Фредгольма)

Для того чтобы система (6.6.1.) была совместной, необходимо и достаточно, чтобы каждое решение сопряженной системы

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

Доказательство необходимости:
Пусть система уравнений (6.6.1.) совместна, то есть для каждого ее решения справедливо равенство . Найдем произведение в предположении, что . Имеем

.
Доказательство достаточности:
Пусть для любого решения системы линейных уравнений . Тогда общие решения систем линейных уравнений и совпадают, и для этих систем число линейно независимых решений одинаково. Поэтому, согласно теореме 6.7.1.
или ,
но поскольку ранг матрицы не меняется при ее транспонировании, то имеет место равенство , означающее в силу теоремы 6.6.1. совместность системы линейных уравнений .
Теорема доказана.

Альтернативное доказательство этой теоремы приведено в разделе “Евклидово пространство” (см. теоремы 10.6.4. и 10.6.5.)

Метод Гаусса

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

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

Под “наиболее простым” видом расширенной матрицы мы будем понимать верхнюю треугольную форму (т.е. случай, когда при ), для которой возможно рекуррентное нахождение неизвестных путем лишь решения на каждом шаге процедуры линейного уравнения с одним неизвестным. Ниже приведен пример матрицы размера , имеющей верхнюю треугольную форму.

К элементарным преобразованиям матрицы относятся:

- перестановка строк (перенумерация уравнений)

- перестановка столбцов основной матрицы (перенумерация неизвестных);

- удаление нулевой строки (исключение уравнений, тождественно удовлетворяющихся любыми значениями неизвестных);

- умножение строки на ненулевое число (нормирование уравнений);

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

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

Непосредственной проверкой можно убедиться, что элементарные преобразования любой матрицы могут быть выполнены при помощи умножения ее на матрицы следующего специального вида:
- перестановка строк с номерами i и j матрицы размера mxn осуществляется путем ее умножения слева на матрицу размера mxm, которая, в свою очередь, получается из единичной матрицы путем перестановки в последней i-й и j-й строк.

- умножение i-й строки матрицы на некоторое число осуществляется путем умножения слева на матрицу , которая, получается из единичной, размера mxm , матрицы путем замены в последней i-го диагонального элемента (равного единице) на .

- сложение строк с номерами i и j матрицы осуществляется путем ее умножения слева на матрицу размера mxm , которая, получается из единичной матрицы путем замены в последней нулевого элемента, стоящего в i-й строке и j-м столбце, на единицу (при этом результат суммирования окажется на месте i-й строки исходной матрицы .)
В дальнейшем (см. теорему 8.4.3.) будет показано, что если матрица квадратная и невырожденная и возможно умножение матрицы на матрицу , то справедливо равенство . Поскольку , и , то ранг при рассмотренных выше преобразованиях не меняется.
Проверьте самостоятельно, что будут также справедливы

Теорема

6.8.1.

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

Теорема

6.8.2.

Если умножение матрицы слева на квадратную матрицу , реализующую некоторое преобразование над строками , то умножение справа на реализует то же самое преобразование матрицы , но выполненное над ее столбцами.

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

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

Проиллюстрируем применение метода Гаусса на примере решения следующей системы линейных уравнений.

Задача Решить систему уравнений

6.8.1.

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

2. Приводим ее к верхнему треугольному виду. Для этого:
а) преобразуем в нули все элементы первого столбца, кроме элемента, стоящего в первой строке. Например, для зануления элемента, стоящего во второй строке первого столбца, заменим вторую строку матрицы строкой, которая является суммой первой строки, умноженной на -3 , и второй строки. Аналогично поступаем с четвертой строкой: ее заменяем линейной комбинацией первой и четвертой строк с коэффициентами -5 и 1 соответственно. Третью, естественно, не меняем: там уже имеется необходимый для треугольного вида ноль. В итоге матрица приобретает вид
;
б) выполняем теперь операцию зануления элементов второго столбца, стоящих в его третьей и четвертой строках. Для этого третью строку матрицы заменяем суммой второй и третьей, а четвертую - разностью второй и четвертой. Получаем

;

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

3. Полученная матрица является расширенной матрицей системы линейных уравнений, равносильной исходной системе. Ранг этой матрицы совпадает с рангом исходной. Потому заключаем, что
а) система совместна, поскольку ранг основной матрицы равен рангу расширенной и равен 2 (по теореме 6.6.1., Кронекера-Капелли);
б) однородная система уравнений будет иметь по теореме 6.7.1. линейно независимых решения.
4. Поскольку общее решение неоднородной системы есть общее решение однородной плюс частное решение неоднородной, то нам достаточно найти три любых линейно независимых решения однородной системы и какое-нибудь одно решение неоднородной.
Перепишем исходную систему в преобразованном виде, приняв первое и второе неизвестные за основные, а третье, четвертое и пятое - за свободные.
( 6.8.1.)
Второе уравнение для удобства вычислений умножим на -1, а третье и четвертое уравнения отбросим как удовлетворяющиеся тождественно.
Положив в системе (6.8.1.) свободные неизвестные равными нулю, находим частное решение неоднородной системы . Значения основных неизвестных определяются из легко решаемой системы линейных уравнений
.
Для однородной системы

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

Аналогично получаются второе и третье решения: , .

Окончательно общее решение исходной неоднородной системы в матричном виде может быть записано как:
.

Замечание:

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

Теорема

5.1.4.

Каждая ортогональная матрица второго порядка , для которой может быть представлена в виде , где j - некоторое число, а каждая ортогональная матрица с - в виде .

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

Пусть матрица ортогональная, тогда должны быть справедливы равенства и, следовательно, .

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

причем из этих равенств, как было показано при доказательстве теоремы 5.1.3., следует, что . Рассмотрим вначале случай .
Если из суммы первого и третьего уравнений системы вычесть удвоенное равенство , то мы получим
или
откуда следует, что .

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

Случай рассматривается аналогично.
Теорема доказана.