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

Прямые методы решения СЛАУ:     Метод Крамера     Метод обратной матрицы     Метод Гаусса Итерационные методы решения линейных алгебраических систем:     Метод простой итерации или метод Якоби     Метод Гаусса – Зейделя

К решению систем линейных алгебраических уравнений сводятся многочисленные практические задачи ( по некоторым оценкам более 75% всех задач). Можно с полным основанием утверждать, что решение линейных систем является одной из самых распространенных и важных задач вычислительной математики.

Конечно, существует много методов и современных пакетов прикладных программ для решения СЛАУ, но для того, чтобы их успешно использовать, необходимо разбираться в основах построения методов и алгоритмов, иметь представления о недостатках и преимуществах используемых методов.

Постановка задачи

Требуется найти решение системы m линейных уравнений, которая записывается в общем виде как

,

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

,

где , , .

A – матрица системы, – вектор правых частей, – вектор неизвестных.

При известных A и требуется найти такие , при подстановке которых в систему уравнений она превращается в тождество.

Необходимым и достаточным условием существования единственного решения СЛАУ является условие det A≠0, т.е. определитель матрицы A не равен нулю. В случае равенства нулю определителя матрица A называется вырожденной и при этом СЛАУ либо не имеет решения, либо имеет их бесчисленное множество.

В дальнейшем будем предполагать наличие единственного решения.

Все методы решения линейных алгебраических задач можно разбить на два класса: прямые (точные) и итерационные (приближенные).

Прямые методы решения слау Метод Крамера

При небольшой размерности системы m (m = 2,…,5) на практике часто используют формулы Крамера для решения СЛАУ:

(i = 1, 2, …, m). Эти формулы позволяют находить неизвестные в виде дробей, знаменателем которых является определитель матрицы системы, а числителем – определители матриц A_i, полученных из A заменой столбца коэффициентов при вычисляемом неизвестном столбцом свободных членов. Так А₁ получается из матрицы А заменой первого столбца на столбец правых частей f.

Например, для системы двух линейных уравнений

Размерность системы (т.е., число m) является главным фактором, из–за которого формулы Крамера не могут быть использованы для численного решения СЛАУ большого порядка. При непосредственном раскрытии определителей решение системы с m неизвестными требует порядка m!*m арифметических операций. Таким образом, для решения системы, например, из m = 100 уравнений потребуется совершить 10¹⁵⁸ вычислительных операций (процесс займёт примерно 10¹⁹ лет), что не под силу даже самым мощным современным ЭВМ

Метод обратной матрицы

Если det A ≠ 0, то существует обратная матрица . Тогда решение СЛАУ записывается в виде: . Следовательно, решение СЛАУ свелось к умножению известной обратной матрицы на вектор правых частей. Таким образом, задача решения СЛАУ и задача нахождения обратной матрицы связаны между собой, поэтому часто решение СЛАУ называют задачей обращения матрицы. Проблемы использования этого метода те же, что и при использовании метода Крамера: нахождение обратной матрицы – трудоемкая операция.