Найти базисные решения онлайн. Решение систем линейных уравнений методом жордана-гаусса. §1. Системы линейных уравнений

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

Система вида

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

Здесь
- неизвестные,- коэффициенты при неизвестных,
- свободные члены уравнений.

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

Система (1) может быть представлена в матричной форме с помощью уравнения

(2)

.

§2. Совместность систем линейных уравнений.

Назовем расширенной матрицей системы (1) матрицу

Теорема Кронекера - Капелли . Система (1) совместна тогда и только тогда, когда ранг матрицы системы равен рангу расширенной матрицы:

.

§3. Решение систем n линейных уравнений с n неизвестными.

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

(3)

Теорема Крамера .Если главный определитель системы (3)
, то система имеет единственное решение, определяемое по формулам:

т.е.
,

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

Если
, а хотя бы один из≠0, то система решений не имеет.

Если
, то система имеет бесконечно много решений.

Систему (3) можно решить, используя ее матричную форму записи (2). Если ранг матрицы А равенn , т.е.
, то матрицаА имеет обратную
. Умножив матричное уравнение
на матрицу
слева, получим:

.

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

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

Решение. Матрица
невырожденная, так как
, значит, существует обратная матрица. Вычислим обратную матрицу:
.

,

Задание . Решить систему методом Крамера.

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

Пусть дана неоднородная система линейных уравнений вида (1).

Предположим, что система совместна, т.е. выполнено условие теоремы Кронекера-Капелли:
. Если ранг матрицы
(числу неизвестных), то система имеет единственное решение. Если
, то система имеет бесконечно много решений. Поясним.

Пусть ранг матрицы r (A )= r < n . Поскольку
, то существует некоторый ненулевой минор порядкаr . Назовем его базисным минором. Неизвестные, коэффициенты которых образуют базисный минор, назовем базисными переменными. Остальные неизвестные назовем свободными переменными. Переставим уравнения и перенумеруем переменные так, чтобы этот минор располагался в левом верхнем углу матрицы системы:

.

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

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

Получили систему r линейных уравнений сr неизвестными, определитель которой отличен от 0. Она имеет единственное решение.

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

Пример .

,r =2.

Переменные
- базисные,
- свободные.

Сложим уравнения; выразим
через
:

- общее решение.

- частное решение при
.

- базисное решение, опорное.

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

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

Элементарными преобразованиями системы являются:

Умножение уравнения на число, отличное от нуля;

Сложение уравнения, умноженного на любое число, с другим уравнением;

Перестановка уравнений;

Отбрасывание уравнения 0 = 0.

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

Пример .

Решение. Выпишем расширенную матрицу системы:

.

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

Замечание . Если при выполнении элементарных преобразований получено уравнение вида 0= к (где к 0), то система несовместна.

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

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

В исходную таблицу записывают расширенную матрицу системы. Далее приступают к выполнению преобразований Жордана:

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

2. Элементы ключевой строки делят на ключевой элемент.

3. Ключевой столбец заполняют нулями.

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

Пример . Найти общее решение и базисное решение системы уравнений:

Решение.

Общее решение системы:

Базисное решение:
.

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

§6. Нахождение опорных решений

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

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

1. В исходной системе все свободные члены должны быть неотрицательны:
.

2. Ключевой элемент выбирают среди положительных коэффициентов.

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

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

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

Пример.

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

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

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

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

Пусть дана однородная система

Рассмотрим соответствующую неоднородную систему

С помощью матриц

эти системы можно записать в матричном виде.

A `x = . (8.3)

A `x = `b . (8.4)

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

Теорема 8.23. Линейная комбинация решений однородной системы (8.1) является решением однородной системы.

Доказательство. Пусть `x , `y и `z - решения однородной системы. Рассмотрим `t = α`x + β`y + γ`z , где α, β и γ - некоторые произвольные числа. Так как `x , `y и `z являются решениями, то A `x = , A `y = и A `z = . Найдем A `t .

A `t = A · (α`x + β`y + γ`z ) = A · α`x + A · β`y + A · γ`z =

= αA `x + βA `y + γA `z = α + β + γ = .

A `t = Þ`t является решением системы.

Теорема 8.24. Разность двух решений неоднородной системы (8.2) является решением однородной системы (8.1).

Доказательство. Пусть `x и ` y - решения системы. Рассмотрим `t = `x - `y .

A `x = `b , A `y = `b

A `t = A (`x - `y ) = A `x - A `y = `b - `b =.

`t = `x + `y является решением однородной системы.

Теорема 8.25. Сумма решения однородной системы с решением неоднородной системы есть решение неоднородной системы.

Доказательство. Пусть `x - решение однородной системы, `y - решение неоднородной системы. Покажем, что `t = `x + `y - решение неоднородной системы.

A `x = , A `y = `b

A `t = A (`x + `y ) = A `x + A `y = `b + = `b .

A `t = `b Þ`t является решением неоднородной системы.

Рассмотрим однородную систему

x 1 = x 2 = … = x n

Теорема 8.26.

Доказательство. с 1 , с 2 , …, с n m

А линейно зависима. А n , т. е. r(A) < n.

Следствие.

Доказательство. Так как r(A) < n

Совместность однородной системы

Рассмотрим однородную систему

Однородная система всегда совместна, так как имеет тривиальное (нулевое) решение x 1 = x 2 = … = x n = 0. Выясним, когда данная система имеет нетривиальное решение.

Теорема 8.26. Однородная система имеет нетривиальное решение тогда и только тогда, когда ранг матрицы, составленной из коэффициентов при неизвестных, меньше числа неизвестных.

Доказательство. Пусть система имеет нетривиальное решение. Это может быть тогда и только тогда, когда найдутся числа с 1 , с 2 , …, с n , не все равные нулю, при подстановке которых в систему мы получим m тождеств. Эти m тождеств можно записать в виде

Следовательно, система векторов-столбцов матрицы А линейно зависима. А это может быть тогда и только тогда, когда ранг системы векторов-столбцов меньше n , т. е. r(A) < n.

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

Доказательство. Так как r(A) < n , то столбцы матрицы линейно зависимы и, следовательно, определитель матрицы равен нулю.

Общее решение однородной системы

Система (8.1) всегда имеет тривиальное решение. Если ранг матрицы, составленной из коэффициентов при неизвестных, меньше числа неизвестных, то система (8.1) имеет нетривиальные решения.

1) r(A) = n - система (8.1) имеет только тривиальное решение:

2) r(A) = r < n - система (8.1) имеет нетривиальные решения.

Количество свободных переменных во втором случае будет равно n - r , а базисных r. Давая свободным переменным произвольные значения, мы будем получать различные решения системы (8.1), т. е. любому вектору размерности n - r

(с r + 1 , c r + 2 , …, c n)

будет соответствовать решение системы (8.1)

(с 1 , c 2 , …, c r , c r + 1 , …, c n).

Определение 8.51. Фундаментальной системой решений однородной системы (8.1) называется максимальная линейно независимая система решений системы (8.1). Фундаментальная система содержит n - r линейно независимых решений системы (8.1).

Чтобы получить фундаментальную систему решений, нужно в (n - r) -мерном пространстве взять линейно независимую систему из n - r векторов и по ним построить соответствующие решения системы (8.1). Полученные решения будут образовывать фундаментальную систему решений `x 1 , `x 2 , ..., `x n-r . Так как эта система максимальна, то любое решение системы (8.1) можно представить в виде линейной комбинации решений фундаментальной системы `x = α 1 `x 1 ‌ α 2 `x 2 ‌ ... ‌ α n-r `x n-r . Полученное выражение является общим решением однородной системы (8.1).

Пример 8.25.

x 1 , x 2 - базисные, x 3 , x 4 , x 5 - свободные. Два последних уравнения линейно выражаются через два первых, поэтому их можно отбросить:

Выразим базисные переменные.

Умножим первое уравнение на 2 и сложим со вторым. Результат разделим на 8.

Умножим первое уравнение на 2, второе на -3 и сложим полученные уравнения. Результат разделим на 8.

В качестве значений свободных переменных возьмем координаты векторов трехмерного единичного базиса.

`x = α 1 `x 1 + α 2 `x 2 + α 3 `x 3 - общее решение однородной системы.

Сумма общего решения однородной системы (8.1) с любым решением неоднородной системы (8.2) является общим решением неоднородной системы (8.2).

Применение линейной алгебры в экономике

Производственные показатели

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

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

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

`q = (20, 50, 30, 40) - вектор ассортимента;

`s = (5, 2, 7, 4) - вектор расхода сырья;

= (10, 5, 15, 8) - вектор затрат рабочего времени;

`p = (30, 15, 45, 20) - ценовой вектор.

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

S = `q `s = 100 + 100 + 210 + 160 = 570 кг,

Т = `q = 1220 ч, P = `q `p = 3500 ден. ед.

Расход сырья

Предприятие выпускает четыре вида изделий с использованием четырех видов сырья. Нормы расхода сырья даны как элементы матрицы А :

Вид сырья 1 2 3 4

Вид изделия.

Требуется найти затраты сырья каждого вида при заданном плане выпуска каждого вида изделия: соответственно, 60, 50, 35 и 40 ед.

Составим вектор-план выпуска продукции:

`q = (60, 50, 35, 40).

Тогда решение задачи дается вектором затрат, координаты которого и являются величинами затрат сырья по каждому его виду: этот вектор затрат вычисляется как произведение вектора `q на матрицу А :

Конечный продукт отрасли

Отрасль состоит из n предприятий, выпускающих по одному виду продукции каждое: обозначим объем продукции i -го предприятия через х i . Каждое из предприятий отрасли для обеспечения своего производства потребляет часть продукции, выпускаемой им самим и другими предприятиями. Пусть а ij - доля продукции i -го предприятия, потребляемая j -м предприятием для обеспечения выпуска своей продукции объема х j . Найдем величину у i - количество продукции i -го предприятия, предназначенной для реализации вне данной отрасли (объем конечного продукта). Эта величина легко может быть подсчитана по формуле

Введем в рассмотрение квадратную матрицу порядка n , описывающую внутреннее потребление отрасли

A = (a ij); i,j = 1, 2, ..., n.

Тогда вектор конечного продукта является решением матричного уравнения

`x - A `x = `y

с использованием единичной матрицы Е получаем

(E - A )`x = `y

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

Получим вектор объемов конечного продукта, предназначенного для реализации вне отрасли, состоящей из трех предприятий:

Прогноз выпуска продукции

Пусть C = (c ij); i = 1, 2, ..., m, j = 1, 2, ..., n , - матрица затрат сырья t видов при выпуске продукции n видов. Тогда при известных объемах запаса каждого вида сырья, которые образуют соответствующий вектор

`q = (q 1 , q 2 , ..., q m)

вектор-план `x = (x 1 , x 2 , ..., x n ) выпуска продукции определяется из решения системы m уравнений с n неизвестными:

C `x T = `x T ,

где индекс «T » означает транспонирование вектора-строки в вектор-столбец.

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

Требуется определить объем выпуска продукции каждого вида при заданных запасах сырья.

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

Обозначим неизвестные объемы выпуска продукции через х 1 , х 2 и х 3 . Тогда при условии полного расхода запасов каждого вида сырья можно записать балансовые соотношения, которые образуют систему трех уравнений с тремя неизвестными:

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

x 1 = 150, x 2 = 250, x 3 = 100.

Рассмотрим произвольную систему

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

(16.2)

называется системой в базисной форме.

Неизвестные называются свободными, а - несвободными или базисными неизвестными. Выбор базисных и свободных переменных может быть различным в общем случае.

Система (16.1) имеет решение в том и только том случае, когда ее можно записать в базисной форме.

Перенесем все свободные неизвестные в правые части уравнений системы (16.2). Тогда получим

(16.3)

Если свободным неизвестным придать конкретные числовые значения, то по формулам (16.3) можно вычислить базисные неизвестные. Таким образом, базисная система (16.2) всегда имеет решение. Причем возможны следующие варианты.

1). m =n , то есть число уравнений равно числу неизвестных. В этом случае все переменные базисные. Система имеет вид

и является определенной, так как имеет единственное, очевидное решение. Матрицей такой системы является единичная матрица

.

2). m Тогда система с расширенной матрицей вида