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

Метод обратной матрицы и формулы Крамера.

Пусть число уравнений совпадает с число переменных m=n. В этом случае матрица А=(а_ij)_nxn является квадратной. Назовем определитель этой матрицы ∆ =│А│ определителем системы.

Предположим, что матрица А невырожденная, т.е. её определитель │А│≠0. В этом случае существует обратная матица А^-1.

Умножим обе части матричного уравнения (3.2.2) слева на матрицу А^-1. Получаем А^-1АХ= А^-1В, но А^-1А=Е, следовательно, ЕХ= А^-1В. Но ЕХ=Х (свойства матриц). И сказанного получаем решение матричного уравнения

Х= А^-1В(3.2.3)

 

Теорема Крамера(правило Крамера)

 

 

Формулы (3.4) называются формулами Крамера.

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

 

Подставим обратную матрицу А^-1 = Ã - матричное уравнение (3.2.3), записав все матрицы в развернутой форме

x₁ а₁₁ а₂₁ ... а_n1 b₁

x₂ а₁₂ а₂₂ …а_n2 b₂

- = - - - - - - - _(3.2.5)

- - - - - - - -

x_n а_1n а_2n …а_nn b_n

учитывая, что │А│= ∆, после умножения матриц получаем:

x₁ b₁ а₁₁ + b₂ а₂₁ + … + b_n а_n1

x₂ b₁ а₁₂ + b₂ а₂₂ + … + b_n а_n2

- = - - - - - - - - - - -

- - - - - - - - - - - -

x_n b_n а_1n + b_n а_2n+ …. + b_n а_nn

 

отсюда следует, что для любого j=1,n

x_j= b₁а_1j+ b₂а_2j+…+ b_nа_nn) (3.2.6)

Но на основании свойства определителей выражение, стоящее в скобках равенства (3.2.5) представляет собой определитель ∆_j для j=1,n. Следовательно, X_j= . Теорема Крамера доказана.

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

 

х₁ + 2х₂ + х₃ = 8

-2х₁ + 3х₂ -3х₃ = -5

3х₁- 4х₂ + 5х₃=10

 

а) матричным способом; б) по формулам Крамера.

Решение.

а)введем матрицы

1 2 1 х₁ 8

А= -2 3 -3 ; Х= х₂ ; В= -5

3 -4 5 х₃ 10

 

В матричной форме решение имеет вид Х=А^-1В. Найдем обратную матрицу в соответствии с алгоритмом:

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

1 2 1

∆= -2 3 -3 = 4 ≠0

3 -4 5

 

Обратная матрица существует.

 

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

3 -3 -2 -3

А₁₁= =15-12=3; А₁₂= = 1, и т.д. А₁₃= - 1

-4 5 3 5

 

А₂₁= -14 А₂₂= 2 А₂₃=10

А₃₁= -9 А₃₂= 1 А₃₃= 7

 

 

3.Присоединённая матрица имеет вид

3 -14 -9

Ã= 1 2 1

-1 10 7

 

 

4. А^-1= * Ã

 

Подставим А^-1 в (3.2.5)

 

Х₁ 3 -14 -9 8 24+70-90 1

Х₂ = 1 2 1 -5 = 8 -10+ 10 = 2

Х₃ -1 10 7 10 -8-50+70 3

 

Решение системы: х₁=1; х₂=2; х₃=3.

 

б) Определитель системы ∆=4

 

Находим определители ∆₁, ∆₂, ∆₃.

 

8 2 1 1 8 1 1 2 8

∆₁= -5 3 -3 =4; ∆₂= -2 -5 -3 =8; ∆₃= -2 3 -5 =12

10 -4 5 3 10 5 3 -4 10

 

 

По формулам Крамера (3.2.4) определяем

х₁= ; х₂ = ; х₃= = = 3

 

В конце целесообразно сделать проверку, подставив найденные значения Х_j в уравнения системы.

Решение систем матричным способом или по правилу Крамера имеет ряд недостатков:

1.Область применения этих способов ограничена условием m=n (число уравнений совпадает с числом неизвестных). В то же время решение практических задач (в экономике в том числе), как правило, приводит к необходимости решения систем, когда число неизвестных n достаточно велико, и m≠n.

2.При выполнении условия m=n матрица системы должна быть невырожденной (│А│=∆≠0).

3.Даже при выполнении 2-го условия (m=n, ∆≠0) вычисление определителей и отыскание обратной матрицы связаны с громоздкими вычислениями.

Метод Гаусса

 

Рассмотрим решение системы (3.2.1) mлинейных уравнений с nпеременными в общем виде.

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

Предположим, что в системе (3.2.1) коэффициент при переменной х₁ в первом уравнении а₁₁≠0 (если это не так, то перестановкой уравнений местами добьёмся того, чтобы а₁₁≠0 ).

Шаг 1. Умножая первое уравнение на подходящие числа и прибавляя полученные уравнения соответственно ко второму, третьему,…, m-му уравнению системы (3.2.1) , исключаем переменную х₁ из всех последующих уравнений, начиная со второго. В результате получаем систему

a₁₁х₁ + а₁₂х₂ + … + а_1nх_n = b₁

a₂₂⁽¹⁾ x₂ + … + a_2n⁽¹⁾x_n = b₂⁽¹⁾

- - - - - - - - - (3.2.6)

a_i2⁽¹⁾x₂ + … + a_in⁽¹⁾x_n = b_i⁽¹⁾

- - - - - - - - - - -

a_m2⁽¹⁾x₂ + … + a_mn⁽¹⁾x_n = b_m⁽¹⁾

 

где буквой с верхним индексом «(1)» обозначены новые коэффициенты, полученные после шага 1.

Рассмотрим, как вычисляются новые коэффициенты. Например, требуется исключить переменную х₁ из i-го уравнения (i =2, n). Выпишем 1-е и i-е уравнения системы (напомним, что а₁₁≠0)

a₁₁х₁ + а₁₂х₂ + … + a_1jx_j + … + a_1nx_n = b₁

- - - - - - - - - - - - - - -

a_i1x₁ + a_i2x₂ + … +a_ijx_j + … + a_inx_n = b_i

- - - - - - - - - - - - - - - -

 

Назовем 1-е уравнение разрешающим,а коэффициент а₁₁ - разрешаю­щимкоэффициентом.

Умножим 1-е уравнение системы на такое «удобное» число λ, чтобы после этого, прибавив 1-е уравнение к i-му уравнению, переменная х₁ в i-ом уравнении не содержалась. При этом само 1-е уравнение сохраняется в системе на своем месте.

Итак,

a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + … + a_ijx_j +… +a_inx_n = b₁

- - - - - - - - - - - - - - - - - - - - - - - - - (3.2.7)

(λa₁₁+a_i1)x₁ + (λa₁₂+a_i2)x₂ +…+ (λa_1j+a_ij)x_j +…+ (λa1_n+a_in)x_n = λb₁+b_i

- - - - - - - - - - - - - - - - - - - - - - - - -

 

Из (3.2.7) следует, что новые коэффициенты при x_j в i-ом уравнении имеют вид a'_ij = λa_1j+a_ij, j=1,n, чтобы x₁ не входило в i-ое уравнение, число λ должно быть таким, чтобы λa₁₁+a_i1=0, откуда λ= - . При таком значении λ

 

 

 

 

Для пересчета коэффициентов и свободного члена по формулам (3.2.8) удобно использовать «правило прямоугольника»:

a₁₁ a_1j a₁₁-разрешающий элемент

a_ij-разрешаемый (пересчитываемый) элемент

a_1j, a_i1­-сопутствующие элементы

a_i1 a_ij

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

Шаг 2.Временно 1-е уравнение исключаем. Если а ⁽¹⁾₂₂≠0 (всегда можно добиться), то второе уравнение выбираем в качестве разрешающего. Со 2-ым уравнением системы поступим так же, как и на 1-м шаге, исключаем из всех уравнений, начиная с 3-го уравнения, переменную х₂.

 

Продолжая процесс последовательного исключения переменных х₃, х₄, …, х_r-1, после (r-1)-го шага получаем систему

 

a₁₁х₁ + а₁₂х₂ + … + a_1rx_r + a_1,r+1x_r+1 + … + a_1nx_n = b₁ ,

a⁽¹⁾₂₂x₂+…+a⁽¹⁾_2rx_r + a⁽¹⁾_2,r+1x_r+1 + … +a⁽¹⁾_2nx_n = b⁽¹⁾₂ ,

…………………………………………………..... (3.2.9)

a^(r-1)_rrx_r + a^(r-1)_r,r+1x_r+1 +…+a^(r-1)_rnx_n = b^(r-1)_r ,

……………………………………………

0=b^(r-1)_r+1 ,

……..

0=b^(r-1)_m

Число ноль в последних m – r уравнениях означает, что их левые частиимеют вид: 0*х₁ + 0*х₂ + … + 0*х_n. Если хотя бы одно из чисел b^(r-1)_r+1,… b^(r-1)_m не равно нулю, то соответствующее равенство противоречиво и система (3.2.9) несовместна.

Таким образом, для любой совместной системы числа b^(r-1)_r+1,… b^(r-1)_m в системе равны нулю. В этом случае последние m – r уравнений в системе (3.2.9) являются тождествами и их можно не принимать во внимание при решение системы (3.2.1). Очевидно, что после отбрасывания «лишних» уравнений возможны два случая: а) число уравнений системы (3.2.1) равно числу переменных, т.е. r = n (в этом случае система (3.2.9) имеет треугольный вид); б) r < n (в этом случае система (3.2.9) имеет ступенчатый вид).Переход системы (3.2.1) к равносильной ей системе (3.2.9) называется прямым ходом метода Гаусса, а нахождение переменных из системы (3.2.9) – обратным ходом.

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

 

a₁₁ а₁₂ … а_1n b₁

a₂₁ a₂₂ … a_2n b₂

(A│B) = …………….. … , (3.2.10)

a_m1 a_m2 … a_mn b_m

 

называемую расширенной матрицей системы (3.1), ибо в нее, кроме матрицы системы А, дополнительно включен столбец свободных членов матрицы В.

Системе (3.2.9) соответствует диагональная матрица. Значит, ее определитель не равен нулю. Это означает что ранг матрицы r=3. Система имеет единственное решение. Закончен прямой ход метода Гаусса.

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

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

х₁+2х₂+ 3х₃=6

2х₁+3х₂ -х₃=4

3х₁+х₂ - 4х₃=0

 

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

 

1 2 3 6

(А/В)= 2 3 -1 4

3 1 -4 0

Шаг 1.Исключим переменную х₁ из 2-го и 3-го уравнений, выбрав 1-е уравнение (строку) разрешающим и коэффициент а₁₁=1≠0 будем считать разрешаемым. Это означает, что после пересчета коэффициентов а_ij в новой (эквивалентной) матрице в 1-м столбце под разрешающим элементом будут стоять нули. Новая матрица будет иметь вид

1 2 3 6 1 2 3 6

0 -1 -7 -8 0 1 7 8

0 -5 -13 -18 0 5 13 18

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

1 2 3 6

0 1 7 8

0 0 22 22

 

Аналогично пересчитываем и свободный член.

На этом закончен 1-й шаг. Начинаем обратный ход.

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

 

 

22х₃ = 22 х₃ = 1

х₂ + 7х₃ = 8 х₂ = 8 – 7х₃ = 1

х₁ + 2х₂ + 3х₃ = 6 х₁ = 6 – 2х₂ – 3х₃

Решение системы: х₁=х₂=х₃=1

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

с n переменными.

Ранее было установлено, что ранг матрицы равен максимальному числу ее линейно независимых строк, поэтому если строки расширенной матрицы (А│В), т.е. уравнения системы (3.2.1), линейно независимы, то ранг матрицы (А│В) равен числу ее уравнений, т.е. r = m, если уравнения линейно зависимы, то r < m.

Вопрос о разрешимости системы (3.2.1) в общем виде рассматривается в следующей теореме.

Теорема Кронекера-Капелли.Система линейных уравнений совместна тогда и только тогда, когда ранг матрицы системы равен рангу расширенной матрицы этой системы. r(A)= r(А│В). При этом:

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

2)еслиранг матрицы совместной системы меньше числа переменных, т.е. r < n , то система (3.2.1) неопределенная и имеет бесконечное множество решений.

Результаты исследования системы (3.2.1) приведем в виде схемы

r<m – уравнения системы зависимые

r(A)≠ r(А│В)- система несовместная

r<n – система неопределенная (бесконечное множество решений)

 

 

 

r(A)= r(А│В) – система совместная

 

 

 

Пусть r<n. Тогдаr переменных х₁, х₂, … х_r называютсяосновнымиилибазисными, если определитель матрицы из коэффициентов при них (т.е. базисный минор) отличен от нуля. Остальные n- r называются неосновными, или свободными.

Придавая свободным переменным x_r+1, x_r+2, …, x_n произвольные значения, из последнего уравнения системы (3.2.9) найдем значение переменной х_r, из предпоследнего x_{r -1} и т.д. – остальные базисные переменные x₁, x₂, … , x_r-2.

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

Так как каждому разбиению переменных на основные и неосновные соответствует одно базисное решение, а число способов разбиения не превосходит числа сочетаний, то и базисных решений имеется не более C­ ^r_n. Таким образом, совместная система m линейных уравнений с n переменными (m<n) имеет бесконечное множество решений, среди которых базисных решений конечное число, не превосходящее C­^r_n , где r≤m.

Приведенная схема не означает, что для решения системы (3.2.1) в общем случае необходимо вычислять отдельно, а затем сравнивать ранги матрицы системы А и расширенной матрицы (А/В). Достаточно сразу применить метод Гаусса.

Метод Гаусса по сравнению с другими методами (в частности, приведенными в параграфе) имеет следующие достоинства:

· значительно менее трудоемкий;

· позволяет однозначно установить, совместна система или нет, а в случае совместности найти ее решения (единственное или бесконечное множество);

· дает возможность найти максимальное число линейно независимых уравнений (ранг матрицы системы).

 

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

 

2х₁ – х₂ + х₃ – х₄ = 5

х₁ + 2х₂ – 2х₃ + 3х₄ = -6

3х₁ + х₂ – х₃ + 2х₄ = -1

 

Т.к. в данной системе число уравнений меньше числа переменных (m=3, n=4), систему невозможно решать ни методом обратной матрицы, ни по формулам Крамера. Используем метод Гаусса. Выпишем расширенную матрицу системы

2 -1 1 -1 5

(А/В) = 1 2 -2 3 -6

3 1 -1 2 -1

Для удобства поменяем местами 1-ю и 2-ю строки, и первое уравнение будем считать разрешающим с разрешающим элементом а₁₁≠0. Матрица (А/В) перейдет в эквивалентную

1 2 -2 3 -6

2 -1 1 -1 5

3 1 -1 2 -1

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

 

 

1 2 -2 3 -6

0 -5 5 -7 17

0 -5 5 -7 17

 

 

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

1 2 -2 3 -6

0 -5 5 -7 17

 

 

1 2

Минор = -5 ≠ 0. Следовательно, ранг А/ В = 2

0 -5

 

Больше шагов не требуется.

В системе две переменные являются базисными. Это могут быть переменные х₁, х₂. Тогда остальные переменные х₃, х₄ можно считать свободными,через которые можно выразить базисные переменные. Из последней матрицы следует:

х₁ + 2х₂ – 2х₃ + 3х₄ = -6

- 5х₂ + 5х₃ – 7х₄ = 17

 

х₂= (5х₃ – 7х₄ - 17)

х₁ = - 6 - (5х₃ – 7х₄ - 17) + 2х₃ – х₄ = 9х₄ +

 

Найдем базисное решение, полагая, что свободные переменные х₃=х₄=0. Тогда х₁ = ; х₂ = - .

Получено базисное решение Χ = ( ).

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

N = C²₄ = =6.