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

(1)

Способы решения систем линейных алгебраических уравнений (СЛАУ) в основном разделяют на две группы: 1) точные методы, представляющие собой конечные алгоритмы для вычисления решений системы (вследствие неизбежных округлений результаты даже точных методов являются приближенными), 2) итера-ционные методы, позволяющие получить решения системы с заданной точностью путем сходящихся бесконечных процессов.

Приведем ряд точных методов решения СЛАУ.

1. Формулы Крамера. Если определитель системы (1) отличен от нуля, то ее решения можно найти по формулам:

, , , …, , где

- определитель системы (1),

, , …, -дополнительные определители для

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

Если матрица невырожденная, т. е. ее определитель не равен 0, то существует обратная матрица . Умножая обе части уравнения на матрицу слева, получим: .

3. Метод Гаусса. Наиболее распространенным приемом решения систем линейных алгебраических уравнений является алгоритм последовательного исключения неизвестных. Этот метод носит название метода Гаусса. Для простоты рассуждений ограничимся рассмотрением системы четырех уравнений с четырьмя неизвестными

(1)

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

, (2),

где

, .

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

(3),

где коэффициенты , вычисляются по формуле

, .

Разделив коэффициенты второго уравнения системы (3) на «ведущий элемент» (), получим уравнение

(4),

где

,

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

(5),

где

,

Разделив коэффициенты третьего уравнения системы (5) на «ведущий элемент» (), получим:

(6),

где

,

Исключив теперь аналогичным путем из системы (5), будем иметь:

(7),

где

,

Отсюда

(8) (),

где

,

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

(9)

Неизвестные последовательно определяют из системы уравнений (9):

Таким образом, процесс решения линейной системы по методу Гаусса сводится к построению эквивалентной системы (9), имеющей треугольную матрицу. Необхо-димым и достаточным условием применимости метода является неравенство нулю всех «ведущих элементов». (Если на каком-то шаге «ведущий элемент» оказался равным нулю, то надо переставить местами уравнения.)

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

Полученные методом Гаусса приближенные решения можно уточнить. Для этого нужно найти невязку для приближенного решения. Пусть - приближенное решение системы , а точный корень уравнения, т. е. , – невязка, тогда .

При решении системы

по методу Гаусса мы заменяли матрицу

исходной системы, треугольной матрицей

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

1. деления на «ведущие элементы» , которые предполагались отличными от нуля;

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

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

Следовательно,

,

т. е. определитель равен произведению «ведущих элементов» для соответствующей схемы Гаусса.

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

Перемножая матрицы и , будем иметь систем уравнений относительно неизвестных

где

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