6.5. ПРИЛОЖЕНИЯ НВП-РАЗЛОЖЕНИЯ

В этом разделе мы покажем, как использовать НВП-разложение для нахождения обратных матриц, вычисления определителей и решения систем линейных уравнений. Мы увидим, что каждая из этих задач сводится к задаче умножения двух матриц и, следовательно, любое улучшение асимптотической временной сложности умножения матриц приводит к улучшению асимптотической временной сложности этих задач. Обратно, умножение матриц, как мы покажем, сводится к обращению матриц и, следовательно, задачи умножения матриц и обращения их эквивалентны с вычислительной точки зрения.

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

Доказательство. Пусть А — невырожденная -матрица. В силу теорем 6.3 и 6.4 можно найти НВП-разложение за время Тогда Матрицу можно вычислить за шагов. Матрицы существуют, и их можно вычислить за шагов в силу теоремы 6.2. Аналогично за шагов можно вычислить произведение

Следствие. Обращение -матрицы можно найти за шагов.

Теорема 6.6. Если функция та же, что и в теореме 6.5, и А есть -матрица, можно вычислить за шагов.

Доказательство. Применим алгоритм 6.1, чтобы найти НВП-разложение матрицы А. Если он не срабатывает из-за того,

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

Следствие. Определитель -матрицы можно вычислить за шагов.

Пример 6.4. Вычислим определитель матрицы из примера 6.3. Там мы нашли НВП-разложение

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

Теорема 6.7. Пусть функция та же, что и в теореме -невырожденная -матрица и вектор-столбец размерности Пусть -столбец неизвестных. Тогда систему линейных уравнений можно решить за шагов.

Доказательство. С помощью алгоритма 6.1 построим НВП-разложение Тогда система решается в два шага. Сначала решаем систему относительно у, а затем — систему относительно х. Каждую из этих подзадач можно решить за шагов, применив метод исключения, т. е. сначала найти значение подставить его вместо переменной затем найти значение НВП-разложение можно построить за шагов в силу теоремы 6.4, а систему можно решить за шагов.

Следствие. Систему из уравнений с неизвестными можно решить за шагов.

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

Теорема 6.8. Пусть для умножения двух -матриц и обращения -матрицы требуется соответственно времени. Предположим, что при некотором и аналогичные неравенства верны для Тогда и совпадают с точностью до постоянного множителя.

Доказательство. Теорема 6.5 показывает, что для некоторой постоянной Чтобы установить неравенство для некоторой постоянной рассмотрим произвольные -матрицы Так как

то можно вычислить произведение обращая -матрицу. Следовательно,