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

27

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

Неизвестные или переменные уравнений общепринято обозначать буквами х₁, х₂,… х_n. Уравнение называется линейным относительно переменных х₁, х₂,… х_n, если оно записано в виде (1)

Здесь - произвольные действительные числа.

Набор чисел называется решением уравнения (1), если в результате подстановки этих чисел вместо неизвестных уравнение превращается в алгебраическое тождество

.

Пусть задана совокупность уравнений вида (1). В общем виде такая система уравнений записывается так:

(2)

В общем виде система уравнений (2) содержит m уравнений и n неизвестных. Коэффициенты при неизвестных имеют два индекса - первый индекс указывает номер уравнения, а второй - номер неизвестной. Коэффициенты b₁, b₂, …b_m, называются свободными элементами уравнений.

Система уравнений называется неоднородной, если хотя бы один свободный член уравнения не равен нулю, однородной - если все свободные члены уравнений равны нулю.

Система уравнений называется совместной, если она имеет хотя бы одно решение.

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

Система уравнений, не имеющая решений, называется несовместной.

Рассмотрим графическую интерпретацию совместной и несовместной систем на примере решения системы двух уравнений.

Пример 3.1.

а)

Решением системы являются корни х₁ = х₂ = 1.

Система уравнений определенна, т. к. имеет единственное решение.

Рассмотрим графическую интерпретацию единственности решения.

Уравнения системы в координатах Х₁ОХ₂ представляют прямые. Первое уравнение - прямая, отсекающая на осях ОХ₁ и ОХ₂ отрезки, равные 2. Второе уравнение - прямая, проходящая через начало координат. Эти прямые пересекаются в одной точке М, что определяет единственность решения (рис. 1.).

Рис. 1.

б)

Эта система имеет бесконечное множество решений. Второе уравнение получается из первого умножением обеих его частей на 2. Поэтому система по существу состоит из одного уравнения с двумя неизвестными. Геометрически (рис. 2) решение такой системы изображается точками двух совпадающих прямых.

Рис. 2.

в)

Эта система уравнений является несовместной. Геометрически (рис. 3) это означает, что прямые линии, которые задаются этими уравнениями, параллельны.



Рис. 3.

Для формулировки условия совместности системы введем понятия матрицы системы и расширенной матрицы системы.

Матрица системы - матрица, составленная из коэффициентов при неихвестных.

(3)

Расширенная матрица системы - матрица системы с добавлением столбца свободных членов.

(4)

Признак совместности системы формулирует теорема Кронекера-Канелли.

Теорема. Для совместности системы линейных алгебраических уравнений необходимо и достаточно, чтобы ранг матрицы системы r(A) равнялся рангу расширенной матрицы этой системы r(C),

т.е. r(A) = r(C).

Если r(A) = r(C), то этот ранг является рангом совместной системы.

Замечание 1. Если ранг совместной системы r равен числу неизвестных n (r=n), то система имеет единственное решение.

Замечание 2. Если ранг совместной системы r меньше числа неизвестных n (r<n), то система имеет бесконечное множество решений.

Пример 3.2.

Исследовать систему уравнений на совместность.

Запишем матрицу системы и определим ее ранг.

Начнем с определения величины минора третьего порядка.

Т.к. минор третьего порядка оказался равным нулю, то r(A) ? 2. Для того, чтобы r(A) = 2 достаточно показать, что какой-либо минор второго порядка не равен нулю.

Например, минор , то доказано, что r(A) = 2.

Определяем ранг расширенной матрицы

Вычислим значение миноров третьего порядка, образованных матрицей С

Значит r(С) = 3.

Т.к. r(A) ? r(C), то система уравнений несовместна.

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

Рассмотрим систему уравнений, в которой число уравнений m равно числу неизвестных n (m = n). Такая система имеет вид

(5)

Введем в рассмотрение матрицы

матрицу системы уравнений (6)

матрицу - столбец неизвестных (7)

матрицу - столбец свободных членов (8)

На основании правил умножения матриц и условия равенства матриц систему уравнений (5) можно записать следующим образом:

или коротко в матричной форме

(9)

Матрицу - неизвестных Х из уравнения (9) получим, умножив уравнение (9) на обратную матрицу А^-1

Т.к. , то (10)

Это и есть решение системы (5) в матричной форме. Из (10) следует, что система уравнений может быть решена при условии, если существует обратная матрица, т.е. если матрица А невырожденная.

Таким образом решение системы уравнений (5) матричным способом сводится к вычислению обратной матрицы А^-1.

Решить матричным способом систему уравнений

Запишем матрицы , ,

Чтобы применить формулу (10), нужно найти обратную матрицу А^-1 к матрице А.

Обратная матрица определяется по формуле .

Определитель матрицы А

Т.к. detА ? 0, решение системы можно найти матричным методом.

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

; ; .

; ; .

; ; .

Союзная матрица - есть матрица, составленная из транспонирования алгебраических дополнений.

Обратная матрица

Наконец, находим матрицу-столбец Х, используя правило умножения матриц

.

Таким образом, х₁ = 4; х₂ = 2; х₃ = 1.

Проверка: подставим найденные корни в одно из уравнений системы. Например, подставляя в первое, получим тождество 4 - 2 + 1 = 3. Это значит, что решение найдено верно.

Решение неоднородных систем линейных алгебраических уравнений методом Крамера

Рассмотрим вывод формул Крамера на примере системы трех уравнений (11).

 (11)

Составим определитель из коэффициентов при неизвестных (12), который назовем главным

(12)

Умножим обе части определителя на неизвестную х₁. В правой части равенства на основании свойства определителя умножим на х₁ один из столбцов. В рассматриваемом случае на х₁ умножим 1-й столбец. Смысл этой операции будет понятен из дальнейших рассуждений.

(13)

Применяя свойство инвариантности определителя, умножим 2-й столбец на х₂ и сложим с 1-м. Получим:

(14)

Применим свойство инвариантности определителя еще раз. Умножим третий столбец на переменную х₃ и сложим с первым. Получим:

 (15)

Сравнивая первый столбец определителя (15) и левую часть уравнений (11), видно, что этот столбец можно заменить на столбец свободных членов. Сделав это, получим:

(16)

Полученный таким образом определитель называется первым вспомогательным определителем (16), который обозначается как ?х₁. Из (16) следует, что если ? ? 0, то первый корень системы будет равен

(17)

По аналогии выводятся формулы для определения значения переменных х₂ и х₃. Они имеют вид:

(18)

(19)

В числителе формулы (18) находится второй вспомогательный определитель, формулы (19) - 3-й вспомогательный определитель.

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

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

Решение системы по методу Крамера, рассмотренное на примере системы 3-х уравнений, может быть обобщен в виде следующей теоремы.

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

, , …, ;

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

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

2. Если все вспомогательные определители равны нулю, система имеет бесконечное множество решений.

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

1) 2)

3)

1. Составляем из коэффициентов при неизвестных главный определитель и определяем его.

(определитель посчитан в примере 3.3)

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

, , ;

Определим величины вспомогательных определителей ?х₁, ?х₂, ?х₃.

Первый вспомогательный определитель

Второй вспомогательный определитель

Третий вспомогательный определитель



Эти корни были получены ранее в примере 3.3.

2. Определяем величину главного определителя системы.

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

.

Т.к один из вспомогательных определителей не равен нулю, система несовместна, т.е. решения не имеет. Система уравнений противоречива. Действительно, сложив 1-е и 2-е уравнения, получим . Сравнивая это уравнение с третьим уравнением системы, приходим к абсурду

4 = 5!?

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

.

Определяем величины вспомогательных определителей.

.

.

.

Т.к. при условии, что ? = 0 все вспомогательные определители оказались равными нулю, система имеет бесконечное множество решений.

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

Исключим из рассмотрения одно из уравнений, например, третье. Будем иметь систему

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

, при х₃ = с, получим



Решаем систему, исключая переменную х₁, для чего умножим первое уравнение на 2- и сложим со вторым

> .

Подставляя найденное значение для х₂ в любое уравнение, например, первое, получим

> .

; .

Таким образом, решением системы будут корни:

; ; , где .

Решение системы уравнений методом Гаусса

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

Рассмотрим алгоритм метода Гаусса на примере решения различных систем уравнений.

Найти решение систем уравнений методом Гаусса.

1. 2) 3)

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

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

Ведущее уравнение запишем первым в системе

Из системы уравнений видно, что для исключения неизвестной х₁ из второго уравнения нужно первое уравнение умножить на (-2) и сложить со вторым. Для исключения неизвестной х₁ из третьего уравнения нужно первое уравнение умножить на (-4) и сложить с третьим.

В результате этих операций система уравнений будет иметь вид:

Теперь за ведущее примем второе уравнение и исключим неизвестную х₂ из третьего уравнения. Для этого второе уравнение нужно умножить на (-8) и сложить с третьим.

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

Это были операции прямого хода. В результате исключения неизвестных х₁ и х₂ получена система треугольного вида.

Операции обратного хода.

Из последнего уравнения определяется ;

Из второго уравнения определяется ;

Из первого уравнения определяется .

В рассмотренном примере последнее уравнение таково, что приводит к единственному решению.

2. Примем первое уравнение за ведущее



Исключим переменную х₁ из 2-го и 3-го уравнений, для чего первое уравнение умножим на (-2) и сложим со вторым, затем первое уравнение умножим на (-3) и сложим с третьим. Получим:

Эта система приводится к следующей

Результат, когда при исключении неизвестных левая часть одного из уравнений превращается в нуль, а правая не равна нулю, означает, что система решения не имеет. Этот же результат был получен ранее при рассмотрении примера 3.4 (2).

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

Примем первое уравнение за ведущее. Исключим с его помощью переменную х₁ из второго и третьего уравнений. В результате получим систему

Вычитая третье уравнение из второго, получим

Решая систему , получим

; ; .

Этот результат был получен ранее при рассмотрении примера 3.4 (3).

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

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

(20)

Очевидно, такая система имеет нулевое (тривиальное) решение

Если ? ? 0, то такая система имеет единственное решение, корни которого . Других ненулевых решений нет.

Если ? = 0, то так как все вспомогательные определители системы равны нулю, то система имеет бесконечное множество решений.

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

Основной определитель системы

Значит система совместна и неопределенна, т.е. имеет бесконечное множество решений.

Т.к. одно из уравнений лишнее (оно является следствием двух других), имеем систему двух уравнений с тремя неизвестными. Решается она по аналогии с примером 3.4 (3).

(21)

Положим, х₃ = с. Тогда система (21) запишется:



> ;

Таким образом корнями системы будут

; ; х₃ = с.

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

1. Кондитерская фабрика для производства трех видов карамели А, В, С использует три вида сырья: сахарный песок, патоку и фруктовое пюре. Нормы расхода сырья каждого вида на производство 1 т карамели определенного вида приведены в таблице. В ней также указано общее количество сырья каждого вида, которое может быть использовано фабрикой. Найти план производства карамели, если все сырье должно быть использовано.

Вид сырья	Нормы расхода сырья, т на 1 т карамели	Общее количество сырья, т.
	А	В	С
Сахарный песок	0,6	0,5	0,6	900
Патока	0,4	0,4	0,3	600
Фруктовое пюре		0,1	0,1	120

Обозначим через х₁, х₂, х₃ количество изготовленной карамели вида А, В и С соответственно. Тогда для производства такого количества карамели потребуется сахара. По условию должно быть израсходовано 900 т. сахара. Таким образом, должно выполняться равенство

Аналогичные рассуждения приводят к следующим уравнениям

Для определения х₁, х₂, х₃ имеем систему уравнений

Задачу можно решить любым рассмотренным методом. Решим ее методом Крамера.

; (т).

; (т).

; (т).

Найденные значения переменных определяют план производства карамели. Карамели вида А будет изготовлено 420 т, вида В - 720 т, вида С - 480 т.

2. Предприятие выпускает продукцию трех видов: Р₁, Р₂, Р₃ и использует сырье двух типов: S₁ и S₂. Нормы расхода сырья характеризуются матрицей , где каждый элемент а_ij (i = 1, 2, 3; j = 1, 2) показывает, сколько единиц сырья j-того типа расходуется на производство продукции i-того вида. План выпуска продукции задан матрицей-строкой С = (100 80 130), стоимость единицы каждого типа сырья (ден. ед.) - матрицей-столбцом.

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

Затраты 1-го и 2-го типа сырья могут быть найдены как сумма произведений норм расхода сырья на количество выпускаемой продукции, т.е.:

ед.

ед.

Используя матричную запись затрат сырья матрица-строка определится как произведение матрицы-строки выпуска продукции на технологическую матрицу А

Общая стоимость сырья

Ф = 730•30 + 980•50 = 70900 ден. ед.

Или в матричной форме

ден. ед.

3. С двух заводов поставляются автомобили для двух автохозяйств, потребности которых соответственно 200 и 300 машин. Первый завод выпустил 350 машин, а второй - 150 машин. Известны затраты на перевозку машин с завода в каждое автохозяйство.

ЗАВОД	Затраты на перевозку в автохозяйство, ден. ед.
	1	2
1	15	20
2	8	25

Минимальные затраты на перевозку равны 7950 ден. ед. Найти оптимальный план перевозок машин.

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

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

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

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

Первое автохозяйство получает 200 автомашин с заводов 1 и 2

.

Второе автохозяйство получает 300 автомашин с тех же заводов

.

Эти уравнения и уравнение материальных затрат образуют систему

Получим систему 5-ти уравнений с четырьмя неизвестными. Решим ее методом Гаусса.

Выполним операции прямого хода.

1 шаг. Считая 1-е уравнение ведущим, исключаем неизвестную х₁₁ из 3-го и 5-го уравнений.

2 шаг. Исключаем неизвестную х₂₁ из 3-го и 5-го уравнений, считая 2-е уравнение ведущим

Т.к 3-е и 4-е уравнения одинаковы, одно из них исключаем



3 шаг. Исключаем неизвестную х₁₂ из 5-го уравнения, принимая 4-е уравнение за ведущим

Выполняем операции обратного хода.

Из последнего уравнения следует х₂₂ = 0.

Из предпоследнего х₁₂ = 300.

Из первого получаем х₁₁ = 50.

Из второго уравнения х₂₁ = 150.