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

Глава I. Математическое введение. Предмет методов оптимизации

Элементы линейной алгебры

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

Система линейных уравнений - это система вида

(1.1)

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

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

Метод Гаусса вспомним на следующих примерах.

1.1.1. Пример. Решить системы.

a) б)

в)

Решение. а) 1) Поменяем местами первое и второе уравнения системы. Тогда получим систему, равносильную данной:

2) Вычтем первое уравнение (полученной системы), умноженное на 3, из второго:

Аналогично, первое уравнение (полученной системы), умноженное на 2, вычитаем из 3-го, и его же, умноженное на 4, вычитаем из 4-го; приходим к системе:

В результате пришли к системе, в которой из уравнений со 2-го по 4-е исключена неизвестная x ₁. В этом и заключается метод Гаусса ¾ метод последовательного исключения неизвестных. На следующем шаге из 3-го и 4-го уравнений исключаем неизвестную x ₂. Это можно осуществить, например, следующим образом: 2-е уравнение, умноженное на , вычитаем из 3-го, и 2-е уравнение, умноженное на , вычитаем из 4-го. Но в этом случае придётся оперировать дробными коэффициентами, что весьма неудобно. Во избежание этого можно поступить так: из 3-го уравнения, умноженного на 17, вычесть 2-е, умноженное на 13, и из 4-го, умноженного на 17, вычесть 2-е, умноженное на 31. Но и здесь свои неудобства ¾ слишком много арифметических операций, что ведёт к повышению трудоёмкости и вероятности допущения ошибок.

Заметим, что в первом шаге (при исключении неизвестной x ₁ из 2-го ¾ 4-го уравнений), мы добились того, что коэффициент при x ₁ в 1-м уравнении оказался равным 1. Постараемся, чтобы коэффициент при x ₂ во 2-м уравнении равнялся либо 1, либо -1. Для этого

4) сумму 2-го и 3-го уравнений вычтем из 4-го:

5) поменяем местами в полученной системе 2-е и 4-е уравнения:

6) В полученной системе 2-е уравнение, умноженное на 13, вычитаем из 3-го, и, умноженное на 17, вычитаем из 4-го:

Таким образом, из 3-го и 4-го уравнений исключили неизвестную x ₂.

7) Умножим 2-е уравнение на -1, а 3-е прибавим к 4-му:

Таким образом, получили систему равносильную исходной, в которой в уравнениях со 2-го по 4-е исключена неизвестная x ₁, в 3-м и 4-м исключена неизвестная x ₂, в 4-м ¾ неизвестная x ₃. Она имеет так называемый «треугольный вид» (под главной диагональю матрицы полученной системы стоят нули, причём диагональные элементы ¾ ненулевые).

8) Из последнего уравнения находим x ₄=1, подставляя которое в предпоследнее (3-е), находим x ₃=0, а из 2-го находим x ₂=3. Наконец, подставляя найденные значения x ₂=3, x ₃=0 и x ₄=1 в 1-е уравнение системы, находим x ₁=1.

Ответ: (1; 3; 0; 1).

б) Вычтем из второго уравнения системы первое и поменяем их местами:

(1.2)

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

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

á(1) 1-е уравнение системы (1.1.4), умноженное на 2, вычитаем из 2-го, и, умноженное на 5, вычитаем из 3-го, а 2-е уравнение вычитаем из 4-го.

(2) Последнее уравнение, умноженное на 3, прибавляем ко 2-му, а 3-е делим на 2.

(3) Умножая 2-е уравнение на 8, вычитаем из 3-го, и, умножая его же на 4, прибавляем к 4-му.

(4) Из 3-го и 4-го находим x ₄.ñ

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

в) Последовательно исключаем переменные:

á(1) Исключили из 2-го, 3-го и 4-го уравнений, вычитая 1-е уравнение, умноженное на соответствующие коэффициенты при x ₁. При этом оказалось, что из этих уравнений исключена также неизвестная x ₂.

(2) 2-е и 3-е уравнения равносильны ¾ они отличаются только знаком. Поэтому одно из них, например, 2-е, исключаем из системы. После этого к последнему уравнению прибавляем 2-е (бывшее 3-е в предыдущей системе).ñ

Таким образом, мы пришли к системе, которая имеет так называемый трапециедальный вид (так мы её называем потому, что её матрица элементарными преобразованиями приводится к трапециедальному виду:

® ®

В этой системе, например, x ₂ и x ₄, могут принимать произвольные значения, скажем, x ₂= a, x ₄= b. Тогда эта система перепишется в виде

откуда находим последовательно x ₃= + b и x ₁= - -2 a - b.

Неизвестные x ₂ и x ₄ в данном случае ¾ свободные, x ₁, x ₃, x ₅ ¾ связанные. В качестве связанных берутся те неизвестные, коэффициенты при которых в последней системе образуют треугольную матрицу. Поэтому в качестве свободных неизвестных можно было взять x ₂ и x ₅, а в качестве связанных ¾ x ₁, x ₃ и x ₄.

Рассмотрим решение системы в этом случае, то есть в случае, когда в качестве свободных взяты неизвестные x ₂ и x ₅, а в качестве связанных ¾ x ₁, x ₃ и x ₄. В этом случае имеем

Последовательно находим x ₄=-5+ b, x ₃= - + b и x ₁= - -2 a - b и множество решений исходной системы запишется так: {(- -2 a - b; a; - + b; -5+ b; b) | a, b Î R }.

Ответ: {(- -2 a - b, a, + b, b, 5+ b) | a, b Î R } или

{(- -2 a - b; a; - + b; -5+ b; b) | a, b Î R }.

Решение системы методом Гаусса можно свести к элементарным преобразованиям строк её расширенной матрицы. Действительно, работая с системой, мы работаем, по существу, с коэффициентами и свободными членами уравнений системы, из которых составлена её матрица. Продемонстрируем это на примере 1.1.1.

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

® ® ®

® ® ®

Ä

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

Ä . Это значит, что

á(1) Разделили последнюю строку на -29.

(2) Последнюю строку вычли из 1-й, прибавили ко 2-й, и, умноженную на 10, прибавили к 3-й.

(3) 3-ю строку вычли из 1-й.

(4) 2-ю строку, умноженную на 7, вычли из 1-й.ñ

Аналогично имеем

® ® ® ® ® .

Последние две строки означают, что x ₄= - и x ₄= - ¾ противоречие.

в) ®

® Ä

á(1) Поменяли 2-ю и 3-ю строки и к 3-ей строке прибавили 2-ю.

(2) Из рассмотрения исключается 3-я строка, соответствующая равенству 0=0.ñ

Далее, перенесём вправо от вертикальной черты 2-й и 4-й столбцы, поменяв знаки при элементах на противоположные. Это соответствует тому, что неизвестным x ₂ и x ₄ придаются свободные значения a и b соответственно, и они переносятся в правую часть. В левой части остаются связанные неизвестные, коэффициенты при которых образуют треугольную подматрицу, после чего эта подматрица элементарными преобразованиями строк преобразуется в единичную:

Ä ®

Последняя матрица означает, что где a, b Î R.

á(3) Из 1-й строки вычли последнюю.

(4) 2-ю строку, умноженную на 3, вычли из 1-й.ñ

При решении практических задач применяется модификация метода Гаусса. Это - Метод Жордана-Гаусса. Он заключается в том, что очередная неизвестная исключается из всех уравнений, кроме одного уравнения, а в уравнении, из которого она не исключается, коэффициент при неизвестной приводится к 1. В результате, если система совместна, она приводится к виду

в предположении, что x ₁, x ₂, …, x_k - связанные неизвестные.

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

1.1.2. Пример. Решить систему методом Жордана-Гаусса:

Решение. Так как коэффициент при x ₁ в первом уравнении равен 1, то первое уравнение берём в качестве ведущего. После преобразований, совпадающими с преобразованиями этой системы в примере 1.1.1, приходим к системе

Разделим второе уравнение на -4: ; и, умножив на 3, вычтем из первого, умножив на 4, вычтем из претьего и прибавим к червёртому:

Удаляем из системы тривиальное уравнение 0=0:

Так как из первого и второго уравнений x ₅ уже исключена, то в качестве базисных можно взять неизвестные x ₁, x ₃, x ₅, а x ₂, x ₃ - свободные. Полагая x ₂= a и x ₄= b, получаем x ₁=- -2 a + b, x ₃= + b, x ₅=5+ b.

Ответ: {(- -2 a + b, a, + b, b, 5+ b) | a, b Î R }.

Замечание. Как и в случае метода Гаусса, элементарные преобразования системы равносильны преобразованиям расширенной матрицы системы:

® ®

® ®

Как известно, ранг матрицы определяется по ненулевому минору максимального порядка.

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

Так, в предыдущей системе, полученной методом Жордана-Гаусса, неизвестные x ₁, x ₂, …, x_k - базисные, остальные неизвестные - свободные.

Так как базисных миноров, вообще говоря, не один, то и групп базисных неизвестных - не одна.

Если зафиксированы базисные неизвестные, то остальные неизвестные называются свободными.

В методах Гаусса и Жордана-Гаусса исключаются как раз базисные неизвестные. В общем случае исключение неизвестных можно начинать с любой, например, с той, у которой коэффициент равен ±1. На очередном шаге выбирается та неизвестная, коэффициент при которой не равен нулю. Например, после исключения х ₁ коэффициент при х ₂ может оказаться равным нулю и тогда можно выбирать любую неизвестную х_l, для которой в системе ¹0. Как правило, выбирают такую х_l, что =…= =0, а ¹0. И т.д. Либо выбирают такую х_l, что = ±1. Поэтому, вообще говоря, матрица окончательной системы имеет вид, в котором под ненулевыми элементами некоторой строки (некоторых строк) стоят сразу несколько нулей:

где ¹0 и ¹0.

Ведущей неизвестной шага называется неизвестная, которая исключается на данном шаге. То уравнение, с помощью которого она исключается, и в котором она остаётся, называется ведущим уравнением. В методе Жордана-Гаусса это то уравнение, в котором ведущая неизвестная остаётся.

Преобразование системы, равносильно элементарным преобразованиям строк её расширенной матрицы. В этом случае вместо термина «ведущая неизвестная» применяется понятие ведущий столбец, а вместо термина «ведущее уравнение» - ведущая строка.

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

Допустим, к системе (1.1) необходимо применить метод Жордана-Гаусса с условием неотрицательности. Прежде всего, если имеются уравнения, в которых свободные члены отрицательны (b_i <0), то, умножив это уравнение на -1, мы добьёмся, чтобы свободные члены всех уравнений были неотрицательны. Поэтому считаем, что в системе (1.1) для всех i =1, 2, …, m имеем b_i ≥0.

Если среди коэффициентов при x ₁ имеются положительные, то выберем в качестве ведущего уравнения то, в котором является минимальным. Тогда при исключении x ₁ из j -го уравнения мы i -е уравнение, делённое на a_{i 1}, умножаем на a_{j 1} и вычитаем из j -го. Другими словами, i -е уравнение, умноженное на , вычитается из j -го. В результате, в новой системе j -й свободный член преобразуется в = b_j - = b_j - a_{j 1}. Покажем, что ≥0. Имеем a_{i 1}>0 в силу выбора, b_i ≥0, и если a_{j 1}≤0, то в силу b_j ≥0 имеем ≥0. Если a_{j 1}>0, то в силу ≥ (мы выбираем из всех положительных коэффициентов при x ₁ тот, при котором отношение свободного члена к нему будет минимальным) имеем - ≥0 Û b_j - a_{j 1}≥0, то есть снова ≥0. В результате исключения x ₁ из всех уравнений (кроме ведущего), получаем систему, в которой все свободные члены неотрицательны. Например, если минимальное достигается при i =1, то приходим к системе

в которой ≥0 (не исключено, что некоторые уравнения вообще исключаются из системы). Если минимальное достигается при i =2, то приходим к системе

и т.д.

На следующем шаге выбираем среди коэффициентов при x ₂ в тех уравнениях, из которых x ₁ исключена, положительные коэффициенты, по ним берём в качестве ведущего то уравнение, в котором достигается минимум , и исключаем из всех уравнений (кроме из ведущего). При этом не должен превышать отношение свободного члена к коэффициенту при x ₂ в уравнении, в котором x ₁ уже исключена. Другими словами, минимальное должно достигаться по всем уравнения и i не должен совпадать с номером уравнения, из которого x ₁ исключено. В противном случае x ₁ не является базисной. И в качестве первой базисной либо необходимо брать другую, например, x ₂, либо в качестве второй базисной необходимо брать другую.

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

Рассмотрим метод на примере.

1.1.3. Пример. Преобразовать систему методом Жордана-Гаусса с условием неотрицательности:

Решение оформим в виде преобразования расширенной матрицы системы:

.

В качестве первой базисной неизвестной возьмём x ₁. Имеем, что min достигается в первой строке (уравнении) матрицы. Поэтому ведущей строкой является первая. Её делим на 3 и, умножив на 2, вычитаем из второй, и, умножив на 3, вычитаем из последней:

.

В качестве второй базисной неизвестной брать x ₂ нельзя, так как коэффициенты при x ₂ во втором и третьем уравнениях отрицательны. Поэтому в качестве второй базисной неизвестной берём x ₃. При этом min = достигается во втором уравнении, и коэффициент при x ₃ в первом уравнении отрицателен. Таким образом, ведущим уравнением при исключении x ₃ будет второе. Его мы делим на . Получается строка , которую, умноженную на , прибавляем к первой, и умноженную на 9, вычитаем из третьей:

.

Так же, как и в случае с x ₂, x ₄ нельзя брать в качестве базисной. Остаётся единственный вариант: x ₅. Он подходит, так как min = достигается в третьем уравнении. Это означает, что x ₅ исключается из первого и второго уравнений, и, таким образом, x ₁, x ₃ и x ₅ образуют базисные неизвестные (довести до конца!).

Ответ: