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

Методы решения систем линейных алгебраических уравнений делятся на две группы. К первой группе принадлежат так называемые точные, или прямые, методы - алгоритмы, позволяющие получить решение системы за конечное число арифметических действий. Сюда относятся известное правило Крамера нахождения решения с помощью определителей, метод Гаусса (метод исключений) и метод прогонки [13]. Правило Крамера при реализации на ЭВМ не применяется ввиду значительно большего по сравнению с методом Гаусса числа арифметических действий. Метод Гаусса используется при решении систем до порядка 10³. Метод прогонки применяется для решения важного класса специальных систем линейных уравнений с трехдиагональной матрицей, часто возникающей в практических приложениях.

Вторую группу составляют приближенные методы, в частности, итерационные методы решения систем линейных алгебраических уравнений, позволяющие решать системы до порядка 10⁶ [1], [4], [7], [13].

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

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

Рассматривается система линейных уравнений n-го порядка

(2.1)

. . . . .

,

что в векторном виде записывается как .

Суть метода исключения по главным элементам (метод Гаусса) заключается в следующем. Находится наибольший по абсолютной величине коэффициент . Для исключения из i-го уравнения необходимо умножить k-е уравнение на и вычесть его из i-го уравнения, после чего процесс повторяется для исключения другого неизвестного из оставшихся -1 уравнений и т. д. В результате система (2.1) приводится к треугольному виду

(2.2)

. . . . . .

,

из которого легко находятся неизвестные . Процесс приведения системы к виду (2.2) называется прямым ходом, а нахождение неизвестных - обратным ходом метода Гаусса.

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

Мерой обусловленности матрицы называют величину , где - норма матрицы . Мера обусловленности равна максимально возможному коэффициенту усиления относительной погрешности от правой части к решению системы (2.1). Если матрица симметричная и выбрана вторая норма, то мера обусловленности может быть найдена как

,

где - i-е собственное число матрицы . Если большая, то матрица (система (2.1)) называется плохо обусловленной, в противном случае - хорошо обусловленной.