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

 

Матричный способ решения СЛУ

 

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

.

Пусть основная матрица системы невырожденная, т.е. . Определитель называется определителем системы.

Данную систему линейных уравнений можно записать в матричной форме

,

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

Покажем, что такая система имеет решение, и притом единственное, и найдем его.

Так как , то для матрицы A существует обратная матрица . Умножив обе части уравнения слева на матрицу , получаем

Û Û .

Итак, формула

(5.3)

является матричной записью решения рассматриваемой системы.

Единственность решения следует из единственности обратной матрицы.

 

Пример 5.1. Решить СЛУ матричным способом

.

Решение. Запишем основную матрицу и матрицы-столбцы, составленные из неизвестных и свободных членов:

, , .

СЛУ в матричной форме имеет вид: , решение которого .

Находим :

.

Находим алгебраические дополнения каждого элемента основной матрицы:

; ; ;

; ; ;

; ; .

Составляем обратную матрицу:

.

Далее получаем решение СЛУ:

.

,

Формулы Крамера

 

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

.

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

.

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

,

где k - одно из чисел 1, 2, …, n.

Теорема 5.1. (Теорема Крамера) Если определитель системы отличен от нуля, то система имеет единственное решение, которое находится по формулам

, (5.4)

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

 

Теорему 5.1. примем без доказательства.

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

Из теоремы Крамера следует: если однородная система имеет решение, то ее определитель равен нулю.

 

Пример 5.2. Решить СЛУ по формулам Крамера

.

Решение. Находим и определители :

; ;

 

; .

Далее получаем решение:

.

,

 

Метод Гаусса

 

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

 

Рассмотрим СЛУ (5.5), содержащую из m уравнений и n неизвестных:

. (5.5)

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

Пусть в системе коэффициент , который называется разрешающим коэф-фициентом. Если , то на первое место можно поставить уравнение, в котором коэффициент при неизвестной отличен от нуля. Умножаем первое уравнение системы (5.5) на и прибавляем ко второму, получаем уравнение, в котором коэффициент при обращается в нуль. Умножаем первое уравнение на и прибавляем к третьему, получаем уравнение, также не содержащее члена с . Аналогичным путем преобразуем все остальные уравнения. Если в -ом уравнении коэффициент при равен нулю, то это уравнение записываем в новую систему без изменений. В результате преобразований придем к системе, эквивалентной исходной системе уравнений:

, (5.6)

где - некоторые новые коэффициенты при неизвестных, - новые свободные члены.

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

1)

, (5.7)

где и .

2)

, (5.8)

где и .

3)

, (5.9)

где .

Запись системы, полученной после преобразований, называют ступенчатой (в частности, при - треугольной).

Система (5.7) имеет единственное решение. Из последнего уравнения находим : . Из предпоследнего уравнения находим , затем из третьего от конца - . Двигаясь, таким образом, снизу вверх, найдем значения всех неизвестные. Процесс преобразования системы (5.5) к одному из видов (5.7), (5.8) или (5.9) называют прямым ходом метода Гаусса, а описанную только что процедуру движения снизу вверх по уравнениям системы (5.7) с целью получения значений неизвестных – обратным ходом.

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

. (5.10)

Полученная система представляет собой общее решение исходной системы. Неизвестные , стоящие в правой части равенств, называются свободными, а - базисными. Свободным неизвестным можно придавать любые числовые значения и по формулам (5.10) находить соответствующие значения базисных неизвестных. Каждый раз будет получаться определенное частное решение исходной системы. Заметим, что частное решение, получаемое из общего при нулевых значениях свободных неизвестных, называются базисным решением системы, которое играет исключительную роль в математическом программировании.

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

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

 

Пример 5.3. Решить СЛУ методом Гаусса:

.

Решение. Составляем расширенную матрицу:

.

Сначала поменяем местами первую и третью строки, получаем:

.

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

.

Теперь поменяем местами вторую и третью строки:

.

Умножаем элементы второй строки на и складываем с соответствующими элементами третьей строки, получаем:

.

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

.

Из последнего уравнения находим , из второго – и из первого – . Итак, исходная система имеет единственное решение .

,

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

.

Решение. Составляем расширенную матрицу:

.

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

~ ~

[вторую и третью строки умножим на (-1)]

~ ~ .

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

.

Из последнего уравнения находим , из второго – и из первого – . Итак, исходная система имеет единственное решение .

,

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

.

Решение. Составляем расширенную матрицу и преобразуем ее:

~ ~ .

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

,

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

.

Решение. Составляем расширенную матрицу и преобразуем ее:

~ ~ ~

~ .

Исходная система свелась к ступенчатой:

.

Из последнего уравнения за базисную неизвестную выберем, например, и выра-зим через свободные неизвестные : . Подставляем в первое уравнение и выражаем , которое становится базисной неизвестной:

.

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

.

Пусть , где - любые действительные числа. Тогда получаем следующее решение

,

где - любые действительные числа.

,

 

5.3.Исследование СЛУ

 

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

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