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

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

a11x1 + a12x2 +… + a1nxn = b1, a21x1 + a22x2 +… + a2nxn = b2, ………………………………………………. am1x1 + am2x2 +… + amnxn = bm.

(7)
Теорема Кронекера-Капелли. Для того, чтобы система m линейных алгебраических уравнений с n неизвестными была совместна, необходимо и достаточно, чтобы ранг ее основной матрицы A был равен рангу расширенной матрицы B, rang A = rang B = r, где

A = , B = . (8)

Если r = n, то система имеет единственное решение, если r < n система имеет бесконечное множество решений, зависящее от n – r произвольных параметров.

Если в системе (7) все свободные члены равны нулю, система называется однородной, в противном случае – неоднородной. Так как для однородной системы rang A = rang B, она всегда совместна.

1. Метод Крамера решения систем n линейных уравнений с n неизвестными состоит в отыскании неизвестных по формуле Крамера

x_i = (i = 1, 2, 3, … , n) , (9)

где Δ – основной определитель системы, а определители Δ_i представляют собой определители того же порядка, которые получены из основного путем замены в нем i-го столбца столбцом свободных членов системы.

2. Матричный метод решает также систему n уравнений с n неизвестными, для которой матрица коэффициентов является невырожденной. Тогда для A существует обратная матрица A^–1.

Заданную систему уравнений

a11x1 + a12x2 +… + a1nxn = b1, a21x1 + a22x2 +… + a2nxn = b2, ……………………………. (10) an1x1 + an2x2 +… + annxn = bn. , если обозначить B = ; X = ,

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

A · X = B, A^–1 · A · X = A^–1 · B, X = A^–1 · B, (11)

где введены в рассмотрение матрицы–столбцы для свободных членов и неизвестных. Умножая матричное уравнение на обратную матрицу A^–1 слева, получим матрицу-столбец, дающую решение системы.

Пример 1

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

4x2 + 4x3 = –19, 2x1 – 3x2 – 5x3 = –5, –3x1 – 2x2 – 3x3 = 2.

Решение системы имеет вид x₁ = ; x₂ = ; x₃ = .

Вычислим определители Δ = = 32; Δ₁ = = –17;

Δ₂ = = –443; Δ₃ = = 291;

x₁ = ; x₂ = ; x₃ = .

Пример 2

Данную систему уравнений записать в матричной форме и решить ее с помощью обратной матрицы:

x1 + 5x2 – x3 = 3 2x1 + 4x2 – 3x3 = 2 3x1 – x2 – 3x3 = –7.

Решение

Обозначим через A – матрицу коэффициентов при неизвестных; X – матрицу-столбец неизвестных x₁, x₂, x₃; B – матрицу-столбец свободных членов:

A = ; X = ; B = .

С учетом этих обозначений данная система уравнений принимает следующую матричную форму:

A · X = B .

Если матрица A – невырожденная (ее определитель Δ отличен от нуля), то она имеет обратную матрицу A^–1. Умножив обе части уравнения на A^–1 слева, получим:

A^–1 · A · X = A^–1 · B .

Но A^–1 · A = E (E – единичная матрица), а E · X = X, поэтому

X = A^–1 · B .

Это равенство называется матричной записью решения системы линейных уравнений. Для нахождения решения системы уравнений необходимо вычислить обратную матрицу A^–1.

Пусть имеем невырожденную матрицу

A = , тогда A^-1= ,

где A_ij (i = 1, 2, 3; j = 1, 2, 3) – алгебраические дополнения для элементов a_ij в определителе матрицы A.

Вычислим определитель Δ и алгебраические дополнения A_ij элементов матрицы A.

Δ = = –16 ≠ 0, следовательно, матрица A имеет обратную матрицу A^–1.

A11 = = –15;	A21 = – = 16;
A31 = = –11;	A12 = – = –3;
A22 = = 0;	A32 = – = 1;
A13 = = –14;	A23 = – = 16;
A33 = = –6;

Тогда A^–1 = ·

Находим решение данной системы уравнений в матричной форме:

X = = – · · = = = .

Отсюда x₁ = –4; x₂ = 1; x₃ = –2.

3. Метод Жордана-Гауссаили метод последовательных исключений является наиболее универсальным по сравнению с предыдущими методами решения систем линейных алгебраических уравнений, так как позволяет решать и системы m линейных уравнений с n неизвестными, когда основная матрица A системы имеет ранг r n. Тогда расширенная матрица системы путем элементарных преобразований может быть приведена к виду

, (12)

т. е. исходная система уравнений к виду:

x1 + a12x2 + … + a1rxr + a1r+1xr+1 + … + a1nxn = b1 x2 + … + a2rxr + a2r+1xr+1 + … + a2nxn = b2 ………………………………………….. xr +arr+1xr+1 + … + arnxn = br 0 = br+1 0 = brn . (13)

Если хотя бы одно из чисел b_r+1= … = b_rn не равно нулю, система не имеет решений. Если b_r+1= … = b_rn = 0, система совместна, из нее можно последовательно выразить в явном виде базисные неизвестные x_r, x_r–1, … , x₂, x₁ через свободные, число которых (n – r): x_r+1, … , x_n .

В случае r = n решение этой системы единственно, и все неизвестные последовательно выражаются из последней системы снизу вверх.

Пример 1

Методом Жордана-Гаусса решить систему:

. (14)

Так как = система имеет единственное решение.

Прямой ход. Умножаем первое уравнение сначала на (-2) и складываем со вторым, затем первое на (-1) и складываем с третьим. Получим

Третье уравнение можно сократить на (+2), а потом третье уравнение сложить со вторым. Получим треугольную систему:

. (15)

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

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

~ .

Получили треугольную матрицу. Из нее получим треугольную систему

(15).

Обратный ход. Из последнего уравнения определяем из второго находим , из первого . Решение системы = (1; 2; 1).

Пример 2

Найти одно из базисных решений системы:

.

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

. (16)

Так как ранг матрицы r =3, поэтому три неизвестных можно выбрать базисными, тогда будет свободной. Обозначим ее через =С, перенесем в правые части уравнений, тогда система приобретает вид:

(17)

и решается так же, как система (5.3).

Приведем матрицу системы к диагональному виду:

.

На последнем этапе поменяли 2 и 3 строку местами. Получим треугольную систему:

.

Обратным ходом найдем решение системы:

Таким образом, мы получим бесчисленное множество решений, называемое общим решением системы.

(4+C; -4-2C; 2; C) ,

где С – произвольная постоянная.

Если положить свободную переменную получим одно из базисных решений (базис) системы:

(4; -4; 2; 0).

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

Замечание: Очевидно, что можно сразу приводить матрицу системы к диагональному виду (13), не перенося заранее свободные переменные в правые части уравнений.

Пример 3

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

Заводы	Затраты на перевозку в ден. ед.
I	II

Минимальные затраты на перевозку составляют 7950 ден. ед.

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

Решение.

Для постановки задачи составим балансовую таблицу, в уголки ячеек которой внесем технологические коэффициенты задачи и впишем переменные задачи x_ij – количество машин, поставляемых i – м заводом j – автохозяйству (i,j=1.2).

Заводы	Автохозяйства	Выпуск
I	II
	x11 15	x12 20
	x21 8	x22 25
Потребности

Итак нужно найти матрицу неизвестных X = , элементы которой удовлетворяют ограничениям:

а) по выпуску автомобилей:

х₁₁+х₁₂=350

х₂₁+х₂₂=150

б) по потребностям автохозяйств:

х₁₁+х₁₂=200

х₂₁+х₂₂=300

в) цель задачи – обеспечить минимальные затраты на перевозку в размере 7950 д.е., в соответствии с технологией перевозок:

15х₁₁=20х₁₂+8х₂₁=25х₂₂=7950.

Получим систему 5 уравнений с четырьмя неизвестными

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

Преобразуем расширенную матрицу системы к треугольному виду. Для этого сначала переставим 4-ю строку на место 2-ой, 2-ую на место 3-ей, доставляя нули в первом столбце.

~

Вычтем из 4-ой строки первую, потом из 5-ой – первую, умноженную на (+15).

~ ~

Разрешающим элементом возьмем а₂₂=1, четвертую строку сложим со второй, пятую сложим со второй, умноженной на (-5):

~ ~ ~

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

~ .

Получаем систему:

Обратным ходом снизу вверх получаем ответ:

х₂₂=0; х₂₁=150; х₁₂=300; х₁₁=50.

Пример 4.

Найти все возможные группы основных (базисных) переменных в системе

Решение. Общее число групп основных переменных не более чем

, т.е. возможные группы основных пе­ременных: , .

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

Пример 5. (ЭУК, глава 48)

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

Решение.

В задаче 1 установлено, что основными могут быть переменные ; ; ; . Возьмем в качестве основ­ных (базисных) переменные , а переменные будем считать неос­новными (совбодными) и перенесем их с соответствующими коэффициентами в правые части уравнений системы. Получим

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

Задание к практическому занятию:

Повышенный уровень:

Задача 5.

Решить систему уравнений в виде вектора , где основными переменными будут х₁ и х₂, а две другие - свободными с₁ и с_{2 ,} где с₁ и с_{2 ,} – произвольные постоянные.

Ответ:

Задача 6

Решить систему уравнений в виде вектора , где основными переменными будут х₁ и х₂, а две другие - свободными с₁ и с_{2 ,} где с₁ и с_{2 ,} – произвольные постоянные.

Ответ:

Задача 7.

Решить систему уравнений в виде вектора , где основными переменными будут х₁ и х₄, , а две другие - свободными с₁ и с_{2 ,} где с₁ и с_{2 ,} – произвольные постоянные.

Задача 8.

Решить систему уравнений в виде вектора , где основными переменными будут х₁ и х₃, а две другие - свободными с₁ и с_{2 ,} где с₁ и с_{2 ,} – произвольные постоянные.

Задача 9.

Решить систему уравнений в виде вектора , где основными переменными будут будут х₁ и х₄, а две другие - свободными с₁ и с_{2 ,} где с₁ и с_{2 ,} – произвольные постоянные.