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

Рассмотрим системы линейных алгебраических уравне- ний (СЛАУ).

Линейная система m уравнений с n неизвестными — это система вида:

 

 

(2.1)

 

 

где

 

a ij — коэффициенты;

x 1, x 2, …, x n — неизвестные;

b 1, b 2, …, b m — свободные члены.

Систему (2.1) можно записать в матричном виде:

AX = B,                                                      (2.2)

 

где                                     — матрица системы;

 

 

— вектор свободных членов;

 

 

— вектор неизвестных.

Решением СЛАУ называется любая совокупность n чисел (x 1, x 2, …, x n), которая обращает каждое уравнение системы (2.1) в верное равенство.

Любая СЛАУ вида (2.1) может иметь одно решение, беско- нечное множество решений, ни одного решения.

Если СЛАУ имеет хотя бы одно решение, то она называет- ся совместной. Если СЛАУ не имеет решений, то она — несов- местная.

Если все свободные члены СЛАУ (2.1) равны нулю, то сис- тема называется однородной, а если хотя бы один из свободных членов системы не равен нулю, то она называется неоднород- ной. Система однородных уравнений всегда совместна, т. е. она имеет хотя бы одно решение (х j =0).

Перед решением СЛАУ надо убедиться в ее совместности. Поэтому приведем без доказательства теорему Кронекера-Ка- пелли, которая позволяет это сделать.

Дополним матрицу А системы (2.2) столбцом свободных чле- нов. В результате этого получим матрицу порядка m (n + 1), которую называют расширенной матрицей системы (С):

 

Через r (А) и r (С) обозначим ранги матриц А и С соответс- твенно.

Теперь сформулируем теорему.

Теорема 2.3 (Кронекера-Капелли). Для того чтобы СЛАУ вида (2.2) была совместна, необходимо и достаточно, чтобы ранг матрицы системы (r (А)) был равен рангу расширенной матри- цы системы (r (С)), т. е. r (А) = r (С). Здесь возможны два случая:

1) если r (А) = r (С) = = n, где n — число неизвестных в систе- ме (2.2), то СЛАУ имеет единственное решение; 2) если r (А) =

= r (С) < n, то СЛАУ имеет бесконечное множество решений.

СЛАУ можно решать или прямыми или итерационными методами.

В прямых (точных) методах решение системы (2.2) нахо- дится за конечное число арифметических действий. К прямым методам относятся метод Гаусса и его модификации, метод квадратного корня, метод Крамера и др.

Итерационные методы (методы последовательных при- ближений) состоят в том, что решение системы (2.2) находится как lim (предел) при k → последовательных приближений х ^{( k )}, где k — номер итерации. Обычно за конечное число итераций этот предел не достигается. Как правило, задается некоторое малое число > 0 (точность) и вычисления проводятся до тех пор, пока не будет выполнено условие

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

В предлагаемом учебнике рассмотрим прямые методы: ме- тод Гаусса и метод Крамера.

Рассмотрим метод Гаусса решения СЛАУ. Он состоит из двух шагов. На первом шаге мы приводим исходную систему уравнений к верхнему треугольному виду, а на втором шаге на- ходим неизвестные (х j), начиная с последнего.

Предположим, что мы имеем систему n уравнений с n не- известными, и она является совместной, т. е.

 

 

(2.3)

 

 

Исключаем неизвестное x 1 из всех уравнений, начиная со второго. Для этого из второго уравнения почленно вычтем пер- вое, умноженное на a 21/ a 11, из третьего почленно вычтем пер-

вое, умноженное на a 31/ a 11 и т. д., причем a 11   0, если a 11 = 0, то переставляем местами уравнения системы (2.3). После этого система (2.3) примет вид.

 

(2.4)

 

 

где

В системе (2.4) исключаем неизвестные x 2 из всех уравне- ний, начиная с третьего, т. е. ведущим  элементом  становится , если он равен нулю, то переставляем уравнение места- ми, т. е. из третьего уравнения системы (2.4) вычитаем второе, умноженное на коэффициент , из четвертого уравнения системы (2.4) вычитаем второе, умноженное  на  коэффициент   и т. д. В результате мы получаем следующую систему уравнений:

 

(2.5)

 

где

Аналогичный процесс мы продолжаем далее и на (n -1)- м шаге приходим к следующей системе уравнений.

 

 

(2.6)

 

То есть исходную систему уравнений (2.3) привели к верх- нему треугольному виду (первый шаг метода Гаусса завершен). Второй шаг (обратный ход) заключается в решении системы уравнений (2.6). Он осуществляется следующим образом: из последнего уравнения системы (2.6) находим , исполь- зуя найденное значение x n из предпоследнего (n−1) уравнения системы (2.6) находим x n −1, затем из (n −2) уравнение системы

(2.6) находим x n −2 и т. д. до x 1.

Алгоритм Гаусса состоит из однотипных операций, кото- рые легко программируются.

Решим систему уравнений, используя метод Гаусса.

Пример 2.6.

(2.7)

 

 

Исключим x 1 из второго и третьего уравнения системы (2.7). Для этого умножим первое уравнение почленно на 4 и вычтем из второго, затем умножим первое уравнение на (−5) и вычтем из третьего. В результате получим следующую систему урав- нений

 

(2.8)

 

Теперь исключим из третьего уравнения системы (2.8) не- известное x 2. Для этого умножим поэлементно второе  уравне-

ние системы (2.8) на (−3) и вычтем из третьего уравнения сис- темы (2.8).

В результате получим следующую систему уравнений

 

(2.9)

 

 

Из системы уравнений (2.9) последовательно находим не- известные х, начиная с последнего (x 3), т. е. x 3 = −1;

Теперь рассмотрим метод Крамера решение СЛАУ.

Рассмотрим систему уравнений (2.3), которую запишем в матричном виде

AX = B,                                                    (2.10)

 

 

где                                    — матрица системы;

 

 

— вектор свободных членов;

 

 

— вектор неизвестных.

 

 

Если определитель матрицы А (det А) не равен нулю, то су- ществует A ⁻¹.

Домножим слева систему (2.10) на A ⁻¹, получим

A ^{− 1} AX = A ^{− 1} B, так как A ^{− 1} A = E, то

имеем EX = A ⁻¹ B, а так как EX = X, то

окончательно получим X = A ^{− 1} B                                   (2.11) или в развернутом виде

 

 

(2.12)

 

 

Из (2.12) следует

 

 

(2.13)

 

 

Числители равенств (2.13) есть разложения по элементам 1, 2, …, n -го столбцов определителя, полученного из det А заме- ной в нем 1, 2, …, n столбцов столбцом свободных членов, т. е.

Таким образом, неизвестные xi можно найти по формуле

                                                                    (2.14)

где i = 1, 2, …, n.

Решим систему уравнений, используя метод Крамера.

Пример 2.7.

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

Затем находим

 

 

и определяем неизвестные x i; i = 1, 2, 3: