2. Прямые методы. Метод Гаусса

Значительная часть наиболее известных прямых методов решения системы (1) сводится к последовательному решению одной или нескольких систем

с матрицами «простого» вида (диагональными, «почти» диагональными, треугольными, «почти» треугольными).

2.1. Классическая схема метода Гаусса. Lu – разложение матрицы

Классическая схема метода Гаусса основана на сведении системы (1) к эквивалентной системе (5) с верхней треугольной матрицей :

Получение такой системы - построение матрицы и вектора правой части называется прямым ходом метода Гаусса. Решение новой системы называется обратным ходом метода Гаусса.

Прямой ход метода Гаусса. Пусть невырожденная матрица имеет ненулевые главные миноры всех порядков от 1 до m-1:

Рассмотрим матрицы и векторы

где нижняя треугольная матрица строится по - тому столбцу матрицы и имеет вид:

Замечание 4. Нижние треугольные матрицы отличаются от единичной матрицы лишь поддиагональными элементами в -ом столбце, . При этом

Очевидно, что

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

Имеем

Аналогично вычисляется произведение матриц .

Обозначим элементы матрицы через . Для каждого элементы матрицы выберем так, чтобы

если

если

На первом шаге прямого хода метода Гаусса имеем (по условию (6) ):

На втором шаге имеем ( по условию (6) ):

Условие (6) позволяет продолжить этот процесс до :

За шагов прямого хода метода Гаусса мы построим верхнюю треугольную матрицу

Отсюда находим представление матрицы в виде произведения нижней и верхней треугольных матриц:

где - нижняя треугольная матрица с единичными диагональными элементами, - верхняя треугольная матрица, . Формулу (9) принято называть LU – разложением матрицы .

Внимание! LU – разложение матрицы (формула (9)) существует и единственно при выполнении условия (6).

Таким образом, при выполнении условия (6) мы в результате прямого хода метода Гаусса получаем эквивалентную (1) систему линейных уравнений с верхней треугольной матрицей:

где и .

Обратный ход метода Гаусса. Теперь мы можем вычислить решение системы (10) с верхней треугольной матрицей. В силу эквивалентности систем (10) и (1) будет и решением системы (1). Пусть и .

Координаты решения находятся в обратном порядке по формулам:

Вычисление решения системы (1) по формулам (11) является обратным ходом метода Гаусса.

Замечание 5. Изложенный алгоритм решения системы (1) называют классической схемой метода Гаусса. Эта схема применима в случае, когда выполнено условие (6). Для реализации алгоритма потребуется примерно арифметических операций.

Внимание! Если известно LU – разложение матрицы , то решение системы (1) сводится к последовательному решению двух систем с треугольными матрицами:

,

Полученное в формуле (9) LU – разложение матрицы позволяет вычислить определитель матрицы и найти обратную матрицу .

Так как

то

Если вырожденная матрица , то на некотором -ом шаге прямого хода метода Гаусса и процесс останавливается. При этом мы можем определить ранг матрицы .

Для построения обратной матрицы нужно решить матричное уравнение

Матрица - решение уравнения (13) и дает . Очевидно, что -ый столбец матрицы является решением системы линейных уравнений где вектор правой части системы При этом для решения системы (13) LU – разложение матрицы строится только один раз.

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

Обозначим через элементы матрицы эквивалентного возмущения , через элементы матрицы .

Имеют место оценки

где - основание системы счисления, - разрядность ЭВМ,

В условиях и обозначениях (14) выполняется неравенство

здесь через обозначена сферическая норма матрицы .

Замечание 6. Оценки (15), (16) получены без каких-либо предположений относительно величины главных миноров матрицы , кроме, конечно, выполнения условия осуществимости прямого хода метода Гаусса. Таким образом, существенным условием неустойчивости процесса вычислений является значительный рост элементов промежуточных матриц .

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