§ 5.6. Метод Гаусса и решение систем уравнений с несколькими правыми частями, обращение матриц, вычисление определителей

Рассмотрим применение метода Гаусса к решению следующих задач линейной алгебры: 1) вычисление решений системы уравнений с несколькими правыми частями; 2) вычисление обратной матрицы; 3) вычисление определителя.

1. Вычисление решений системы уравнений с несколькими правыми частями.

Довольно часто на практике встречается ситуация, когда нужно решить несколько систем уравнений

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

Конечно, применяя метод Гаусса к каждой из систем (5.46) независимо от других, можно найти соответствующие решения

затратив примерно арифметических операций. Однако при одновременном решении систем (5.46) число операций можно существенно сократить. Как было отмечено в § 5.5, основные вычислительные затраты в методе Гаусса связаны с преобразованием матрицы к треугольному виду. Преобразование же правой части производится параллельно и требует примерно арифметических операций. Если параллельно с приведением матрицы А к треугольному виду преобразовать по однотипным формулам все правых частей, то на прямой ход метода будет затрачено только примерно операций. С учетом обратного хода общие вычислительные затраты составят примерно арифметических операций.

Преобразование правых частей не обязательно производить параллельно. Каждую из правых частей можно обработать последовательно, если после приведения матрицы А к треугольному виду сохранить в памяти ЭВМ множители и матрицу

2. Вычисление обратной матрицы.

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

К сожалению, зачастую обращение матрицы А производится с единственной целью вычислить по известному вектору 6 вектор х вида Умножение матрицы на вектор требует примерно арифметических операций. Однако вычисление обходится (как будет показано ниже) примерно в операций. Это означает, что на вычисление решения системы по формуле будет затрачено примерно операций. В данном случае х можно найти в 3 раза быстрее методом Гаусса и вычисление не нужно. Более того, можно ожидать, что вычисленное методом Гаусса решение окажется точнее, так как потребуется выполнение меньшего числа операций.

Может показаться особенно выгодным предварительное вычисление матрицы если далее потребуется найти большое число векторов по формулам

Однако суммарные затраты при таком подходе составят примерно операций, в то время как при одновременном решении методом Гаусса эквивалентной системы (5.46) получаем значения примерно за операций. Следовательно, и в этом случае вычисление нецелесообразно.

Иногда в пользу необходимости вычисления приводится следующий довод. Если известно, что в течение длительного времени потребуется неоднократно решать системы уравнений вида (5.46) с фиксированной матрицей А и различными правыми частями то имеет смысл предварительно вычислить Записав в память ЭВМ, можно затем по мере необходимости быстро вычислять по формуле Однако использование LU-разложения матрицы А (см. § 5.7) позволяет вычислять столь же быстро, а предварительная работа на этапе разложения дает трехкратную экономию. Таким образом, и этот довод в пользу необходимости вычисления обратной матрицы неубедителен.

Довольно часто при решении различных задач средствами линейной алгебры возникают выражения типа

Если у исследователя нет достаточного опыта решения задач линейной алгебры на ЭВМ, то он может принять решение о необходимости вычислять матрицы с тем чтобы действовать далее по формуле (5.48). Однако и в этом случае можно поступить иначе и найти с меньшими затратами. Решая систему найдем Затем вычислим решая систему найдем Наконец, вычислим решая систему найдем

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

Покажем, как вычисление обратной матрицы можно свести к рассмотренной выше задаче решения системы уравнений с несколькими правыми частями. Обозначим матрицу через V, ее столбцы — через и столбцы единичной матрицы через

Согласно определению обратной матрицы верно равенство эквивалентное совокупности равенств

Таким образом, столбцы матрицы (а следовательно, и саму матрицу), можно найти, решая систем уравнений с общей матрицей

А. Согласно изложенному выше, для этого потребовалось бы примерно арифметических операций, однако учет специального вида правых частей системы (5.49) позволяет вычислять матрицу примерно за операций.

3. Вычисление определителя.

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

где число потребовавшихся перестановок строк. Остается воспользоваться формулой (5.17) и тогда получим

где Отметим, что вычисление по формуле (5.50) требует особой аккуратности, в особенности если число велико. Как мы убедились в примере 3.29, при вычислении произведений следует специальным образом упорядочивать сомножители. Неудачный порядок их расположения может привести к аварийному останову по переполнению либо к исчезновению порядка.

Можно избежать переполнения и исчезновения порядка, если для вычисления воспользоваться формулой

Однако следует иметь в виду, что ее использование может привести к некоторой потере точности.

Замечание. Действительная необходимость в вычислении определителей возникает довольно редко. Во всяком случае основанные на их использовании алгоритмы оказываются весьма неэффективными (как в примере 3.34, где обсуждалось правило Крамера), и поэтому вычисление определителей давно уже не является элементом современных алгоритмов линейной алгебры. Кроме того, из результатов в § 5.4 следует, что использование величины для определения степени близости системы уравнений к вырожденной дает весьма ненадежный и сомнительный критерий.

Пример 5.11. Используя метод Гаусса с выбором главного элемента по столбцу вычислим определитель матрицы

на 6-разрядной десятичной ЭВМ.

Повторяя преобразования из примера 5.9, получим матрицу

Так как была сделана одна перестановка строк, то формула (5.50) дает .

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